How many ways are there to place 4 apples, 5 oranges and 6 banana into 4 indistinguishable baskets?
My thinking was to use stars and bars methods separately for each fruit and then multiply the totals of each to get the total number of ways.
Apples:
${4+3 \choose 3}$
Oranges:
${5+3 \choose 3}$
Banans:
${6+3 \choose 3}$
Total = ${7 \choose 3}{8 \choose 3}{9\choose 3}$
Am I right in my thinking here?
Best Answer
The species formula for one non-empty basket is
$$oneBasket = Ens_0^4 \ (A) \cdot Ens_0^5 \ (O) \cdot Ens_0^6 \ (B) -1 $$
where $E_0^k$ are sets with at most $k$ elements. A set of four non-empty baskets is: $$Ens_4 \ (oneBasket)$$
Since the parts of a partition must be non-empty, we will have to calculate four cases, from one non-empty basket to four non-empty baskets.
After writing the cycle index we will extract some coefficients of $ \ {a^4\over 4!}{o^5\over 5!}{b^6\over 6!} \ $ for the e.g.f. and $ \ a^4o^5b^6 \ $ for the GF, the types generating function.
1) We write down the cycle indices of considered species $Ens_0^4(A), \ Ens_0^5(O), \ Ens_0^6(B)$
$$Z(A) = 1 + a_1 + {1 \over 2!}(a_1^2 +a_2) +... {1 \over 4!}(a_1^4+...+6a_4) $$
$$Z(B) = 1 + b_1 + {1 \over 2!}(b_1^2 +b_2) +... {1 \over 5!}(b_1^5+...+24b_5) $$
$$Z(C) = 1 + c_1 + {1 \over 2!}(c_1^2 +c_2) +... {1 \over 6!}(c_1^6+...+120c_6) $$
No further symmetric cycle indices are needed.
2) Then the cycle index of one non-empty basket is:
$$basket (a_1,a_2,a_3,a_4;\ b_1,b_2,...,b_5;\ c_1,c_2,...,c_6) = Z(A)Z(B)Z(C) - 1$$
3) in order to make a "plethystic substitution" we need the ingredients :
$$basket _2 = basket \ (a_2, a_4, 0, 0 \ ; \ b_2, b_4, 0, 0, 0\ ; \ c_2, c_4, c_6,0,0,0)$$
$$basket _3 = basket \ (a_3, 0, 0, 0\ ; \ b_3, 0, 0, 0, 0\ ; \ c_3, c_6, 0,0,0,0)$$
$$basket _4 = basket \ (a_4, 0, 0, 0\ ; \ b_4, 0, 0, 0, 0 \ ; \ c_4, 0, 0,0,0,0)$$
4) In the cycle index of $Ens_4$
$$ {1 \over 24}(X_1^4 + 6X_1^2X_2 + 3X_2^2 + 8X_1X_3+ 6X_4)$$
we replace $X1, \ X2, \ X3, \ X4 \ $ with $ \ basket , \ basket _2, \ basket _3, \ basket _4$
5) now we can extract information from the cycle index Z just obtained.
$$Z^{types} = Z(a, a^2, a^3, a^4; \ o,o^2,...,o^5; \ b,b^2,...,b^6) $$
is the type indicator polynomial. The coefficient of $a^4o^5b^6$ in $Z^{types}$ is $5808$ and it represents the number of types of partitioning the 15 mixed fruits in four nonempty baskets.
6) By repeating the above for 3,2, and one nonempty bucket we get
$$ 5808 + 1383 + 104 + 1 = 7296 $$
7)
$$Z^{egf} = Z(a, 0, 0,0; \ o,0,...,0; \ b,0,...0) $$
is the e.g.f polynomial. The coefficient of ${a^4\over 4!}{o^5\over 5!}{b^6\over 6!} = 42355950$ in $Z^{egf}$ represents the different distributions of 4+5+6 labelled fruits in four baskets.
8) by considering the other cases of non-empty baskets, one has :
$$ 42355950 + 2375101 + 16383 + 1 = 44747435$$
9) we may do some double check. For example, 1+104 = 105 means to distribute 5 oranges in two baskets in three ways : 5+0, 4+1, 3+2; then the apples and bananas multiplies the number of cases to 3.5.7= 105.
10) the $42355950$ may be obtained faster by taking the coefficient of $x^{15}$ in
$$ {1\over4!} (x + {1\over 2!}x^2 + \cdots + {1\over 15!}x^{15})^4 $$
Indeed, when distributing labelled fruits, the colouring does not matter. Whatever comnposition of a total of 15 labelled apples, oranges and bananas will produce the same number of cases.