login
Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having the top of the rightmost column at height k.
8

%I #89 Nov 29 2022 01:31:42

%S 1,1,1,2,2,1,4,5,3,1,8,12,9,4,1,16,28,25,14,5,1,32,64,66,44,20,6,1,64,

%T 144,168,129,70,27,7,1,128,320,416,360,225,104,35,8,1,256,704,1008,

%U 968,681,363,147,44,9,1,512,1536,2400,2528,1970,1182,553,200,54,10,1,1024

%N Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having the top of the rightmost column at height k.

%C From _Gary W. Adamson_, Apr 24 2005: (Start)

%C Let A be the array

%C 1, 0, 0, 0, 0, 0, ...

%C 0, 1, 0, 0, 0, 0, ...

%C 1, 0, 1, 0, 0, 0, ...

%C 0, 2, 0, 1, 0, 0, ...

%C 1, 0, 3, 0, 1, 0, ...

%C 0, 3, 0, 4, 0, 1, ...

%C ...

%C where columns are bin(n,k) with alternating zeros. (Row sums = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...(Fibonacci numbers).) Let P = infinite lower triangular Pascal triangle matrix (A007318). Form P * A: this gives the rows of the present sequence. [Comment corrected by _Philippe Deléham_, Dec 09 2008] (End)

%C T(n,k) is the number of nondecreasing Dyck paths of semilength n, having height of rightmost peak equal to k. Example: T(4,1)=4 because we have UDUDUDUD, UDUUDDUD, UUDDUDUD and UUUDDDUD, where U=(1,1) and D=(1,-1). Sum of row n = Fibonacci(2n-1) (A001519). Basically the same as A062110.

%C T(n,k) is the number of permutations of [n] with length n-k that avoid the patterns 321 and 3412. - _Bridget Tenner_, Sep 28 2005

%C T(2*n-1,n)/n = A001003(n-1) (little Schroeder numbers). Proof with Lagrange inversion of inverse of g.f. of A001003.

%C Row sums = odd-indexed Fibonacci numbers.

%C Diagonal sums: A077998. - _Philippe Deléham_, Nov 16 2008

%C Central coefficients are A176479. Inverse is A125692. - _Paul Barry_, Apr 18 2010

%C Riordan matrix ((1-x)/(1-2x),(x-x^2)/(1-2x)). - _Emanuele Munarini_, Mar 22 2011

%C T(n,k) is the number of ideals in the fence Z(2n-1) with n-k elements of rank 0. - _Emanuele Munarini_, Mar 22 2011

%C Triangle T(n,k), 1 <= k <= n, read by rows, given by (0,1,1,0,0,0,0,0,0,0,...) DELTA (1,0,0,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - _Philippe Deléham_, Oct 30 2011

%C T(n,k) is the number of permutations of [n] for which k is equal to both the length and reflection length. - _Bridget Tenner_, Feb 22 2012

%D V. E. Hoggatt, Jr. and Marjorie Bicknell, editors: "A Primer for the Fibonacci Numbers", 1970, p. 87.

%H Michael De Vlieger, <a href="/A105306/b105306.txt">Table of n, a(n) for n = 1..11325</a> (rows 1 <= n <= 150, flattened)

%H E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)82778-1">Nondecreasing Dyck paths and q-Fibonacci numbers</a>, Discrete Math., 170, 1997, 211-217.

%H Jean-Luc Baril, Javier F. González, and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/BGR.pdf">Last symbol distribution in pattern avoiding Catalan words</a>, Univ. Bourgogne (France, 2022).

%H Eunice Y. S. Chan, Robert M. Corless, Laureano Gonzalez-Vega, J. Rafael Sendra, Juana Sendra, and Steven E. Thornton, <a href="https://arxiv.org/abs/1809.10664">Bohemian Upper Hessenberg Toeplitz Matrices</a>, arXiv:1809.10664 [cs.SC], 2018.

%H Eunice Y. S. Chan, Robert M. Corless, Laureano Gonzalez-Vega, J. Rafael Sendra, and Juana Sendra, <a href="https://arxiv.org/abs/1907.10677">Upper Hessenberg and Toeplitz Bohemians</a>, arXiv:1907.10677 [cs.SC], 2019.

%H Emeric Deutsch and H. Prodinger, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00222-6">A bijection between directed column-convex polyominoes and ordered trees of height at most three</a>, Theoretical Comp. Science, 307, 2003, 319-325.

%H Sergi Elizalde, Rigoberto Flórez, and José Luis Ramírez, <a href="https://doi.org/10.26493/1855-3974.2478.d1b">Enumerating symmetric peaks in non-decreasing Dyck paths</a>, Ars Mathematica Contemporanea (2021).

