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,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

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

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

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.

Sequence in context: A217521 A331925 A252943 * A320450 A100886 A326175

Adjacent sequences: A294614 A294615 A294616 * A294618 A294619 A294620

Keyword

nonn

Author

Gus Wiseman, Nov 05 2017

Status

approved