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

Links

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.

Formula

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!).

Maple

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

Mathematica

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

Crossrefs

Cf. A000296, A327885.

Sequence in context: A368598 A346428 A148453 * A108630 A338735 A161408

Adjacent sequences: A097511 A097512 A097513 * A097515 A097516 A097517

Keyword

easy,nonn

Author

Vladeta Jovovic, Aug 26 2004

Extensions

More terms from Emeric Deutsch, Nov 18 2004

Status

approved