A347106 Number of derangements of [n] having an even number of 2-cycles.

1, 0, 0, 2, 9, 24, 160, 1350, 10353, 89936, 910656, 10070730, 120546745, 1566125352, 21934589664, 329037515534, 5264316535905, 89493067364640, 1610885172539008, 30606819613112466, 612136012448309481, 12854856587833586360, 282806860558105285920

Offset

0,4

Links

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

Wikipedia, Derangement.

Formula

E.g.f.: (exp(-x)+exp(-x*(x+1)))/(2-2*x).

a(n) = A000166(n) - A248087(n).

a(n) = Sum_{k=0..floor(n/4)} A162974(n,2*k).

a(n) mod 2 = A121262(n).

Example

a(3) = 2: (123), (132).
a(4) = 9: (12)(34), (13)(24), (14)(23), (1234), (1243), (1324), (1342), (1423), (1432).

Maple

b:= proc(n, t) option remember; `if`(n=0, t, add(b(n-j,
     `if`(j=2, 1-t, t))*binomial(n-1, j-1)*(j-1)!, j=2..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..27);

Crossrefs

Cf. A000166, A088336, A121262, A162974, A248087.

Sequence in context: A073981 A006973 A137852 * A097346 A343576 A261431

Adjacent sequences: A347103 A347104 A347105 * A347107 A347108 A347109

Keyword

nonn

Author

Alois P. Heinz, Jan 27 2022

Status

approved