These exercises are taken from various sources,
including Prof. P. J. Cameron's notes.
Some of them will be used for assessment.
Subsets and binomial coefficients
 Write 1001 as a binomial coefficient \(n\choose k\) with \(n\le20\).
 If \(X\) is a set of 8 elements, then the number of 3element subsets of \(X\)
is twice the number of 2element subsets. Is there any other number for which
this holds?
 Calculate \(\sum\limits_{k=0}^n k^2{n\choose k}\).
 Let \(X\) be an \(n\)element set. Find a bijection \(F\) between the set
of \(k\)element subsets of \(X\) and the set of all \((nk)\)element subsets of \(X\).
Deduce that \[{n\choose k}={n\choose nk}.\]
 Let \(\mathrm i\) denote the square root of \(1\), and note that
\(1+\mathrm i=\sqrt{2}\mathrm e^{\pi/4}\). Hence find the real and imaginary parts
of \((1+\mathrm i)^n\) for any natural number \(n\). (You will probably find it
convenient to consider the different congruence classes mod 8 separately.)
Expanding \((1+\mathrm i)^n\) by the Binomial Theorem, find expressions for
\[\sum_{j=0}^{\lfloor(nt)/4\rfloor}{n\choose 4j+t},\]
for \(t=0,1,2,3\), again separating the congruence classes mod 8.
(This involves a lot of repetitious work. You should at least do the calculations
for \(n\equiv 0\pmod 8\).)
 By calculating the coefficient of \(x^n\) on the two sides of the identity
\[(1+x)^n.(1x)^n=(1x^2)^n,\]
or otherwise, prove that
\[ \sum_{k=0}^n(1)^k{n\choose k}^2 = \begin{cases}
0 & \mbox{if \(n\) is odd}\cr
(1)^m{2m \choose m} & \mbox{if \(n=2m\)}\end{cases}\]

(a) Prove that
\[{n\choose k+1} = \frac{nk}{k+1}{n\choose k}.\]
(b) Prove that, if \(n>2k+1\), then \({n\choose k+1}>{n\choose k}\);
if \(n=2k+1\), then \({n\choose k+1}={n\choose k}\); and
if \(n<2k+1\), then \({n\choose k+1}<{n\choose k}\).
(c) Hence show that, for fixed \(n\) and \(k=0,1,\ldots,n\),
the binomial coefficients increase, then remain constant for one step
(if \(k\) is odd), then decrease.
(Such a sequence is said to be unimodal.)
(d) Show further that the largest binomial coefficient is
\(2m\choose m\) if \(n=2m\) is even, while if \(n=2m+1\) is odd, then
\(2m+1\choose m\) and \(2m+1\choose m+1\) are equal largest.
(e) Deduce that, if \(n=2m\), then
\[\frac{2^{2m}}{2m+1} \le {2m\choose m}\le 2^{2m}.\]

(a) Show that the binomial coefficient \(2m\choose m\)
is divisible by every prime \(p\) satisfying \(m+1\le p\le 2m\).
(b) Hence show that the number of primes between \(m+1\) and \(2m\) is
at most \(2m/\log_2 m\).
Remark: this is a weak version of the famous Prime Number Theorem,
which says that the number of prime numbers \(p\) satisfying
\(1\le p\le n\) is asymptotically \(n/\log n\).
 Show that a set \(X=\{x_1,x_2,\ldots,x_n\}\) of \(n\) distinct elements can be made into a sequence \((y_1,y_2,\ldots,y_n)\) of length \(n\) in exactly \(n!\) ways.
 Making use of the formula
\[
{n\choose k} = \frac{n!}{k!\,(nk)!},\quad 0\leq k\leq n
\]
established in the course, show the following.
a) \({n\choose k} = {n\choose nk},\quad 0\leq k\leq n\);
b) \(k {n\choose k} = n {n1\choose k1},\quad 1\leq k\leq n\);
c) \({n+1\choose k} = {n\choose k} + {n\choose k1},\quad 1\leq k\leq n+1\).
 Give alternative proofs for the formulae in the previous question,
by showing that the lefthand and righthand sides count the elements of one and the same set, respectively of equipotent sets.
 Show that \({n\choose 0} = {n\choose n} =1\), and that \({n\choose k}=0\) for \(k>n\).
 Prove that
a) \({n\choose k1} < {n\choose k},\quad 1\leq k<\frac{n+1}{2}\);
b) \({n\choose k} < {n+1\choose k},\quad 1\leq k\leq n+1\).
 Show by induction on \(n\) that, for numbers \(a,b\) and every nonnegative integer \(n\), we have
\[
(a+b)^n = \sum_{i=0}^n {n\choose i} a^i\, b^{ni}\quad\mbox{(general binomial theorem)}.
\]
 Show that, for \(0\leq k < n\),
\[
{n\choose k} = \sum_{i=0}^k {ni1\choose ki}.
\]
 Use the fact that \((1+x)^{m+n}=(1+x)^m (1+x)^n\) plus the binomial theorem to give an alternative proof of the ChuVandermonde identity:
