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

Author

Vladeta Jovovic, Aug 26 2004

Keywords

• easy
• nonn

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.

Crossrefs

Cf. A000296, A327885.

Programs

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

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

Extensions

More terms from Emeric Deutsch, Nov 18 2004