A115728 Number of subpartitions of partitions in Abramowitz and Stegun order.

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

Offset: 0

Author

Franklin T. Adams-Watters, Mar 11 2006

Keywords

• nonn

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.

Row sums are A297388. Row lengths are A000041. - Geoffrey Critzer, Jan 10 2021

Examples

			Partition 5 in A&S order is [2,1]; it has 5 subpartitions: [], [1], [2], [1^2] and [2,1] itself.
1
2
3, 3
4, 5, 4
5, 7, 6, 7,  5
6, 9, 9, 10, 9, 9, 6
		

Links

• 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].

Crossrefs

Cf. A115729, A036036, A000108, A009766, A007318, A297388, A000041.

Programs

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^n-sum(k=0, n-1, s(k)*x^k*(1-x+x*O(x^n))^p(k)),n)} \\ Paul D. Hanna, Jul 03 2006

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 i-th 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/(1-x) = Sum_{n>=0} s(n)*x^n*(1-x)^p(n). - Paul D. Hanna, Jul 03 2006