A080528 Sum of multinomials of (-1 + number of runs) in the partitions of n.

1, 1, 2, 3, 5, 7, 12, 17, 28, 42, 68, 104, 171, 268, 442, 715, 1192, 1970, 3332, 5611, 9614, 16472, 28546, 49583, 86876, 152656, 269983, 479077, 854309, 1528314, 2745113, 4945015, 8937266, 16194872, 29426358, 53592060, 97828713, 178942169, 327956023, 602130762

Offset

0,3

Comments

Sum of multinomials of number of runs in the partitions of n equals 2^(n-1), so a(n) is less than 2^(n-1).

Links

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

Example

The partitions of 4: {4},{3,1},{2,2},{2,1,1},{1,1,1,1} have {1},{1,1},{2},{2,1},{4} runs of equal integers. The sum of the Multinomials of {0},{0,0},{1},{1,0},{3} equals 5.

Maple

b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
      b(n, i-1, p)+add(b(n-i*j, i-1, p+j-1)/(j-1)!, j=1..n/i)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..45);  # Alois P. Heinz, Jul 07 2014

Mathematica

multiplicity2[li:{__Integer}] := (Multinomial@@(-1+Length/@Split[ # ]))&[Sort@li]; Table[Plus@@multiplicity2/@IntegerPartitions[n], {n, 32}]
(* Second program: *)
b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i < 1, 0, b[n, i - 1, p] + Sum[b[n - i*j, i - 1, p + j - 1]/(j - 1)!, {j, 1, n/i}]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 45}] (* Jean-François Alcover, Aug 29 2016, after Alois P. Heinz *)

Crossrefs

Sequence in context: A305651 A318185 A048816 * A245152 A374634 A334271

Adjacent sequences: A080525 A080526 A080527 * A080529 A080530 A080531

Keyword

easy,nonn

Author

Wouter Meeussen, Mar 22 2003

Extensions

More terms from Alois P. Heinz, Jul 07 2014

Status

approved