1
$\begingroup$

In Miklos Bona's very nice "A Walk through Combinatorics", a following question is asked:

Suppose you have two hundred balls placed in 100 urns, so that each urn contains at least one ball, and no urn contains more than 100 balls. Then, there exists a subset of the urns which contains exactly 100 balls.

The solution is a nice application of the pigeonhole principle, and it (the solution) also indicates that there should be a lot of such subsets. And that is the question: how many such subsets are there for a given partition of $200,$ and is there a reasonable generating function?

Improve this question
$\endgroup$
5
  • $\begingroup$ Generating function for what function (sequence) and of what argument (index)? $\endgroup$
    – Max Alekseyev
    Commented Sep 2, 2017 at 1:29
  • $\begingroup$ @MaxAlekseyev The simplest is to fix $n$ ($100$ here) as a parameter, and then for each restricted partition partition of $2n$ we have a generating function which gives the number of subsets which add up to $i.$ If there is a less clumsy way to do it, I am open to suggestion... $\endgroup$
    – Igor Rivin
    Commented Sep 2, 2017 at 1:39
  • 1
    $\begingroup$ For a composition $b_1+\dots+b_n=2n$ of balls, the number of subsets with total $i$ balls equals the coefficient of $x^i$ in $$(1+x^{b_1})\cdots(1+x^{b_n}).$$ Is that what you look for? $\endgroup$
    – Max Alekseyev
    Commented Sep 2, 2017 at 2:18
  • $\begingroup$ @MaxAlekseyev I am well aware of this, but this does not tell us that the coefficient of $x^n$ is not zero (much less gives any sort of estimate on its magnitude), so one would like a lot more (think of the partition function: the formula along your lines is due to Euler, while the asymptotics came 150 years later, indiicating that the formula is only somewhat useful. $\endgroup$
    – Igor Rivin
    Commented Sep 2, 2017 at 4:06
  • 1
    $\begingroup$ Not quite in the direction of your question, but it may be worth remarking that in fact, for any $0\le N\le 200$ (not only for $N=100$) there is a set of urns containing exactly $N$ balls $-$ with the single exception where every urn contains exactly two balls. $\endgroup$
    – Seva
    Commented Sep 2, 2017 at 17:02

1 Answer 1

Reset to default
2
$\begingroup$

As mentioned by Max Alekseyev in the comments, the number of subsets containing exactly $n$ balls is a coefficient of $x^n$ in the product $(1+x^{b_1})\dots (1+x^{b_n})$, where we denote $100=n$ and $b_i$ denote the number of balls in $i$-th urn. Since $b_i>0$ and $\sum b_i=2n$, there are two more subsets with the number of balls divisible by $n$: the empty subset and the whole set. But the sum of coefficients of $x^0,x^n,x^{2n},\dots$ in the polynomial $f(x)$ equals $\frac1n\sum_{w:w^n=1}f(w)$. Therefore the number of our subsets equals $$-2+\frac1n\sum_{w:w^n=1}(1+w^{b_1})\dots (1+w^{b_n}).$$ The summand corresponding to $w=1$ is often much greater then all other summands, that gives a huge number of urn subsets containing $n$ balls. But this is not always the case: say, if $b_n=n$, $b_1=\dots=b_{n-2}=1$, $b_{n-1}=2$ we have only two such subsets. And if $n$ were odd (it is not the case for $n=100$), it could even appear that there are no such subsets: take all $b_i$ equal to 2.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This is an instance of series multisection en.wikipedia.org/wiki/Series_multisection Next step could be switching from complex numbers to cosines: $$-2+\frac{2^{n}}{n}\sum_{k=0}^{n-1} \cos\frac{\pi b_1k}{n}\cdots \cos\frac{\pi b_nk}{n}.$$ $\endgroup$
    – Max Alekseyev
    Commented Sep 2, 2017 at 12:29
  • $\begingroup$ Nice argument!... $\endgroup$
    – Igor Rivin
    Commented Sep 2, 2017 at 16:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .