login
a(n) = a(n-1) + a(n-2) - 2, a(0) = 4, a(1) = 3.
(Formerly M2396 N0953)
28

%I M2396 N0953 #85 Apr 13 2022 13:25:14

%S 4,3,5,6,9,13,20,31,49,78,125,201,324,523,845,1366,2209,3573,5780,

%T 9351,15129,24478,39605,64081,103684,167763,271445,439206,710649,

%U 1149853,1860500,3010351,4870849,7881198

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

%C 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 J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 233.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P. Stanley, Enumerative Combinatorics I, Example 4.7.15, p. 252.

%H T. D. Noe, <a href="/A000211/b000211.txt">Table of n, a(n) for n = 0..500</a>

%H 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 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 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 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H J. Riordan, <a href="/A000211/a000211.pdf">Discordant permutations</a>, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]

%H 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 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 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1).

%F G.f.: 2/(1-x)+(2-x)/(1-x-x^2) = (4-5*x-x^2) / ((x-1)*(x^2+x-1)).

%F a(n) = Lucas number A000032(n) + 2.

%F 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 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 a(n) = per(I+P+P^2) = per(P^(-1)+I+P). - _Vladimir Shevelev_, Apr 11 2010

%F E.g.f.: 2*exp(x/2)*(exp(x/2) + cosh(sqrt(5)*x/2)). - _Ilya Gutkovskiy_, Feb 01 2017

%p 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 with(combinat): seq(fibonacci(n-1)+fibonacci(n+1)+2, n=0..32); # _Zerinvary Lajos_, Feb 01 2008

%p 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 Transpose[NestList[{Last[#],First[#]+Last[#]-2}&,{4,3},40]] [[1]] (* _Harvey P. Dale_, Mar 22 2011 *)

%t Table[LucasL[n] + 2, {n, 0, 40}] (* _Jean-François Alcover_, Jul 30 2015 *)

%t LinearRecurrence[{2, 0, -1}, {4, 3, 5}, 40] (* _Jean-François Alcover_, Mar 15 2020 *)

%o (Haskell)

%o a000211 n = a000211_list !! n

%o a000211_list = 4 : 3 : map (subtract 2)

%o (zipWith (+) a000211_list (tail a000211_list))

%o -- _Reinhard Zumkeller_, Feb 29 2012

%o (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 Cf. A000204.

%K nonn,easy,nice

%O 0,1

%A _N. J. A. Sloane_