Counting Rooted Directed Polyominoes: 1 2 1 5 3 1 13 9 4 1 35 26 14 5 1 96 75 45 20 6 1 267 216 140 71 27 7 1 750 623 427 238 105 35 8 1 Recursion: A[n,k] = A[n-1,k-1] + A[n-1,k] + A[n-1,k+1] for k>0. A[n,k] = 2*A[n-1,k] + A[n-1,k+1] for k=0. A simple consequence of this recursion is, that the row sums are powers of three. Relation with the Trinomial coefficients: A[n,k] = T[n,k] + T[n,k+1]. Interpretation: rooted directed polynomials Table: A(0,0)=1: z A(1,0)=2: x z x z A(2,0)=5: x x x x x x z x x z x z x z z A(3,0)=13: x x x x x x x x x x z x x x z x x z x x z x x z z x z x x x x x x x x x x x x x x x x x z z x z z z x z The root is marked with z. Every further square is attatched as a neighbor right or above. The recursion formulars can be interpreted in this model, but this is very hard (see [Gouyou-Beauchamps, Viennot]). References: - Dominique Gouyou-Beauchamps and G. Viennot, Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Advances in Applied Math., 9 (1988) 334--357; MR 90c:05009. [A set $P$ of lattice points in the plane is called a directed animal if there is a subset of $P$, whose elements are called root points, such that the root points lie on a line perpendicular to the line $y=x$, and every point of $P$ can be reached from a root point by a path in $P$ using only north and east steps. This paper is concerned with the enumeration of compact-rooted animals, which are animals in which the root points are consecutive. Animals which differ only by translation are considered to be equivalent. The main result is a bijection between compact-rooted animals of size $n+1$ and paths of length $n$ on the integers, with steps +1, 0 and $-1$. This bijection implies that there are $3^n$ compact-rooted animals of size $n+1$. Moreover the bijection allows the compact-rooted animals to be counted according to the number of root points. Further consequences are that the generating function for directed animals with one root point is ${1\over2}((1+t)/\sqrt{1-2t-3t^2}-1)$ and that the number of directed animals of size $n$ rooted at the origin and contained in the first octant $0\leq x\leq y$ is the Motzkin number $m_{n-1}$. The paper also contains many references to work by physicists on problems of counting animals, which arise in studying thermodynamic models for critical phenomena and phase transitions. {\it Ira Gessel}] ------------------------------------------------------------------------------ - (centered) Trinomial Coefficients T_n(x) = (1/x+1+x)^n T[n,k] = [x^k] (1/x+1+x)^n = T[n-1,k-1] + T[n-1,k] + T[n-1,k+1] (for n>=1) k : -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 1 1 1 1 1 2 3 2 1 1 3 6 7 6 3 1 1 4 10 16 19 16 10 4 1 1 5 15 30 45 51 45 30 15 5 1 1 6 21 50 90 126 141 126 90 50 21 6 1 1 7 28 77 161 266 357 393 357 266 161 77 28 7 1 - Motzkin Triangle M_n(x) = (1-1/x^2) (1/x+1+x)^n = (1-1/x^2) T_n(x) = (1-1/x) A_n(x) M[n,k] = [x^k] (1-1/x^2) (1/x+1+x)^n = T[n,k] - T[n,k+2] = A[n,k] - A[n,k+1] = M[n-1,k-1] + M[n-1,k] + M[n-1,k+1] (for n>=1) k : -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 -1 0 1 -1 -1 0 1 1 -1 -2 -2 0 2 2 1 -1 -3 -5 -4 0 4 5 3 1 -1 -4 -9 -12 -9 0 9 12 9 4 1 -1 -5 -14 -25 -30 -21 0 21 30 25 14 5 1 -1 -6 -20 -44 -69 -76 -51 0 51 76 69 44 20 6 1 -7 -27 -70 -133 -189 -196 -127 0 127 196 189 133 70 27 7 1 - Rooted (convex) directed animals A_n(x) = (1+1/x) (1/x+1+x)^n = (1+1/x) T_n(x) A[n,k] = [x^k] (1+1/x) (1/x+1+x)^n = T[n,k] + T[n,k+1] = A[n-1,k-1] + A[n-1,k] + A[n-1,k+1] (for n>=1) k : -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 1 1 1 2 2 1 1 3 5 5 3 1 1 4 9 13 13 9 4 1 1 5 14 26 35 35 26 14 5 1 1 6 20 45 75 96 96 75 45 20 6 1 1 7 27 71 140 216 267 267 216 140 71 27 7 1 1 8 35 105 238 427 623 750 750 623 427 238 105 35 8 1 Now extract the 0th columns: t(n) = T[n,0] m(n) = M[n,0] a(n) = A[n,0] Via the three term recursions in the triangles we get the following relations: a(n) = A[n-1,-1] + A[n-1,0] + A[n-1,1] as A[n-1,-1] = A[n-1,0] = 2 a(n-1) + A[n-1,1] as M[n-1,0] = A[n-1,0] - A[n-1,1] = 3 a(n-1) - m(n-1) a(n) = T[n,0] + T[n,1] as T[n,1] = T[n,-1] = 1/2 t(n) + 1/2(T[n,-1] + T[n,0] + T[n,1]) = 1/2 (t(n) + t(n+1)) m(n) = 3 a(n) - a(n+1) m(n) = 1/2 ( 3 t(n) + 2 t(n+1) - t(n+2) ) Writing this relations in term of there GFs A(x), M(x) and T(x) we get (1-3x) A(x) + x M(x) = 1 (x+1) T(x) - 2x A(x) = 1 (1-2x-3x^2) T(x) + x^2 M(x) = 1-x Note: Gouyou-Beauchamps and Viennot use shifted indices c(n,k) = A[n-1,k-1]. They gave the relation a(n) = 1/2 (t(n) + t(n+1)) but not the other. References: - Dominique Gouyou-Beauchamps and G. Viennot, Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Advances in Applied Math., 9 (1988) 334--357; MR 90c:05009. [A set $P$ of lattice points in the plane is called a directed animal if there is a subset of $P$, whose elements are called root points, such that the root points lie on a line perpendicular to the line $y=x$, and every point of $P$ can be reached from a root point by a path in $P$ using only north and east steps. This paper is concerned with the enumeration of compact-rooted animals, which are animals in which the root points are consecutive. Animals which differ only by translation are considered to be equivalent. The main result is a bijection between compact-rooted animals of size $n+1$ and paths of length $n$ on the integers, with steps +1, 0 and $-1$. This bijection implies that there are $3^n$ compact-rooted animals of size $n+1$. Moreover the bijection allows the compact-rooted animals to be counted according to the number of root points. Further consequences are that the generating function for directed animals with one root point is ${1\over2}((1+t)/\sqrt{1-2t-3t^2}-1)$ and that the number of directed animals of size $n$ rooted at the origin and contained in the first octant $0\leq x\leq y$ is the Motzkin number $m_{n-1}$. The paper also contains many references to work by physicists on problems of counting animals, which arise in studying thermodynamic models for critical phenomena and phase transitions. {\it Ira Gessel}] - Zeilberger, Six etudes in generating functions (Catalan, Motzkin, Narayana) Intern. J. Comput. Math. 29 (1989) 201-215 (Catalan, Motzkin, Narayana) - ??? Three combinatorial sequences derivable from lattice path counting, Ann. Disc. Math. 52 (1992) 81-92 (45 ref, new), MR 93j:05005 ------------------------------------------------------------------------------ From the On-Line Encyclopedia of Integer Sequences! %I A005773 M1443 %S A005773 1,2,5,13,35,96,267,750,2123,6046,17303,49721,143365,414584,1201917,3492117, %T A005773 10165779,29643870,86574831,253188111,741365049,2173243128,6377181825,18730782252 %N A005773 Directed animals of size n (or directed n-ominoes in standard position). %R A005773 AAM 9 340 1988. DM 180 75 1998. %O A005773 1,2 %A A005773 njas, sp, Clark Kimberling (ck6@cedar.evansville.edu) %F A005773 G.f.: (1/2)((1+x)/(1-3x))^1/2 - 1/2 . Related to Motzkin numbers A001006 by a(n+1) = 3 a(n) - A001006(n). %Y A005773 Inverse of A001006. Also sum of numbers in row n+1 of array T in A026300. Leading column of array in A038622. %K A005773 nonn,easy %D A005773 J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 237. %I A001006 M1184 N0456 %S A001006 1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572, %T A001006 853467,2356779,6536382,18199284,50852019,142547559,400763223,1129760415 %N A001006 Motzkin numbers: ways to join n points on a circle by nonintersecting chords. %R A001006 BAMS 54 359 1948. JSIAM 18 254 1969. JCT A23 291-301 1977. JCT B22 114-121 1977. JCT A76 145-147 1996. %O A001006 0,3 %K A001006 nonn,core,easy %Y A001006 Cf. A005717. %H A001006 See also %D A001006 Richard Stanley's home page, under Enumerative Combinatorics, Vol II has a list of manifestations of Motzkin numbers. %F A001006 G.f.: (1 - x - (1-2*x-3*x^2)^(1/2) ) / (2*x^2). Satifies A = 1 + xA + x^2 A^2. %F A001006 a(n) = (-1/2) SUM (-3)^a C(1/2,a) C(1/2, b); a+b=n+2, a>=0, b>=0. %t A001006 a[0]=1;a[n_Integer]:=a[n]=a[n-1]+Sum[a[k]*a[n-2-k],{k,0,n-2}]; Array[ a[#]&, 30 ] %A A001006 njas %I A002426 M2673 N1070 %S A002426 1,1,3,7,19,51,141,393,1107,3139,8953,25653,73789,212941, %T A002426 616227,1787607,5196627,15134931,44152809,128996853,377379369, %U A002426 1105350729,3241135527,9513228123,27948336381,82176836301 %N A002426 Central trinomial coefficient: largest coefficient of (1+x+x^2 )^n. %R A002426 EUL (1) 15 59 1927. RCI 74. FQ 7 341 1969. Henr74 1 42. DAM 34 234 1991. GKP 575. %K A002426 easy,huge,nonn,nice %O A002426 0,3 %F A002426 G.f.: 1 / ( 1 + x )^1/2 (1 - 3x)^1/2 . %A A002426 njas,sp %E A002426 DAM ref added 5/95. Revised description 4/96. %D A002426 The Euler reference is to his "Exemplum Memorabile Inductionis Fallacis". %D A002426 See also R. K. Guy, The Second Strong Law of Small Numbers [Math Mag, 63(1990) 3-20, esp. 18-19] %D A002426 George Andrews, "Euler's `exemplum memorabile inductionis fallacis' and $q$-trinomial coefficients", J. Amer. Math. Soc. 3 (1990) 653-669.