I have seen these formulas in my textbook:
(i)The number of ways of selecting one or more items from ${n}$ distinct items is
${2^n – 1}$.
(ii)The number of ways of selecting zero or more items from a group of ${n}$ distinct items
is ${n+1}$.
(iii)The number of ways of dividing ${n}$ identical items among ${r}$ persons,each one of whom receives at least one item is ${^{n-1}C_{r-1}}$.
(iv)The number of dividing ${n}$ identical items among ${r}$ persons,each of them who can receive 0,1,2, or more items is ${^{n+r-1}C_{r-1}}$.
So what is the main difference between difference between division and selection of identical and distinct objects.
I get confused when I see problems involving some kind of selection of distinct or identical objects.
For example:-
Q.1 In a shop there are 5 types of ice creams available.A child buys six ice-creams.How many number of different ways are there for child to buy six ice-creams?
In the above problem I thought that there unlimited ice-creams of 5 types.
If a child wants to choose from them it must involve selection of icecreams.
But in my textbook I see that
The number of different ways the child can buy 6 ice-creams is same as the number of dividing ${6}$ identical items among ${5}$ persons,each of them who can receive 0,1,2, or more items is ${^{6+5-1}C_{5-1}}$=${^{10}C_{4}}$.
I am confused how can division be involved here when it there are unlimited number of objects that are to be divided.
Best Answer
Imagine there are $3$ distinct items: $A,B,C$.
(i) The number of ways of selecting one or more items from $3$ distinct items is: $${3\choose 1}+{3\choose 2}+{3\choose 3}=2^3-1=7 \ \ \ (\text{note:} \sum_{k=0}^n {n\choose k}=2^n).$$ Indeed, the outcomes are: $$A,B,C,AB,AC,BC,ABC.$$ Now imagine there are $3$ identical items: $A,A,A$.
(iv) The number of dividing $3$ identical items among $2$ persons, each of them who can receive 0,1,2, or more items is: $${3+2-1\choose 2-1}={4\choose 1}=4 \ \ \ (\text{explained below})$$ Indeed, the outcomes are: $$\{AAA,0\}, \{AA,A\}, \{A,AA\}, \{0,AAA\}.$$ Explanation: let $x_1,x_2$ be the number of identical items the two persons receive, respectively. Then, the equation is: $$x_1+x_2=3, \ \ \ \ 0\le x_1,x_2\le 3.$$ 1-method: Stars and bars. Consider the number of stars as number of items to be given to a person and a bar to switch from one person to another person. For example, several examples: $$\begin{align}**|* &\ \ (\text{the first person gets $2$, the second gets $1$})\\ |*** &\ \ (\text{the first person gets $0$, the second gets $3$})\\ *|** &\ \ (\text{the first person gets $1$, the second gets $2$})\\ ***| &\ \ (\text{the first person gets $3$, the second gets $0$}) \end{align}$$ Note that it is basically a combination of $4$ symbols (items) taken $1$ (bar) or $3$ (stars) at a time: $${4\choose 1}={4\choose 3}=4.$$ 2-method: Generating functions. The equation to be solved is: $$x_1+x_2=3, \ \ \ \ 0\le x_1,x_2\le 3.$$ Let the equation $$(x^0+x^1+x^2+x^3)(x^0+x^1+x^2+x^3)=x^{3}$$ represent the number of items (indicated on the exponents) the two persons (indicated by the brackets) can receive. For example: $$x^0\cdot x^3=x^3 \ \ (\text{the first person gets $0$, the second gets $3$})\\ x^2\cdot x^1=x^3 \ \ (\text{the first person gets $2$, the second gets $1$})\\ x^3\cdot x^0=x^3 \ \ (\text{the first person gets $3$, the second gets $0$})\\ x^1\cdot x^2=x^3 \ \ (\text{the first person gets $1$, the second gets $2$})\\$$ Now if we consider the sum of $x^3$ we get $4x^3$. So, the problem reduces to finding the coefficient of $x^3$ in the expansion of the left-hand side: $$\begin{align}[x^3](1+x+x^2+x^3)^2&=[x^3]\left(\frac{1-x^4}{1-x}\right)^2= \quad \quad \quad \quad \quad \quad \quad \quad \quad (1)\\ &=[x^3](1-x^4)^2(1-x)^{-2}= \ \quad \quad \quad \quad \quad \quad (2)\\ &=[x^3]\sum_{k=0}^2 {2\choose k}(-x^4)^k\cdot \sum_{k=0}^{\infty} {-2\choose k}(-x)^k= \ \ (3)\\ &=[x^3]{2\choose 0}(-x^4)^0\cdot {-2\choose 3}(-x)^3= \quad \quad \quad \quad (4)\\ &={2+3-1\choose 3}= \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad (5)\\ &={4\choose 3}.\end{align}$$ where:
(1) inside brackets: the sum of four terms of GeomProg.
(2) simple algebra.
(3) negative binomial series.
(4) considering only the terms, whose exponents add up to $3$.
(5) negative binomial theorem.