67. In how many ways can $k$ items be chosen from $n$ items?
67. By definition of $C_{n}^{k}$, $k$ items can be chosen from $n$ in $C_{n}^{k}$ ways. We can solve our problem (i.e., find an explicit formula for $C_{n}^{k}$) in the same way as the previous one. Alternatively, we can use induction. We proved in problem 63 that

$$
C_{n}^{k-1}+C_{n}^{k}=C_{n+1}^{k}
$$

We will prove by induction on $n$ that

![](https://cdn.mathpix.com/cropped/2024_05_21_683be32ee1eca857285bg-109.jpg?height=104&width=101&top_left_y=848&top_left_x=86)

$$
C_{n}^{k}=\frac{n(n-1) \ldots(n-k+1)}{k!}
$$

(we will agree that $0!=1$). For $n=1$, our statement is true. Suppose it is true for $n$. Then, by the inductive hypothesis,

$$
\begin{aligned}
C_{n+1}^{k}= & \frac{n(n-1) \ldots(n-k+2)}{(k-1)!}+ \\
& +\frac{n(n-1) \ldots(n-k+1)}{k!}= \\
= & \frac{n(n-1) \ldots(n-k+2)}{(k-1)!}\left(1+\frac{n-k+1}{k}\right)= \\
= & \frac{(n+1) \cdot n(n-1) \ldots(n+1-k+1)}{k!}
\end{aligned}
$$

We have proved that our statement is true for $n+1$ as well. The induction is complete. The obtained formula can be rewritten as

$$
C_{n}^{k}=\frac{n!}{k!(n-k)!}
$$

The number $C_{n}^{k}$ is called the number of combinations of $n$ taken $k$ at a time.

$C_{n}^{k}$ is the number of ways to choose $k$ items from $n$ without regard to the order of selection.

There is a special notation for the number of ways to choose $k$ items from $n$ in a specific order: $A_{n}^{k}$. We already used this notation in solving problem 62; there, the formulas were proved: $A_{8}^{5}=C_{8}^{5} \cdot 5!=\frac{8!}{3!}$. Similar formulas are valid in the general case:

$$
A_{n}^{k}=C_{n}^{k} k!=\frac{n!}{(n-k)!}
$$

Verify this.

The number $A_{n}^{k}$ is called the number of arrangements of $n$ taken $k$ at a time.

When $k=n$, the number $A_{n}^{k}$ is called the number of permutations of $n$ elements and is sometimes denoted by $P_{n}$.

The terms "number of combinations of $n$ taken $k$ at a time" and "number of permutations of $n$" and the notation $C_{n}^{k}$ are commonly used. The term "number of arrangements of $n$ taken $k$ at a time" and the notations $A_{n}^{k}$ and $P_{n}$ are used less frequently.