4 Combinatorics

Combinatorics is the part of mathematics concerned with counting in a broad sense, for example counting the number of ways to arrange a set of objects or the number of combinations that can be made from a set of objects. It is a fundamental part of discrete mathematics and has applications in many areas of mathematics, computer science, chemistry, and physics.

Exercises: Factorials

The factorial of a non-negative integer \(n\) is defined as the product of all positive integers less than or equal to \(n\):

\[ n! = n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1, \quad n \geq 1. \]

It is also defined that \(0! = 1\). The factorial appears in many mathematical contexts, including series expansions, and of course combinatorics. Its basic use is the following:

Factorial and counting

Given a set of \(n\) distinct objects, the number of ways to arrange them in a sequence (i.e., the number of permutations) is \(n!\).

In one exercise, you will need the following approximation for large \(n\), known as Stirling’s approximation:

Stirling’s approximation

For large \(n\), the factorial \(n!\) can be approximated as

\[ n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n. \]

In calculations, especially numerical calculations, it is often convenient to use the logarithm of the factorial. Using Stirling’s approximation, we have

\[ \log(n!) \approx \frac{1}{2}\log(2\pi n) + n\log(n) - n. \]

Exercise 4.1 (Basic factorials) Compute the factorials \(0!\), \(1!\), \(2!\), \(3!\), \(4!\), and \(5!\).

Exercise 4.2 (Lunch line) 42 people stand in a lunch line. How many different lunch line arrangements with 42 people are possible?

Exercise 4.3 (Chemist’s shelf) Compute the number of arrangements for the following scenarios:

A chemist has 10 different chemical samples. How many ways can the chemist arrange the samples on a shelf?
A chemist has 10 different chemical samples. 4 of the samples are liquids, and the other 6 are solids. How many ways can the chemist arrange the samples on a shelf if all the liquids must be together?

Exercise 4.4 (Stirling’s approximation) We study Stirling’s approximation for the factorial.

Use Stirling’s approximation to estimate \(5!\). Compare your result with the exact result

\[ 5! = 120. \]

Use Stirling’s approximation to estimate \(10!\). Compare again with the exact number

\[ 10! = 3\,628\,800. \]

The relative error of an approximation \(A\) to an exact value \(x\) is

\[ \frac{|A-x|}{x}. \]

Calculate the relative error of Stirling’s approximation for \(5!\) and \(10!\). For which value of \(n\) is the approximation better?

Use Stirling’s approximation to estimate \(50!\). The exact value is approximately

\[ 50! \approx 3.041\times10^{64}. \]

Based on your results above, what happens to the accuracy of Stirling’s approximation as \(n\) increases?

Exercises: Binomial coefficients and Pascal’s triangle

The binomial coefficient \(\binom{n}{k}\) is defined as the number of ways to choose \(k\) elements from a set of \(n\) elements, without regard to the order of selection. It is given by the formula:

\[ \binom{n}{k} = \frac{n!}{k!(n-k)!}, \]

Pascal’s triangle is a triangular array of numbers where each number is the sum of the two numbers directly above it:

\[ \begin{gather} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ \vdots \end{gather} \]

Fact: The \(n\)-th row of Pascal’s triangle contains the binomial coefficients \(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\).

Exercise 4.5 (Basic binomial coefficients)

Compute the binomial coefficients \(\binom{5}{2}\), \(\binom{6}{3}\), and \(\binom{7}{4}\).
In Norwegian Lotto, 7 numbers are drawn from a set of 34 numbers. How many different combinations of 7 numbers can be drawn?

Exercise 4.6 (Pascal’s triangle) Compute the first 6 rows of Pascal’s triangle. Verify that the numbers in the \(n\)-th row correspond to the binomial coefficients \(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\).

Exercise 4.7 (Pascal’s identity) The binomial coefficients satisfy Pascal’s identity,

\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. \]

Explain why this relation is equivalent to the construction of Pascal’s triangle, where each number is the sum of the two numbers directly above it.
Write each binomial coefficient on the right-hand side in terms of factorials.
Put the two terms over a common denominator and simplify the expression.
Show that the resulting expression is

\[ \frac{n!}{k!(n-k)!}, \]

and hence prove Pascal’s identity.
Give a combinatorial explanation of Pascal’s identity. Hint: Consider choosing \(k\) objects from a set of \(n\) objects. Pick one particular object and separate the choices into two cases: those that contain this object and those that do not.

Exercise 4.8 (Pascal’s triangle and the Sierpinski triangle) Write a computer program to generate the first \(2^n\) rows of Pascal’s triangle, where \(n=1,2,\ldots\). Create a \(2^n\times 2^n\) lower triangular matrix \(T\), where \(T_{k,n} = 0\) if \(\binom{n}{k}\) is even, and \(T_{k,n}=1\) if the coefficient is odd, for \(k \leq n\) (indexing from zero). Visualize the matrix. What pattern do you observe? This pattern is known as the Sierpinski triangle.

If you use Python and sympy, you can generate binomial factors with the function sympy.binomial(n, k). Check for parity using the modulo operator %. For example, sympy.binomial(n, k) % 2 will return 0 for even numbers and 1 for odd numbers.

Exercise 4.9 (The binomial theorem) The binomial theorem states that

\[ (x+y)^n = \sum_{k=0}^n \binom{n}{k}x^{n-k}y^k. \]

Use ordinary multiplication to expand \((x+y)^2\).
Use the binomial theorem to expand \((x+y)^3\).
Use the binomial theorem to expand \((x+y)^4\).
Compare the coefficients in your expansion of \((x+y)^4\) with the row

\[ 1,\quad 4,\quad 6,\quad 4,\quad 1 \]

of Pascal’s triangle.
Use the binomial theorem to expand \((1+x)^5\).
Without carrying out any multiplication, find the coefficient of \(x^3\) in \((1+x)^7\).

Exercise 4.10 (Coefficients in binomial expansions) Consider the binomial expansion

\[ (a+b)^n = \sum_{k=0}^n \binom{n}{k}a^{n-k}b^k. \]

Write out the complete expansion of \((a+b)^6\).
Find the coefficient of \(a^4b^2\) in \((a+b)^6\) without writing out the full expansion.
Find the coefficient of \(x^4\) in \((2+x)^7\).
Find the coefficient of \(x^3\) in \((1-2x)^5\).
Suppose that each of \(n\) electrons can independently be assigned either label \(\alpha\) or label \(\beta\). Explain why the number of assignments containing exactly \(k\) electrons labelled \(\beta\) is \(\binom{n}{k}\).
Use the binomial theorem with \(a=b=1\) to show that

\[ \sum_{k=0}^n \binom{n}{k}=2^n. \]

Interpret this result in terms of the number of possible assignments of the two labels \(\alpha\) and \(\beta\) to \(n\) electrons.