Let u_{n} be the number of symmetric n x n matrices whose elements are all 0 or 1, with exactly one 1 in each row. Take u_{0} = 1. Prove u_{n+1} = u_{n} + n u_{n-1} and ∑_{0}^{∞} u_{n} x^{n}/n! = e^{f(x)}, where f(x) = x + (1/2) x^{2}.

**Solution**

There is an obvious bijection between (1) n x n matrices satisfying the conditions and (2) (n+1) x (n+1) matrices satisfying the conditions which have 1 at the top left. [Just delete the first row and column to get from (2) to (1) ).

Similarly for any i = 2, 3, ... or n+1, there is an obvious bijection between (1) (n-1) x (n-1) matrices satisfying the conditions and (2) (n+1) x (n+1) matrices satisfying the conditions which have a 1 in row 1, col i (and hence also in row i, col 1). Just delete rows 1 and i and cols 1 and i to get from (2) to (1).

That establishes that u_{n+1} = u_{n} + n u_{n-1}. Also, we are given that u_{0} = 1 and it is clear that u_{1} = 1.

We have that e^{f(x)} = 1 + (x + 1/2 x^{2}) + (x + 1/2 x^{2})^{2}/2! + ... which is clearly 1 + v_{1}x/1! + v_{2}x^{2}/2! + ... for some v_{n}. Differentiating, we get that (1 + x) (1 + v_{1}x/1! + v_{2}x^{2}/2! + ...) = v_{1} + v_{2}x/1!+ v_{3}x^{2}/2! + ... . Hence v_{1} = 1, v_{2} = v_{1} + 1, v_{n+1} = v_{n} + n v_{n-1}. A trivial induction now shows that v_{n} = u_{n}.

© John Scholes

jscholes@kalva.demon.co.uk

14 Jan 2002