A055790 a(n) = n*a(n-1) + (n-2)*a(n-2), a(0) = 0, a(1) = 2.

0, 2, 4, 14, 64, 362, 2428, 18806, 165016, 1616786, 17487988, 206918942, 2657907184, 36828901754, 547499510764, 8691268384262, 146725287298888, 2624698909845026, 49592184973992676, 986871395973226286, 20630087248996393888, 451982388752415571082

Offset: 0

Author

Henry Bottomley, Jul 13 2000

Keywords

• nonn

Comments

With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=1 and n-1 zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al. Extremes of permanents of (0,1)-matrices, p. 201-202. - Jaap Spies, Dec 12 2003

With a(0) = 1, number of degree-(n+1) permutations p such that p(i) != i+2 for each i=1,2,...,n+1. - Vladeta Jovovic, Jan 03 2003

Equivalently number of degree-(n+1) permutations p such that p(i) != i-2 for each i=1,2,...,n+1.

With a(0) = 1, number of degree-(n+1) permutations without fixed points between 2 and n. - Olivier Gérard, Jul 29 2016

Also column 3 of Euler's difference table (third diagonal in example of A068106). - Enrique Navarrete, Oct 31 2016

For n>=2, the number of circular permutations (in cycle notation) on [n+2] that avoid substrings (j,j+3), 1<=j<=n-1. For example, for n=2, the 4 circular permutations in S4 that avoid the substring {14} are (1234),(1243),(1324),(1342). Note that each of these circular permutations represent 4 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 15 2017

Examples

			G.f. = 2*x + 4*x^2 + 14*x^3 + 64*x^4 + 362*x^5 + 2428*x^6 + ...
a(3) = 3*a(2)+(3-2)*a(1) = 12+2 = 14.
for n=1, the 2 permutations of [2] matches:
12, 21
for n=2, the 4 permutations of [3] without 2 as a fixed point are
132, 213, 231, 312.
for n=3, the 14 permutations of [4] without fixed point at 2 or 3 are
1324 1342 1423    2143 2314 2341 2413
3124 3142 3412 3421    4123 4312 4321
		

References

• Brualdi, Richard A. and Ryser, Herbert J., Combinatorial Matrix Theory, Cambridge NY (1991), Chapter 7.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..250
• T. Mansour and M. Shattuck, Counting permutations by the number of successors within cycles, Discr. Math., 339 (2016), 1368-1376.
• Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations, arXiv:1610.06217 [math.CO], 2016.
• Enrique Navarrete, Forbidden Substrings in Circular K-Successions, arXiv:1702.02637 [math.CO], 2017.
• Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002). Linear Algebra Appl. 373 (2003), pp. 197-210.

Crossrefs

Cf. A000166 (Derangements, permutations without fixed points ).

Cf. A000255 (permutations with p(i)!=i+1, same type of recurrence).

Cf. A000153, A000261, A001909, A001910, A090010, A090012-A090016.

Apart from first term, appears in triangles A047920 or A068106 of differences of factorials, i.e. as third term of A000142, A001563, A001564, A001565 etc.

Programs

Haskell

a055790 n = a055790_list !! n
a055790_list = 0 : 2 : zipWith (+)
   (zipWith (*) [0..] a055790_list) (zipWith (*) [2..] $ tail a055790_list)
-- Reinhard Zumkeller, Mar 05 2012

Maple

f := proc(n) option remember; if n <= 1 then 2*n else n*f(n-1)+(n-2)*f(n-2); fi; end;

Mathematica

a[0] = 0; a[1] = 2; a[n_] := a[n] = a[n] = n*a[n - 1] + (n - 2)*a[n - 2];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Nov 14 2017 *)
RecurrenceTable[{a[0]==0,a[1]==2,a[n]==n*a[n-1]+(n-2)a[n-2]},a,{n,30}] (* Harvey P. Dale, May 07 2018 *)

PARI

a(n) = if(n==0, 0, round((n+3+1/n)*n!/exp(1))) \\ Felix Fröhlich, Jul 29 2016

Formula

For n > 0, a(n) = round[(n+3+1/n)*n!/e] = 2*A000153(n) = A000255(n-1)+A000255(n) = A000166(n-1)+2*A000166(n)+A000166(n+1).

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

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

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

G.f.: W(0) -1, where W(k) = 1 - x*(k+2)/( x*(k+1) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 26 2013

a(n) ~ sqrt(Pi/2)*n^n*sqrt(n)*(12*n + 37)/(6*exp(n+1)). - Ilya Gutkovskiy, Jul 29 2016

0 = a(n)*(+a(n+1) + 3*a(n+2) - a(n+3)) + a(n+1)*(-a(n+1) + 2*a(n+2) - a(n+3)) + a(n+2)*(+a(n+2)) for n>=0. - Michael Somos, Nov 01 2016

Extensions

Comments corrected, new interpretation and examples by Olivier Gérard, Jul 29 2016