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

1. Write 1001 as a binomial coefficient \(n\choose k\) with \(n\le20\).
2. If \(X\) is a set of 8 elements, then the number of 3-element subsets of \(X\) is twice the number of 2-element subsets. Is there any other number for which this holds?
3. Calculate \(\sum\limits_{k=0}^n k^2{n\choose k}\).
4. 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 \((n-k)\)-element subsets of \(X\). Deduce that \[{n\choose k}={n\choose n-k}.\]
5. 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(n-t)/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\).)

6. By calculating the coefficient of \(x^n\) on the two sides of the identity \[(1+x)^n.(1-x)^n=(1-x^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}\]
7. (a) Prove that \[{n\choose k+1} = \frac{n-k}{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}.\]
8. (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\).

9. 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.
10. Making use of the formula \[ {n\choose k} = \frac{n!}{k!\,(n-k)!},\quad 0\leq k\leq n \] established in the course, show the following.
    a) \({n\choose k} = {n\choose n-k},\quad 0\leq k\leq n\);
    b) \(k {n\choose k} = n {n-1\choose k-1},\quad 1\leq k\leq n\);
    c) \({n+1\choose k} = {n\choose k} + {n\choose k-1},\quad 1\leq k\leq n+1\).
11. Give alternative proofs for the formulae in the previous question, by showing that the left-hand and right-hand sides count the elements of one and the same set, respectively of equipotent sets.
12. Show that \({n\choose 0} = {n\choose n} =1\), and that \({n\choose k}=0\) for \(k>n\).
13. Prove that
    a) \({n\choose k-1} < {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\).
14. Show by induction on \(n\) that, for numbers \(a,b\) and every non-negative integer \(n\), we have \[ (a+b)^n = \sum_{i=0}^n {n\choose i} a^i\, b^{n-i}\quad\mbox{(general binomial theorem)}. \]
15. Show that, for \(0\leq k < n\), \[ {n\choose k} = \sum_{i=0}^k {n-i-1\choose k-i}. \]
16. 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 Chu-Vandermonde identity: \[ {m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k},\qquad m,n,r\in\mathbb{N}_0. \]

    Selections and arrangements

17. (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?
18. 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)?
19. 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. one-to-one?
    (c) How many of these functions are bijections, i.e. one-to-one and onto?
    (d) (Much harder) How many of these functions are surjections, i.e. onto?
20. 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\)?
21. For which values of \(n\) is \(W(n)\) odd?
22. 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 non-negative integers \(x_1,x_2,\ldots,x_n\).
23. 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 non-abelian for \(\vert S\vert \geq 3\).
24. 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.
25. 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_{n-1}\}, 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).
26. 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}. \]
27. Show that the sum \(\sum_{k=1}^{n-1} {n\choose k}^{-1}\) tends to zero as \(n\) tends to infinity.
28. 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\}\).
29. 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

30. 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 n-1\), 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)(n-k)!\) permutations with any given value of \(k\). Hence show that \[ \sum_{k=1}^n g(k)(n-k)! = 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)(1-G(x))=1.\] Note that this equation makes sense even though the power series do not converge for any non-zero value of \(x\).

31. Show from the multiplication rule that, in the calculus of formal power series, \[ (1-x)(1+x+x^2+x^3+\cdots) = 1. \]
32. 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). \]
33. 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.
    
34. 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. \]
35. 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_0-a_1x-\cdots-a_{h-1}x^{h-1}}{x^h}. \]
36. 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}. \]
37. Find a closed formula for the series \[ \sum\limits_{n\geq0} (n^2+4n+5)/n! \] making use of the previous exercise.
38. 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

39. 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}^{n-1}s(k)\] for \(n\ge 2\).
    (b) Deduce that \(s(1)=1\) and \(s(n)=2s(n-1)\) for \(n\ge 2\).
    (c) Hence show that \(s(n)=2^{n-1}\) for \(n\ge 1\).
    Notice how we have converted a rather complicated recurrence relation into a much simpler one!
