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

Author

Gus Wiseman, Jul 16 2020

Keywords

• nonn

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

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.

Programs

Maple

b:= proc(n, i, p) option remember; `if`(i*(i+1)/2 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 *)

Formula

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