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

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

Author

Gus Wiseman, Nov 05 2017

Keywords

• nonn

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)

Examples

			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}}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..5000
• Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

Crossrefs

Cf. A000009, A000110, A063834, A258466, A259936, A279375, A279785, A279790.

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.

Cf. A188920, A238343, A274174, A373949, A374518, A376263.

Cf. A374631, A374632, A374634, A374635, A374686, A374688.

Programs

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 *)

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