A105306 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.

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, 144, 168, 129, 70, 27, 7, 1, 128, 320, 416, 360, 225, 104, 35, 8, 1, 256, 704, 1008, 968, 681, 363, 147, 44, 9, 1, 512, 1536, 2400, 2528, 1970, 1182, 553, 200, 54, 10, 1, 1024

Offset: 1

Author

Emeric Deutsch, Apr 25 2005

Keywords

• nonn
• tabl

Comments

From Gary W. Adamson, Apr 24 2005: (Start)

Let A be the array

1, 0, 0, 0, 0, 0, ...

0, 1, 0, 0, 0, 0, ...

1, 0, 1, 0, 0, 0, ...

0, 2, 0, 1, 0, 0, ...

1, 0, 3, 0, 1, 0, ...

0, 3, 0, 4, 0, 1, ...

...

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)

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.

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

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

Row sums = odd-indexed Fibonacci numbers.

Diagonal sums: A077998. - Philippe Deléham, Nov 16 2008

Central coefficients are A176479. Inverse is A125692. - Paul Barry, Apr 18 2010

Riordan matrix ((1-x)/(1-2x),(x-x^2)/(1-2x)). - Emanuele Munarini, Mar 22 2011

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

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

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

Examples

			Triangle begins:
   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, 144, 168, 129,  70,  27,   7,   1;
  ...
From _Paul Barry_, Apr 18 2010: (Start)
Production matrix is
   1,  1;
   1,  1,  1;
   0,  1,  1,  1;
  -1,  0,  1,  1,  1;
   0, -1,  0,  1,  1,  1;
   2,  0, -1,  0,  1,  1,  1;
   0,  2,  0, -1,  0,  1,  1,  1;
  -5,  0,  2,  0, -1,  0,  1,  1,  1;
   0, -5,  0,  2,  0, -1,  0,  1,  1,  1;
  14,  0, -5,  0,  2,  0, -1,  0,  1,  1,  1; (End)
		

References

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

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150, flattened)
• E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
• Jean-Luc Baril, Javier F. González, and José L. Ramírez, Last symbol distribution in pattern avoiding Catalan words, Univ. Bourgogne (France, 2022).
• Eunice Y. S. Chan, Robert M. Corless, Laureano Gonzalez-Vega, J. Rafael Sendra, Juana Sendra, and Steven E. Thornton, Bohemian Upper Hessenberg Toeplitz Matrices, arXiv:1809.10664 [cs.SC], 2018.
• Eunice Y. S. Chan, Robert M. Corless, Laureano Gonzalez-Vega, J. Rafael Sendra, and Juana Sendra, Upper Hessenberg and Toeplitz Bohemians, arXiv:1907.10677 [cs.SC], 2019.
• Emeric Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.
• Sergi Elizalde, Rigoberto Flórez, and José Luis Ramírez, Enumerating symmetric peaks in non-decreasing Dyck paths, Ars Mathematica Contemporanea (2021).
• Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 9-10, 19.
• Milan Janjić, Words and Linear Recurrences, J. Int. Seq. 21 (2018), #18.1.4.
• V. V. Kruchinin and D. V. Kruchinin, A Method for Obtaining Generating Function for Central Coefficients of Triangles, arXiv preprint arXiv:1206.0877 [math.CO], 2012, and J. Int. Seq. 15 (2012) #12.9.3.
• E. Munarini and N. Zagaglia Salvi, On the Rank Polynomial of the Lattice of Order Ideals of Fences and Crowns, Discrete Mathematics 259 (2002), 163-177.
• T. K. Petersen and B. E. Tenner, The depth of a permutation, arXiv:1202.4765 [math.CO], 2012-2014..
• M. Pétréolle, Characterization of Cyclically Fully commutative elements in finite and affine Coxeter Groups, arXiv preprint arXiv:1403.1130 [math.GR], 2014.
• Bridget Eileen Tenner, Interval structures in the Bruhat and weak orders, arXiv:2001.05011 [math.CO], 2020.
• S.-n. Zheng and S.-l. Yang, On the-Shifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages.

Crossrefs

Cf. A001519. Essentially the same array as A062110.

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

Programs

Maple

T:=proc(n,k) if k
				

Mathematica

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 *)

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 */

Formula

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)

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

From Emanuele Munarini, Mar 22 2011: (Start)

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

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)

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

Extensions

Entry revised by N. J. A. Sloane, Apr 27 2007