MathDB

A2

Part of 1967 Putnam

Problems(1)

Putnam 1967 A2

Source: Putnam 1967

5/13/2022
Define S0S_0 to be 1.1. For n≥1n \geq 1 , let SnS_n be the number of n×nn\times n matrices whose elements are nonnegative integers with the property that aij=ajia_{ij}=a_{ji} (for i,j=1,2,…,ni,j=1,2,\ldots, n) and where ∑i=1naij=1\sum_{i=1}^{n} a_{ij}=1 (for j=1,2,…,nj=1,2,\ldots, n). Prove that a) Sn+1=Sn+nSn−1.S_{n+1}=S_{n} +nS_{n-1}. b) ∑n=0∞Snxnn!=exp⁡(x+x22).\sum_{n=0}^{\infty} S_{n} \frac{x^{n}}{n!} =\exp \left(x+\frac{x^{2}}{2}\right).
PutnamMatricespower seriesgenerating functions