cp's OEIS Frontend

A294617 Number of ways to choose a set partition of a strict integer partition of n.

%I A294617 #27 Sep 19 2024 08:23:05
%S A294617 1,1,1,3,3,5,10,12,17,24,44,51,76,98,138,217,272,366,493,654,848,1284,
%T A294617 1560,2115,2718,3610,4550,6024,8230,10296,13354,17144,21926,27903,
%U A294617 35556,44644,59959,73456,94109,117735,150078,185800,235719,290818,365334,467923
%N A294617 Number of ways to choose a set partition of a strict integer partition of n.
%C A294617 From _Gus Wiseman_, Sep 17 2024: (Start)
%C A294617 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:
%C A294617   ()  (1)  (2)  (3)    (4)    (5)    (6)      (7)
%C A294617                 (1,2)  (1,3)  (1,4)  (1,5)    (1,6)
%C A294617                 (2,1)  (3,1)  (2,3)  (2,4)    (2,5)
%C A294617                               (3,2)  (4,2)    (3,4)
%C A294617                               (4,1)  (5,1)    (4,3)
%C A294617                                      (1,2,3)  (5,2)
%C A294617                                      (2,1,3)  (6,1)
%C A294617                                      (2,3,1)  (1,2,4)
%C A294617                                      (3,1,2)  (2,1,4)
%C A294617                                      (3,2,1)  (2,4,1)
%C A294617                                               (4,1,2)
%C A294617                                               (4,2,1)
%C A294617 (End)
%H A294617 Alois P. Heinz, <a href="/A294617/b294617.txt">Table of n, a(n) for n = 0..5000</a>
%H A294617 Gus Wiseman, <a href="/A374629/a374629.txt">Sequences counting and ranking compositions by their leaders (for six types of runs)</a>.
%F A294617 A279375(n) <= a(n) <= A279790(n).
%F A294617 G.f.: Sum_{k>=0} Bell(k) * x^(k*(k + 1)/2) / Product_{j=1..k} (1 - x^j). - _Ilya Gutkovskiy_, Jan 28 2020
%e A294617 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}}.
%p A294617 b:= proc(n, i, t) option remember; `if`(n>i*(i+1)/2, 0,
%p A294617       `if`(n=0, combinat[bell](t), b(n, i-1, t)+
%p A294617       `if`(i>n, 0, b(n-i, min(n-i, i-1), t+1))))
%p A294617     end:
%p A294617 a:= n-> b(n$2, 0):
%p A294617 seq(a(n), n=0..50);  # _Alois P. Heinz_, Nov 07 2017
%t A294617 Table[Total[BellB[Length[#]]&/@Select[IntegerPartitions[n],UnsameQ@@#&]],{n,25}]
%t A294617 (* Second program: *)
%t A294617 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]]]];
%t A294617 a[n_] := b[n, n, 0];
%t A294617 a /@ Range[0, 50] (* _Jean-François Alcover_, May 10 2021, after _Alois P. Heinz_ *)
%Y A294617 Cf. A000009, A000110, A063834, A258466, A259936, A279375, A279785, A279790.
%Y A294617 Row sums of A330460 and of A330759.
%Y A294617 This is a strict case of A374689, weak version A189076.
%Y A294617 A011782 counts compositions, strict A032020.
%Y A294617 A238130, A238279, A333755 count compositions by number of runs.
%Y A294617 Cf. A188920, A238343, A274174, A373949, A374518, A376263.
%Y A294617 Cf. A374631, A374632, A374634, A374635, A374686, A374688.
%K A294617 nonn
%O A294617 0,4
%A A294617 _Gus Wiseman_, Nov 05 2017