cp's OEIS Frontend

A038622 Triangular array that counts rooted polyominoes.

%I A038622 #76 Aug 08 2024 06:38:34
%S A038622 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,
%T A038622 7,1,750,623,427,238,105,35,8,1,2123,1800,1288,770,378,148,44,9,1,
%U A038622 6046,5211,3858,2436,1296,570,201,54,10,1,17303,15115,11505,7590,4302,2067,825,265
%N A038622 Triangular array that counts rooted polyominoes.
%C A038622 The PARI program gives any row k and any n-th term for this triangular array in square or right triangle array format. - _Randall L Rathbun_, Jan 20 2002
%C A038622 Triangle T(n,k), 0 <= k <= n, read by rows given by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = 2*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,k+1) for k >= 1. - _Philippe Deléham_, Mar 27 2007
%C A038622 This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + y*T(n-1,k) + T(n-1,k+1) for k >= 1. Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - _Philippe Deléham_, Sep 25 2007
%C A038622 Triangle read by rows = partial sums of A064189 terms starting from the right. - _Gary W. Adamson_, Oct 25 2008
%C A038622 Column k has e.g.f. exp(x)*(Bessel_I(k,2x)+Bessel_I(k+1,2x)). - _Paul Barry_, Mar 08 2011
%H A038622 Reinhard Zumkeller, <a href="/A038622/b038622.txt">Rows n = 0..120 of triangle, flattened</a>
%H A038622 D. Gouyou-Beauchamps and G. Viennot, <a href="http://dx.doi.org/10.1016/0196-8858(88)90017-6">Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem</a>, Adv. in Appl. Math. 9 (1988), no. 3, 334-357.  See Table 1 on page 340.
%F A038622 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.
%F A038622 Riordan array ((sqrt(1-2x-3x^2)+3x-1)/(2x(1-3x)),(1-x-sqrt(1-2x-3x^2))/(2x)). Inverse of Riordan array ((1-x)/(1+x+x^2),x/(1+x+x^2)). First column is A005773(n+1). Row sums are 3^n (A000244). If L=A038622, then L*L' is the Hankel matrix for A005773(n+1), where L' is the transpose of L. - _Paul Barry_, Sep 18 2006
%F A038622 T(n,k) = GegenbauerC(n-k,-n+1,-1/2) + GegenbauerC(n-k-1,-n+1,-1/2). In this form also the missing first column of the triangle 1,1,1,3,7,19,... (cf. A002426) can be computed. - _Peter Luschny_, May 12 2016
%F A038622 From _Peter Bala_, Jul 12 2021: (Start)
%F A038622 T(n,k) = Sum_{j = k..n} binomial(n,j)*binomial(j,floor((j-k)/2)).
%F A038622 Matrix product of Riordan arrays ( 1/(1 - x), x/(1 - x) ) * ( (1 - x*c(x^2))/(1 - 2*x), x*c(x^2) ) = A007318 * A061554 (triangle version), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.
%F A038622 Triangle equals A007318^(-1) * A092392 * A007318. (End)
%F A038622 The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 + x)*(1 + x + x^2)^n expanded about the point x = 0. - _Peter Bala_, Sep 06 2022
%e A038622 From _Paul Barry_, Mar 08 2011: (Start)
%e A038622 Triangle begins
%e A038622      1;
%e A038622      2,    1;
%e A038622      5,    3,    1;
%e A038622     13,    9,    4,   1;
%e A038622     35,   26,   14,   5,   1;
%e A038622     96,   75,   45,  20,   6,   1;
%e A038622    267,  216,  140,  71,  27,   7,  1;
%e A038622    750,  623,  427, 238, 105,  35,  8, 1;
%e A038622   2123, 1800, 1288, 770, 378, 148, 44, 9, 1;
%e A038622 Production matrix is
%e A038622   2, 1,
%e A038622   1, 1, 1,
%e A038622   0, 1, 1, 1,
%e A038622   0, 0, 1, 1, 1,
%e A038622   0, 0, 0, 1, 1, 1,
%e A038622   0, 0, 0, 0, 1, 1, 1,
%e A038622   0, 0, 0, 0, 0, 1, 1, 1,
%e A038622   0, 0, 0, 0, 0, 0, 1, 1, 1,
%e A038622   0, 0, 0, 0, 0, 0, 0, 1, 1, 1
%e A038622 (End)
%p A038622 T := (n,k) -> simplify(GegenbauerC(n-k,-n+1,-1/2)+GegenbauerC(n-k-1,-n+1,-1/2)):
%p A038622 for n from 1 to 9 do seq(T(n,k),k=1..n) od; # _Peter Luschny_, May 12 2016
%t A038622 nmax = 10; t[n_ /; n > 0, k_ /; k >= 1] := t[n, k] = t[n-1, k-1] + t[n-1, k] + t[n-1, k+1]; t[0, 0] = 1; t[0, _] = 0; t[_?Negative, _?Negative] = 0; t[n_, 0] := 2 t[n-1, 0] + t[n-1, 1]; Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]](* _Jean-François Alcover_, Nov 09 2011 *)
%o A038622 (PARI) s=[0,1]; {A038622(n,k)=if(n==0,1,t=(2*(n+k)*(n+k-1)*s[2]+3*(n+k-1)*(n+k-2)*s[1])/((n+2*k-1)*n); s[1]=s[2]; s[2]=t; t)}
%o A038622 (Haskell)
%o A038622 import Data.List (transpose)
%o A038622 a038622 n k = a038622_tabl !! n !! k
%o A038622 a038622_row n = a038622_tabl !! n
%o A038622 a038622_tabl = iterate (\row -> map sum $
%o A038622    transpose [tail row ++ [0,0], row ++ [0], [head row] ++ row]) [1]
%o A038622 -- _Reinhard Zumkeller_, Feb 26 2013
%Y A038622 Cf. A005773 (1st column), A005774 (2nd column), A005775, A066822, A000244 (row sums).
%Y A038622 Cf. A064189, A007318, A061554, A092392.
%K A038622 nonn,tabl,easy,nice
%O A038622 0,2
%A A038622 _N. J. A. Sloane_, torsten.sillke(AT)lhsystems.com
%E A038622 More terms from _David W. Wilson_