6
$\begingroup$

This seems to be a "stars and bars problem" - however I am unsure how to apply a constraint. Furthermore, I would like to understand how this would be done in both counting as well as generating functions.

The question: There are 5 brother sister pairs. I have 10 identical barbie dolls and 10 identical toy cars. How many ways can you distribute the barbie dolls among girls and toy cars among boys such that every one gets a gift and every brother-sister pair has at least 3 gifts?

Here is what I have with counting: Since every boy has to get a toy as well as every girl, there are then 5 toy cars and 5 barbie dolls left for distribution. This then leads to $$ (5+5-1)C(5-1))^{2} $$ as there are 5 toys and 5 boys (considering them as "bins") as well as the same with girls hence multiplying these two combinations together will give the total number of combinations between the two.

The next part though gives me more troubles as I am unsure of how to put the constraint on - that each brother-sister pair has to have 3 gifts. Now we know that each pair has at least 2 gifts as they all received one. So if each pair received 3 gifts, there would be a total of 15 gifts that have set distributions. Now we don't care if the brother-sister pair get an extra girl toy or a boy toy, so we have 5 total toys that can be distributed. Would we then have 5 pairs (bins) and 5 toys such that again we would have $$ (5+5-1)C(5-1)) $$ ways to distribute the 5 remaining toys - hence give us a grand total of

$$ (5+5-1)C(5-1))^{3} $$ ways to do this?

How would I go about doing this with generating functions? I am guessing I would start with that since each child gets a toy, that as above I would have 5 cars and 5 dolls to distribute among the boys and girls respectively. So I would have, along with each pair getting 3 toys (x^3?) thus:

$$(x^{1}+x^{2}+x^{3}+x^{4}+x^{5})(x^{1}+x^{2}+x^{3}+x^{4}+x^{5})$$

I however don't see how to add the constraint for the brother-sister pair getting at least 3 toys, as well as which coefficient in the generating function to look for. I do however see that the above can be reduced to:

$$x^{2}(x^{0}+x^{1}+x^{2}+x^{3}+x^{4})(x^{0}+x^{1}+x^{2}+x^{3}+x^{4}) = x^{2}(1-x^{5}/(1-x))^{2}$$

Not sure what to do from here.

Thanks for any help,

Brian

$\endgroup$
  • $\begingroup$ Coefficient of $x^{10}y^{10}$ in $(x^2y+xy^2+x^3y+x^2y^2+xy^3+\dots)^5$? The quantity in brackets is $(x+x^2+\cdots)(y+y^2+\cdots)-xy$ which is $xy(1-x)^{-1}(1-y)^{-1}-xy$ which is $xy((1-x)^{-1}(1-y)^{-1}-1)$. So we're after the coefficient of $x^5y^5$ in $((1-x)^{-1}(1-y)^{-1}-1)^5$. $\endgroup$ – Gerry Myerson Jun 24 '16 at 12:50
0
$\begingroup$

To balance the gender-coded problem statement, I'll be distributing the cars to the girls and the dolls to the boys.

So one car to each girl and one doll to each boy is clear, and we have $5$ cars and $5$ dolls left. Choose $k$ girls in $\binom5k$ ways and give at least one extra car to each of them and none to the others, in $\binom{5-1}{k-1}$ ways. Now give an extra doll to each boy whose sister didn't get an extra car, and distribute the other $k$ dolls arbitrarily among the boys, in $\binom{k+5-1}{5-1}$ ways, for a total of

$$ \sum_{k=1}^5\binom5k\binom4{k-1}\binom{k+4}4=4251\;. $$

I don't see how to do this with generating functions in an efficient way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.