A005436 Number of convex polygons of perimeter 2n on square lattice.

1, 2, 7, 28, 120, 528, 2344, 10416, 46160, 203680, 894312, 3907056, 16986352, 73512288, 316786960, 1359763168, 5815457184, 24788842304, 105340982248, 446389242480, 1886695382192, 7955156287456, 33468262290096, 140516110684832, 588832418973280, 2463133441338048

Offset: 2

Author

Simon Plouffe and N. J. A. Sloane

Keywords

• nonn

Comments

Or, a(n) = number of convex polyominoes of perimeter 2n. - David Callan, Jul 25 2008

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Robert Israel, Table of n, a(n) for n = 2..1650 (n = 2..105 from I. Jensen)
• Peter Balazs, Generation and Empirical Investigation of hv-Convex Discrete Sets, in Image Analysis, Lecture Notes in Computer Science, Volume 4522/2007, Springer-Verlag. [From _N. J. A. Sloane_, Jul 09 2009]
• 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.
• A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, J. Int. Seq. 10 (2007) # 07.9.7.
• Adrien Boussicault and P. Laborde-Zubieta, Periodic Parallelogram Polyominoes, arXiv preprint arXiv:1611.03766 [math.CO], 2016.
• 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.
• Kevin Buchin, Man-Kwun Chiu, Stefan Felsner, Günter Rote, and André Schulz, The Number of Convex Polyominoes with Given Height and Width, arXiv:1903.01095 [math.CO], 2019.
• M.-P. Delest and G. Viennot, Algebraic languages and polyominoes enumeration, Theoretical Computer Sci., 34 (1984), 169-206.
• F. Disanto, A. Frosini, R. Pinzani and S. Rinaldi, A closed formula for the number of convex permutominoes, arXiv:math/0702550 [math.CO], 2007.
• Filippo Disanto, Andrea Frosini, Simone Rinaldi, and Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.
• E. Duchi, S. Rinaldi and G. Schaeffer, The number of Z-convex polyominoes, arXiv:math/0602124 [math.CO], 2006.
• I. G. Enting and A. J. Guttmann, Area-weighted moments of convex polygons on the square lattice, J. Phys. A 22 (1989), 2639-2642. See Eq. (4).
• I. G. Enting and A. J. Guttmann, On the area of square lattice polygons, J. Statist. Phys., 58 (1990), 475-484. See p. 477.
• A. J. Guttmann and I. G. Enting, The number of convex polygons on the square and honeycomb lattices, J. Phys. A 21 (1988), L467-L474.
• I. Jensen, More terms
• K. Y. Lin and S. J. Chang, Rigorous results for the number of convex polygons on the square and honeycomb latticesJ. Phys. A: Math. Gen., 21 (1988), 2635-2642.
• Anne Micheli and Dominique Rossin, Counting k-Convex Polyominoes, Electron. J. Combin., Volume 20, Issue 2 (2013), #P56.
• Eric Weisstein's World of Mathematics, Convex Polyomino
• V. M. Zhuravlev, Horizontally-convex polyiamonds and their generating functions, Mat. Pros. 17 (2013), 107-129 (in Russian).

Crossrefs

Cf. A005768, A005769, A005770, A093118, A260346, A324009.

Programs

Magma

[1,2] cat [4^n*(2*n+11)-4*(2*n+1)*Binomial(2*n,n): n in [0..25]]; // Vincenzo Librandi, Jun 25 2015

Maple

t1:=x^2*( (1-6*x+11*x^2-4*x^3)/(1-4*x)^2 - 4*x^2/(1-4*x)^(3/2));
series(t1,x,40);
gfun:-seriestolist(%); # N. J. A. Sloane, Aug 02 2015

Mathematica

Join[{1, 2}, Table[(2 n + 11) 4^n - 4 (2 n + 1) Binomial[2 n, n], {n, 0, 25}]] (* Vincenzo Librandi, Jun 25 2015 *)

SageMath

def A005436(n): return (2*n+3)*4^(n-4) -4*(n-3)*binomial(2*n-7, n-4) + (9/16)*int(n==2) - (1/4)*int(n==3)
[A005436(n) for n in range(2,40)] # G. C. Greubel, Nov 20 2022

Formula

a(n) = (2*n + 3)*4^(n-4) - 4*(n-3)*C(2*n-7, n-4) for n >= 4. - Corrected by Robert Israel, Apr 04 2016

a(n) = A005768(n) + A005769(n) + A005770(n).

a(n) = (2*n+11)*4^n - 4*(2*n+1)*binomial(2*n,n) produces the terms (except the first two) with a different offset. - N. J. A. Sloane, Oct 14 2017

G.f.: x^2*(1-6*x+11*x^2-4*x^3)/(1-4*x)^2 - 4*x^4*(1-4*x)^(-3/2). - Markus Voege (voege(AT)blagny.inria.fr), Nov 28 2003

a(n) = (2*(8*n^2 -106*n +303)*a(n-1) - 8*(2*n-9)*(2*n-17)*a(n-2))/((n-4)*(2*n- 19)), with a(2) = 1, a(3) = 2, a(4) = 7, a(4) = 28. - G. C. Greubel, Nov 20 2022