\[
{m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose rk},\qquad m,n,r\in\mathbb{N}_0.
\]
Selections and arrangements

(a) How many ordered sequences of length 5 can be made using the elements
\(\{1,2,3,4,5,6,7\}\) if repetitions are allowed? How many of these contain
exactly two of the numbers 1,2,3? In how many of them do even and odd numbers
alternate?
(b) What are the answers to these questions if repetitions are not allowed?
 How many words can be made using the letters of the word STARTS? How many
of these are palindromes (that is, read the same backward as forward)?
 Let \(X\) and \(Y\) be sets with \(X=n\) and \(Y=m\).
(a) Determine the number of functions \(f\) mapping \(X\) into \(Y\).
(b) How many of these functions are injections, i.e. onetoone?
(c) How many of these functions are bijections, i.e. onetoone and onto?
(d) (Much harder) How many of these functions are surjections, i.e. onto?
 How many permutations of the set \(\{1,2,\ldots,n\}\) are there? How many of
these are cyclic permutations, that is, their cycle decomposition
consists of a single cycle of length \(n\)?
 For which values of \(n\) is \(W(n)\) odd?
 Write out a complete proof of the Theorem from the notes concerning the number of solutions of the equation
\[
x_1 + x_2 + \cdots + x_k = n
\]
in nonnegative integers \(x_1,x_2,\ldots,x_n\).
 a) Write down the axioms of a group, and those of an abelian group.
b) Show in detail that the permutations of an \(n\)set \(S\) form a group \(\Sigma(S)\) of order \(n!\) under composition.
c) Show that \(\Sigma(S)\) is nonabelian for \(\vert S\vert \geq 3\).
 How many solutions does the equation \(
x_1 + x_2 + \cdots + x_k = n
\) have in positive integers \(x_1,x_2,\ldots,x_k\)? Provide proof for your assertion.
 Let \(S\) be an \(n\)set.
(a) Choose an ordering \(S=\{x_1,x_2,\ldots,x_n\}\) of the elements of \(S\), and set
\[
\mathcal{C} = \big\{\emptyset, \{x_1\}, \{x_1,x_2\},\ldots, \{x_1,\ldots,x_{n1}\}, S\big\}.
\]
Show that \(\mathcal{C}\) is a maximal chain of \(\mathcal{B}(S)\).
(b) Let \(\mathcal{C}\) be a maximal chain of \(\mathcal{B}(S)\). Show that \(\mathcal{C}\) arises from an ordering of \(S\) in the way described in Part (a).
 A finite sequence \(c_1, c_2,\ldots,c_n\) of numbers is called unimodal, if there exists an integer \(s\) with \(1\leq s\leq n\) such that
\[
c_1 \leq c_2 \leq \cdots \leq c_s \geq c_{s+1} \geq \cdots \geq c_n.
\]
Show that the rows of Pascal's triangle \(\{{n\choose k}\}_{0\leq k\leq n}\) are unimodal in the following strong sense:
(i) if \(n\) is even, \(n=2m\) say, then
\[
{n\choose 0} < {n\choose 1} < \cdots < {n\choose m} > {n\choose m+1} > \cdots > {n\choose n};
\]
(ii) If \(n\) is odd, \(n=2m+1\) say, then
\[
{n\choose 0} < {n\choose 1} < \cdots < {n\choose m} = {n\choose m+1} > {n\choose m+2} > \cdots > {n\choose n}.
\]
 Show that the sum \(\sum_{k=1}^{n1} {n\choose k}^{1}\) tends to zero as \(n\) tends to infinity.
 For each of the following families of sets, decide (with justification) whether it has a transversal; and if it does, exhibit one.
(a) \(S_1 = \{1,2,3\}\), \(S_2 = \{1,2\}\), \(S_3=\{1,2,5\}\), \(S_4 = \{1,5\}\), \(S_5=\{1,2,4\}\).
(b) \(T_1=\{a,b\}\), \(T_2=\{a,c\}\), \(T_3 = \{b,c,d\}\), \(T_4=\{a,b,c\}\), \(T_5=\{a,b,c,d\}\).
 A Latin square of order \(n\) is an \(n\times n\) matrix with entries taken from the set \([n]\), with the property that each \(i\in [n]\) occurs exactly once in each row and each column. More generally, given any \(n\times n\) matrix \(A=(a_{ij})\) with entries from the set \([n]\), as well as an ordered \(n\)set \(G=\{g_1,g_2,\ldots,g_n\}\), we can use \(A\) to define a binary operation \(\circ\) on \(G\) via
