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

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,1

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

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

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

Prog

(Haskell)
a000211 n = a000211_list !! n
a000211_list = 4 : 3 : map (subtract 2)
   (zipWith (+) a000211_list (tail a000211_list))
-- Reinhard Zumkeller, Feb 29 2012
(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

Crossrefs

Cf. A000204.

Sequence in context: A023829 A335583 A328109 * A059902 A304225 A068982

Adjacent sequences: A000208 A000209 A000210 * A000212 A000213 A000214

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved