Voozh

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

(list; graph; refs; listen; history; text; internal format)

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

# Alternative:

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