login
A097514
Number of partitions of an n-set without blocks of size 2.
20
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
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
Sequence in context: A368598 A346428 A148453 * A108630 A338735 A161408
KEYWORD
easy,nonn
AUTHOR
Vladeta Jovovic, Aug 26 2004
EXTENSIONS
More terms from Emeric Deutsch, Nov 18 2004
STATUS
approved