A196593 Number of fixed tree-like convex polyominoes.

1, 2, 6, 18, 51, 134, 328, 758, 1677, 3594, 7530, 15530, 31687, 64190, 129420, 260142, 521889, 1045730, 2093806, 4190402, 8384091, 16772022, 33548496, 67102118, 134210101, 268426874, 536861298, 1073731098, 2147471727, 4294954094, 8589920020, 17179853150

Offset: 1

Author

Gill Barequet, Oct 04 2011

Keywords

• nonn
• easy

Comments

In a 1-1 mapping with permutations that avoid the patterns (1423, 4213, 2314, 2431, 2413, <3142,{2},{2}>) (the fourth pattern is bivincular).

Links

• Harvey P. Dale, Table of n, a(n) for n = 1..1000
• Gadi Aleksandrowicz, Andrei Asinowski and Gill Barequet, A polyominoes-permutations injection and tree-like convex polyominoes, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, Pages 503-520
• A. Goupil, H. Cloutier, and F. Nouboud, Enumeration of inscribed polyominos, FPSCA 2010 (San Francisco) DMTS proc. AN 2010, 737-748, eq. (10)
• Index entries for linear recurrences with constant coefficients, signature (6,-14,16,-9,2).

Crossrefs

Cf. A001168 (fixed polyominoes), A066158 (fixed tree polyominoes), A067675 (fixed convex polyominoes).

Programs

Mathematica

LinearRecurrence[{6,-14,16,-9,2},{1,2,6,18,51},50] (* Harvey P. Dale, Oct 16 2011 *)

Formula

G.f.: (x*(1-4*x+8*x^2-6*x^3+4*x^4))/((1-x)^4*(1-2*x)).

a(n) = 6*a(n-1) - 14*a(n-2) + 16*a(n-3) - 9*a(n-4) + 2*a(n-5).

a(n) = 2^(n+2) - (n^3-n^2+10*n+4)/2.