I have put together a summary of the possible ways with assigning 20 Apples to 3 Baskets, I am wondering are my solutions correct? I know a couple might be wrong as I didn't use inclusion exclusion principle:
- Indistinguishable Apples:
$$x_1 + x_2 + x_3 = 20 \rightarrow \dbinom{22}{20}$$
- Distinguishable Apples:
$$3^{20}$$
- Basket $1 (B_1)$ $\leq$ 5:
- Indistinguishable Apples:
$$x1' + x2' + x3' = 14 => \dbinom{22}{20} – \dbinom{16}{14}$$
Question Here: suppose B1 <= 1, B2 <= 1, B3 <= 1
I also got: $x1' + x2' + x3' = 14$ => $\dbinom{22}{20} – \dbinom{16}{14}$ Same as just B1 <= 5?
But shouldn't this be $\dbinom{20}{3}$ ? from the pov of basket
Or $3*2*1=3!$ from pov of apples? I thought this will reduce into binomial theorem n choose k, since unordered with replacement but constrained to less than or equal to 1. I tried with example of choosing 3 object from 5 object using x1 + x2 + x3 + x4 +x5 = 3 and apply constraint of <= 1, I got negative on RHS. And this certainly doesn't equal $\dbinom{5}{3}$ ?!
-
Distinguishable Apples:
$$2^{20} + \dbinom{20}{1}2^{19} + \dbinom{20}{2}2^{18} + \dbinom{20}{3}2^{17} + \dbinom{20}{4}2^{16} + \dbinom{20}{5}2^{15}$$
- Basket 1 (B1) >= 5:
-
Indistinguishable Apples:
$$x1' + x2' + x3' = 15 => \dbinom{17}{15}$$
-
Distinguishable Apples:
$$\dbinom{20}{5}3^{15}$$
- B1 <= 5, B2 <= 3:
-
Indistinguishable Apples:
$$x1' + x2' + x3' = 10 => \dbinom{22}{20} – \dbinom{12}{10}$$
-
Distinguishable Apples:
The cartesian product of sets: |{0,1,2,3,4,5}$\times${0,1,2,3}| = 24
$$\dbinom{20}{0}\dbinom{20}{0} + \dbinom{20}{0}\dbinom{20}{1} + \dbinom{20}{0} \dbinom{20}{2} … + \dbinom{20}{1} \dbinom{19}{0} + \dbinom{20}{1}\dbinom{19}{1} + \dbinom{20}{1}\dbinom{19}{2} + …$$ to all 24 ways
- B1 >= 5, B2 >= 3:
-
Indistinguishable Apples:
$$x1' + x2' + x3' = 12 => \dbinom{14}{12} $$
-
Distinguishable Apples:
$$\dbinom{20}{5}\dbinom{15}{3} *3^{12}$$
I am hoping for distinguishable apples case of 4 and 6, I don't need to do calculation for each permutation, and just do a single calculation like above. What happens when both apples and baskets become in distinguishable? and basket becomes indistinguishable and apple distinguishable?
Best Answer
According to my first glance , you have problem with distinguishable apple to distinguishable baskets in question $4$ and $6$.
The most suitable ways for distinguishable objects into distinguishable boxes is exponential generating functions , they prevent you to overcounting.
Lets firtly check over the fourth question , we see that you are making overcounting when the apples are distinguishable. If the first basket will have more than or equal to $5$ , then the exponential generating function for it must be $$\frac{x^5}{5!} + \frac{x^6}{6!} + \frac{x^7}{7!}+...$$
There is not any restriction for the others , so their exponential generating functions must be $$\bigg(1+\frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}+...\bigg)$$
As a result , we should the coefficient of $\frac{x^{20}}{20!}$ or find the coefficient of $x^{20}$ and multiply it by $20!$ in the expansion of $$\bigg(\frac{x^5}{5!} + \frac{x^6}{6!} + \frac{x^7}{7!}+...\bigg) \times \bigg(1+\frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}+...\bigg)^2 $$
When we comes to sixth question , the expoenetial generating functions :
For first basket : $$\bigg(\frac{x^5}{5!} + \frac{x^6}{6!} + \frac{x^7}{7!}+...\bigg)$$
For second basket : $$\bigg(\frac{x^3}{3!} + \frac{x^4}{4!} + \frac{x^5}{5!}+...\bigg)$$
For third basket : $$\bigg(1+\frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}+...\bigg)$$
As a result , we should the coefficient of $\frac{x^{20}}{20!}$ or find the coefficient of $x^{20}$ and multiply it by $20!$ in the expansion of $$\bigg(\frac{x^5}{5!} + \frac{x^6}{6!} + \frac{x^7}{7!}+...\bigg) \times \bigg(\frac{x^3}{3!} + \frac{x^4}{4!} + \frac{x^5}{5!}+...\bigg) \times \bigg(1+\frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}+...\bigg) $$