|
%I #74 May 07 2018 12:08:37
%S 0,2,4,14,64,362,2428,18806,165016,1616786,17487988,206918942,
%T 2657907184,36828901754,547499510764,8691268384262,146725287298888,
%U 2624698909845026,49592184973992676,986871395973226286,20630087248996393888,451982388752415571082
%N a(n) = n*a(n-1) + (n-2)*a(n-2), a(0) = 0, a(1) = 2.
%C 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
%C 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
%C Equivalently number of degree-(n+1) permutations p such that p(i) != i-2 for each i=1,2,...,n+1.
%C With a(0) = 1, number of degree-(n+1) permutations without fixed points between 2 and n. - _Olivier Gérard_, Jul 29 2016
%C Also column 3 of Euler's difference table (third diagonal in example of A068106). - _Enrique Navarrete_, Oct 31 2016
%C 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
%D Brualdi, Richard A. and Ryser, Herbert J., Combinatorial Matrix Theory, Cambridge NY (1991), Chapter 7.
%H Reinhard Zumkeller, <a href="/A055790/b055790.txt">Table of n, a(n) for n = 0..250</a>
%H T. Mansour and M. Shattuck, <a href="http://dx.doi.org/10.1016/j.disc.2015.12.004">Counting permutations by the number of successors within cycles</a>, Discr. Math., 339 (2016), 1368-1376.
%H Enrique Navarrete, <a href="https://arxiv.org/abs/1610.06217">Generalized K-Shift Forbidden Substrings in Permutations</a>, arXiv:1610.06217 [math.CO], 2016.
%H Enrique Navarrete, <a href="https://arxiv.org/abs/1702.02637">Forbidden Substrings in Circular K-Successions</a>, arXiv:1702.02637 [math.CO], 2017.
%H Seok-Zun Song et al., <a href="http://dx.doi.org/10.1016/S0024-3795(03)00382-3">Extremes of permanents of (0,1)-matrices</a>, Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002). Linear Algebra Appl. 373 (2003), pp. 197-210.
%F 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).
%F 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
%F 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
%F 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
%F 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
%F a(n) ~ sqrt(Pi/2)*n^n*sqrt(n)*(12*n + 37)/(6*exp(n+1)). - _Ilya Gutkovskiy_, Jul 29 2016
%F 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
%e G.f. = 2*x + 4*x^2 + 14*x^3 + 64*x^4 + 362*x^5 + 2428*x^6 + ...
%e a(3) = 3*a(2)+(3-2)*a(1) = 12+2 = 14.
%e for n=1, the 2 permutations of [2] matches:
%e 12, 21
%e for n=2, the 4 permutations of [3] without 2 as a fixed point are
%e 132, 213, 231, 312.
%e for n=3, the 14 permutations of [4] without fixed point at 2 or 3 are
%e 1324 1342 1423 2143 2314 2341 2413
%e 3124 3142 3412 3421 4123 4312 4321
%p f := proc(n) option remember; if n <= 1 then 2*n else n*f(n-1)+(n-2)*f(n-2); fi; end;
%t a[0] = 0; a[1] = 2; a[n_] := a[n] = a[n] = n*a[n - 1] + (n - 2)*a[n - 2];
%t Table[a[n], {n, 0, 21}] (* _Jean-François Alcover_, Nov 14 2017 *)
%t 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 *)
%o (Haskell)
%o a055790 n = a055790_list !! n
%o a055790_list = 0 : 2 : zipWith (+)
%o (zipWith (*) [0..] a055790_list) (zipWith (*) [2..] $ tail a055790_list)
%o -- _Reinhard Zumkeller_, Mar 05 2012
%o (PARI) a(n) = if(n==0, 0, round((n+3+1/n)*n!/exp(1))) \\ _Felix Fröhlich_, Jul 29 2016
%Y Cf. A000166 (Derangements, permutations without fixed points ).
%Y Cf. A000255 (permutations with p(i)!=i+1, same type of recurrence).
%Y Cf. A000153, A000261, A001909, A001910, A090010, A090012-A090016.
%Y 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.
%K nonn
%O 0,2
%A _Henry Bottomley_, Jul 13 2000
%E Comments corrected, new interpretation and examples by _Olivier Gérard_, Jul 29 2016
| 