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)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..5000
FORMULA
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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 05 2017
STATUS
approved