cp's OEIS Frontend

A000211 a(n) = a(n-1) + a(n-2) - 2, a(0) = 4, a(1) = 3.

%I A000211 M2396 N0953 #85 Apr 13 2022 13:25:14
%S A000211 4,3,5,6,9,13,20,31,49,78,125,201,324,523,845,1366,2209,3573,5780,
%T A000211 9351,15129,24478,39605,64081,103684,167763,271445,439206,710649,
%U A000211 1149853,1860500,3010351,4870849,7881198
%N A000211 a(n) = a(n-1) + a(n-2) - 2, a(0) = 4, a(1) = 3.
%C A000211 Let I=I_n be the n X n identity matrix and P=P_n be the incidence matrix of the cycle (1,2,3,...,n). Then, for n>=3, a(n) is the number of (0,1) n X n matrices A<=P^(-1)+I+P with exactly two 1's in every row and column. - _Vladimir Shevelev_, Apr 11 2010
%D A000211 J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.
%D A000211 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 233.
%D A000211 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000211 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000211 R. P. Stanley, Enumerative Combinatorics I, Example 4.7.15, p. 252.
%H A000211 T. D. Noe, <a href="/A000211/b000211.txt">Table of n, a(n) for n = 0..500</a>
%H A000211 N. Metropolis, M. L. Stein, and P. R. Stein, <a href="http://dx.doi.org/10.1016/S0021-9800(69)80058-X">Permanents of cyclic (0,1) matrices</a>, J. Combin. Theory, 7 (1969), 291-321.
%H A000211 H. Minc, <a href="http://dx.doi.org/10.4153/CMB-1964-023-3">Permanents of (0,1)-circulants</a>, Canad. Math. Bull., 7 (1964), 253-263.
%H A000211 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A000211 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A000211 J. Riordan, <a href="/A000211/a000211.pdf">Discordant permutations</a>, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]
%H A000211 N. J. A. Sloane, <a href="/A001883/a001883_21.pdf">Annotated copy of Riordan's Three-Ply Staircase paper</a> (unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963).
%H A000211 K. Yamamoto, <a href="https://www.jstage.jst.go.jp/article/kyushumfs/10/1/10_1_1/_pdf">Structure polynomial of Latin rectangles and its application to a combinatorial problem</a>, Memoirs of the Faculty of Science, Kyusyu University, Series A, 10 (1956), 1-13.
%H A000211 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1).
%F A000211 G.f.: 2/(1-x)+(2-x)/(1-x-x^2) = (4-5*x-x^2) / ((x-1)*(x^2+x-1)).
%F A000211 a(n) = Lucas number A000032(n) + 2.
%F A000211 Binomial transform of [4, -1, 3, -4, 7, -11, 18, ...], i.e., the series continues as a signed version of the Lucas series, A000204. - _Gary W. Adamson_, Nov 08 2007
%F A000211 a(n) = F(n-1) + F(n+1) + 2, where F(n) is the n-th Fibonacci number. - _Zerinvary Lajos_, Feb 01 2008; corrected by _Michel Marcus_, Jan 05 2021
%F A000211 a(n) = per(I+P+P^2) = per(P^(-1)+I+P). - _Vladimir Shevelev_, Apr 11 2010
%F A000211 E.g.f.: 2*exp(x/2)*(exp(x/2) + cosh(sqrt(5)*x/2)). - _Ilya Gutkovskiy_, Feb 01 2017
%p A000211 A000211:=-(1+z)*(4*z-3)/(z-1)/(z**2+z-1); # conjectured by _Simon Plouffe_ in his 1992 dissertation; gives sequence except for the leading 4
%p A000211 with(combinat): seq(fibonacci(n-1)+fibonacci(n+1)+2, n=0..32); # _Zerinvary Lajos_, Feb 01 2008
%p A000211 a:= n-> (Matrix([[4,1,5]]). Matrix(3, (i,j)-> if (i=j-1) then 1 elif j=1 then [2, 0, -1][i] else 0 fi)^n)[1,1]: seq(a(n), n=0..33); # _Alois P. Heinz_, Aug 01 2008
%t A000211 Transpose[NestList[{Last[#],First[#]+Last[#]-2}&,{4,3},40]] [[1]]  (* _Harvey P. Dale_, Mar 22 2011 *)
%t A000211 Table[LucasL[n] + 2, {n, 0, 40}] (* _Jean-François Alcover_, Jul 30 2015 *)
%t A000211 LinearRecurrence[{2, 0, -1}, {4, 3, 5}, 40] (* _Jean-François Alcover_, Mar 15 2020 *)
%o A000211 (Haskell)
%o A000211 a000211 n = a000211_list !! n
%o A000211 a000211_list = 4 : 3 : map (subtract 2)
%o A000211    (zipWith (+) a000211_list (tail a000211_list))
%o A000211 -- _Reinhard Zumkeller_, Feb 29 2012
%o A000211 (PARI) a(n)=([0,1,0; 0,0,1; -1,0,2]^n*[4;3;5])[1,1] \\ _Charles R Greathouse IV_, Jan 05 2016
%Y A000211 Cf. A000204.
%K A000211 nonn,easy,nice
%O A000211 0,1
%A A000211 _N. J. A. Sloane_