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)

I wanted to add one more earlyish source. In the 1975 paper, "Some distributions associated with Bose–Einstein statistics" by Yuji Ijiri and Herbert A. Simon in Proc Natl Acad Sci U S A 72 pp. 1654–1657, we find,

"We use the familiar model of placing r objects called 'stars' in n cells arranged in linear order as in |***|*||**|, two adjacent bars defining a cell."

Later, page 38 of the 3rd (1968) edition of Feller's book is cited for the counting formula. It is also cited in the paper's introduction for a fact about Bose–Einstein statistics.

My conclusion from all this is that by the early 1970s the use of stars and bars in problems of this type had become standard, as had the phrase "stars and bars". But the method itself appears earlier, as illustrated by the 1950 edition of Feller's book, where bars and letters are used rather than bars and stars, and by the 1914 paper of Ehrenfest and Kamerlingh Onnes (see Example 5 in the Wikipedia article), where different symbols are used.

It is interesting that Ehrenfest and Kamerlingh Onnes seem to feel that the method is original with them. In a footnote they explain their motivation for looking for an alternative to Planck's derivation of the formula,

"We were led to the introduction of the (N−1) partitions between the N resonators, in trying to find an explanation of the form (N−1)! in the denominator of (A)..."

They later explain that for the proof of the formula, Planck referred to the reasoning in "treatises on combinations" and add that,

"In these treatises the expression (A) is arrived at by the aid of the device of 'transition from n to n+1', and this method taken as a whole does not give an insight into the origin of the final expression."

I take it that 'transition from n to n+1' means induction.

Whatever the truth of the matter, I suspect, without firm evidence, that the method was widely known before 1950. Feller's book was hugely influential, and widely cited for many results in probability theory, both elementary and advanced, including stars and bars, but it's not clear to me that stars and bars has any special connection with Feller. An edit summary (see also the immediately prior edit) states that the method is not in the 2nd edition of Feller's book, but I have been unable to check that for myself. Will Orrick (talk) 16:51, 17 May 2024 (UTC)

Let's beat this dead horse some more. Just as a sanity check I looked to see what one might find in a 19th century book on this topic. In Choice and Chance, an Elementary Treatise on Permutations, Combinations, and Probability by William A. Whitworth, Cambridge (1886) one finds Proposition XV on page 89:

"The number of ways in which n different things can be arranged in r different groups (blank groups being admissible) is

$r(r+1)(r+2)\ldots (r+n-1).$

For we shall obtain the arrangements by taking the n different things and putting with them r−1 indifferent points of partition, and arranging these n+r−1 things in all possible orders. Since r−1 of them are alike the number of arrangements is by Prop. VII

$(n+r-1)!\div (r-1)!,$

or

$r(r+1)(r+2)\ldots (r+n-1).$"

I have replaced the old fashioned notation Whitworth used for factorials with the modern one. Prop. VII cited in this passage gives the formula for multinomial coefficients. Although no diagram is drawn here and the situation differs from the usual situation to which stars and bars is applied in that the objects (stars) are distinguishable (with the result that there is no denominator factor of n!), the proof given is, to my mind, essentially the same as the stars and bars argument. In particular, treating the partition points as things, which are then permuted along with the objects is very much the idea of using bar symbols along with object symbols.

The propositions in the book that treat the usual stars and bars problems are Prop. XXV and Prop. XXVI. Prop. XXV:

"The number of ways in which n indifferent things can be distributed into r different parcels (blank lots being inadmissible) is the number of combinations of n−1 things taken r−1 at a time."

"For we may perform the operation by placing the n things in a row, then placing r−1 points of partition amongst them..."

Again, no diagram is drawn but this is Theorem one and the proof is exactly the stars and bars argument. Prop. XXVI:

"The number of ways in which n indifferent things can be distributed into r different parcels (blank lots being admissible) is the number of combinations of n+r−1 things taken r−1 at a time."

This is Theorem two. It is not proved from scratch, but by adapting the result of Prop. XXV.

Assessing this evidence suggests to me that these constructions have long been well known, the complaints of Ehrenfest and Kamerlingh Onnes notwithstanding. (Planck used German language sources—he refers to a book of Joh. v. Kries—which may indeed have presented things differently.) I feel confident that removing the sentence giving particular credit to Feller was the right thing to do. Unfortunately one now finds mathematical blogs and other texts referring to "Feller's stars and bars method", despite Feller's apparently not having used that name, having originally used different symbols, and having been far from the first to present the method. I love Wikipedia, but it does have a way of sometimes polluting the information environment.

Incidentally, I would still recommend the Ehrenfest and Kamerlingh Onnes paper just for historical interest, as it provides a glimpse of the state of thought during the period of the old quantum mechanics. It seems, as far as I understand it, that Ehrenfest was wrestling with what he saw as discrepancies between Planck's conception of the light quantum and then-popular interpretations of Einstein's conception. Will Orrick (talk) 02:57, 19 May 2024 (UTC)

