A003480 a(0) = 1, a(1) = 2, for n > 1, a(n) = 4*a(n-1) - 2*a(n-2).

1, 2, 7, 24, 82, 280, 956, 3264, 11144, 38048, 129904, 443520, 1514272, 5170048, 17651648, 60266496, 205762688, 702517760, 2398545664, 8189147136, 27959497216, 95459694592, 325919783936, 1112759746560, 3799199418368, 12971278180352, 44286713884672, 151204299177984

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Gives the number of L-convex polyominoes with n cells, that is convex polyominoes where any two cells can be connected by a path internal to the polyomino and which has at most 1 change of direction (i.e., one of the four orientation of the L). - Simone Rinaldi (rinaldi(AT)unisi.it), Feb 19 2007

Joe Keane (jgk(AT)jgk.org) observes that this sequence (beginning at 2) is "size of raises in pot-limit poker, one blind, maximum raising".

Dimensions of the graded components of the Hopf algebra of noncommutative multi-symmetric functions of level 2. For level r, the sequence would be the INVERT transform of binomial(n+r-1,n). - Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Jun 26 2008

The sum of the numbers in the n-th row of the summatory Pascal triangle (A059576). - Ron R. King, Jan 22 2009

(1 + 2x + 7x^2 + 24x^3 + ...) = 1 / (1 - 2x - 3x^2 - 4x^3 - ...). - Gary W. Adamson, Jul 27 2009

Let M be a triangle with the odd-indexed Fibonacci numbers (1, 2, 5, 13, ...) in every column, with the leftmost column shifted upwards one row. A003480 = lim_{n->oo} M^n, the left-shifted vector considered as a sequence. The analogous operation using the even-indexed Fibonacci numbers generates A001835 starting with offset 1. - Gary W. Adamson, Jul 27 2010

a(n) is the number of generalized compositions of n when there are i+1 different types of the part i, (i=1,2,...). - Milan Janjic, Sep 24 2010

Let h(t) = (1-t)^2/(2*(1-t)^2-1) = 1/(1-(2*t + 3*t^2 + 4*t^3 + ...)),

an o.g.f. for A003480, then

