Let un be the number of symmetric n x n matrices whose elements are all 0 or 1, with exactly one 1 in each row. Take u0 = 1. Prove un+1 = un + n un-1 and ∑0∞ un xn/n! = ef(x), where f(x) = x + (1/2) x2.
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 un+1 = un + n un-1. Also, we are given that u0 = 1 and it is clear that u1 = 1.
We have that ef(x) = 1 + (x + 1/2 x2) + (x + 1/2 x2)2/2! + ... which is clearly 1 + v1x/1! + v2x2/2! + ... for some vn. Differentiating, we get that (1 + x) (1 + v1x/1! + v2x2/2! + ...) = v1 + v2x/1!+ v3x2/2! + ... . Hence v1 = 1, v2 = v1 + 1, vn+1 = vn + n vn-1. A trivial induction now shows that vn = un.
© John Scholes
jscholes@kalva.demon.co.uk
14 Jan 2002