\[
g_i\circ g_j = g_k\,\Longleftrightarrow\,a_{ij} = k.
\]
Conversely, any binary operation on \(G\) gives rise to such a matrix, once we have ordered the elements of \(G\). A binary structure \((G,\circ)\) is called a quasigroup, if the following two axioms hold:
(Q1) (left division) For each pair \((g_j,g_k)\in G^2\) there exists a unique \(g_i\in G\) with \(g_ig_j=g_k\).
(Q2) (right division) For each pair \((g_i,g_k)\in G^2\) there is a unique \(g_j\in G\) such that \(g_ig_j=g_k\).
Show that a binary structure \((G,\circ)\) is a quasigroup if, and only if, the matrix \(A\) corresponding to \(G\) after ordering is a Latin square.
Power series
 The purpose of this exercise is to show you that, even when a power series
fails to converge, algebraic manipulations on it can still give us something
interesting.
Let \(\pi\) be a permutation of the set \(\{1,2,\ldots,n\}\). We say that
\(\pi\) is decomposable if there is a number \(k\), with
\(1\le k\le n1\), such that \(\pi\) maps the numbers \(1,\ldots,k\)
to themselves. If no such \(k\) exists then \(\pi\) is indecomposable.
There are \(n!\) permutations of the set \(\{1,\ldots,n\}\). Suppose that
\(g(n)\) of them are indecomposable. (By convention we take \(0!=1\) but we do not
define \(g(0)\).)
For any permutation \(\pi\), let \(k\) be the smallest number such that
\(\pi\) maps \(1,\ldots,k\) to themselves (so that \(k=n\) if \(\pi\) is indecomposable).
Show that there are \(g(k)(nk)!\) permutations with any given value of \(k\).
Hence show that
\[ \sum_{k=1}^n g(k)(nk)! = n!.\]
Now let \(F(x)=\sum\limits_{n\ge 0} n!x^n\) and
\(G(x)=\sum\limits_{n\ge 1} g(n)x^n\) be the generating functions for the
factorial numbers and the numbers \(g(n)\) respectively.
Note that \(G(x)\) has constant term zero since we start at 1.
Prove that
\[F(x)(1G(x))=1.\]
Note that this equation makes sense even though the power series do not
converge for any nonzero value of \(x\).
 Show from the multiplication rule that, in the calculus of formal power series,
\[
(1x)(1+x+x^2+x^3+\cdots) = 1.
\]
 Show that, for two formal power series \(f(x) = \sum_{n\geq0} a_n x^n\) and \(g(x) = \sum_{n\geq0} b_n x^n\), we have
