|
|
A030186
|
|
a(n) = 3*a(n-1) + a(n-2) - a(n-3) for n >= 3, a(0)=1, a(1)=2, a(2)=7.
|
|
28
|
|
|
1, 2, 7, 22, 71, 228, 733, 2356, 7573, 24342, 78243, 251498, 808395, 2598440, 8352217, 26846696, 86293865, 277376074, 891575391, 2865808382, 9211624463, 29609106380, 95173135221, 305916887580, 983314691581, 3160687827102, 10159461285307, 32655756991442
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Number of matchings in ladder graph L_n = P_2 X P_n.
Cycle-path coverings of a family of digraphs.
a(n+1) = Fibonacci(n+1)^2 + Sum_{k=0..n} Fibonacci(k)^2*a(n-k) (with the offset convention Fibonacci(2)=2). - Barry Cipra, Jun 11 2003
Equivalently, ways of paving a 2 X n grid cells using only singletons and dominoes. - Lekraj Beedassy, Mar 25 2005
It is easy to see that the g.f. for indecomposable tilings (pavings) i.e. those that cannot be split vertically into smaller tilings, is g=2x+3x^2+2x^3+2x^4+2x^5+...=x(2+x-x^2)/(1-x); then G.f.=1/(1-g)=(1-x)/(1-3x-x^2+x^3). - Emeric Deutsch, Oct 16 2006
a(n) = Lucas(2n) + Sum_{k=2..n-1} Fibonacci(2k-1)*a(n-k). This relationship can be proven by a visual proof using the idea of tiling a 2 X n board with only singletons and dominoes while conditioning on where the vertical dominoes first appear. If there are no vertical dominoes positioned at lengths 2 through n-1, there will be Lucas(2n) ways to tile the board since a complete tour around the board will be made possible. If the first vertical domino appears at length k (where 2 <= k <= n-1) there will be Fibonacci(2k-1)*a(n-k) ways to tile the board. - Rana Ürek, Jun 25 2018
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 25.
J. D. E. Konhauser et al., Which Way Did The Bicycle Go? Problem 140 "Count The Tilings" pp. 42; 180-1 Dolciani Math. Exp. No. 18 MAA Washington DC 1996.
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Matching
|
|
FORMULA
|
G.f.: (1-x)/(1-3*x-x^2+x^3).
a(n) = ( (Sum_{k=0..n-1} a(k))^2 + (Sum_{k=0..n-1} a(k)^2) ) / a(n-1) for n>1 with a(0)=1, a(1)=2 (similar to A088016). - Paul D. Hanna, Nov 20 2012
|
|
MAPLE
|
a[0]:=1: a[1]:=2: a[2]:=7: for n from 3 to 30 do a[n]:=3*a[n-1]+a[n-2]-a[n-3] od: seq(a[n], n=0..30); # Emeric Deutsch, Oct 16 2006
|
|
MATHEMATICA
|
Table[RootSum[1 -# -3#^2 +#^3 &, 9#^n -10#^(n+1) +7#^(n+2) &]/74, {n, 0, 30}] (* Eric W. Weisstein, Oct 03 2017 *)
CoefficientList[Series[(1-x)/(1-3x-x^2+x^3), {x, 0, 30}], x] (* Eric W. Weisstein, Oct 03 2017 *)
|
|
PROG
|
(Haskell)
a030186 n = a030186_list !! n
a030186_list = 1 : 2 : 7 : zipWith (-) (tail $
zipWith (+) a030186_list $ tail $ map (* 3) a030186_list) a030186_list
(PARI) {a(n)=if(n==0, 1, if(n==1, 2, (sum(k=0, n-1, a(k))^2+sum(k=0, n-1, a(k)^2))/a(n-1)))} \\ Paul D. Hanna, Nov 20 2012
(Sage)
P.<x> = PowerSeriesRing(ZZ, prec)
return P((1-x)/(1-3*x-x^2+x^3)).list()
(GAP) a:=[1, 2, 7];; for n in [4..30] do a[n]:=3*a[n-1]+a[n-2]-a[n-3]; od; a; # G. C. Greubel, Sep 27 2019
|
|
CROSSREFS
|
Bisection (even part) gives A260033.
|
|
KEYWORD
|
nonn,easy,nice,changed
|
|
AUTHOR
|
Ottavio D'Antona (dantona(AT)dsi.unimi.it)
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|