A162974 Triangle read by rows: T(n,k) is the number of derangements of {1,2,...,n} having k cycles of length 2 (0 <= k <= floor(n/2)).

1, 0, 0, 1, 2, 0, 6, 0, 3, 24, 20, 0, 160, 90, 0, 15, 1140, 504, 210, 0, 8988, 4480, 1260, 0, 105, 80864, 41040, 9072, 2520, 0, 809856, 404460, 100800, 18900, 0, 945, 8907480, 4447520, 1128600, 166320, 34650, 0, 106877320, 53450496, 13347180, 2217600

Offset: 0

Author

Emeric Deutsch, Jul 22 2009

Keywords

• nonn
• tabf

Comments

Row n has 1 + floor(n/2) entries.

Sum of entries in row n = A000166(n) (the derangement numbers).

T(n,0) = A038205(n).

Sum_{k>=0} k*T(n,k) = A000387(n).

Examples

			T(4,2)=3 because we have (12)(34), (13)(24), and (14)(23).
Triangle starts:
    1;
    0;
    0,  1;
    2,  0;
    6,  0,  3;
   24, 20,  0;
  160, 90,  0, 15;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened

Crossrefs

Cf. A000166, A000387, A038205, A114320.

T(2n,n) gives A001147.

T(2n+3,n) gives A000906(n) = 2*A000457(n).

Programs

Maple

G := exp((1/2)*z*(t*z-z-2))/(1-z): Gser := simplify(series(G, z = 0, 16)): for n from 0 to 13 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n from 0 to 13 do seq(coeff(P[n], t, j), j = 0 .. floor((1/2)*n)) end do;
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add((j-1)!*
      `if`(j=2, x, 1)*b(n-j)*binomial(n-1, j-1), j=2..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n/2))(b(n)):
seq(T(n), n=0..14);  # Alois P. Heinz, Jan 27 2022

Mathematica

b[n_] := b[n] = Expand[If[n == 0, 1, Sum[(j - 1)!*If[j == 2, x, 1]*b[n - j]*Binomial[n - 1, j - 1], {j, 2, n}]]];
T[n_] := With[{p = b[n]}, Table[Coefficient[p, x, i], {i, 0, n/2}]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Sep 17 2024, after Alois P. Heinz *)

Formula

E.g.f.: G(t,z) = exp(z(tz-z-2)/2)/(1-z).