0
$\begingroup$

In how many ways can we place 7 identical red balls and 7 identical blue balls into 5 distinct urns if each urn has at least 1 ball?

This is how I approached the problem:

1) Compute the number of total combinations if there were no constraints:

Placing just the red balls, allowing for empty urns: $\binom{n+k-1}{k-1} = \binom{7+5-1}{5-1} = \binom{11}{4} = 330$. There are the same number of blue ball configurations.

Since each red ball configuration can have 330 possible blue ball configurations, then in total we should have $330^2 = 108900$

2) Compute the number of illegal configurations with 1, 2, 3 or 4 empty urns:

$r_1$ = ways to put 7 red balls into 1 urn = $\binom{7-1}{1-1} = \binom{6}{0} = 1$
$r_2$ = ways to put 7 red balls into 2 urns = $\binom{7-1}{2-1} = \binom{6}{1} = 6$
$r_3$ = ways to put 7 red balls into 3 urns = $\binom{7-1}{3-1} = \binom{6}{2} = 15$
$r_4$ = ways to put 7 red balls into 4 urns = $\binom{7-1}{4-1} = \binom{6}{3} = $20

$b_1$ = ways to put 7 blue balls into 1 urn = $r_1$
$b_2$ = ways to put 7 blue balls into 2 urns = $r_2$
$b_3$ = ways to put 7 blue balls into 3 urns = $r_3$
$b_4$ = ways to put 7 blue balls into 4 urns = $r_4$

$u_1$ = ways to pick 1 urn = $\binom{5}{1} = 5$
$u_2$ = ways to pick 2 urns = $\binom{5}{2} = 10$
$u_3$ = ways to pick 3 urns = $\binom{5}{3} = 10$
$u_4$ = ways to pick 4 urns = $\binom{5}{4} = 5$

# ways to put 7 red and 7 blue balls into 1, 2, 3, or 4 urns =
# ways to put 7 red and 7 blue balls into 5 urns where 1 or more urns are empty =

$r_1 b_1\binom{5}{1} + r_2 b_2\binom{5}{2} + r_3 b_3\binom{5}{3} + r_4 b_4\binom{5}{4} = $

$1^2 \cdot 5 + 6^2 \cdot 10 + 15^2 \cdot 10 + 20^2 \cdot 5 = 4615$ = # of illegal configurations

3) Subtract the number of illegal configurations from the number of total configurations:

108900 - 4615 = 104285

Is this correct? If not, could someone explain where either my logic breaks down or where I calculated something incorrectly?

$\endgroup$
4
$\begingroup$

Your error lies in multiplying the number of ways to distribute $7$ red balls over $k$ non-empty urns by the number of ways to distribute $7$ blue balls over $k$ non-empty urns and treating that as the number of ways to distribute all $14$ balls over $2$ non-empty urns. You’re missing the distributions where $k$ urns are non-empty but not all of them contain both red and blue balls.

For a correct count, you can perform inclusion–exclusion like this: There are $5$ conditions for the $5$ urns to be non-empty. There are $\binom5k$ ways to choose $k$ particular conditions, and $\binom{7+(5-k)-1}{(5-k)-1}^2=\binom{11-k}7^2$ ways to violate them by distributing all balls to the remaining $5-k$ urns. Thus the number of admissible distributions is

\begin{eqnarray} \sum_{k=0}^4(-1)^k\binom5k\binom{11-k}7^2 &=& 1\cdot\binom{11}7^2-5\cdot\binom{10}7^2+10\cdot\binom97^2-10\cdot\binom87^2+5\cdot\binom77^2 \\ &=& 49225\;. \end{eqnarray}

$\endgroup$
1
$\begingroup$
A=[ nchoosek(1:11,4)-ones(size(nchoosek(1:11,4))), diff(nchoosek(1:11,4),[],2) - ones(size(diff(nchoosek(1:11,4),[],2))), -nchoosek(1:11,4)+11*ones(size(nchoosek(1:11,4)))];
B=A(:, [1,5,6,7,11]);
valid=0;
for i=1:size(B,1)
    for j=1:size(B,1)
        C=B(i,:)+B(j,:);
        if (min(C) > 0) 
            valid=valid+1;
        end
    end
end
valid

the Matlab code above generates the right answer, which is 49225

one nice way to solve this sort of problems is through generating functions

How to solve this distribution problem with generating functions?

I think you would be very interested to read Section 4.2 of Wilf's generatingfunctionology.

Note that what Wilf calls the sieve method is precisely inclusion-exclusion.

Inclusion Exclusion vs. Generating Functions

$\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.