A336140 Number of ways to choose a set partition of the parts of a strict integer composition of n.

1, 1, 1, 5, 5, 9, 39, 43, 73, 107, 497, 531, 951, 1345, 2125, 8789, 9929, 16953, 24723, 38347, 52717, 219131, 240461, 419715, 600075, 938689, 1278409, 1928453, 6853853, 7815657, 13205247, 19051291, 29325121, 40353995, 60084905, 80722899, 277280079, 312239953

Offset

0,4

Comments

A strict composition of n is a finite sequence of distinct positive integers summing to n.

Links

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

Formula

a(n) = Sum_{k = 0..n} A000110(k) * A072574(n,k) = Sum_{k = 0..n} k! * A000110(k) * A008289(n,k).

Maple

b:= proc(n, i, p) option remember; `if`(i*(i+1)/2<n, 0,
      `if`(n=0, combinat[bell](p)*p!, b(n, i-1, p)+
         b(n-i, min(n-i, i-1), p+1)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 30 2020

Mathematica

Table[Sum[BellB[Length[ctn]], {ctn, Join@@Permutations/@Select[ IntegerPartitions[n], UnsameQ@@#&]}], {n, 0, 10}]
(* Second program: *)
b[n_, i_, p_] := b[n, i, p] = If[i(i+1)/2 < n, 0, If[n == 0,
     BellB[p]*p!, b[n, i-1, p] + b[n-i, Min[n-i, i-1], p+1]]];
a[n_] := b[n, n, 0];
a /@ Range[0, 40] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

Crossrefs

Set partitions are A000110.

Strict compositions are A032020.

Set partitions of binary indices are A050315.

Set partitions of strict partitions are A294617.

Cf. A000009, A001055, A008289, A035470, A063834, A072574, A137341, A279375.

Sequence in context: A321655 A336128 A049122 * A321660 A351292 A290240

Adjacent sequences: A336137 A336138 A336139 * A336141 A336142 A336143

Keyword

nonn

Author

Gus Wiseman, Jul 16 2020

Status

approved