More updates:

I've had a more complete look at the 3rd edition of Feller's book, which contains a stars and bars diagram on page 38. I am now fairly confident that, although the book uses the words "stars" and "bars", it does not contain the phrase "stars and bars". I also notice that the section in which the diagram is presented is a starred section, meaning Feller recommends omitting it on a first reading. This makes it more plausible to me that this topic, which was presented in somewhat different form in the first edition, really may have disappeared in the 2nd edition and then returned, rewritten, in the 3rd edition. I still would like additional confirmation of this. (The material is also in an optional section in the first edition.)

I have also been able to look at the first edition (1961) of the book of Mosteller, Rourke, and Thomas and, although it's hard to be completely sure, I now believe that the stars and bars method, diagram, and the types of problems it is used on are all absent from the first edition. This means that the 2nd (1970) edition of the book is the first place I know of where the phrase "stars and bars" is used in connection with this kind of problem. It also means, assuming that the 2nd (1957) edition of Feller's book really does omit the topic, that Feller's 3rd (1968) edition is the first place where diagrams using both stars and bars appear, although, as detailed in previous comments, diagrams using different symbols and the method itself have a long history.

I've run across a few additional early 1970s books that present the method using diagrams containing stars and bars (and I do not find any earlier than this):

Marcel F. Neuts, Probability, Allyn and Bacon, 1973, p. 35. Neuts uses the phrase "bar-and-star displays".

George G. Roussas, A First Course in Mathematical Statistics, Addison–Wesley, 1973, p. 29.

Walter Feibes, Introduction to Finite Mathematics, Hamilton, 1974, p. 27.

It seems that none of these books use the phrase "stars and bars", but I have been unable to do a thorough confirmation of that for the last two.

Thus a hypothesis is that the reintroduction of the method in the 3rd edition of Feller's book in 1968 and the change in notation from letters to stars brought more attention to the method and inspired widespread imitation among authors of other probability textbooks. Still it seems far fetched that a single diagram in the text of a proof in an optional section of a 500 page book would attract so much notice.

Perhaps more relevant is Chapter 1 of the book where Feller discusses sample spaces using "proto-stars-and-bars" diagrams as examples. Table 1 on page 9 lists all 27 ways of putting balls a, b, c in three bins using the notation { b | - | ac } to represent ball b in bin 1, balls a and c in bin 3, and bin 2 empty. He then moves on to indistinguishable balls, showing the 10 analogous diagrams for this case in Table 2 on page 12, with stars in place of letters: { * | - | ** }. These highly visible tables early in the book, although differing slightly from the usual stars and bars notation may have been the real influence. These examples are absent from the first edition of the book. I would be interested in whether they appear in the 2nd edition.

All this may explain how there came to be a link in people's minds between the stars and bars method and Feller, and how the statement that Feller popularized the method found its way into Wikipedia. It's unclear how much citation practice bears this out. Prior to 2010 one occasionally finds Feller's book cited in passages mentioning stars and bars. But Feller's book at this point in time is a pretty common reference for many standard results in probability theory, so it's hard to draw firm conclusions from that.

An example that is suggestive of a significant role for Feller is

J. Buhler, D. Eisenbud, R Graham, and C. Wright, Juggling drops and descents, Canadian Mathematical Society Conference Proceedings 20 (1997),

where on page 143 we find, "A standard 'stars and bars' argument (in Feller's terminology, e.g., p. 38 of [9]) gives the answer." The only early references I've run across that assign more definite credit to Feller are issues 3.10 and 3.11 of CHANCE News, which both contain the phrase "Feller's stars and bars counting argument", and

John D. Cook, Richard Stanley's twelvefold way, August 31, 2009, p. 3,

which has similar wording. After 2010, it becomes increasingly common to link the method to Feller, even to say he invented it, no doubt due to the influence of Wikipedia. Will Orrick (talk) 23:18, 20 May 2024 (UTC)

I just noticed that in both the first and third editions of Feller's book the introduction to Chapter 2 has a footnote referencing Whitworth's Choice and Chance, which I quoted from above:

"The interested reader will find many topics of elementary combinatorial analysis treated in the classical textbook, Choice and chance, by W. A. Whitworth, fifth edition, London, 1901, reprinted by G. E. Stechert, New York, 1942. The companion volume by the same author, DCC exercises, reprinted New York, 1945, contains 700 problems with complete solutions."

The treatment of stars and bars problems appears in the very chapter where this footnote appears in the third edition of Feller's book, and in the following chapter in the first edition. Will Orrick (talk) 16:48, 25 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)