A049220 -id:A049220 - cp's OEIS frontend

A008998 a(n) = 2*a(n-1) + a(n-3), with a(0)=1 and a(1)=2.

1, 2, 4, 9, 20, 44, 97, 214, 472, 1041, 2296, 5064, 11169, 24634, 54332, 119833, 264300, 582932, 1285697, 2835694, 6254320, 13794337, 30424368, 67103056, 148000449, 326425266, 719953588, 1587907625, 3502240516, 7724434620, 17036776865, 37575794246

Offset: 0

N. J. A. Sloane

A transform of A000079 under the mapping g(x)->(1/(1-x^3))g(x/(1-x^3)). - Paul Barry, Oct 20 2004
The binomial transform yields 1,3,9,..., i.e., A049220 without the leading zeros. - R. J. Mathar, May 15 2008
a(n-3) is the top left entry of the n-th power of the 3 X 3 matrix [0, 0, 1; 1, 1, 1; 0, 1, 1] or of the 3 X 3 matrix [0, 1, 0; 0, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
a(n) equals the number of n-length words on {0,1,2} such that 0 appears only in a run which length is a multiple of 3. - Milan Janjic, Feb 17 2015
a(n) is the number of ways to fill a 1 X n strip of tiles, using only trominos, of length 3, and squares which can be chosen to have one of two possible colors. - Michael Tulskikh, Feb 12 2020
For x the real root of x^3 - 2*x^2 - 1 from A356035, then x^n = a(n-4)*x^2 + a(n-2)*x + a(n-3). - Greg Dresden and Qianhuai He, Jul 01 2025

Vincenzo Librandi, Table of n, a(n) for n = 0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 452
B. Rittaud, On the Average Growth of Random Fibonacci Sequences, Journal of Integer Sequences, 10 (2007), Article 07.2.4.
Index entries for linear recurrences with constant coefficients, signature (2,0,1).

Cf. A077852, A077926. Partial sums of A052980.

a:=[1,2,4];; for n in [4..40] do a[n]:=2*a[n-1]+a[n-3]; od; a; # G. C. Greubel, Feb 14 2020

[ n eq 1 select 1 else n eq 2 select 2 else n eq 3 select 4 else 2*Self(n-1)+Self(n-3): n in [1..40]]; // Vincenzo Librandi, Aug 21 2011

A008998 := proc(n) option remember; if n <= 2 then 2^n else 2*procname(n-1) +procname(n-3); fi; end proc;

LinearRecurrence[{2, 0, 1}, {1, 2, 4}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 13 2012 *)

{a(n)=polcoeff(exp(sum(m=1,n+1,((1+sqrt(1+x+x*O(x^n)))^m + (1-sqrt(1+x+x*O(x^n)))^m)*x^m/m)),n)} /* Paul D. Hanna, Dec 21 2012 */

def A008998_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/(1-2*x-x^3) ).list()
A008998_list(40) # G. C. Greubel, Feb 14 2020

