A008951 - OEIS

%I #45 Sep 26 2021 01:52:52

%S 1,1,1,2,2,3,4,1,5,7,2,7,12,5,11,19,9,1,15,30,17,2,22,45,28,5,30,67,

%T 47,10,42,97,73,19,1,56,139,114,33,2,77,195,170,57,5,101,272,253,92,

%U 10,135,373,365,147,20,176,508,525,227,35,1,231,684,738,345,62,2,297

%N Array read by columns: number of partitions of n into parts of 2 kinds.

%C Fine-Riordan array S_n(m) = a(n,m) with extra row for n=0 added.

%C Row n of this triangle has length floor(1/2 + sqrt(2*(n+1))), n>=0. This is sequence {A002024(n+1)} = [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,...].

%C Written as a triangle this becomes A103923.

%C a(n,m) also gives the number of partitions of n-t(m), where t(m):=A000217(m) (triangular numbers), with two kinds of parts 1,2,..m. See the column o.g.f.'s in table A103923.

%C In general, column m is asymptotic to exp(Pi*sqrt(2*n/3)) * 6^(m/2) * n^((m-2)/2) / (4*sqrt(3) * m! * Pi^m), equivalently to 6^(m/2) * n^(m/2) / (m! * Pi^m) * p(n), where p(n) is the partition function A000041. - _Vaclav Kotesovec_, Aug 28 2015

%D H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 90.

%D J. Riordan, Combinatorial Identities, Wiley, 1968, p. 199.

%H Alois P. Heinz, <a href="/A008951/b008951.txt">Columns n = 0..500, flattened</a>

%H William K. Keith, <a href="http://arxiv.org/abs/1408.4089">Restricted k-color partitions</a>, arXiv preprint arXiv:1408.4089 [math.CO], 2014.

%H Wolfdieter Lang, <a href="/A103922/a103922.txt">First 20 rows and comments.</a>

%F Riordan gives formula.

%F a(n, m) is the sum over partitions of n of Product_{j=1..m} k(j), where k(j) is the number of parts of size j (exponent of j in a given partition of n), if m>=1. If m=0 then a(n, 0)=p(n):=A000041(n) (number of partitions of n). O is counted as a part for n=0 and only for this n.

%F a(n, m) is the sum over partitions of n of binomial(q(partition), m), with q the number of distinct parts of a given partition. m>=0.

%F a(n, m) = a(n-m, m-1) + a(n-m, m), n >= t(m):=m*(m+1)/2 = A000217(m) (triangular numbers), otherwise 0, with input a(n, 0) = p(n):=A000041(n).

%e Array begins:

%e m\n 0 1 2 3 4 .5 .6 .7 .8 ...

%e 0 | 1 1 2 3 5 .7 11 15 22 ... (A000041)

%e 1 | . 1 2 4 7 12 19 ... (A000070)

%e 2 | . . . 1 2 .5 .9 ... (A000097)

%e 3 | . . . . . .. .1 ... (A000098)

%e [1]; [1,1]; [2,2]; [3,4,1]; [5,7,2]; [7,12,5]; [11,19,9,1]...

%e a(3,1) = 4 because the partitions (3), (1,2) and (1^3) have q values 1,2 and 1 which sum to 4.

%e a(3,1) = 4 because the exponents of part 1 in the above given partitions of 3 are 0,1,3 and they sum to 4.

%e a(3,1) = 4 because the partitions of 3-t(1)=2 with two kinds of part 1, say 1 and 1' and one kind of part 2 are (2),(1^2), (1'^2) and (11').

%p a:= proc(n, m) option remember; `if`(n<0, 0,

%p       `if`(m=0, combinat[numbpart](n), a(n-m, m-1) +a(n-m, m)))

%p     end:

%p seq(seq(a(n,m), m=0..round(sqrt(2*n+2))-1), n=0..20);  # _Alois P. Heinz_, Nov 16 2012

%t a[n_, 0] := PartitionsP[n]; a[n_, m_] /; (n >= m*(m+1)/2) := a[n, m] = a[n-m, m-1] + a[n-m, m]; a[n_, m_] = 0; Flatten[ Table[ a[n, m], {n, 0, 18}, {m, 0, Floor[1/2 + Sqrt[2*(n+1)]] - 1}]](* _Jean-François Alcover_, May 02 2012, after recurrence formula *)

%t DeleteCases[Flatten@Transpose@Table[ConstantArray[0, m (m + 1)/2]~Join~Table[Length@IntegerPartitions[n, All, Range@n~Join~Range@m], {n, 0, 21 - m (m + 1)/2}] , {m, 0, 6}], 0](* _Robert Price_, Jul 28 2020 *)

%Y The first column (m=0) gives A000041(n). Columns m=1..10 are A000070 (partial sums of partition numbers), A000097, A000098, A000710, A103924-A103929.

%K nonn,tabf,nice

%O 0,4

%A _N. J. A. Sloane_

%E More terms from Robert G Bearden (nem636(AT)myrealbox.com), Apr 27 2004

%E Correction, comments and Riordan formulas from _Wolfdieter Lang_, Apr 28 2005