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

%I #21 May 21 2021 04:17:09

%S 1,1,1,5,5,9,39,43,73,107,497,531,951,1345,2125,8789,9929,16953,24723,

%T 38347,52717,219131,240461,419715,600075,938689,1278409,1928453,

%U 6853853,7815657,13205247,19051291,29325121,40353995,60084905,80722899,277280079,312239953

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

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

%H Alois P. Heinz, <a href="/A336140/b336140.txt">Table of n, a(n) for n = 0..5000</a>

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

%p b:= proc(n, i, p) option remember; `if`(i*(i+1)/2<n, 0,

%p `if`(n=0, combinat[bell](p)*p!, b(n, i-1, p)+

%p b(n-i, min(n-i, i-1), p+1)))

%p end:

%p a:= n-> b(n$2, 0):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Jul 30 2020

%t Table[Sum[BellB[Length[ctn]],{ctn,Join@@Permutations/@Select[ IntegerPartitions[n],UnsameQ@@#&]}],{n,0,10}]

%t (* Second program: *)

%t b[n_, i_, p_] := b[n, i, p] = If[i(i+1)/2 < n, 0, If[n == 0,

%t BellB[p]*p!, b[n, i-1, p] + b[n-i, Min[n-i, i-1], p+1]]];

%t a[n_] := b[n, n, 0];

%t a /@ Range[0, 40] (* _Jean-François Alcover_, May 21 2021, after _Alois P. Heinz_ *)

%Y Set partitions are A000110.

%Y Strict compositions are A032020.

%Y Set partitions of binary indices are A050315.

%Y Set partitions of strict partitions are A294617.

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

%K nonn

%O 0,4

%A _Gus Wiseman_, Jul 16 2020