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

Table of n, a(n) for n=0..22.

R. A. Brualdi and E. Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Formula

a(n) = Sum((-1)^{s+t}*(n-t)!/s!/t!,s>=0,t>=0,s+2t<=n).

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)=0. - 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 *)

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