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

1, 1, 1, 2, 2, 5, 9, 21, 38, 146, 322, 902, 3106, 8406, 35865, 123321, 393691, 1442688, 7310744, 23471306, 129918661, 500183094, 2400722981, 9592382321, 47764284769, 280267554944, 1247781159201, 7620923955225, 36278364107926, 189688942325418, 1124492015730891

Offset

0,4

Comments

Number of partitions of [n] such that each block contains its size as an element. So the block sizes have to be distinct. a(6) = 9: 123456, 12|3456, 1345|26, 1346|25, 1456|23, 1|23456, 1|24|356, 1|25|346, 1|26|345.

Links

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

Wikipedia, Multinomial coefficients

Wikipedia, Partition (number theory)

Wikipedia, Partition of a set

Maple

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

Mathematica

b[n_, i_, p_] := b[n, i, p] = If[i(i+1)/2 < n, 0, If[n==0, p!, b[n, i-1, p] + b[n-i, Min[n-i, i-1], p-1]/(i-1)!]];
a[n_] := b[n, n, n];
a /@ Range[0, 31] (* Jean-François Alcover, Dec 09 2020, after Alois P. Heinz *)

Crossrefs

Cf. A000110, A007837, A327711, A327712, A362362, A363881, A364207, A364278.

Sequence in context: A052969 A002990 A060405 * A003228 A184713 A110182

Adjacent sequences: A326490 A326491 A326492 * A326494 A326495 A326496

Keyword

nonn

Author

Alois P. Heinz, Sep 22 2019

Status

approved