A327885 -id:A327885 - cp's OEIS frontend

A097514 Number of partitions of an n-set without blocks of size 2.

1, 1, 1, 2, 6, 17, 53, 205, 871, 3876, 18820, 99585, 558847, 3313117, 20825145, 138046940, 959298572, 6974868139, 52972352923, 419104459913, 3446343893607, 29405917751526, 259930518212766, 2376498296500063, 22441988298860757, 218615700758838253

Offset: 0

Vladeta Jovovic, Aug 26 2004

Alois P. Heinz, Table of n, a(n) for n = 0..500
Toufik Mansour and Mark Shattuck, Counting subword patterns in permutations arising as flattened partitions of sets, Appl. Anal. Disc. Math. (2022), OnLine-First (00):9-9.

Cf. A000296, A327885.

g:=exp(exp(x)-1-x^2/2): gser:=series(g,x=0,31): 1,seq(n!*coeff(gser,x^n),n=1..29); # Emeric Deutsch, Nov 18 2004
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(`if`(
       j=2, 0, a(n-j)*binomial(n-1, j-1)), j=1..n))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 18 2015

a[n_] := a[n] = If[n == 0, 1, Sum[If[j == 2, 0, a[n-j]*Binomial[n-1, j-1]], {j, 1, n}]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 13 2015, after Alois P. Heinz *)

a(n) = Sum_{k=0..floor(n/2)} (-1)^k*binomial(n, 2*k)*(2*k-1)!!*Bell(n-2*k).

E.g.f.: exp(exp(x)-1-x^2/2). More generally, e.g.f. for number of partitions of an n-set which contain exactly q blocks of size p is x^(p*q)/(q!*p!^q)*exp(exp(x)-1-x^p/p!).

More terms from Emeric Deutsch, Nov 18 2004

A327884 Number T(n,k) of set partitions of [n] such that at least one of the block sizes is k or k=0; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 5, 4, 3, 1, 15, 11, 9, 4, 1, 52, 41, 35, 20, 5, 1, 203, 162, 150, 90, 30, 6, 1, 877, 715, 672, 455, 175, 42, 7, 1, 4140, 3425, 3269, 2352, 1015, 280, 56, 8, 1, 21147, 17722, 17271, 13132, 6237, 1890, 420, 72, 9, 1, 115975, 98253, 97155, 76540, 39480, 12978, 3150, 600, 90, 10, 1

Offset: 0

Alois P. Heinz, Sep 28 2019

			T(4,1) = 11: 123|4, 124|3, 12|3|4, 134|2, 13|2|4, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4.
T(4,2) = 9: 12|34, 12|3|4, 13|24, 13|2|4, 14|23, 1|23|4, 14|2|3, 1|24|3, 1|2|34.
T(4,3) = 4: 123|4, 124|3, 134|2, 1|234.
T(4,4) = 1: 1234.
T(5,1) = 41: 1234|5, 1235|4, 123|4|5, 1245|3, 124|3|5, 12|34|5, 125|3|4, 12|35|4, 12|3|45, 12|3|4|5, 1345|2, 134|2|5, 13|24|5, 135|2|4, 13|25|4, 13|2|45, 13|2|4|5, 14|23|5, 1|2345, 1|234|5, 15|23|4, 1|235|4, 1|23|45, 1|23|4|5, 145|2|3, 14|25|3, 14|2|35, 14|2|3|5, 15|24|3, 1|245|3, 1|24|35, 1|24|3|5, 15|2|34, 1|25|34, 1|2|345, 1|2|34|5, 15|2|3|4, 1|25|3|4, 1|2|35|4, 1|2|3|45, 1|2|3|4|5.
Triangle T(n,k) begins:
      1;
      1,     1;
      2,     1,     1;
      5,     4,     3,     1;
     15,    11,     9,     4,    1;
     52,    41,    35,    20,    5,    1;
    203,   162,   150,    90,   30,    6,   1;
    877,   715,   672,   455,  175,   42,   7,  1;
   4140,  3425,  3269,  2352, 1015,  280,  56,  8, 1;
  21147, 17722, 17271, 13132, 6237, 1890, 420, 72, 9, 1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Iverson bracket
Wikipedia, Partition of a set

Columns k=0-3 give: A000110, A000296(n+1), A327885, A328153.
T(2n,n) gives A276961.
Cf. A080510, A327869.

b:= proc(n, k) option remember; `if`(n=0, 1, add(
      `if`(j=k, 0, b(n-j, k)*binomial(n-1, j-1)), j=1..n))
    end:
T:= (n, k)-> b(n, 0)-`if`(k=0, 0, b(n, k)):
seq(seq(T(n, k), k=0..n), n=0..11);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[If[j == k, 0, b[n - j,k] Binomial[ n - 1, j - 1]], {j, 1, n}]];
T[n_, k_] := b[n, 0] - If[k == 0, 0, b[n, k]];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 30 2020, after Alois P. Heinz *)

E.g.f. of column k: exp(exp(x)-1) - [k>0] * exp(exp(x)-1-x^k/k!).

T(n,0) - T(n,1) = A000296(n).

cp's OEIS Frontend

A097514 Number of partitions of an n-set without blocks of size 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions