# [seqfan] Number of ways to write n^2 as the sum of n odd numbers

Fri Sep 25 19:11:17 CEST 2009

```Greetings Sequence Fans,

Everybody knows that the nth square is equal to the sum of the first n
odd numbers.
It might be interesting to calculate the number of ways to write n^2
as the sum of n
odd numbers, disregarding order.

For example, 9 can be written as a sum of three odd numbers in 3 ways: 1+1+7,
1+3+5, and 3+3+3.

I wrote Maple program to compute the first few terms of this sequence. It does
not match any sequence in the OEIS. It would be interesting to know the
asymptotic behavior or a simpler formula for this sequence.

The first 20 terms are:
1, 1, 3, 9, 30, 110, 436, 1801, 7657, 33401, 148847, 674585, 3100410, 14422567,
67792847, 321546251, 1537241148, 7400926549, 35854579015, 174677578889.

My Maple code is listed below.

f := proc (n, k) option remember;
if n = 0 and k = 0 then return 1 end if;
if n <= 0 or n < k then return 0 end if;
if `mod`(n+k, 2) = 1 then return 0 end if;
if k = 1 then return 1 end if;
return f(n-1, k-1) + f(n-2*k, k)
end proc;

seq(f(k,k^2), k=1..20);

--