

A115728


Number of subpartitions of partitions in Abramowitz and Stegun order.


26



1, 2, 3, 3, 4, 5, 4, 5, 7, 6, 7, 5, 6, 9, 9, 10, 9, 9, 6, 7, 11, 12, 13, 10, 14, 13, 10, 12, 11, 7, 8, 13, 15, 16, 14, 19, 17, 16, 16, 19, 16, 14, 15, 13, 8, 9, 15, 18, 19, 18, 24, 21, 15, 23, 22, 26, 21, 19, 22, 23, 24, 19, 15, 18, 18, 15, 9, 10, 17, 21, 22, 22, 29
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

subpart([n^k]) = C(n+k,k); subpart([1,2,3,...,n]) = C_n = A000108(n). The b(i,j) defined in the formula for sequences [1,2,3,...] form A009766.


LINKS

Table of n, a(n) for n=0..72.
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].


FORMULA

For a partition P = [p_1,...,p_n] with the p_i in increasing order, define b(i,j) to be the number of subpartitions of [p_1,...,p_i] with the ith part = j (b(i,0) is subpartitions with less than i parts). Then b(1,j)=1 for j<=p_1, b(i+1,j) = Sum_{k=0}^j} b(i,k) for 0<=j<=p_{i+1}; and the total number of subpartitions is sum_{k=1}^{p_n} b(n,k).
For a partition P = {p(n)}, the number of subpartitions {s(n)} of P can be determined by the g.f.: 1/(1x) = Sum_{n>=0} s(n)*x^n*(1x)^p(n).  Paul D. Hanna, Jul 03 2006


EXAMPLE

Partition 5 in A&S order is [2,1]; it has 5 subpartitions:
[], [1], [2], [1^2] and [2,1] itself.


PROG

(PARI) /* Expects input as vector in increasing order  e.g. [1, 1, 2, 3] */ subpart(p)=local(i, j, v, n); n=matsize(p)[2]; if(n==0, 1, v=vector(p[n]+1); v[1] =1; for(i=1, n, for(j=1, p[i], v[j+1]+=v[j])); for(j=1, p[n], v[j+1]+=v[j]); v[p[n ]+1])
(PARI) /* Given Partition p(), Find Subpartitions s(): */ {s(n)=polcoeff(x^nsum(k=0, n1, s(k)*x^k*(1x+x*O(x^n))^p(k)), n)}  Paul D. Hanna, Jul 03 2006


CROSSREFS

Cf. A115729, A036036, A000108, A009766, A007318.
Sequence in context: A305579 A321440 A115729 * A188553 A026354 A179840
Adjacent sequences: A115725 A115726 A115727 * A115729 A115730 A115731


KEYWORD

nonn


AUTHOR

Franklin T. AdamsWatters, Mar 11 2006


STATUS

approved



