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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5000

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.

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