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

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

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

Crossrefs

Cf. A026898, A326493, A327711, A364281.

Sequence in context: A117976 A010098 A029857 * A257611 A268617 A264412

Adjacent sequences: A327709 A327710 A327711 * A327713 A327714 A327715

Keyword

nonn

Author

Alois P. Heinz, Sep 22 2019

Status

approved