Skip to main content

Discrete Mathematics: Combinatorics, Codes, and Graphs

Sam Macdonald

Section 1.2 Permutations and Combinations

We will now look at how to count selections taken in order or without order.

Definition 1.14.

First some notation. For a natural number \(n\text{,}\) define
  • \(n\) factorial
    \begin{equation*} n!=(n)(n-1)(n-2)\cdots 3\cdot 2\cdot 1=\prod_{i=0}^{n-1}(n-i). \end{equation*}
  • falling factorial
    \begin{equation*} n_{(k)}=\prod_{i=0}^{k-1}(n-i)=(n)(n-1)(n-2)\cdots(n-k+1) \end{equation*}
    (\(k\) terms).
  • rising factorial
    \begin{equation*} n^{(k)}=\prod_{i=0}^{k-1}(n+i)=(n)(n+1)(n+2)\cdots(n+k-1) \end{equation*}
    (\(k\) terms).
There are four main cases for choosing \(k\) items from a set of \(n\) elements, depending on whether the items are ordered or not ordered, or chosen with repetition or without repetition.

Definition 1.15.

Let \(S\) be a set of \(n\) elements.
  • A \(k\)-set in \(S\) is a subset of \(S\) with \(k\) distinct elements.
    • The number of \(k\)-sets will be denoted \(\binom{n}{k}\) “\(n\) choose \(k\text{.}\)”
      \(\binom{n}{k}\) is the number of ways to select \(k\) items from \(n\) without order.
    • \(k\)-sets are sometimes called combinations.
    • Observe that \(\binom{n}{k} = 0\) unless \(0 \leq k \leq n\) (by combinatorial defn).
  • A multiset from \(S\) is a selection of elements from \(S\) where repetition is allowed.
  • A word of length \(k\) from \(S\) is a list of \(k\) elements from \(S\text{.}\) \(S\) is the “alphabet.” (order matters, repetition is allowed)
  • A word is simple if elements/letters are distinct.
    • A simple word of length \(n\) from \(S\) is called a permutation (order matters, no repetition)
We will now look at how to count each of these types of sets/words. Often parts of counting problems can be cast as one of these main types, so words and subsets are useful models for counting.
By product principle, there are \(n\) choices for each of the \(k\) positions, so there are \(n^k\) words.
Elements may not repeat in the word. There are \(n\) choices for position 1, \(n-1\) choices for position 2, etc. In general, \(n+1-i\) choices for position \(i\text{.}\) So word may be formed in
\begin{equation*} \prod_{i=1}^{k}(n-i+1)=n_{(k)} \end{equation*}
ways.
We will count the simple \(k\)-words in two ways. From above, there are \(n_{(k)}\) simple words from \([n]\text{.}\) Alternatively, we can form a simple \(k\)-word by first choosing the elements from \([n]\text{,}\) and then permute them. This gives \(\binom{n}{k}k!\) possible simple \(k\)-words. Thus
\begin{equation*} \binom{n}{k}k!=n_{(k)}\implies \binom{n}{k}=\frac{n_{(k)}}{k!}. \end{equation*}
Observe that for a fixed \(k\text{,}\) \(\binom{n}{k}\) is a polynomial of degree \(k\text{.}\) (Later we’ll extend the definition to real-valued \(n\text{,}\) but the combinatorial meaning will be lost.)

Example 1.20.

A 7-multiset of \(\{a,b,c,d,e\}\) could be \(\{a,a,a,c,d,d,e\}\) which may be written \(\{3\cdot a,c,2\cdot d, e\}\) so repetition numbers are \(3,0,1,2,1\text{,}\) respectively.

Remark 1.21.

The number of \(k\)-element multisets from \([n]\) is the same as the number of nonegative integer solutions to \(x_1+\cdots+x_n=k\) where \(x_i\) is the number of copies of element \(i\) chosen for the multiset.
From above, the number of \(k\)-element multisets from \([n]\) is equivalent to the number of solutions to \(\sum_{i = 1}^n x_i = k\) in nonnegative integers. We proceed by establishing a bijection from the set of these solutions to the number of lists of \(k\) stars and \(n-1\) bars.
We can represent each solution of \(x_1+\cdots+x_n=k\) as a list of \(x_1+\cdots+x_n=k\) stars, where after \(x_1\) stars we place a bar, then \(x_2\) stars, then bar, \(x_3\) stars, etc. Given such a list, we can read off the values of \(x_i\text{,}\) since \(x_i\) will be the number of stars between the \((i-1)^{\text{th}}\) bar and the \(i^{\text{th}}\) bar (assuming 0 bar and \(n^{\text{th}}\) bar at ends).
This gives a bijection between solutions \(x_1,\dots,x_n\) and star/bar lists of length \(k+n-1\) with \(n-1\) bars.
Thus, the number of solutions is \(=\binom{k+n-1}{n-1}\) since there are this many ways to choose \(n-1\) positions for the bars.

Example 1.23.

\(\binom{7+5-1}{5-1}=\binom{11}{4}\) is number of solutions to \(x_1+x_2+x_3+x_4+x_5=7\)
\begin{equation*} \star\star\star||\star|\star\star|\star \end{equation*}
corresponds to solution \(3+0+1+2+1\)
We can restrict the variables in the integer sum problem to be positive. Doing this leads to another useful counting model called a composition.

Definition 1.24.

A composition of the positive integer \(k\) is a list of positive integers summing to \(k\text{.}\) The entries in the list are called parts.
  1. We convert the problem to the case of counting solutions in nonnegative integers.
    Consider \(x_1+\cdots+x_n=k\) where \(x_i>0\text{.}\) Now let \(y_i=x_i-1\) for \(i=1,\dots,n\text{.}\) So \(y_i\geq 0\text{.}\) The solutions to \(\sum_{i=1}^n x_i=k\) corresponds to solutions of \(\sum_{i=1}^n y_i=k-n\) in nonnegative integers.
    (To see this, \(\sum_{i=1}^n x_i=\sum_{i=1}^n (y_i+1)=k\) so \(x_1,\dots,x_n\) is a solution for \(\sum_{i=1}^n y_i=k-n\text{.}\))
    There are \(\binom{k-n+n-1}{n-1}\) such solutions, which is \(\binom{k-1}{n-1}\text{.}\)
  2. Use stars and bars.
    The number of solutions in positive integers corresponds to an arrangement of \(k\) stars and \(n-1\) bars where no two bars can occur consecutively. Place the \(k\) stars. There are \(k-1\) positions between the stars where bars may be placed. So the number of arrangements is \(\binom{k-1}{n-1}\)

Example 1.26.

A solution to \(x_1+x_2+x_3+x_4+x_5=7\) in positive integers corresponds to \(y_1+y_2+y_3+y_4+y_5=2\) in nonnegative integers (you’re just deciding where to put the extra two 1s).
<Prev^TopNext>