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,3

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)

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 *)

Crossrefs

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

Sequence in context: A272079 A212606 A192440 * A274964 A054357 A056606

Adjacent sequences: A327708 A327709 A327710 * A327712 A327713 A327714

Keyword

nonn

Author

Alois P. Heinz, Sep 22 2019

Status

approved