A191528 Triangle read by rows: T(n,k) is the number of left factors of Dyck paths of length n that have k returns to the axis.

1, 1, 1, 1, 2, 1, 3, 2, 1, 6, 3, 1, 10, 6, 3, 1, 20, 10, 4, 1, 35, 20, 10, 4, 1, 70, 35, 15, 5, 1, 126, 70, 35, 15, 5, 1, 252, 126, 56, 21, 6, 1, 462, 252, 126, 56, 21, 6, 1, 924, 462, 210, 84, 28, 7, 1, 1716, 924, 462, 210, 84, 28, 7, 1, 3432, 1716, 792, 330, 120, 36, 8, 1, 6435, 3432, 1716, 792, 330, 120, 36, 8, 1

Offset: 0

Author

Emeric Deutsch, Jun 06 2011

Keywords

• nonn
• tabf

Comments

Row n contains 1+floor(n/2) entries.

Sum of entries in row n is binomial(n, floor(n/2)) =A001405(n).

T(n,0) = A001405(n-1).

Rows 0, 2, 4, ... form triangle A100100.

Rows 1, 3, 5, ... form triangle A092392.

Sum_{k>=0} k*T(n,k) = A037955(n).

From Roger Ford, Oct 16 2020: (Start)

This is an empirical observation. T(n,k) = the number of different semi-meander arch depth models with n+2 top arches and k+1 arches at depth 0. T(3,1) = the number of different semi-meander arch depth models with 5 top arches and 2 arches at depth 0.

Example: The depth of a semi-meander arch is the number of covering arches directly above the arch. The arch depth model is the number of arches at each depth starting at 0 for a specific semi-meander. The following is the arch depth models for semi-meanders with 5 top arches.

/\ /\

//\\ / \

///\\\ depth //\ \ depth

////\\\\ /\ (0)(1)(2)(3) ///\\/\\ /\ (0)(1)(2)

depth 0123 0 model= 2 1 1 1 012 1 0 model= 2 2 1

/\

//\\ /\ depth /\ /\ depth

///\\\ //\\ (0)(1)(2) //\\ //\\ /\ (0)(1)

depth 012 01 model= 2 2 1 01 01 0 model= 3 2

/\

/ \ depth

//\/\\ /\ /\ (0)(1)

depth 01 1 0 0 model= 3 2

There are 5 more semi-meanders with 5 top arches. They are reflections of the above semi-meanders over a center vertical line and they yield the same arch depth models as the semi-meanders above.

T(3,1) = 2 different models= 2 2 1 and 2 1 1 1;

T(3,2) = 1 model= 3 2 (End).

Examples

			T(6,2)=3 because we have U(D)U(D)UU, U(D)UUD(D), and UUD(D)U(D), where U=(1,1) and D=(1,-1) (the return steps to the axis are shown between parentheses).
Triangle starts:
   1:
   1;
   1, 1;
   2, 1;
   3, 2, 1;
   6, 3, 1;
  10, 6, 3, 1;
		

Links

• Indranil Ghosh, Rows 0..100, flattened

Crossrefs

Cf. A001405, A037955, A092392, A100100.

Programs

Maple

T := proc (n, k) if k <= floor((1/2)*n) then binomial(n-k-1, ceil((1/2)*n)-1) else 0 end if end proc: for n from 0 to 16 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

Mathematica

Flatten[Table[Binomial[n-k-1,Ceiling[(n/2)-1]],{n,0,16},{k,0,Floor[n/2]}]] (* Indranil Ghosh, Mar 05 2017 *)

PARI

tabf(nn) = if(n==0, print1(1,", "), {for (n=1, nn, for(k=0, floor(n/2), print1(binomial(n-k-1, ceil((n/2)-1)),", ");); print();); });
tabf(16); \\ Indranil Ghosh, Mar 05 2017

Formula

T(n,k) = binomial(n-k-1, ceiling(n/2)-1) if 0 <= k <= floor(n/2).

G.f.: G(t,z) = 1/((1-z*c)*(1-t*z^2*c)), where c = (1-sqrt(1-4*z^2))/(2*z^2) is the Catalan function with argument z^2.