A003480 a(n) = 4*a(n-1) - 2*a(n-2) (n >= 3). (Formerly M1763)

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

Offset

0,2

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)

D. Battaglino, J. M. Fedou, S. Rinaldi and S. 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.

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

G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. 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.

Tomislav Doslic, Planar polycyclic graphs and their Tutte polynomials, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607.

E. Duchi, S. Rinaldi and G. Schaeffer, The number of Z-convex polyominoes, arXiv:math/0602124 [math.CO], 2006.

A. Frosini and S. Rinaldi, An object grammar for the class of L-convex polyominoes, PU.M.A. Vol. 17 (2006), No. 1-2, pp. 97-110.

Y-h. 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.

J.-C. Novelli and J.-Y. 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).

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

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

Prog

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

Crossrefs

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

Cf. A007052, A126764.

Cf. A001835, A006012, A145839, A145840, A145841.

Column k=2 of A261780.

Sequence in context: A027128 A099463 A021000 * A020727 A329274 A370477

Adjacent sequences: A003477 A003478 A003479 * A003481 A003482 A003483

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved