Talk:Stars and bars (combinatorics)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Low-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Low Importance
 Field:  Discrete mathematics

The example is incomplete[edit]

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 (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 (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[edit]

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:

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

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