\[
\big(f(x) + g(x)\big)' = f'(x) + g'(x).
\]
 Show the following. If \(f'=0\), where \(f(x)=\sum_{n\geq0} a_n x^n\) is a formal power series, then \(f(x)=a_0\); that is, \(f\) is a constant.
 Prove the Leibniz rule for the derivatives of a product of two formal power series
\[
(fg)^{(k)} = \sum_{\kappa=0}^k {k\choose \kappa} f^{(\kappa)} g^{(k\kappa)},\quad k\geq0.
\]

Operations on formal series involve corresponding operations on their coefficients (and vice versa). Here, we begin to explore this connection for formal power series.
Definition. The symbol \(f\overset{gps}{\longleftrightarrow}\{a_n\}_0^\infty\) (written this way or the other way round) means that \(f\) is the generating power series for the sequence \(a_0,a_1,a_2,\ldots\); that is, \(f=\sum_{n\geq0} a_nx^n\).
Show the following: if \(f\overset{gps}{\longleftrightarrow}\{a_n\}_0^\infty\) and \(h>0\) is an integer, then
\[
\big\{a_{n+h}\big\}_0^\infty \overset{gps}{\longleftrightarrow} \frac{f(x)a_0a_1x\cdotsa_{h1}x^{h1}}{x^h}.
\]
 Show: if \(f\overset{gps}{\longleftrightarrow}\{a_n\}_0^\infty\) and \(P(y)\) is a polynomial, then
\[
P(xD_x) f\,\overset{gps}{\longleftrightarrow}\,\big\{P(n) a_n\big\}_{n\geq0}.
\]
 Find a closed formula for the series
\[
\sum\limits_{n\geq0} (n^2+4n+5)/n!
\]
making use of the previous exercise.
 For \(i=1,2,\ldots,k,\) let \(f_i\overset{gps}{\longleftrightarrow}\big\{a_n^{(i)}\big\}_{n\geq0}\). Show that
\[
f_1f_2\cdots f_k\, \overset{gps}{\longleftrightarrow}\,\Bigg\{\underset{n_1+\cdots+n_k=n}{\sum_{n_1,\ldots,n_k\geq0}} a_{n_1}^{(1)} a_{n_2}^{(2)} \cdots a_{n_k}^{(k)}\Bigg\}_{n=0}^\infty.
\]
Recurrence relations
 Let \(s(n)\) be the number of expressions for \(n\) as a sum of positive
integers. For example
\[4=3+1=1+3=2+2=1+1+2=1+2+1=2+1+1=1+1+1+1,\]
so \(s(4)=8\).
(a) Show that \(s(1)=1\) and \[s(n)=1+\sum_{k=1}^{n1}s(k)\] for \(n\ge 2\).
(b) Deduce that \(s(1)=1\) and \(s(n)=2s(n1)\) for \(n\ge 2\).
(c) Hence show that \(s(n)=2^{n1}\) for \(n\ge 1\).
Notice how we have converted a rather complicated recurrence relation into a much
simpler one!
 Solve the recurrence relation and intial conditions
\[a_0=2,a_1=4,a_2=7,\quad a_n=4a_{n1}5a_{n2}+2a_{n3}\mbox{ for }n\ge 3.\]
 I purchase an item costing \(n\) pence. I have a large number of
1 and 2 pence coins at my disposal. In how many ways can I pay for the item
(a) if I an buying it from a machine and have to insert the coins one at a time;
(b) if I am buying it in a shop and can hand the money over all at once?
 Solve the recurrence relation and initial conditions
\[a_0=1,\qquad a_1=1,\qquad a_n=3a_{n1}2a_{n2}\mbox{ for }n\ge 2.\]
 Solve the recurrence relation and initial conditions
\[a_0=2,\qquad a_n=(a_{n1})^2\mbox{ for }n\ge 1.\]
 Let \[A=\begin{pmatrix}0&1\cr 1&1\end{pmatrix}.\]
Prove by induction that
\[A^{n+1}=\begin{pmatrix}F_{n1}& F_n\cr F_n&F_{n+1}\end{pmatrix}\]
for \(n\ge 1\), where \(F_n\) is the \(n\)th Fibonacci number.

(a) Use the recurrence relation in the notes to prove that the derangement
numbers \(d(n)\) satisfy the simpler recurrence
\[d(0)=1,\qquad d(n)=nd(n1)+(1)^n\mbox{ for }n\ge 1.\]
(b) Now put \(f(n)=d(n)/n!\). Show that
\[f(0)=1,\qquad f(n)=f(n1)+\frac{(1)^n}{n!}\mbox{ for }n\ge 1.\]
Hence show that \(f(n)=\sum\limits_{k=0}^n (1)^k/k!\), and deduce the formula
in the notes for \(d(n)\).
(c) Use this formula to show that
\[ \sum_{n\ge 0} \frac{d(n)x^n}{n!} = \frac{\mathrm e^{x}}{1x}.\]
The series on the left is the exponential generating function
of the derangement numbers.
 Take a circle and put \(2n\) points \(P_1,Q_1,P_2,Q_2,\ldots,P_n,Q_n\)
equally spaced around the circumference. A matching is a set of \(n\)
chords to the circle such that
 each chord joins a point \(P_i\) to a point \(Q_j\) for some \(i,j\);
 each of the \(2n\) points lies on exactly one of the chords;
 no two chords cross.
Let \(A_n\) be the number of different matchings.
(a) Show that \(A_0=1,A_1=2,A_2=3,A_3=5\).
(b) Show that, for \(n\ge 1\), we have
\[ A_n=\sum_{i=1}^n A_{i1}A_{ni}.\]
[Hint: consider the matchings in which \(P_1\) is joined to \(Q_i\), and show
that there are \(A_{i1}A_{ni}\) of these.]
(c) Hence show by induction that \(A_n\) is the \((n+1)\)st Catalan number \(C_{n+1}\).
Partitions and permutations

(a) Prove each of the following statements (i) by directly counting the partitions,
(ii) by using the recurrence relation:
 \(S(n,2)=2^{n1}1\);
 \(S(n,n1)={n\choose 2}\).
(b) Find a formula for \(S(n,n2)\).

(a) Prove (i) by directly counting the permutation, (ii) by using the recurrence
relation, that \(s(n,n1)={n\choose 2}\).
(b) Find a formula for \(s(n,n2)\).
 Calculate the number of permutations of \(\{1,2,3,4,5,6\}\) with three cycles
(a) by using the recursion formula for the appropriate Stirling numbers;
(b) by listing the possible cycle lengths of such a permutation and counting
the number of permutations with each possible cycle structure.
 Let \(k\) be given, and let \(p_k(n)\) be the probability that a randomlychosen
permutation of \(\{1,\ldots,n\}\) has exactly \(k\) fixed points.
Show that
\(p_k(n)={n\choose k}d(nk)/n!\), where \(d(nk)\) is the
\((nk)\)th derangement number, and hence show that
(a) \(\sum\limits_{k=0}^n {n\choose k}d(nk)=n!\);
(b) \(\lim\limits_{n \rightarrow\infty} p_k(n) = \frac{\mathrm e^{1}}{k!}\).
[If you have studied some probability theory, the last statement says that the
number of fixed points of a randome permutation of the set \(\{1,\ldots,n\}\)
approaches a Poisson distribution with parameter 1 as \(n\rightarrow\infty\).]
 Consider configurations in the plane consisting of layers, each layer in turn consisting of consecutive squares. Two consecutive layers meet along the edges of a (positive) number of squares. Such configurations are called polyominoes (more precisely, horizontally convex or HC polyominoes). Let \(a_n\) be the number of polyominoes consisting of a total of \(n\) squares, setting \(a_0=0\). One can show (cf., for instance, Example~14.5 in van Lint & Wilson) that the sequence \(\{a_n\}_{n\geq0}\) satisfies the recurrence relation
\[
a_n = 5 a_{n1}  7 a_{n2} + 4 a_{n3},\quad n\geq5.
\]
a) Determine the initial values \(a_i\) for \(i=1,2,3,4\) by explicitly listing all polyominoes with \(1, 2,3,\) and \(4\) squares.
b) Use the result of a) plus the recurrence relation above to determine the generating power series \(f(x)=\sum_{n\geq0}a_n x^n\) of the sequence \(\{a_n\}_{n\geq0}\).
 By expanding \(f(x)\) into partial fractions, compute an asymptotic formula for the numbers \(a_n\). You may use the fact that \(\gamma_1 = 3.20556943\ldots\) and \(\gamma_{2,3} = 0.897215\pm0.665457 i\) are the reciprocal values of the three distinct roots of the polynomial \(Q(x)=15x+7x^24x^3\). Your asymptotic formula for \(a_n\) should be explicit in the quantities \(\gamma_1,\gamma_2,\gamma_3\).
 Let \(f(n,k)\) denote the number of ways to write the nonnegative integer \(n\) as an ordered sum of \(k\) nonnegative integers. Find a closed formula for \(f(n,k)\).
 Let \(n,k\in\mathbb{N}\) be given. Consider all ways of writing \(n\) as an ordered sum of \(k\) nonnegative integers, and form the product of these \(k\) numbers. Let \(f(n,k)\) denote the sum of all these products. Determine \(f(n,k)\).
 Show the following: if \(f \overset{gps}{\longleftrightarrow} \{a_n\}_0^\infty,\) then
