A177258 Number of derangements of {1,2,...,n} having no adjacent transpositions.

1, 0, 0, 2, 7, 36, 225, 1610, 13104, 119548, 1208583, 13413960, 162176105, 2121703324, 29866022640, 450112042926, 7231658709455, 123388310103660, 2228221240575337, 42459591881035062, 851420058861276576, 17922280827967843160, 395141598274153826095

Offset: 0

Author

Emeric Deutsch, May 08 2010

Keywords

• nonn

Examples

			a(4)=7 because we have (1342), (13)(24), (1324), (1432), (1423), (1234), and (1243).
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..445
• R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Crossrefs

Cf. A000166, A177259, A177260.

Programs

Magma

F:=Factorial;
A177258:= func< n | (&+[(&+[(-1)^(j+k)*F(n-k)/(F(j)*F(k)): k in [0..Floor((n-j)/2)]]): j in [0..n]]) >;
[A177258(n): n in [0..40]]; // G. C. Greubel, May 13 2024

Maple

p := 1: q := 2: a := proc (n) local ct, t, s; ct := 0: for s from 0 to n/p do for t from 0 to n/q do if p*s+q*t <= n then ct := ct+(-1)^(s+t)*factorial(n-(p-1)*s-(q-1)*t)/(factorial(s)*factorial(t)) else end if end do end do: ct end proc; seq(a(n), n = 0 .. 22);

Mathematica

p = 1; q = 2; a[n_] := Module[{ct, t, s}, ct = 0; For[s = 0, s <= n/p, s++, For[t = 0, t <= n/q, t++, If[p*s + q*t <= n, ct = ct + (-1)^(s+t) * Factorial[n - (p-1)*s - (q-1)*t]/(Factorial[s]*Factorial[t])]]]; ct];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 24 2017, translated from Maple *)

SageMath

f=factorial;
def A177258(n): return sum(sum((-1)^(j+k)*f(n-k)/(f(j)*f(k)) for k in range(1+(n-j)//2)) for j in range(n+1))
[A177258(n) for n in range(41)] # G. C. Greubel, May 13 2024

Formula

a(n) = Sum_{s=0..n} Sum_{t=0..floor((n-s)/2)} (-1)^(s+t)*(n-t)!/(s!*t!).

G.f.: 1/Q(0), where Q(k)=1 + x*(1+x) - x*(k+1)/(1-x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 19 2013

a(n) ~ exp(-1) * n!. - Vaclav Kotesovec, Dec 10 2021

Conjecture D-finite with recurrence a(n) = (n-1)*a(n-1) + (n-1)*a(n-2) + (n-1)*a(n-3) + a(n-4). - R. J. Mathar, Jul 26 2022

G.f.: Sum_{k>=0} k! * x^k * ( (1-x)/(1-x^3) )^(k+1). - Seiichi Manyama, Feb 20 2024