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

1, 1, 1, 3, 3, 9, 29, 57, 135, 615, 2635, 6273, 25151, 82623, 525281, 2941047, 9100709, 38766777, 205155713, 902705793, 7714938567, 52987356783, 204844103977, 1042657233471, 5520661314689, 38159472253821, 211945677298567, 2404720648663335, 19773733727088813

Offset: 0

Author

Alois P. Heinz, Sep 22 2019

Keywords

• nonn

Comments

Number of partitions of [n] with distinct block sizes such that each block contains exactly one block size as an element. a(5) = 9: 12345, 1235|4, 124|35, 125|34, 12|345, 134|25, 135|24, 13|245, 1|2345.

Links

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

Crossrefs

Cf. A026898, A326493, A327711, A364281.

Programs

Maple

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

Mathematica

a[m_] := a[m] = Module[{b}, b[n_, i_, j_] := b[n, i, j] = If[i(i + 1)/2 >= n, If[n == 0, (m - j)! j!, b[n, i - 1, j] + b[n - i, Min[n - i, i - 1], j + 1]/(i - 1)!], 0]; b[m, m, 0]];
a /@ Range[0, 28] (* Jean-François Alcover, May 10 2020, after 2nd Maple program *)