40. Solve the recurrence relation and intial conditions \[a_0=2,a_1=4,a_2=7,\quad a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}\mbox{ for }n\ge 3.\]
41. 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?
42. Solve the recurrence relation and initial conditions \[a_0=1,\qquad a_1=1,\qquad a_n=3a_{n-1}-2a_{n-2}\mbox{ for }n\ge 2.\]
43. Solve the recurrence relation and initial conditions \[a_0=2,\qquad a_n=(a_{n-1})^2\mbox{ for }n\ge 1.\]
44. Let \[A=\begin{pmatrix}0&1\cr 1&1\end{pmatrix}.\] Prove by induction that \[A^{n+1}=\begin{pmatrix}F_{n-1}& F_n\cr F_n&F_{n+1}\end{pmatrix}\] for \(n\ge 1\), where \(F_n\) is the \(n\)th Fibonacci number.
45. (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(n-1)+(-1)^n\mbox{ for }n\ge 1.\]
    (b) Now put \(f(n)=d(n)/n!\). Show that \[f(0)=1,\qquad f(n)=f(n-1)+\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}}{1-x}.\] The series on the left is the exponential generating function of the derangement numbers.
46. 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_{i-1}A_{n-i}.\] [Hint: consider the matchings in which \(P_1\) is joined to \(Q_i\), and show that there are \(A_{i-1}A_{n-i}\) of these.]
    (c) Hence show by induction that \(A_n\) is the \((n+1)\)st Catalan number \(C_{n+1}\).

    Partitions and permutations

47. (a) Prove each of the following statements (i) by directly counting the partitions, (ii) by using the recurrence relation:
    • \(S(n,2)=2^{n-1}-1\);
    • \(S(n,n-1)={n\choose 2}\).
    (b) Find a formula for \(S(n,n-2)\).
48. (a) Prove (i) by directly counting the permutation, (ii) by using the recurrence relation, that \(s(n,n-1)=-{n\choose 2}\).
    (b) Find a formula for \(s(n,n-2)\).
49. 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.
50. Let \(k\) be given, and let \(p_k(n)\) be the probability that a randomly-chosen permutation of \(\{1,\ldots,n\}\) has exactly \(k\) fixed points. Show that \(p_k(n)={n\choose k}d(n-k)/n!\), where \(d(n-k)\) is the \((n-k)\)th derangement number, and hence show that
    (a) \(\sum\limits_{k=0}^n {n\choose k}d(n-k)=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\).]
51. 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_{n-1} - 7 a_{n-2} + 4 a_{n-3},\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}\).
52. 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)=1-5x+7x^2-4x^3\). Your asymptotic formula for \(a_n\) should be explicit in the quantities \(\gamma_1,\gamma_2,\gamma_3\).
53. Let \(f(n,k)\) denote the number of ways to write the non-negative integer \(n\) as an ordered sum of \(k\) non-negative integers. Find a closed formula for \(f(n,k)\).
    
54. Let \(n,k\in\mathbb{N}\) be given. Consider all ways of writing \(n\) as an ordered sum of \(k\) non-negative integers, and form the product of these \(k\) numbers. Let \(f(n,k)\) denote the sum of all these products. Determine \(f(n,k)\).
55. Show the following: if \(f \overset{gps}{\longleftrightarrow} \{a_n\}_0^\infty,\) then \[ \frac{f(x)}{1-x}\,\overset{gps}{\longleftrightarrow}\,\bigg\{\sum_{\nu=0}^n a_\nu\bigg\}_{n\geq0}. \]
56. 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

57. 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?
58. 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

59. Let \(n=2k\). Show that there are \(2^{2k-1 \choose k-1}\) intersecting families of \(k\)-element subsets of \(\{1,\ldots,n\}\) having the maximum number \(2k-1\choose k-1\) 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ös-Ko-Rado Theorem goes badly wrong when \(n=2k\).
60. Identify the right-hand 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.]
61. Construct a finite field with 8 elements.
62. Let \(X=\{1,\ldots,n\}\). Show that, for every non-empty subset \(A\) of \(X\), there is an intersecting family \(\mathcal F\) of subsets of \(X\) of size \(2^{n-1}\) 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?
63. 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?
64. 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.

65. 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_i-1) = b(b-1).\] [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

66. (a) Write down a SDR for the Fano plane.
    (b) How many different SDRs can you find?
67. 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.

68. 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?

69. 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)|\ge|J|-m\mbox{ for all }J\subseteq\{1,\ldots,n\},\] where \(A(J)=\bigcup\limits_{j\in J} A_j\). Then it is possible to find \(n-m\) 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