\[
\frac{f(x)}{1x}\,\overset{gps}{\longleftrightarrow}\,\bigg\{\sum_{\nu=0}^n a_\nu\bigg\}_{n\geq0}.
\]
 Derive a closed formula for the sum \(\sum_{n=1}^N n^2\) of squares of the first \(N\) positive integers. [Hint: use the previous exercise, plus a result from above.]
The principle of inclusion and exclusion
 An opinion poll reports that the percentage of voters who would be satisfied
with each of the three candidates A, B, C for President is 65%, 57%, 58% respectively.
Further, 28% would accept A or B, 30% A or C, 27% B or C, and 12% would be
content with any of the three. What do you conclude?
 I have 25 sweets to distribute to a class of 10 children.
(a) In how many ways can I distribute the sweets?
(b) In how many ways can I distribute the sweets if I give Alice at least four sweets?
(c) In how many ways can I distribute the sweets if I give both Alice and Bob
at least four sweets?
(d) Use the Principle of Inclusion and Exclusion to count the number of ways
I can distribute the sweets if no child is to have more than three sweets.
Families of sets
 Let \(n=2k\). Show that there are \(2^{2k1 \choose k1}\) intersecting
families of \(k\)element subsets of \(\{1,\ldots,n\}\) having the maximum
number \(2k1\choose k1\) of members. Show that only \(2k\) of them have the form
\(\mathcal F_k(i)\) for \(i\in\{1,\ldots, n\}\). Hence show that the second
part of the ErdösKoRado Theorem goes badly wrong when \(n=2k\).
 Identify the righthand picture before Theorem 7.5 in the notes with the
example constructed using the finite field \(F=\mathbb Z_2\).
[Hint: the subspace spanned by the vector \(v=(a,b,c)\) corresponds to the point
with label \(4a+2b+c\) in the figure.]
 Construct a finite field with 8 elements.
 Let \(X=\{1,\ldots,n\}\). Show that, for every nonempty subset \(A\) of \(X\),
there is an intersecting family \(\mathcal F\) of subsets of \(X\) of size
\(2^{n1}\) with \(A\in\mathcal F\).
Show further that any two subsets \(A,B\) with \(A\cap B\ne\emptyset\) are contained
in a family with these properties. What about three pairwise intersecting sets?
 Show that the largest Sperner family of subsets of \(\{1,2,3,4,5\}\) containing
the sets \(\{1,2\}\) and \(\{3,4,5\}\) contains eight sets. How does this
compare with Sperner's Theorem?
 Let \(\mathcal S\) be the family
\[\{\{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\},\{2,5,7\},\{3,4,7\},\{3,5,6\}\}\]
of subsets of \(\{1,2,3,4,5,6,7\}\).
Let \(\mathcal F\) be the family of all subsets of \(\{1,\ldots,7\}\)
which contain a member of \(\mathcal S\). Show that
(a) \(\mathcal F\) is an intersecting family;
(b) \(\mathcal F\) contains 7 sets of size 3, 28 of size 4, 21 of size 5, 7 of size 6,
and 1 of size 7; in all, 64 sets.
 Let \(X=\{1,2,\ldots,n\}\) and \(\mathcal S=\{A_1,A_2,\ldots,A_b\}\) be a family
