what is the difference between selection and division of identical and distinct objects and which these will be used in this problem?

Question

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.

Answer 1

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.

Answer 2

The answer in your textbook would have clearer if the author had used the word distributing rather than dividing.

In a shop, there are five types of ice cream available. A child buys six ice creams. How many different ways are there for the child to buy six ice creams.

Let $x_i$, $1 \leq i \leq 5$, be the number of ice creams of type $i$ that the child buys. Then $$x_1 + x_2 + x_3 + x_4 + x_5 = 6$$ Since there is no restriction on how many ice creams of each type the child buys, this is an equation in the nonnegative integers. A particular solution of this equation corresponds to the placement of four addition signs in a row of six ones. For instance, $$1 1 + + 1 1 1 + 1 +$$ corresponds to the solution $x_1 = 2$, $x_2 = 0$, $x_3 = 3$, $x_4 = 1$, $x_5 = 0$. Therefore, the number of solutions of this equation is the number of ways we can place four addition signs in a row of six ones, which is $$\binom{6 + 5 - 1}{5 - 1} = \binom{10}{4}$$ since we must choose which four of the ten positions required for six ones and four addition signs will be filled with addition signs.

What the author is saying is that this problem is that this problem is equivalent to distributing six identical objects to five children. To see this, let $x_i$, $1 \leq i \leq 5$, be the number of objects distributed to the $i$th child. Then $$x_1 + x_2 + x_3 + x_4 + x_5 = 6$$ Since there are no restrictions on the number of objects given to each child, this is also an equation in the nonnegative integers. You will notice that this is the same equation we obtained above.

While I feel that the author's explanation obscures the fact that we are selecting six objects with repetition from five types of objects, the problems are equivalent. Notice that the ones are identical while the five types of objects are distinct, just as the objects in the author's formulation are identical while the children are distinct.

More generally, the number of ways $k$ objects can be selected from $n$ types of objects is equivalent to the number of ways of distributing $k$ identical objects to $n$ distinct boxes. Both lead to finding the number of solutions of the equation $$x_1 + x_2 + \cdots + x_n = k$$ in the nonnegative integers.