Talk:Stars and bars (combinatorics)

The example is incomplete

The example states that the stars and bar notation would represent the 4-tuple (1,3,0,1), but there is no way to map this to the set { a, b, c, d } unless by specifying an ordering to the set, like the 4-tuple (a,b,c,d). Am I right ? —Preceding unsigned comment added by 193.57.67.241 (talk) 10:18, 26 April 2011 (UTC)

You are right that the bijection depends on a chosen ordering of the set. But since this is about counting only, it suffices to show the existence of a bijection, not its uniqueness in any sense. So one can start by choosing an arbitrary ordering on the set, and then define the bijection in terms of that, which is what the starts and bars argument does. Often enumerative combinatorialists assume sets to be ordered without even mentioning so. Marc van Leeuwen (talk) 17:13, 26 April 2011 (UTC)

Thank you. So assuming that the chosen ordering is the one that the set has been presented with (in this case, a, then b, then c, then d), OK. I understand that there actually are 24 possible orderings yielding 12 different sets. Do you think it would be worth mentioning? —Preceding unsigned comment added by 193.57.67.241 (talk) 07:50, 27 April 2011 (UTC)

It is worth mentioning that the construction given in this article depends on considering the set (to be selected from) as an ordered set. The precise number of different bijections that can be constructed would seem off topic to me, and distracting in this article. Marc van Leeuwen (talk) 08:46, 27 April 2011 (UTC)

An interesting example of a stars & bars problem

I think a few more examples would be appropriate to add to this article. One I recently discovered, which might be useful is:

How many solutions are there to x1 + x2 + x3 = 11 using non-negative integers. Answer c(11+3-1, 11) = 78

Note, this problem comes from _A Probability Course for the Actuaries: A Preparation for Exam P/1_ by Marcel B. Finan, p. 51 available for free in pdf at: http://faculty.atu.edu/mfinan/actuarieshall/book.pdf.

I leave it to you wikipedia experts to decide if and how to include this example. Cheers! — Preceding unsigned comment added by 38.109.25.246 (talk) 17:37, 4 March 2013 (UTC)

That’s exactly the “Theorem two”.—Emil J. 15:45, 25 April 2014 (UTC)

Question on name "Stars and Bars"

In Feller's book I did not find the name "stars and bars". May it be that Feller introduced the diagram, but someone else (years) later the sketchy name for it?--84.135.41.219 (talk) 09:26, 1 July 2020 (UTC)

I can't trace the name but I also don't see it in Feller. It seems quite likely to have originated with an American. I'm having trouble finding results before about 2004. Miclugo (talk) 15:07, 15 May 2024 (UTC)

The phrase appears on page 20 of Introduction to Statistics and Probability by Edward J. Dudewicz, published in 1976,

"If we consider that we have $r$ balls (represented by stars) and $n$ cells, thus $n+1$ cell walls (represented by bars) (Figure 2.2-1), then we must put one cell wall on the outside on each end in any distribution of balls into cells (distribution of stars and bars in a line); the $n-1$ walls and $r$ balls can be mixed up in any way, the number of such ways being the number of ways of choosing, out of $n+r-1$ places, $r$ for balls."

I wouldn't say this passage by itself is a smoking gun that it was commonplace in 1976 to refer to a "stars and bars method", but it is telling that the index of the book contains the item "stars and bars" with a reference to page 20. Will Orrick (talk) 17:07, 15 May 2024 (UTC)

There's an earlier use of the phrase in the book Probability: A First Course by Frederick Mosteller, Robert E. K. Rourke, and George Brinton Thomas. Google Books shows snippets on page 62,

"Example 5 Stars and bars In how many ways can 10 identical objects be placed in 4 different boxes (a) if at least one object must go into each box, (b) if one or two or three of the boxes may be left empty?"

Also page 66 has Exercise 5, "Use the method of stars and bars to show...". It's not clear whether these are the first or only uses of the phrase in the book. Google Books shows the 2nd edition of the book, from 1970. The first edition was published in 1961, but I don't know whether the quoted passages are also contained in that edition. Will Orrick (talk) 17:47, 15 May 2024 (UTC)

Some more history. The original edition of Feller's book was published in 1950. The material on occupancy problems is on pages 51–53 and the diagram is shown there. This text uses bars to represent cell boundaries, and the word "bars" is used in the text. For the objects, however, it uses letters—the letter A in particular.

Google Books shows me snippets of the 1970 reprinting of the 3rd edition of the book (1968). The reprinting contains substantial corrections to the original 3rd edition. The relevant material is now on pages 38–39 and looks rather different in language and presentation from the first edition. In this edition bars and stars are used instead of bars and letters, and the word "stars" is used. I do not see the phrase "stars and bars", but I am only looking at tiny fragments of text. The citation in our article refers to page 38 and to the 3rd edition, but gives an incorrect copyright date of 1950 (the date of the first edition).

I'm now unsure of the word "popularized" in the first paragraph of our article. What are we trying to say here? Will Orrick (talk) 19:09, 15 May 2024 (UTC)

I've removed the claim about Feller from the first paragraph, and I've edited the reference to Feller's book to give the correct date for the 3rd edition. Will Orrick (talk) 21:09, 15 May 2024 (UTC)

Have I overloaded this article with explanatory figures?

II will be happy to move one or both recently added figures to Wikiversity or Wikibooks, if the editors so choose. Like most mediocracy on Wikipedia, the situation just grew organically, beginning with the clever use of text to create figures such as ★ ★ ★ ★ ★ ★ ★. I wanted to illustrate the importance of gaps in Theorem 1. But when I later decided to tackle Theorem 2, I saw the opportunity to contrast the two conventions in a single figure. The replacement Tom, Dick, and Harry by animals was done for the benefit of non-English wikis. If a figure is to be removed, it should probably be the one on the left:--Guy vandegrift (talk) 01:28, 24 December 2021 (UTC)

• 
• 

Feller

I've removed the claim in the first paragraph that the method was popularized by Feller in his book. See the section Question on name "Stars and Bars" for some additional discussion on this.

To restore the claim I think we should require a reliable source for it, preferably one written before November 2010, when the claim was first added to this article. Will Orrick (talk) 21:07, 15 May 2024 (UTC)