of distinct subsets of \(X\) such that \(A_j\cap A_k=1\) for all \(j\ne k\).
For each \(i\in X\), let \(r_i\) be the number of subsets of \(\mathcal S\)
which contain \(i\). Prove that
\[\sum_{i=1}^n r_i(r_i1) = b(b1).\]
[Hint: count the number of ordered triples \((i,A_j,A_k)\), where \(A_j,A_k\)
are distinct sets in \(\mathcal S\) and \(A_j\cap A_k=\{i\}\), in two
different ways.]
Systems of distinct representatives
 (a) Write down a SDR for the Fano plane.
(b) How many different SDRs can you find?
 Let \(A_1,\ldots, A_n\) be subsets of \(\{1,\ldots,n\}\). Let \(M\) be the
\(n\times n\) matrix whose \((i,j)\) entry is 1 if \(j\in A_i\), and 0 otherwise.
Prove that the number of SDRs of \((A_1,\ldots,A_n)\) is at least
\(\det(M)\).
[Hint: use the formula for the determinant as a sum over permutations.
Each SDR contributes a term \(\pm1\) to the sum.]
Deduce that the Fano plane has at least 24 SDRs.
 Construct five families, \(\mathcal F_1,\mathcal F_2,\mathcal F_3,\mathcal F_4,\mathcal F_6\), each consisting of three subsets of \(\{1,2,3\}\), such that \(\mathcal F_i\)
has exactly \(i\) different SDRs, for each \(i\in\{1,2,3,4,6\}\).
Does there exist a family of three subsets of \(\{1,2,3,4,5,6\}\) with
five SDRs?
 This exercise gives the deficit form of Hall's Theorem. It is a
