A327711 - OEIS

%I #18 Jul 10 2023 09:52:08

%S 1,1,2,3,6,10,27,55,171,475,1555,4915,20023,68243,288024,1213828,

%T 5435935,23966970,121432923,578757824,3130381590,16427772974,

%U 91877826663,519546134163,3199523135912,18868494152257,120274458082095,772954621249540,5219747666882153

%N 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).

%C 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.

%H Alois P. Heinz, <a href="/A327711/b327711.txt">Table of n, a(n) for n = 0..635</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients">Multinomial coefficients</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>

%p with(combinat):

%p a:= n-> add(multinomial(n-nops(p), map(

%p     x-> x-1, p)[], 0), p=partition(n)):

%p seq(a(n), n=0..28);

%p # second Maple program:

%p b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<2, 0,

%p       b(n, i-1, p)) +b(n-i, min(n-i, i), p-1)/(i-1)!)

%p     end:

%p a:= n-> b(n$3):

%p seq(a(n), n=0..28);

%t 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)!];

%t a[n_] := b[n, n, n];

%t a /@ Range[0, 28] (* _Jean-François Alcover_, May 01 2020, from 2nd Maple program *)

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

%K nonn

%O 0,3

%A _Alois P. Heinz_, Sep 22 2019