MathDB
Putnam 1967 A2

Source: Putnam 1967

May 13, 2022
PutnamMatricespower seriesgenerating functions

Problem Statement

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).
Back to ProblemsView on AoPS