0
$\begingroup$

How many different ways are there to choose 5 items from 12 distinct items if…

a. (5 pt.) the order of the items matters and repetition of items is not allowed?

b. (5 pt.) the order of the items matters and repetition of items is allowed?

c. (5 pt.) the order of the items does not matter and repetition of items is not allowed?

d. (5 pt.) the order of the items does not matter and repetition of items is allowed?

My Work

a) $P(12,5)$

b)$12^5$

c)$\binom{12}{5}$

d)Please explain this

Can you please verify my work

$\endgroup$
  • 1
    $\begingroup$ I don't understand your reasoning for $b$. Hint: there are $12$ possibilities for the first choice, $12$ possibilities for the second choice, ... $\endgroup$ – lulu Apr 25 '18 at 23:39
  • $\begingroup$ So, the b is $12^5$ right $\endgroup$ – tien lee Apr 25 '18 at 23:41
  • $\begingroup$ Yes, that is right. For $d$, I think Stars and Bars is the way to go. $\endgroup$ – lulu Apr 25 '18 at 23:42
  • $\begingroup$ Then, what about C $\endgroup$ – tien lee Apr 25 '18 at 23:45
  • $\begingroup$ Your answers for $a,c$ are correct,. $\endgroup$ – lulu Apr 25 '18 at 23:46
3
$\begingroup$

a) Correct

b) No. You have 12 choices on the first item. 12 on the second. 12 on the third, fourth and fifth. So it should be $12^5$.

c) Correct

d) This is a bit tricky, I shall explain this below.


We have $C$ for combination, $P$ for permutation, and the first time I was taught this one (order does not matter + repetition allowed), my teacher called it $H$ although I am not sure if it is standard notation.

Anyway, the formula in general is $H_r^{n}=C_r^{n+r-1}$.

The reasoning behind this is as follows (for simplicity we shall take $H_5^{12}$ as in this case as an example):

Let the $12$ possible choices be $a,b,c,\dots,l$.

We don't care about the order here, we only care about how many of each item you choose, and with each choice, we can assign with it a unique "binary code".

For example, if you choose $aabbc$, then we write $0010010111111111$ where the first two $0$'s represent the two $a$'s, after the $1$ we have two $0$'s for the two $b$'s, and so on.

As another example, $abjkl$ is represented by $0101111111101010$.

In this way, each possible choice can be represented by a string of five $0$'s and eleven $1$'s for a total of $16$ numbers. So to count all possible choices, we simply have to choose the five places to insert the $0$'s.

This is given by $C_5^{16}$, hence $H_5^{12}=C_5^{16}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Isn't $C(16,4)$ $\endgroup$ – tien lee Apr 25 '18 at 23:57
  • $\begingroup$ Why should it be $C_4^{16}$? $\endgroup$ – glowstonetrees Apr 26 '18 at 0:07
  • 1
    $\begingroup$ @tienlee If the number of items of type $k$ is $x_k$, then we want the number of solutions of the equation $$x_1 + x_2 + x_3 + \cdots + x_{12} = 5$$ in the nonnegative integers. The number of such solutions is $$\binom{12 + 5 - 1}{12 - 1} = \binom{12 + 5 - 1}{5}$$ where the expression $\binom{12 + 5 - 1}{12 - 1}$ counts the number of ways of choosing which $12 - 1 = 11$ positions of $12 + 5 - 1$ positions required for five ones and eleven addition signs will be filled with addition signs and the expression $\binom{12 + 5 - 1}{5}$ comes from choosing the positions of the ones in the same row. $\endgroup$ – N. F. Taussig Apr 26 '18 at 0:19
2
$\begingroup$

I will leave you with a quick guide on how to tackle these problems.

Suppose you have $n$ distinct objects, and you want to select $r$ out of these $n$ objects. Then, if:

  • Order is relevant and repetition is not allowed: look at the possible permutations of size $r$ which is given by $$P(n,r)=\frac{n!}{(n-r)!}$$ with $0\leq r \leq n.$
  • Order is relevant and repetition is allowed: look at the possible arrangements of size $r$, which is given by $n^r$, with $n,r \geq 0.$
  • Order is not relevant and repetitions are not allowed: look at the possible combinations of size $r,$ which is given by $$C(n,r)= \binom{n}{r}=\frac{n!}{(n-r)! r!}$$ with $0 \leq r \leq n.$
  • Order is not relevant and repetition is allowed: look at the possible combinations with repetitions, which is given by $$\binom{n+r-1}{r}\ \ $$ with $n,r \geq 0.$
| cite | improve this answer | |
$\endgroup$

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.