a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k, k)*2^(n-3k). - Paul Barry, Oct 20 2004
O.g.f.: 1/(1-2*x-x^3). - R. J. Mathar, May 15 2008
O.g.f.: exp( Sum_{n>=1} ( (1 + sqrt(1+x))^n + (1 - sqrt(1+x))^n ) * x^n/n ). - Paul D. Hanna, Dec 21 2012
G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+2 + x^2)/( x*(4*k+4 + x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 30 2013
a(n) = Sum_{k=0..n} A052980(n). - Greg Dresden, May 28 2020

A001169 Number of board-pile polyominoes with n cells.

Original entry on oeis.org

1, 2, 6, 19, 61, 196, 629, 2017, 6466, 20727, 66441, 212980, 682721, 2188509, 7015418, 22488411, 72088165, 231083620, 740754589, 2374540265, 7611753682, 24400004911, 78215909841, 250726529556, 803721298537, 2576384425157, 8258779154250, 26474089989299

Offset: 1

N. J. A. Sloane

The inverse binomial transform is 1,1,3,6,..., i.e., the unsigned version of A077926. - R. J. Mathar, May 15 2008

a(n+1)/a(n) tends to a limit which is equal to the largest real root of the denominator of the g.f., 3.20556943040... = A246773 . - Robert G. Wilson v, Feb 01 2015

W. F. Lunnon, Counting polyominoes, pp. 347-372 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
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, p. 259.

T. D. Noe, Table of n, a(n) for n = 1..200
I. G. Enting and A. J. Guttmann, On the area of square lattice polygons, J. Statist. Phys., 58 (1990), 475-484.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 367
Dean Hickerson, Counting Horizontally Convex Polyominoes, J. Integer Sequences, Vol. 2 (1999), #99.1.8.
David A. Klarner, Some results concerning polyominoes, Fibonacci Quarterly 3 (1965), 9-20.
David A. Klarner, The number of graded partially ordered sets, Journal of Combinatorial Theory, vol.6, no.1, pp.12-19, (January-1969).
Todd Mullen, On Variants of Diffusion, Dalhousie University (Halifax, NS Canada, 2020).
R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 239
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
G. Pólya, On the number of certain lattice polygons, J. Combinatorial Theory 6 1969 102--105. MR0236031 (38 #4329) - From _N. J. A. Sloane_, Jun 05 2012
K. A. Van'kov, V. M. Zhuravlyov, Regular tilings and generating functions, Mat. Pros. Ser. 3, issue 22, 2018 (127-157) [in Russian]. See page 128. - _N. J. A. Sloane_, Jan 09 2019
Kirill Vankov, Valerii Zhuravlev, Regular and semiregular (uniform) tilings and generating functions, hal-02535947, [math.CO], 2020.
Eric Weisstein's World of Mathematics, Column-Convex Polyomino.
D. Zeilberger, Automated counting of LEGO towers, arXiv:math/9801016 [math.CO], 1998.
V. M. Zhuravlev, Horizontally-convex polyiamonds and their generating functions, Mat. Pros. 17 (2013), 107-129 (in Russian).
Index entries for linear recurrences with constant coefficients, signature (5, -7, 4).

Cf. A049219, A049220 (partial sums), A049221, A049222, A246773, A273895.

I:=[1,2,6,19,61]; [n le 5 select I[n] else 5*Self(n-1)-7*Self(n-2)+4*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Feb 15 2015

a[n_] := a[n] = If[n<5, {1, 2, 6, 19}[[n]], 5a[n-1] - 7a[n-2] + 4a[n-3]]; Table[a[n], {n, 30}]
Join[{1},LinearRecurrence[{5,-7,4},{2,6,19},40]] (* Harvey P. Dale, Sep 11 2014 *)
Rest@ CoefficientList[ Series[x (1 - x)^3/(1 - 5x + 7x^2 - 4x^3), {x, 0, 28}], x] (* Robert G. Wilson v, Feb 01 2015 *)

makelist(sum(sum(binomial(k,i)*binomial(n+2*i-1,4*k-i),i,0,k),k,0,n-1),n,0,24); /* Emanuele Munarini, May 19 2011 */

{a(n) = if( n<0, 0, polcoeff( x * (1 - x)^3 / (1 - 5*x + 7*x^2 - 4*x^3) + x * O(x^n), n))}; /* Michael Somos, Jun 02 2016 */

G.f.: x*(1-x)^3/(1 - 5*x + 7*x^2 - 4*x^3). - Simon Plouffe in his 1992 dissertation
a(n) = 5*a(n-1) - 7*a(n-2) + 4*a(n-3) for n >= 5.
a(n) = sum(k=0..n-1, sum(i=0..k, binomial(k,i)*binomial(n+2*i-1,4*k-i))). - Emanuele Munarini, May 19 2011
a(n) = a(n-1) + A049219(n) + A049220(n) for n >= 2.
Row sums of A273895. - Michael Somos, Jun 02 2016

More terms from Dean Hickerson

A049222 Number of horizontally convex n-ominoes in which the top row has exactly 1 square, which is not above the rightmost square in the second row and the rightmost square in the second row is above the leftmost square in the third row.

Original entry on oeis.org

0, 0, 0, 1, 4, 13, 41, 130, 415, 1329, 4260, 13657, 43781, 140346, 449891, 1442157, 4622932, 14819125, 47503729, 152276498, 488132887, 1564743865, 5015895108, 16078800033, 51541709869, 165220529546, 529625878779, 1697752526549

Offset: 1

Dean Hickerson, Aug 10 1999

Dean Hickerson, Counting Horizontally Convex Polyominoes, J. Integer Sequences, Vol. 2 (1999), #99.1.8.
Index entries for linear recurrences with constant coefficients, signature (5, -7, 4).

Cf. A049220.

a[ n_ ] := a[ n ]=If[ n<6, {0, 0, 0, 1, 4}[ [ n ] ], 5a[ n-1 ]-7a[ n-2 ]+4a[ n-3 ] ]
Join[{0,0,0},LinearRecurrence[{5,-7,4},{0,1,4},30]] (* or *) CoefficientList[ Series[x^4 (1-x)/(1-5x+7x^2-4x^3),{x,0,30}],x] (* Harvey P. Dale, May 10 2011 *)

G.f.: x^4 (1-x)/(1-5x+7x^2-4x^3).
a(n) = 5*a(n-1) - 7*a(n-2) + 4*a(n-3) for n >= 6.
a(n) = a(n-1) + A049220(n-1) for n >= 2.

cp's OEIS Frontend

A008998 a(n) = 2*a(n-1) + a(n-3), with a(0)=1 and a(1)=2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A001169 Number of board-pile polyominoes with n cells.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Formula

Extensions

A049222 Number of horizontally convex n-ominoes in which the top row has exactly 1 square, which is not above the rightmost square in the second row and the rightmost square in the second row is above the leftmost square in the third row.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula