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,4

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.

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

Example

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

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

Prog

(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
(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

Crossrefs

Cf. A000166, A177259, A177260.

Sequence in context: A129261 A371545 A370471 * A018997 A018954 A019030

Adjacent sequences: A177255 A177256 A177257 * A177259 A177260 A177261

Keyword

nonn

Author

Emeric Deutsch, May 08 2010

Status

approved