In the theory of permutations and combinations there are several formulas which include permutations with repetition and without , same for combinations. I know the difference between permutations and combinations is that in permutations order matters , but I cannot understand when to use each formula in a given problem. Can someone explain when each formula will be used in a problem?
$$ 1) P(n,k)=\frac{n!}{(n-k)!} $$
$$2) n^{k}$$
$$ 3) \frac{(n+k-1)!}{(n-1)!} $$
$$ 4) C(n+k-1,k)=\frac{(n+k-1)!}{(n-1)!k!}$$
$$5) C(n,k)=\frac{n!}{(n-k)!k!} $$
Best Answer
Combinations
The formula $$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$ is the number of ways of selecting a subset of $k$ objects from a set of $n$ objects, that is, the number of ways of making an unordered selection of $k$ objects from a set of $n$ objects.
Example. In how many ways can a committee of five people be selected from a group of twelve people?
Solution. Since the order in which the members of the committee are selected does not matter, the number of such committees is the number of subsets of five people that can be selected from the group of twelve people, which is $$\binom{12}{5}$$
Note. The formula $$\binom{n}{k}$$ also counts the number of ways $k$ indistinguishable objects may be placed in $n$ distinct boxes if we are restricted to placing one object in each box. In this case, we are selecting the subset of $k$ boxes which will be filled with an object.
Permutations with Repetition
The formula $$n^k$$ represents the number of ways of selecting $k$ objects from a set of $n$ objects when repetition is permitted.
Example. How many sequences of length $5$ can be formed from the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ if repetition of digits is permitted?
Solution. There are ten choices for each of the five positions in the sequence, so there are $10^5$ such sequences.
Note. The formula $n^k$ can also be interpreted as the number of functions $$f: \{1, 2, 3, \ldots, k\} \to \{1, 2, 3, \ldots, n\}$$ since there are $n$ choices in the codomain for each of the $k$ elements in the domain.
Note. Yet another interpretation is that the formula $n^k$ counts the number of ways of placing $k$ distinct objects in $n$ distinct boxes if each box can hold at least $k$ objects since we have a choice of $n$ boxes for each of the $k$ objects.
Permutations
The formula $$P(n, k) = \frac{n!}{(n - k)!}$$ represents the number of ways of forming a sequence of $k$ distinct objects from a set of $n$ objects, that is, of making a selection of $k$ objects from a set with $n$ objects when order matters.
Example. In how many ways can a president, secretary, and treasurer be selected for a French club with twelve members if each person holds at most one office?
Solution. Since selecting Andrea as president, Bruce as secretary, and Clara as treasurer is different from selecting Andrea as president, Clara as secretary, and Bruce as treasurer, the order of selection matters. Hence, the president can be selected in twelve ways, the secretary can be selected in eleven ways, and the treasurer can be chosen in ten ways. Thus, the offices can be filled in $$12 \cdot 11 \cdot 10 = \frac{12 \cdot 11 \cdot 10 \cdot 9!}{9!} = \frac{12!}{9!} = \frac{12!}{(12 - 3)!} = P(12, 3)$$ ways.
Note. The formula $P(n, k)$ also counts the number of injective (one-to-one) functions $$f: \{1, 2, 3, \ldots, k\} \to \{1, 2, 3, \ldots, n\}$$
Note. Yet another interpretation is that $P(n, k)$ is the number of ways of distributing $k$ distinct objects to $n$ distinct boxes if only one object may be placed in each box since it matters which object is placed in which box.
Combinations with Repetition
The formula $$\binom{k + n - 1}{n - 1} = \binom{k + n - 1}{k}$$ counts the number of ways $k$ objects may be selected from $n$ types of objects when repetition is permitted.
Example. In how many ways can twelve chocolates be selected from six varieties of chocolates?
Solution. Let $x_i$ be the number of chocolates of type $i$ that are selected. Then $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 12$$ which is an equation in the nonnegative integers.
A particular solution of the equation corresponds to the placement of five addition signs in a row of twelve ones. For instance, $$1 1 1 + + 1 1 1 1 1 + 1 + 1 1 + 1$$ corresponds to the solution $x_1 = 3$, $x_2 = 0$, $x_3 = 5$, $x_4 = 1$, $x_5 = 2$, $x_6 = 1$. The number of such solutions is $$\binom{12 + 6 - 1}{6 - 1} = \binom{17}{5}$$ since we must select which five of the seventeen positions required for twelve ones and five addition signs will be filled with addition signs.
Note. The formula $$\binom{n + k - 1}{k - 1}$$ also counts the number of ways of placing $k$ indistinguishable objects in $n$ distinct boxes if each box can hold at least $k$ objects.
Example. In how many ways can twelve indistinguishable pencils be distributed to six children?
Solution. Let $x_i$ be the number of pencils given to the $i$th child. Then $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 12$$ Since we are not required to give a pencil to each child, this is an equation in the nonnegative integers. We showed above that this equation has $$\binom{12 + 6 - 1}{6 - 1} = \binom{17}{5}$$ solutions.
Note. The number of ways of placing $k$ indistinguishable objects in $n$ distinct boxes if at least one object is placed in each box is $$\binom{n - 1}{k - 1}$$
Example. In how many ways can twelve indistinguishable pencils be distributed to five children if each child receives at least one pencil?
Solution. Let $x_i$ be the number of pencils given to the $i$th child. Then $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 12$$ This is an equation in the positive integers since each child receives at least one pencil. A particular solution of the equation corresponds to the placement of five addition signs in the eleven spaces between successive one in a row of twelve ones. $$1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1$$ For instance, $$1 1 + 1 1 1 + 1 + 1 1 1 + 1 + 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 3$, $x_3 = 1$, $x_4 = 3$, $x_5 = 1$, $x_6 = 1$. The number of such solutions is the number of ways we can place an addition sign in five of the eleven spaces between successive ones in a row of twelve ones, which is $$\binom{12 - 1}{6 - 1} = \binom{11}{5}$$