generalisation of Hall's Theorem, but can be deduced from Hall's Theorem.
Theorem
Let
\(A_1,\ldots,A_n\) be subsets of a set \(X\). Suppose that, for some positive integer
\(m\), we have
\[A(J)\geJm\mbox{ for all }J\subseteq\{1,\ldots,n\},\]
where \(A(J)=\bigcup\limits_{j\in J} A_j\). Then it is possible to find \(nm\)
of the
sets \(A_1,\ldots, A_n\) which have a SDR.
Prove this. [Hint: take \(m\) `dummy' elements \(z_1,\ldots,z_m\) and add them to all
the sets \(A_i\).]
Latin squares
 Let \(A\) and \(B\) be orthogonal Latin squares of order \(n\), which use the
symbols \(0,1,\ldots,n1\). Construct a matrix \(S\) in which the \((i,j)\)th entry
consists of the pair \((a_{ij},b_{ij})\), regarded as a 2digit number written in
base \(n\). Show that \(S\) has the properties
(a) its entries are all the integers from 0 to \(n^21\) inclusive;
(b) the sum of the entries in any row or column is \(n(n^21)\).
(This construction is due to Euler.)
 Show that, up to permutations of rows and columns and changes in the names
of the symbols, there are just two different Latin squares of order 4.
Show that one, but not the other, has an orthogonal mate
(a Latin square orthogonal to it).
 Prove that the Latin square given by the addition table of the integers mod \(n\)
has an orthogonal mate if and only if \(n\) is odd.
 Let \(A\) be a Latin square of order \(n\). Suppose that, for some
positive integer \(r < n\), only the numbers \(1,\ldots,r\) occur in the first
\(r\) rows and columns of \(A\).
(a) Show that the submatrix of \(A\) formed by the first \(r\) rows and columns
is a Latin square of order \(r\).
(b) Show that \(n\ge 2r\).
(c) Give an example with \(r=3\) and \(n=7\).
 Let \(m\) be an integer greater than 1. Let \(X(m)\) be the multiplication table
of the nonzero integers mod \(m\), that is, the \((m1)\times(m1)\)
matrix defined as follows:
rows and columns are indexed by \(1,2,\ldots, m1\) and the \((i,j)\) entry is
\(ij\bmod m\).
Prove that \(X(m)\) is a Latin square if and only if \(m\) is prime.
(**) Does it have an orthogonal mate?
Steiner triple systems
 Suppose that an \(\mathrm{STS}(v)\) of order \(v\) on a set \(X\) has a subsystem
\(Y\) of order \(u\), with \(u < v\). Show that \(v\ge 2u+1\).
[Hint: Let \(x\) be a point not in \(Y\). Show that the triples containing
\(x\) and a point of \(Y\) are all distinct.]
 Prove directly that if an \(\mathrm{STS}(v)\) and an \(\mathrm{STS}(w)\)
exist, then an \(\mathrm{STS}(vw)\) exists.
Show further that, if \(v,w\ge 3\), then we can find an \(\mathrm{STS}(vw)\)
containing a subsystem of order 9.
 Let \(\mathbb Z_2\) denote the integers mod 2. Let \(X\) be the set of all
nonzero vectors in the \(n\)dimensional vector space
\((\mathbb Z_2)^n\). Let \(\mathcal B\) be the set of all triples
\(\{x,y,z\}\) of vectors of \(X\) satisfying \(x+y+z=0\).
(a) Prove that \(X,\mathcal B)\) is a Steiner triple system of order \(2^n1\).
(b) Identify the Fano plane as a Steiner triple system of this form.
 Let \(X=\{1,\ldots,n\}\) and suppose that \(\mathcal B\) is a collection
of 3element subsets of \(X\) with the property that any two members of \(\mathbb B\)
intersect in at most one element.
(a) Let \(r_x\) denote the number of members of \(\mathcal B\) containing
the element \(x\in \{1,\ldots,n\}\). Show that \(r_x\le\lfloor (n1)/2\rfloor\).
(b) By counting pairs \((x,B)\), with \(x\in X\) and \(B\in\mathcal B\), show that
\[\mathcal B = \frac{\sum_{x\in\{1,\ldots,n\}} r_x}{3}.\]
(c) Deduce that
\[\mathcal B \le \left\lfloor\frac{n}{3}\left\lfloor\frac{n1}{2}\right\rfloor
\right\rfloor.\]
(d) Hence or otherwise show that, if \(n=6\), then \(\mathcal B\le 4\).
(e) Find an example of four 3element subsets of \(\{1,\ldots,6\}\) which satisfy
the hypothesis \(B_i\cap B_j\le 1\) for \(B_i,B_j\in\mathcal B, i\ne j\).
Supplementary questions
 Show that the coefficient of \(x^n\) in \((x+x^2)^k\) is equal to \(nk\choose k\).
Hence show that the coefficient of \(x^n\) in \((1xx^2)^{1}\) is equal to
\(\sum\limits_{k=0}^{\lfloor n/2\rfloor}{nk\choose k}\). Deduce that
\(\sum\limits_{k=0}^{\lfloor n/2\rfloor}{nk\choose k}=F_n\).
 Prove that \(2^a+b\choose 2b+1\) is odd if and only if \(b=2^a1\).
 How many words can be made using some or all (possibly none) of the letters of the
word MAMMAL?
 (a) How many permutations of \(\{1,\ldots,9\}\) are there?
(b) How many of them consist of a single cycle?
(c) How many of them have exactly three cycles, none of which is of length 1?
 (a) In how many ways can 25 sweets be distributed to a class of 12 children?
(b) How many ways are there if each child is to have at least one sweet?
(c) How many ways are there if each child is to have at least two sweets?
 Let \(B(n)\) be the \(n\)th Bell number, the number of partitions of
\(\{1,\ldots,n\}\). Prove directly that \(B(n)\le n!\) for all \(n\).
 Let \(F_n\) be the \(n\)th Fibonacci number. Prove by induction that
\[{F_n}^2F_{n1}F_{n+1}=(1)^n\]
for all \(n\ge 1\).
 Let \(S(n,k)\) be the Stirling number of the second kind (the number of partitions
of \(\{1,\ldots,n\}\) into \(k\) parts), and let
\[F_k(x)=\sum_{n\ge k} S(n,k)x^n.\]
(a) Prove that \(F_1(x)=1/(1x)\).
(b) Write down a recurrence relation for \(S(n,k)\).
(c) Use it to show that
\[F_k(x)=\frac{x}{1kx}F_{k1}(x)\]
for \(k\ge 1\).
(d) Hence show by induction on \(k\) that
\[F_k(x)=\frac{x^k}{(1x)(12x)\cdots(1kx)}\]
for \(k\ge 1\).
 Show that a permutation is even if and only if it has an even number of cycles of
even length (with no restriction on cycles of odd length).
 Let \(A_1,\ldots,A_n\) be subsets of a set \(X\). For \(J\subseteq\{1,\ldots,n\}\), let
\[A_J=\bigcap_{i\in J} A_i\]
be the set of elements which lie in all the sets \(A_i\) for \(i\in J\) (and possibly in
some other sets as well). Let \(B_J\) be the set of elements which lie in the
sets \(A_i\) for \(i\in J\) and do not lie in the sets \(A_k\) for \(k\not\in J\).
Use the Principle of Inclusion and Exclusion to show that
\[B_J = \sum_{K\supseteq J}(1)^{K\setminus J} A_K.\]
 Let \(B\) be the matrix obtained from Pascal's Triangle by moving the rows right so that
the lefthand side is vertical. So the entry in row \(n\) and column \(k\) is \(n\choose k\).
Let \(B^*\) be the matrix in which the entry in row \(n\) and column \(k\) is \((1)^{nk}{n\choose k}\).
Prove that the matrices \(B\) and \(B^*\) are inverses of each other, by finding
two bases for the space of all polynomials, such that \(B\) and \(B^*\) are
the transition matrices. [Hint: the binomial theorem]
 (a) Show that there does not exist a Latin square orthogonal to the square
\[\begin{array}{ccccc}
\hline
1&2&3&4&5\cr\hline 2&1&4&5&3\cr\hline 3&4&5&1&2\cr\hline 4&5&2&3&1\cr\hline 5&3&1&2&4\cr\hline
\end{array}\]
[Hint: Suppose that \(B\) is orthogonal to the given square and has entry 1 in position (1,1).
Where can the other 1s in \(B\) occur?]
(b) Write down two orthogonal Latin squares of order 5.
 Let \(F=\mathbb Z_3\), the integers mod 3. Let \(V=F^n\) be the vector space of all
\(n\)tuples of \(F\). Let
\[\mathcal B = \{\{x,y,z\}: x,y,z\in V, \mbox{ and } x,y,z\mbox{ are distinct, and }x+y+z=0\}.\]
Show that \((V,\mathcal B)\) is a Steiner triple system of order \(3^n\).
 Let \(\mathcal F\) be an intersecting family of subsets of \(X=\{1,2,\ldots,n\}\).
(a) Show that \(\mathcal F\le 2^{n1}\).
(b) Show that, if \(\mathcal F=2^{n1}\), then for any subset \(A\) of \(X\), either
\(A\in\mathcal F\), or \(X\setminus A\in\mathcal F\).
(c) Show that, if \(\mathcal F=2^{n1}\), and \(A\in\mathcal F\), and \(B\) is a subset of \(X\)
containing \(A\), then \(B\in\mathcal F\).
 Let \(\mathcal F\) be an intersecting family of 2element subsets of \(\{1,\ldots,n\}\).
Show that either
(a) there is an element \(x\in\{1,\ldots,n\}\) contained in every set in \(\mathcal F\),
or
(b) \(\mathcal F = \{\{x,y\},\{y,z\},\{x,z\}\}\) for some \(x,y,z\in\{1,\ldots, n\}\).
 Let
\[\mathcal F = \{123,456,789,147,258,369,159,267,348\},\]
where, for example, \(123\) means \(\{1,2,3\}\).
(a) Prove directly that \(\mathcal F\) satisfies Hall's condition.
(b) Find a \(3\times 9\) Latin rectangle whose columns are the sets of \(\mathcal F\).
Revision Exercises for Reading Week
These questions are taken from past exam papers.
 Let \(X=\{1,2,3,4,5,6,7\}\).
(a) How many sequences of length four can be constructed using the elements of \(X\),
if repetitions are allowed?
(b) How many sequences of length four can be constructed using the elements of \(X\),
if repetitions are not allowed?
(c) How many of the sequences in (b) contain exactly two even numbers?
(d) How many of the sequences in (b) contain at least two even numbers?
 (a) Define the Stirling numbers of the second kind \(S(n,k)\).
(b) Determine \(S(3,k)\) for all \(0\le k\le 3\).
(c) Write down the recurrence relation for \(S(n,k)\) and use it to determine
\(S(4,3)\).
 Use the Principle of Inclusion and Exclusion to determine the number of sequences
\((x_1,x_2,x_3,x_4)\) of integers which satisfy \(0\le x_i\le 4\) for all \(1\le i\le 4\),
and \(x_1+x_2+x_3+x_4=13\).
 Let \((r_n)\) be a sequence of numbers defined by the recurrence relation
\(r_n=r_{n1}+2r_{n2}\) for \(n\ge 2\), and the initial conditions \(r_0=1,r_1=4\).
(a) Use the characteristic equation of the recurrence relation to determine \(r_n\)
for all \(n\ge 0\).
(b) Use the recurrence relation to show that the generating function for the
equence \((r_n)\) is \((1+5t)/(1t2t^2)\).
(c) Determine the numbers \((r_n)\) for all \(n\ge 0\) by expanding the
generating function using partial fractions.
 Making use of the formula
\[
{n\choose k} = \frac{n!}{k!\,(nk)!},\quad 0\leq k\leq n
\] show the following:
a) \(k {n\choose k} = n {n1\choose k1},\quad 1\leq k\leq n\);
b) \({n+1\choose k} = {n\choose k} + {n\choose k1},\quad 1\leq k\leq n+1\).
 State the (discrete) binomial theorem, and use it to give an alternative proof
of part (b) of the previous question.
 Describe a bijective proof of the formula in part (a) of that question.
 State the ChuVandermonde convolution formula, and prove it, making
use of the identity
\[(1+x)^{m+n}=(1+x)^m(1+x)^n.\]
 How many solutions \((x_1,x_2,x_3,x_4,x_5)\) does the equation
\[x_1+x_2+x_3+x_4+x_5=21\]
have in integers \(x_1,x_2,x_3,x_4,x_5\ge 2\)? Justify your answer.
You may use the fact that the equation
\[x_1+x_2+\cdots+x_k=n\]
has \(n+k1\choose k1\) nonnegative integral solutions \((x_1,\ldots,x_k)\).
R. A. Wilson
Created 3 September 2010
Updated 5 November 2010