cp's OEIS Frontend

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

%I A177258 #31 May 14 2024 06:13:36
%S A177258 1,0,0,2,7,36,225,1610,13104,119548,1208583,13413960,162176105,
%T A177258 2121703324,29866022640,450112042926,7231658709455,123388310103660,
%U A177258 2228221240575337,42459591881035062,851420058861276576,17922280827967843160,395141598274153826095
%N A177258 Number of derangements of {1,2,...,n} having no adjacent transpositions.
%H A177258 G. C. Greubel, <a href="/A177258/b177258.txt">Table of n, a(n) for n = 0..445</a>
%H A177258 R. A. Brualdi and Emeric Deutsch, <a href="http://arxiv.org/abs/1005.0781">Adjacent q-cycles in permutations</a>, arXiv:1005.0781 [math.CO], 2010.
%F A177258 a(n) = Sum_{s=0..n} Sum_{t=0..floor((n-s)/2)} (-1)^(s+t)*(n-t)!/(s!*t!).
%F A177258 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
%F A177258 a(n) ~ exp(-1) * n!. - _Vaclav Kotesovec_, Dec 10 2021
%F A177258 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
%F A177258 G.f.: Sum_{k>=0} k! * x^k * ( (1-x)/(1-x^3) )^(k+1). - _Seiichi Manyama_, Feb 20 2024
%e A177258 a(4)=7 because we have (1342), (13)(24), (1324), (1432), (1423), (1234), and (1243).
%p A177258 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);
%t A177258 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];
%t A177258 Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Nov 24 2017, translated from Maple *)
%o A177258 (Magma)
%o A177258 F:=Factorial;
%o A177258 A177258:= func< n | (&+[(&+[(-1)^(j+k)*F(n-k)/(F(j)*F(k)): k in [0..Floor((n-j)/2)]]): j in [0..n]]) >;
%o A177258 [A177258(n): n in [0..40]]; // _G. C. Greubel_, May 13 2024
%o A177258 (SageMath)
%o A177258 f=factorial;
%o A177258 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))
%o A177258 [A177258(n) for n in range(41)] # _G. C. Greubel_, May 13 2024
%Y A177258 Cf. A000166, A177259, A177260.
%K A177258 nonn
%O A177258 0,4
%A A177258 _Emeric Deutsch_, May 08 2010