70. Let \(A\) and \(B\) be orthogonal Latin squares of order \(n\), which use the symbols \(0,1,\ldots,n-1\). Construct a matrix \(S\) in which the \((i,j)\)th entry consists of the pair \((a_{ij},b_{ij})\), regarded as a 2-digit number written in base \(n\). Show that \(S\) has the properties
    (a) its entries are all the integers from 0 to \(n^2-1\) inclusive;
    (b) the sum of the entries in any row or column is \(n(n^2-1)\).
    (This construction is due to Euler.)
71. 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).
72. 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.
73. 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\).
74. Let \(m\) be an integer greater than 1. Let \(X(m)\) be the multiplication table of the non-zero integers mod \(m\), that is, the \((m-1)\times(m-1)\) matrix defined as follows: rows and columns are indexed by \(1,2,\ldots, m-1\) 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

75. 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.]
76. 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.
77. Let \(\mathbb Z_2\) denote the integers mod 2. Let \(X\) be the set of all non-zero 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^n-1\).
    (b) Identify the Fano plane as a Steiner triple system of this form.
78. Let \(X=\{1,\ldots,n\}\) and suppose that \(\mathcal B\) is a collection of 3-element 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 (n-1)/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{n-1}{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 3-element 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

79. Show that the coefficient of \(x^n\) in \((x+x^2)^k\) is equal to \(n-k\choose k\). Hence show that the coefficient of \(x^n\) in \((1-x-x^2)^{-1}\) is equal to \(\sum\limits_{k=0}^{\lfloor n/2\rfloor}{n-k\choose k}\). Deduce that \(\sum\limits_{k=0}^{\lfloor n/2\rfloor}{n-k\choose k}=F_n\).
80. Prove that \(2^a+b\choose 2b+1\) is odd if and only if \(b=2^a-1\).
81. How many words can be made using some or all (possibly none) of the letters of the word MAMMAL?
82. (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?
83. (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?
84. 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\).
85. Let \(F_n\) be the \(n\)th Fibonacci number. Prove by induction that \[{F_n}^2-F_{n-1}F_{n+1}=(-1)^n\] for all \(n\ge 1\).
86. 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/(1-x)\).
    (b) Write down a recurrence relation for \(S(n,k)\).
    (c) Use it to show that \[F_k(x)=\frac{x}{1-kx}F_{k-1}(x)\] for \(k\ge 1\).
    (d) Hence show by induction on \(k\) that \[F_k(x)=\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}\] for \(k\ge 1\).
87. 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).
88. 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|.\]
89. Let \(B\) be the matrix obtained from Pascal's Triangle by moving the rows right so that the left-hand 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)^{n-k}{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]
90. (a) Show that there does not exist a Latin square orthogonal to the square \[\begin{array}{|c|c|c|c|c|} \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.
91. 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\).
92. Let \(\mathcal F\) be an intersecting family of subsets of \(X=\{1,2,\ldots,n\}\).
    (a) Show that \(|\mathcal F|\le 2^{n-1}\).
    (b) Show that, if \(|\mathcal F|=2^{n-1}\), 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^{n-1}\), and \(A\in\mathcal F\), and \(B\) is a subset of \(X\) containing \(A\), then \(B\in\mathcal F\).
93. Let \(\mathcal F\) be an intersecting family of 2-element 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\}\).
94. 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.
95. 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?
96. (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)\).
97. 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\).
98. Let \((r_n)\) be a sequence of numbers defined by the recurrence relation \(r_n=r_{n-1}+2r_{n-2}\) 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)/(1-t-2t^2)\).
    (c) Determine the numbers \((r_n)\) for all \(n\ge 0\) by expanding the generating function using partial fractions.
99. Making use of the formula \[ {n\choose k} = \frac{n!}{k!\,(n-k)!},\quad 0\leq k\leq n \] show the following:
    a) \(k {n\choose k} = n {n-1\choose k-1},\quad 1\leq k\leq n\);
    b) \({n+1\choose k} = {n\choose k} + {n\choose k-1},\quad 1\leq k\leq n+1\).
100. State the (discrete) binomial theorem, and use it to give an alternative proof of part (b) of the previous question.
101. Describe a bijective proof of the formula in part (a) of that question.
102. State the Chu-Vandermonde convolution formula, and prove it, making use of the identity \[(1+x)^{m+n}=(1+x)^m(1+x)^n.\]
103. 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+k-1\choose k-1\) non-negative integral solutions \((x_1,\ldots,x_k)\).

R. A. Wilson

Created 3 September 2010
Updated 5 November 2010