%H Milan Janjić, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Janjic/janjic93.html">Words and Linear Recurrences</a>, J. Int. Seq. 21 (2018), #18.1.4.

%H V. V. Kruchinin and D. V. Kruchinin, <a href="http://arxiv.org/abs/1206.0877">A Method for Obtaining Generating Function for Central Coefficients of Triangles</a>, arXiv preprint arXiv:1206.0877 [math.CO], 2012, and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Kruchinin/kruchinin5.html">J. Int. Seq. 15 (2012) #12.9.3</a>.

%H E. Munarini and N. Zagaglia Salvi, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00378-3">On the Rank Polynomial of the Lattice of Order Ideals of Fences and Crowns</a>, Discrete Mathematics 259 (2002), 163-177.

%H T. K. Petersen and B. E. Tenner, <a href="http://arxiv.org/abs/1202.4765">The depth of a permutation</a>, arXiv:1202.4765 [math.CO], 2012-2014..

%H M. Pétréolle, <a href="http://arxiv.org/abs/1403.1130">Characterization of Cyclically Fully commutative elements in finite and affine Coxeter Groups</a>, arXiv preprint arXiv:1403.1130 [math.GR], 2014.

%H Bridget Eileen Tenner, <a href="https://arxiv.org/abs/2001.05011">Interval structures in the Bruhat and weak orders</a>, arXiv:2001.05011 [math.CO], 2020.

%H S.-n. Zheng and S.-l. Yang, <a href="http://dx.doi.org/10.1155/2014/848374">On the-Shifted Central Coefficients of Riordan Matrices</a>, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages.

%F T(n,k) = sum(binomial(k+j, k-1)*binomial(n-k-1, j), j=0..n-k-1) (0<=k<=n). (This appears to be incorrect. - _Emanuele Munarini_, Mar 22 2011)

%F G.f.: t*z*(1-z)/(1 - 2*z - t*z*(1-z)).

%F From _Emanuele Munarini_, Mar 22 2011: (Start)

%F T(n,k) = Sum_{i=0..n-k} binomial(k+1,i)*binomial(n-i,k)*(-1)^i*2^(n-k-i).

%F T(n,k) = Sum_{i=0..n-k} binomial(k+1,i)*M(i,n-k-i)*2^(n-k-i), where M(n,k) = n*(n+1)*(n+2)*...*(n+k-1)/k!. (End)

%F T(n,k) = 2*T(n-1,k) + T(n-1,k-1) - T(n-2,k-1), T(0,0) = T(1,0) = T(1,1) = 1, T(n,k) = 0 if k>n or if k<0. - _Philippe Deléham_, Oct 30 2013

%e Triangle begins:

%e 1;

%e 1, 1;

%e 2, 2, 1;

%e 4, 5, 3, 1;

%e 8, 12, 9, 4, 1;

%e 16, 28 25, 14, 5, 1;

%e 32, 64, 66, 44, 20, 6, 1;

%e 64, 144, 168, 129, 70, 27, 7, 1;

%e ...

%e From _Paul Barry_, Apr 18 2010: (Start)

%e Production matrix is

%e 1, 1;

%e 1, 1, 1;

%e 0, 1, 1, 1;

%e -1, 0, 1, 1, 1;

%e 0, -1, 0, 1, 1, 1;

%e 2, 0, -1, 0, 1, 1, 1;

%e 0, 2, 0, -1, 0, 1, 1, 1;

%e -5, 0, 2, 0, -1, 0, 1, 1, 1;

%e 0, -5, 0, 2, 0, -1, 0, 1, 1, 1;

%e 14, 0, -5, 0, 2, 0, -1, 0, 1, 1, 1; (End)

%p T:=proc(n,k) if k<n-1 then sum(binomial(k+j,k-1)*binomial(n-k-1,j),j=0..n-k-1) elif k=n-1 then n-1 elif k=n then 1 else 0 fi end: for n from 1 to 12 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

%t t[n_, k_] := 2^(n-2*k-1)*Binomial[n, k]*Hypergeometric2F1[-k-1, -k, -n, -1]; t[n_, n_] = 1; Table[t[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jan 28 2014 *)

%o (Maxima) create_list(sum(binomial(k+1,i)*binomial(n-i,k)*(-1)^i*2^(n-k-i),i,0,n-k),n,0,8,k,0,n); /* _Emanuele Munarini_, Mar 22 2011 */

%Y Cf. A001519. Essentially the same array as A062110.

%Y Row sums = A001519(n-1), n >= 1.

%K nonn,tabl

%O 1,4

%A _Emeric Deutsch_, Apr 25 2005

%E Entry revised by _N. J. A. Sloane_, Apr 27 2007