A368675 Number of partitions of [n] whose block maxima sum to 2n.

1, 0, 0, 1, 2, 7, 15, 39, 81, 193, 396, 885, 1816, 3915, 7973, 16860, 34165, 71092, 143804, 295963, 596872, 1219950, 2455139, 4989265, 10028841, 20296288, 40745616, 82225558, 164916967, 332045545, 665566046, 1337794545, 2680049287, 5380396625, 10774301183

Offset

0,5

Links

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

Wikipedia, Partition of a set

Formula

a(n) = A367955(n,2n).

a(n) ~ c * 2^n, where c = 0.636808431228827742738441592748953932083264824206324529619378074873607293... - Vaclav Kotesovec, Jan 13 2024

Example

a(0) = 1: the empty partition.
a(3) = 1: 1|2|3.
a(4) = 2: 1|23|4, 1|24|3.
a(5) = 7: 12|3|45, 13|2|45, 1|234|5, 1|235|4, 145|2|3, 1|24|35, 1|25|34.
a(6) = 15: 12|34|56, 12|356|4, 134|2|56, 1356|2|4, 1|2345|6, 1|2346|5, 1|235|46, 1|236|45, 14|2|356, 1|245|36, 1|246|35, 156|2|34, 1|25|346, 1|26|345, 1|2|3|456.

Maple

b:= proc(n, m) option remember; `if`(n=0, 1,
      b(n-1, m)*m + expand(x^n*b(n-1, m+1)))
    end:
a:= n-> coeff(b(n, 0), x, 2*n):
seq(a(n), n=0..42);
# second Maple program:
b:= proc(n, i, t) option remember; `if`(i*(i+1)/2<n, 0,
      `if`(n=0, t^i, `if`(t=0, 0, t*b(n, i-1, t))+
       (t+1)^max(0, 2*i-n-1)*b(n-i, min(n-i, i-1), t+1)))
    end:
a:= n-> b(2*n, n, 0):
seq(a(n), n=0..42);

Crossrefs

Cf. A367955, A365441, A368678.

Sequence in context: A308631 A052130 A366130 * A065506 A330454 A121165

Adjacent sequences: A368672 A368673 A368674 * A368676 A368677 A368678

Keyword

nonn

Author

Alois P. Heinz, Jan 02 2024

Status

approved