login
A294617
Number of ways to choose a set partition of a strict integer partition of n.
21
1, 1, 1, 3, 3, 5, 10, 12, 17, 24, 44, 51, 76, 98, 138, 217, 272, 366, 493, 654, 848, 1284, 1560, 2115, 2718, 3610, 4550, 6024, 8230, 10296, 13354, 17144, 21926, 27903, 35556, 44644, 59959, 73456, 94109, 117735, 150078, 185800, 235719, 290818, 365334, 467923
OFFSET
0,4
COMMENTS
From Gus Wiseman, Sep 17 2024: (Start)
Also the number of strict integer compositions of n whose leaders, obtained by splitting into maximal increasing subsequences and taking the first term of each, are decreasing. For example, the strict composition (3,6,2,1,4) has maximal increasing subsequences ((3,6),(2),(1,4)), with leaders (3,2,1), so is counted under a(16). The a(0) = 1 through a(7) = 12 compositions are:
() (1) (2) (3) (4) (5) (6) (7)
(1,2) (1,3) (1,4) (1,5) (1,6)
(2,1) (3,1) (2,3) (2,4) (2,5)
(3,2) (4,2) (3,4)
(4,1) (5,1) (4,3)
(1,2,3) (5,2)
(2,1,3) (6,1)
(2,3,1) (1,2,4)
(3,1,2) (2,1,4)
(3,2,1) (2,4,1)
(4,1,2)
(4,2,1)
(End)
FORMULA
A279375(n) <= a(n) <= A279790(n).
G.f.: Sum_{k>=0} Bell(k) * x^(k*(k + 1)/2) / Product_{j=1..k} (1 - x^j). - Ilya Gutkovskiy, Jan 28 2020
EXAMPLE
The a(6) = 10 set partitions are: {{6}}, {{1},{5}}, {{5,1}}, {{2},{4}}, {{4,2}}, {{1},{2},{3}}, {{1},{3,2}}, {{2,1},{3}}, {{3,1},{2}}, {{3,2,1}}.
MAPLE
b:= proc(n, i, t) option remember; `if`(n>i*(i+1)/2, 0,
`if`(n=0, combinat[bell](t), b(n, i-1, t)+
`if`(i>n, 0, b(n-i, min(n-i, i-1), t+1))))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50); # Alois P. Heinz, Nov 07 2017
MATHEMATICA
Table[Total[BellB[Length[#]]&/@Select[IntegerPartitions[n], UnsameQ@@#&]], {n, 25}]
(* Second program: *)
b[n_, i_, t_] := b[n, i, t] = If[n > i (i + 1)/2, 0, If[n == 0, BellB[t], b[n, i - 1, t] + If[i > n, 0, b[n - i, Min[n - i, i - 1], t + 1]]]];
a[n_] := b[n, n, 0];
a /@ Range[0, 50] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)
CROSSREFS
Row sums of A330460 and of A330759.
This is a strict case of A374689, weak version A189076.
A011782 counts compositions, strict A032020.
A238130, A238279, A333755 count compositions by number of runs.
Sequence in context: A217521 A331925 A252943 * A320450 A100886 A326175
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 05 2017
STATUS
approved