A309058 Partitions of n with parts having at most 3 distinct magnitudes.

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 41, 54, 72, 91, 115, 145, 177, 215, 258, 308, 364, 424, 491, 568, 651, 742, 838, 940, 1065, 1181, 1320, 1454, 1619, 1757, 1957, 2124, 2329, 2510, 2763, 2934, 3244, 3432, 3752, 3964, 4329, 4531, 4965, 5179, 5627, 5872, 6391, 6577, 7178, 7405

Offset: 0

Author

Nathan McNew, Jul 09 2019

Keywords

• nonn

Comments

Partitions whose Ferrers diagrams do not contain the pattern 4321 under removal of rows and columns (as defined by Bloom and Saracino).

Examples

			a(10) = 41 because all of the 42 integer partitions of 10 count (i.e., 10 = 10, 10 = 9+1 = 8+1+1, etc.), except the partition 10 = 4+3+2+1.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..5000
• J. Bloom and D. Saracino, Rook and Wilf equivalence of integer partitions, arXiv:1808.04238 [math.CO], 2018.
• J. Bloom and D. Saracino, Rook and Wilf equivalence of integer partitions, European J. Combin., 71 (2018), 246-267.

Crossrefs

Cf. A265250 (partitions of n with parts having at most 2 distinct magnitudes). Sum of A002134, A002133 and A000005.

Cf. A116608.

Programs

Maple

b:= proc(n, i, t) option remember; `if`(n=0, 1, `if`(i<1, 0,
      `if`(t=1, `if`(irem(n, i)=0, 1, 0)+b(n, i-1, t),
       add(b(n-i*j, i-1, t-`if`(j=0, 0, 1)), j=0..n/i))))
    end:
a:= n-> b(n$2, 3):
seq(a(n), n=0..100);  # Alois P. Heinz, Jul 11 2019

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, If[i < 1, 0, If[t == 1, If[Mod[n, i] == 0, 1, 0] + b[n, i - 1, t], Sum[b[n - i*j, i - 1, t - If[j == 0, 0, 1]], {j, 0, n/i}]]]];
a[n_] := b[n, n, 3];
a /@ Range[0, 100] (* Jean-François Alcover, Feb 27 2020, after Alois P. Heinz *)

Formula

G.f.: Sum_{i>=1} x^i/(1-x^i) + Sum_{j=1..i-1} x^(i+j)/((1-x^i)*(1-x^j)) + Sum_{k=1..j-1} x^(i+j+k)/((1-x^i)*(1-x^j)*(1-x^k)).

a(n) = Sum_{k=0..3} A116608(n,k). - Alois P. Heinz, Jul 11 2019