A327711 Sum of multinomials M(n-k; p_1-1, ..., p_k-1), where p = (p_1, ..., p_k) ranges over all partitions of n (k is a partition length).

1, 1, 2, 3, 6, 10, 27, 55, 171, 475, 1555, 4915, 20023, 68243, 288024, 1213828, 5435935, 23966970, 121432923, 578757824, 3130381590, 16427772974, 91877826663, 519546134163, 3199523135912, 18868494152257, 120274458082095, 772954621249540, 5219747666882153

Offset: 0

Author

Alois P. Heinz, Sep 22 2019

Keywords

• nonn

Comments

Number of partitions of [n] whose block sizes are nondecreasing when blocks are ordered by their minima and these minima are {1..k} (for some k <= n). a(5) = 10: 12345, 13|245, 14|235, 15|234, 1|2345, 1|24|35, 1|25|34, 1|2|345, 1|2|3|45, 1|2|3|4|5.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..635
• Wikipedia, Multinomial coefficients
• Wikipedia, Partition (number theory)

Crossrefs

Cf. A005651, A179973, A326493, A327712, A327729.

Programs

Maple

with(combinat):
a:= n-> add(multinomial(n-nops(p), map(
    x-> x-1, p)[], 0), p=partition(n)):
seq(a(n), n=0..28);
# second Maple program:
b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<2, 0,
      b(n, i-1, p)) +b(n-i, min(n-i, i), p-1)/(i-1)!)
    end:
a:= n-> b(n$3):
seq(a(n), n=0..28);

Mathematica

b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i < 2, 0, b[n, i - 1, p]] + b[n - i, Min[n - i, i], p - 1]/(i - 1)!];
a[n_] := b[n, n, n];
a /@ Range[0, 28] (* Jean-François Alcover, May 01 2020, from 2nd Maple program *)