1
$\begingroup$

We distribute n pennies to k boys and l girls, so that (to be really unfair) we require that each girls gets at least one penny. In how many ways can we do this?

  • 0
    ^^was it *that* hard to parse? (Also, @Nguyën, "penny" is the singular form of the plural "pennies")2012-06-11

1 Answers 1

2

I'm assuming each boy and girl is labeled (that is, giving 3 pennies to boy 1 and 5 to boy 2 is counted as distinct from giving 5 to boy 1 and 3 to boy 2).

Since each girl gets at least one penny, removing $l$ pennies and removing the special condition for girls does not change the number of possibilities: we have the "sex change" equality $f(n,k,l)=f(n-l,k+l,0)$

Finally it is well known that $f(n,k,0)=\binom{n+k-1}{k-1}$: a $k-1$-element subset $x_1<\dots of $[1,n+k-1]$ corresponds bijectively to the assignment of $n$ pennies to $k$ boys $y_i=x_i-x_{i-1}-1$ (with the boundary values $x_0=0$ and $x_k=n+k$).

So: $f(n,k,l)=\binom{n+k-1}{k+l-1}$