A238875 Subdiagonal partitions: number of partitions (p1, p2, p3, ...) of n with pi <= i.

1, 1, 1, 2, 2, 4, 5, 7, 10, 15, 18, 26, 35, 47, 61, 80, 103, 138, 175, 224, 283, 362, 455, 577, 721, 898, 1111, 1380, 1701, 2106, 2577, 3156, 3844, 4680, 5671, 6879, 8312, 10034, 12060, 14478, 17319, 20715, 24703, 29442, 35004, 41578, 49247, 58278, 68796, 81132, 95502, 112320, 131877, 154705, 181158, 211908, 247475

Offset: 0

Author

Joerg Arndt, Mar 24 2014

Keywords

• nonn

Comments

The partitions are represented as weakly increasing lists of parts.

Partitions with subdiagonal growth (A238876) with first part = 1.

Examples

			The a(11) = 26 such partitions of 11 are:
  01:  [ 1 1 1 1 1 1 1 1 1 1 1 ]
  02:  [ 1 1 1 1 1 1 1 1 1 2 ]
  03:  [ 1 1 1 1 1 1 1 1 3 ]
  04:  [ 1 1 1 1 1 1 1 2 2 ]
  05:  [ 1 1 1 1 1 1 1 4 ]
  06:  [ 1 1 1 1 1 1 2 3 ]
  07:  [ 1 1 1 1 1 1 5 ]
  08:  [ 1 1 1 1 1 2 2 2 ]
  09:  [ 1 1 1 1 1 2 4 ]
  10:  [ 1 1 1 1 1 3 3 ]
  11:  [ 1 1 1 1 1 6 ]
  12:  [ 1 1 1 1 2 2 3 ]
  13:  [ 1 1 1 1 2 5 ]
  14:  [ 1 1 1 1 3 4 ]
  15:  [ 1 1 1 2 2 2 2 ]
  16:  [ 1 1 1 2 2 4 ]
  17:  [ 1 1 1 2 3 3 ]
  18:  [ 1 1 1 3 5 ]
  19:  [ 1 1 1 4 4 ]
  20:  [ 1 1 2 2 2 3 ]
  21:  [ 1 1 2 2 5 ]
  22:  [ 1 1 2 3 4 ]
  23:  [ 1 1 3 3 3 ]
  24:  [ 1 2 2 2 2 2 ]
  25:  [ 1 2 2 2 4 ]
  26:  [ 1 2 2 3 3 ]
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000
• M. Archibald, A. Blecher, S. Elizalde, and A. Knopfmacher, Subdiagonal and superdiagonal partitions, Afr. Mat. 36, 77 (2025). See p. 9.

Crossrefs

Cf. A008930 (subdiagonal compositions), A010054 (subdiagonal partitions into distinct parts).

Cf. A219282 (superdiagonal compositions), A238873 (superdiagonal partitions), A238394 (strictly superdiagonal partitions), A238874 (strictly superdiagonal compositions), A025147 (strictly superdiagonal partitions into distinct parts).

Cf. A238859 (compositions of n with subdiagonal growth), A238876 (partitions with subdiagonal growth), A001227 (partitions into distinct parts with subdiagonal growth).

Cf. A238860 (partitions with superdiagonal growth), A238861 (compositions with superdiagonal growth), A000009 (partitions into distinct parts have superdiagonal growth by definition).

Cf. A129176 and A227543.

Programs

PARI

\\ here b: nr parts; k: max part, b+w-1: partition sum.
seq(n)={my(M=matrix(n,1), v=vector(n+1)); M[1,1]=v[1]=v[2]=1; for(b=2, n, M=matrix(n-b+1,b,w,k, if(w>=k, sum(j=1, min(b-1,k), M[w+1-k,j]))); v+=concat(vector(b),vecsum(Vec(M))~)); v} \\ Andrew Howroyd, Jan 19 2024

PARI

N=55;
VP=vector(N+1);  VP[1] =VP[2] = 1;  \\ one-based; memoization
P(n) = VP[n+1];
for (n=2, N, VP[n+1] = sum( i=0, n-1, P(i) * P(n-1 -i) * x^((i+1)*(n-1-i)) ) );
x='x+O('x^N);
A(x) = sum(n=0, N, x^n * P(n) );
Vec(A(x)) \\ Joerg Arndt, Jan 23 2024

Formula

G.f.: Sum_{n>=0} x^n * P(n) where P(n) is the row polynomial of the n-th row of A129176. This works because A129176(j,k) is also the number of subdiagonal partitions of j+k with j parts. - John Tyler Rascoe, Jan 20 2024