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 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 and then-popular interpretations of Einstein's conception. Will Orrick (talk) 02:57, 19 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)