1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In (ii), did you mean to say identical objects? $\endgroup$ – N. F. Taussig Sep 5 '18 at 10:33
  • $\begingroup$ oh sorry for error,yes. $\endgroup$ – pranjal verma Sep 5 '18 at 10:35
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what is the need of ${+}$ operators when you say "$$(x^0+x^1+x^2+x^3)(x^0+x^1+x^2+x^3)=x^{3}$$". For example,if one man gets 1 object the other would get 2 objects so it would be written like ${x^{1}x^{2} = x^{3}}$. But where would the smaller and higher power go as you write in your equation? $\endgroup$ – pranjal verma Sep 6 '18 at 9:55
  • $\begingroup$ when you expand the two brackets, only one term from each brackets will be used, hence only one exponent from each brackets will be used, hence only one selection of the person will be used. And we are interested in the choices, for which the two persons together receive $3$ items. $\endgroup$ – farruhota Sep 6 '18 at 10:00
  • $\begingroup$ that is the thing, any exponent not equal to $3$ we will ignore. That is why, in the next step we are searching for the coefficient of the term $x^3$ only. $\endgroup$ – farruhota Sep 6 '18 at 10:01
  • $\begingroup$ But why coefficient of ${x}$ has to do anything with the answer?(this is a higher level combinatorics which is not taught to us in such a great way that's why I am not very much familier to that) $\endgroup$ – pranjal verma Sep 6 '18 at 10:08
  • $\begingroup$ you must add up all possible terms $x^3$, so the coefficient will tell you all possible ways the two persons can choose the $3$ items. $\endgroup$ – farruhota Sep 6 '18 at 10:10
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To get the formula $\binom{n + r - 1}{r - 1}$ for the number of solutions, write the last equation in the form $x_1 + x_2 + \cdots + x_r = n$. $\endgroup$ – N. F. Taussig Sep 5 '18 at 10:55
  • $\begingroup$ Why do you write "Let $x_i$, $1 \leq i \leq 5$, be the number of ice creams of type $i$ that the child buys" when it can also choose all the six ice-creams from one type of ice-cream? $\endgroup$ – pranjal verma Sep 5 '18 at 11:09
  • $\begingroup$ If all six ice-creams are of type $1$, then $x_1 = 6$, $x_2 = x_3 = x_4 = x_5 = 0$ since $x_i$ is the number of ice creams of type $i$ that the child purchases. $\endgroup$ – N. F. Taussig Sep 5 '18 at 12:19

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.