[seqfan] Re: Peculiar Integer Recurrences ... Proof?

[Maximilian Hasler]

On Sun, Feb 8, 2009 at 10:20 PM, Maximilian Hasler wrote:
>> If a(n,x) = (1/n) Sum_{k=1..n} x^(k^2) a(n-k), with a(0)=1,
>> then the polynomial a(n,x) takes integer values on the integers.
>
> These polynomials are the cycle index polynomials of the symmetric group S_n,
> denoted Z(S_n) in A102189, upon the substitution x[2] = x^2, x[3] = x^9 etc.

Sorry, I meant of course x[2] = x^4, in general: x[k] = x^(k^2).
See also http://en.wikipedia.org/wiki/Polya_theorem

Maximilian