A generalization of partitions

[David Wilson]

Consider the sequence f_k formed by concatenating k copies of each positive integer, e.g:

f_3 = (1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 ...)

and let g_k be the sequence of partial sums of f_k:

g_3 = (1 2 3 5 7 9 12 15 18 22 26 30 35 40 45 ...)

Also, let s_k be the periodic sequence with repeating block (1^(k-1), 0, (-1)^(k-1), 0):

s_3 = (1 1 0 -1 -1 0 1 1 0 -1 -1 0 1 1 0 ...)

(f_k, g_k and s_k are indexed starting at 1).

The partition numbers p = (1 1 2 3 5 7 11 15 22 ...) = A000041 obey

p(0) = 1
p(n) = SUM(i with g_3(i) <= n; s_3(i) * p(n - g_3(i)) (n >= 1).

This generalizes to

p_k(0) = 1
p_k(n) = SUM(i with g_k(i) <= n; s_k(i) * p_k(n - g_k(i)) (n >= 1)

with the partition numbers being the special case p = p_3.

------------------------------------------------------------------------
Computing a few terms of p_k for small k gives

p_1 = (1 0 0 0 0 0 0 0 0 0 0 0 0 0 ...)
p_2 = (1 1 1 1 0 -1 -2 -3 -3 -1 2 6 10 11 ...)
p_3 = (1 1 2 3 5 7 11 15 22 30 42 56 77 101 ...)
p_4 = (1 1 2 4 7 13 23 42 75 135 242 434 779 1396 ...)
p_5 = (1 1 2 4 8 15 29 55 106 202 387 739 1414 2702 ...)
p_6 = (1 1 2 4 8 16 31 61 119 234 458 898 1759 3447 ...)
p_7 = (1 1 2 4 8 16 32 63 125 247 490 970 1922 3806 ...)
p_8 = (1 1 2 4 8 16 32 64 127 253 503 1002 1994 3970 ...)
p_9 = (1 1 2 4 8 16 32 64 128 255 509 1015 2026 4042 ...)
p_10 = (1 1 2 4 8 16 32 64 128 256 511 1021 2039 4074 ...)

p_1 = A000007 and p_3 = A000041 and the termwise limit p_inf = A011782 are easy. I was hoping for a combinatorial interpretation of other sequences, but alas, they are not in the OEIS or elsewhere.

------------------------------------------------------------------------
p_2 is interesting. It has the recurrence

p_2(0) = 1
p_2(n) = SUM(k with 1 <= k^2 <= n; (-1)^(k+1) * p_2(n-k^2)) (n >= 1)

or more prettily

p_2(0) = 1
p_2(n) = p_2(n-1) - p_2(n-4) + p_2(n-9) - p_2(n-16) + p_2(n-25) - ...

where terms with negative index are dropped in the latter sum.

p_2 is the only one of the p_n having negative elements. Here are more
terms of p_2, formatted to emphasize the regularity of the sign changes: 

p_2 = (
1 1 1 1 0
-1 -2 -3 -3 -1
2 6 10 11 8 0
-14 -29 -39 -38 -18
22 74 123 144 110 6
-161 -352 -491 -484 -251
235 896 1528 1825 1452 191
-1892 -4317 -6164 -6243 -3488
2482 10788 18957 23140 19085 3858
-22025 -52833 -77224 -80198 -47899
25330 129563 234774 292984 249938 66467
-254632 -645419 -966200 -1028145 -651774
244756 1550984 2903014 3703662 3262048 1057768
-2919617 -7868439 -12071433 -13154408 -8798790
2156064 18502260 35840006 46747073 42441704 16042331
-33149312 -95721387 -150601090 -167980582 -117979248
15610769 219874960 441758527 589147690 550604495 235523164
-371916746 -1161853462 -1876169578 -2141169812 -1572640509
52991977 2601849672 5435999338 7413974493 7123950308 3377603117
...)

------------------------------------------------------------------------
Let P_k be the g.f. for p_k.  I am fairly convinced that

P_k = SUM(j = 0 to inf; (-(x^k))^j * Q_j)

where the Q_j are the g.f.'s for sequences q_j with

q_0 = (1 1 2 4 8 16 32 64 128 256 512 ...) = A011782
q_1 = (1 3 9 22 54 126 290 654 1458 3214 7026 ...)
q_2 = (1 5 20 64 189 519 1367 3475 8611 20887 49807 ...)
...

I am not sure of the significance of these sequences. q_1 and q_2 are
not in the OEIS.  I have not looked at q_3 or beyond.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061020/3bd65ec0/attachment-0001.htm>