A001003(n) = (1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=1. - Tom Copeland, Sep 06 2011

Excluding the initial 1, a(n) is the 2nd subdiagonal of A228405. - Richard R. Forberg, Sep 02 2013

References

• G. Castiglione and A. Restivo, L-convex polyominoes: a survey, Chapter 2 of K. G. Subranian et al., eds., Formal Models, Languages and Applications, World Scientific, 2015.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
• Daniela Battaglino, Jean-Marc Fédou, Simone Rinaldi, and Samanta Socci, The number of k-parallelogram polyominoes, FPSAC 2013 Paris, France DMTCS Proc. AS, 2013, 1143-1154.
• Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, (an + b)-color compositions, arXiv:1707.07798 [math.CO], 2017.
• Adrien Boussicault, Simone Rinaldi, and Samanta Socci, The number of directed k-convex polyominoes, arXiv preprint arXiv:1501.00872 [math.CO], 2015; Discrete Math., 343 (2020), #111731, 22 pages. See t_n.
• Steve Butler, Jeongyoon Choi, Kimyung Kim, and Kyuhyeok Seo, Enumerating multiplex juggling patterns, arXiv:1702.05808 [math.CO], 2017.
• Peter J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
• Giuseppa Castiglione, Andrea Frosini, Emanuele Munarini, Antonio Restivo, and Simone Rinaldi, Combinatorial aspects of L-convex polyominoes, European J. Combin. 28 (2007), no. 6, 1724-1741.
• Yumin Cho, Jaehyun Kim, Jang Soo Kim, and Nakyung Lee, Enumeration of multiplex juggling card sequences using generalized q-derivatives, arXiv:2402.09903 [math.CO], 2024. See p. 6.
• Ana Djurdjevac, Vesa Kaarnioja, Claudia Schillings, and André-Alexander Zepernick, Uncertainty quantification for stationary and time-dependent PDEs subject to Gevrey regular random domain deformations, arXiv:2502.12345 [math.NA], 2025. See p. 34.
• Tomislav Doslic, Planar polycyclic graphs and their Tutte polynomials, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607.
• Enrica Duchi, Simone Rinaldi, and Gilles Schaeffer, The number of Z-convex polyominoes, arXiv:math/0602124 [math.CO], 2006.
• Andrea Frosini and Simone Rinaldi, An object grammar for the class of L-convex polyominoes, PU.M.A. Vol. 17 (2006), No. 1-2, pp. 97-110.
• Taras Goy and Mark Shattuck, Toeplitz-Hessenberg determinant formulas for the sequence F_n-1, Online J. Anal. Comb. (2025) Vol. 19, Paper 1, 1-26. See pp. 12, 18
• Yu-hong. Guo, Some n-Color Compositions, J. Int. Seq. 15 (2012) 12.1.2, eq (12).
• Harri Hakula, Helmut Harbrecht, Vesa Kaarnioja, Frances Y. Kuo, and Ian H. Sloan, Uncertainty quantification for random domains using periodic random variables, arXiv:2210.17329 [math.NA], 2022.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 418
• Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
• Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products and noncommutative multi-symmetric functions, arXiv:0806.3682 [math.CO], 2008.
• 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, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.
• J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222. [Annotated scanned copy]
• Index entries for sequences related to poker
• Index entries for linear recurrences with constant coefficients, signature (4,-2).

Crossrefs

Row sums of A059576 and of A181289. Second differences of A007070.

Cf. A007052, A126764.

Cf. A000129, A001003, A001835, A006012, A029744, A145839, A145840, A145841, A228405.

Column k=2 of A261780.

Programs

Haskell

a003480 n = a003480_list !! n
a003480_list = 1 : 2 : 7 : (tail $ zipWith (-)
   (tail $ map (* 4) a003480_list) (map (* 2) a003480_list))
-- Reinhard Zumkeller, Jan 16 2012, Oct 03 2011

Maple

INVERT([seq(n+1,n=1..20)]); # Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Jun 26 2008

Mathematica

a[0]=1; a[1]=2; a[2]=7; a[n_]:=a[n]=4*a[n-1] - 2*a[n-2]; Table[a[n],{n,0,24}] (* Jean-François Alcover, Mar 22 2011 *)
Join[{1},LinearRecurrence[{4,-2},{2,7},40]] (* Harvey P. Dale, Oct 23 2011 *)

PARI

a(n)=polcoeff((1-x)^2/(1-4*x+2*x^2)+x*O(x^n),n)

PARI

a(n)=local(x); if(n<1,n==0,x=(2+quadgen(8))^n; imag(x)+real(x)/2)

Formula

a(n) = (n+1)*a(0) + n*a(1) + ... + 3*a(n-2) + 2*a(n-1). - Amarnath Murthy, Aug 17 2002

G.f.: (1-x)^2/(1-4*x+2*x^2). - Simon Plouffe in his 1992 dissertation

a(n) = A007070(n)/2, n > 0.

G.f.: 1/( 1 - Sum_{k>=1} (k+1)*x^k ).

a(n+1)*a(n+1) - a(n+2)*a(n) = 2^n, n > 0. - D. G. Rogers, Jul 12 2004

For n > 0, a(n) = ((2+sqrt(2))^(n+1) - (2-sqrt(2))^(n+1))/(4*sqrt(2)). - Rolf Pleisch, Aug 03 2009

If the leading 1 is removed, 2, 7, 24, ... is the binomial transform of 2, 5, 12, 29, ..., which is A000129 without its first 2 terms, and the second binomial transform of 2, 3, 4, 6, ..., which is A029744, again without its leading 1. - Al Hakanson (hawkuu(AT)gmail.com), Aug 08 2009

a(n) = Sum((1+p_1)*(1+p_2)*...*(1+p_m)), summation being over all compositions (p_1, p_2, ..., p_m) of n. Example: a(3)=24; indeed, the compositions of 3 are (1,1,1), (1,2), (2,1), (3) and we have 2*2*2 + 2*3 + 3*2 + 4 = 24. - Emeric Deutsch, Oct 17 2010

a(n) = Sum_{k>=0} binomial(n+2*k-1,n) / 2^(k+1). - Vaclav Kotesovec, Dec 31 2013

E.g.f.: (1 + exp(2*x)*(cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x)))/2. - Stefano Spezia, May 20 2024