login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000211 a(n) = a(n-1) + a(n-2) - 2.
(Formerly M2396 N0953)
27
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 (list; graph; refs; listen; history; text; internal format)
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

N. Metropolis et al., 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.

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.

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.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..500

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 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)

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) + F(n+2) + 2, n>=-1 {where F(n) is the n-th Fibonacci number}. - Zerinvary Lajos, Feb 01 2008

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)+fibonacci(n+2)+2, n=-1..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 *)

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: A226211 A016701 A023829 * A059902 A068982 A171021

Adjacent sequences:  A000208 A000209 A000210 * A000212 A000213 A000214

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 28 05:07 EDT 2017. Contains 284182 sequences.