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

4, 3, 5, 6, 9, 13, 20, 31, 49, 78, 125, 201, 324, 523, 845, 1366, 2209, 3573, 5780, 9351, 15129, 24478, 39605, 64081, 103684, 167763, 271445, 439206, 710649, 1149853, 1860500, 3010351, 4870849, 7881198

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

References

• J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 233.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. P. Stanley, Enumerative Combinatorics I, Example 4.7.15, p. 252.

Links

• T. D. Noe, Table of n, a(n) for n = 0..500
• N. Metropolis, M. L. Stein, and P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291-321.
• H. Minc, Permanents of (0,1)-circulants, Canad. Math. Bull., 7 (1964), 253-263.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]
• N. J. A. Sloane, Annotated copy of Riordan's Three-Ply Staircase paper (unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963).
• K. Yamamoto, Structure polynomial of Latin rectangles and its application to a combinatorial problem, Memoirs of the Faculty of Science, Kyusyu University, Series A, 10 (1956), 1-13.
• Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Crossrefs

Cf. A000204.

Programs

Haskell

a000211 n = a000211_list !! n
a000211_list = 4 : 3 : map (subtract 2)
   (zipWith (+) a000211_list (tail a000211_list))
-- Reinhard Zumkeller, Feb 29 2012

Maple

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

Mathematica

Transpose[NestList[{Last[#],First[#]+Last[#]-2}&,{4,3},40]] [[1]]  (* Harvey P. Dale, Mar 22 2011 *)
Table[LucasL[n] + 2, {n, 0, 40}] (* Jean-François Alcover, Jul 30 2015 *)
LinearRecurrence[{2, 0, -1}, {4, 3, 5}, 40] (* Jean-François Alcover, Mar 15 2020 *)

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

Formula

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

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

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

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

a(n) = per(I+P+P^2) = per(P^(-1)+I+P). - Vladimir Shevelev, Apr 11 2010

E.g.f.: 2*exp(x/2)*(exp(x/2) + cosh(sqrt(5)*x/2)). - Ilya Gutkovskiy, Feb 01 2017