A297388 Number of pairs (p,q) of partitions such that q is a partition of n and p <= q (diagram containment).

1, 2, 6, 13, 30, 58, 120, 219, 413, 730, 1296, 2201, 3766, 6206, 10241, 16500, 26502, 41748, 65600, 101417, 156264, 237741, 360146, 539838, 806030, 1192365, 1756766, 2568418, 3739724, 5408247, 7791474, 11156601, 15916288, 22585112, 31933166, 44932450, 63010688

Offset

0,2

Comments

For fixed q, the number of p is given by a determinant due to MacMahon (the case mu=empty set and n=1 of Exercise 3.149 of the reference below).

References

R. Stanley, Enumerative Combinatorics, vol. 1, second ed., Cambridge Univ. Press, 2012.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

a(n) = A000041(n) + Sum_{k=1..n} A259478(n,k). - Alois P. Heinz, Jan 10 2018

Example

For n = 2 the six pairs are (empty set,2), (1,2), (2,2), (empty set,11), (1,11), (11,11).

Maple

b:= proc(n, i, t) option remember; `if`(n=0 or i=1, 1+
      `if`(t=0, 0, n), b(n, i-1, min(i-1, t))+ add(
       b(n-i, min(i, n-i), min(j, n-i)), j=0..t))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..40);  # Alois P. Heinz, Dec 29 2017

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n == 0 || i == 1, 1 + If[t == 0, 0, n], b[n, i - 1, Min[i - 1, t]] + Sum[b[n - i, Min[i, n - i], Min[j, n - i]], {j, 0, t}]];
a[n_] := b[n, n, n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Apr 30 2018, after Alois P. Heinz *)

Crossrefs

Cf. A000041, A259478, A305023.

Sequence in context: A075632 A288979 A289048 * A115217 A094687 A369584

Adjacent sequences: A297385 A297386 A297387 * A297389 A297390 A297391

Keyword

nonn,easy

Author

Richard Stanley, Dec 29 2017

Status

approved