0,2

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

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..250

Toufik Mansour and Mark Shattuck, Counting permutations by the number of successions 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.

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

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

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

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

(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

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

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.

Sequence in context: A352644 A389806 A132079 * A322623 A245139 A020131

Adjacent sequences: A055787 A055788 A055789 * A055791 A055792 A055793

Henry Bottomley, Jul 13 2000

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

approved