A065601 -id:A065601 - cp's OEIS frontend

A126093 Inverse binomial matrix applied to A110877.

1, 0, 1, 1, 2, 1, 2, 6, 4, 1, 6, 18, 15, 6, 1, 18, 57, 54, 28, 8, 1, 57, 186, 193, 118, 45, 10, 1, 186, 622, 690, 474, 218, 66, 12, 1, 622, 2120, 2476, 1856, 976, 362, 91, 14, 1, 2120, 7338, 8928, 7164, 4170, 1791, 558, 120, 16, 1

Offset: 0

Philippe Deléham, Mar 03 2007

Diagonal sums are A065601. - Philippe Deléham, Mar 05 2007

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

			Triangle begins:
     1;
     0,    1;
     1,    2,    1;
     2,    6,    4,    1;
     6,   18,   15,    6,    1;
    18,   57,   54,   28,    8,    1;
    57,  186,  193,  118,   45,   10,   1;
   186,  622,  690,  474,  218,   66,  12,   1;
   622, 2120, 2476, 1856,  976,  362,  91,  14,  1;
  2120, 7338, 8928, 7164, 4170, 1791, 558, 120, 16, 1;
Production matrix begins
  0, 1;
  1, 2, 1;
  0, 1, 2, 1;
  0, 0, 1, 2, 1;
  0, 0, 0, 1, 2, 1;
  0, 0, 0, 0, 1, 2, 1;
  0, 0, 0, 0, 0, 1, 2, 1;
  0, 0, 0, 0, 0, 0, 1, 2, 1;
  0, 0, 0, 0, 0, 0, 0, 1, 2, 1;
- _Philippe Deléham_, Nov 07 2011

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Yidong Sun and Luping Ma, Minors of a class of Riordan arrays related to weighted partial Motzkin paths, Eur. J. Comb. 39, 157-169 (2014), Table 2.2.

T[0, 0, x_, y_]:= 1; T[n_, 0, x_, y_]:= x*T[n-1,0,x,y] + T[n-1,1,x,y]; T[n_, k_, x_, y_]:= T[n, k, x, y]= If[k<0 || k>n, 0, T[n-1,k-1,x,y] + y*T[n-1,k,x,y] + T[n-1,k+1,x,y]]; Table[T[n,k,0,2], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Apr 21 2017 *)

@CachedFunction
def T(n, k, x, y):
    if (k<0 or k>n): return 0
    elif (n==0 and k==0): return 1
    elif (k==0): return x*T(n-1,0,x,y) + T(n-1,1,x,y)
    else: return T(n-1,k-1,x,y) + y*T(n-1,k,x,y) + T(n-1,k+1,x,y)
[[T(n,k,0,2) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Jan 27 2020

Triangle T(n,k), 0<=k<=n, read by rows defined by : T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0) = T(n-1,1), T(n,k) = T(n-1,k-1) + 2*T(n-1,k) + T(n-1,k+1) for k>=1.
Sum_{k=0..n} T(m,k)*T(n,k) = T(m+n,0) = A000957(m+n+1).
Sum_{k=0..n-1} T(n,k) = A026641(n), for n>=1. - Philippe Deléham, Mar 05 2007
Sum_{k=0..n} T(n,k)*(3k+1) = 4^n. - Philippe Deléham, Mar 22 2007

A065600 Triangle T(n,k) giving number of Dyck paths of length 2n with exactly k hills (0 <= k <= n).

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 6, 4, 3, 0, 1, 18, 13, 6, 4, 0, 1, 57, 40, 21, 8, 5, 0, 1, 186, 130, 66, 30, 10, 6, 0, 1, 622, 432, 220, 96, 40, 12, 7, 0, 1, 2120, 1466, 744, 328, 130, 51, 14, 8, 0, 1, 7338, 5056, 2562, 1128, 455, 168, 63, 16, 9, 0, 1, 25724, 17672, 8942, 3941, 1590, 602, 210, 76, 18, 10, 0, 1

Offset: 0

N. J. A. Sloane, Dec 02 2001

T(n,k) is the number of Łukasiewicz paths of length n having k level steps (i.e., (1,0)) on the x-axis. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,1)=2 because we have HUD and UDH, where H=(1,0), U(1,1) and D=(1,-1). - Emeric Deutsch, Jan 06 2005
The summand i*binomial(k+i,i)*binomial(2*n-2*k-2*i,n-k)/(n-k-i) in the Maple formula below counts Dyck n-paths containing k low peaks and k+i returns altogether. For example, with n=3, k=1, i=1, it counts the 2 paths UDUUDD, UUDDUD: each has k=1 low peaks and k+i=2 returns to ground level. - David Callan, Nov 02 2005
Renewal array for the Fine numbers: Riordan array (f(x)/x,f(x)) where f(x) is the g.f. for A000957. Row sums are the Catalan numbers A000108. - Paul Barry, Oct 30 2006, Jan 27 2009
T(n,k) is the number of 321-avoiding permutations of [n] having k fixed points. Example: T(4,2)=3 because we have 1243, 1324 and 2134. T(n,k) is the number of Dyck paths of semilength n having k centered tunnels. Example: T(4,2)=3 because we have UD(U)(U)(D)(D)UD, (U)UD(U)(D)UD(D) and (U)(U)UDUD(D)(D) (the extremities of the centered tunnels are shown between parentheses). - Emeric Deutsch, Sep 06 2007
Inverse of Riordan array ((1-2x)/(1-x)^2,x(1-2x)/(1-x)^2); see A124394. - Paul Barry, Jan 27 2009
Triangle read by rows, product of A033184 and A130595 considered as infinite lower triangular arrays; A065600 = A033184*A130595. - Philippe Deléham, Dec 07 2009
T(n,k) is the number of ordered, unlabeled, rooted trees with n+1 nodes that have exactly k subtrees of size 1.  A subtree of size 1 is a subtree attached to the root that consists of only a single node.  Cf. A000957 (column 1). - Geoffrey Critzer, Sep 16 2013
Also the convolution triangle of the Fine numbers A000957. - Peter Luschny, Oct 08 2022

			From _Philippe Deléham_, Feb 23 2012: (Start)
Triangle begins:
   1;
   0,  1;
   1,  0,  1;
   2,  2,  0,  1;
   6,  4,  3,  0,  1;
  18, 13,  6,  4,  0,  1;
  57, 40, 21,  8,  5,  0,  1; (End)
T(4,2)=3 because we have (UD)(UD)UUDD, (UD)UUDD(UD) and UUDD(UD)(UD), where U=(1,1), D=(1,-1) (the hills, i.e., peaks at level 1, are shown between parentheses).

Alois P. Heinz, Rows n = 0..200, flattened
E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.
Naiomi Cameron, J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.
E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.
S. Elizalde and I. Pak, Bijections for refined restricted permutations, Journal of Combinatorial Theory Ser. A, 105, 2004, 207-219.
FindStat - Combinatorial Statistic Finder, The number of centered tunnels of a Dyck path.
Shishuo Fu, Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
B. Hackl, H. Prodinger, Growing and destroying Catalan-Stanley trees, arxiv:1704.03734 [math.CO] (2017), proposition 2.1
R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 235.
A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.
Index entries for sequences related to Łukasiewicz

First columns are A000957, A065601, A294527.

T := proc(n,k) if k0, b(x-1, y-1, 0)*`if`(t*y=1, z, 1), 0)+
      `if`(y (p-> seq(coeff(p, z, i), i=0..n))(b(n+n, 0$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Nov 02 2017
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, A000957); # Peter Luschny, Oct 08 2022

t[n_, k_] := If[ kJean-François Alcover, Dec 14 2011, after Maple *)
nn=10;g=(1-(1-4x)^(1/2))/2;CoefficientList[Series[x/(1-(g-x+y x)),{x,0,nn}],{x,y}]//Grid (* Geoffrey Critzer, Sep 16 2013 *)
T[ n_, k_] := If[ k < 0 || k > n, 0, Coefficient[ SeriesCoefficient[ Series[ 2 / (1 + 2*x + Sqrt[1 - 4*x] - 2*x*y), {x, 0, n}], {x, 0, n}], y, k]]; (* Michael Somos, Jun 01 2016 *)

{T(n, k) = if( k<0 || k>n, 0, polcoeff( polcoeff( 2 / (1 + 2*x + (1 - 4*x)^(1/2) - 2*x*y) + x * O(x^n), n), k))}; /* Michael Somos, Jun 01 2016 */

See Maple line.
G.f.: (1 - (1 - 4*x)^(1/2))/(x*(3 - y + (1 - 4*x)^(1/2)*(y-1))) = Sum_{n>=0, k>=0} T(n, k)x^n*y^k. - David Callan, Aug 17 2004
G.f.: 1/(1-xy-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-.... (continued fraction). - Paul Barry, Jan 27 2009
G.f.: ((1-sqrt(1-4*x))/(3-sqrt(1-4*x)))^k = Sum_{n>=k} T(n+1,k+1)*x^n, where T(n,k) = (Sum_{i=0..n-k} (-1)^i*(k+i+1)*binomial(k+i,i)*binomial(2*n-k-i,n))/(n+1). - Vladimir Kruchinin, Dec 20 2011
T(n,k) = T(n-1,k-1) + Sum_{i>=0} T(n-1,k+1+i)*2^i. - Philippe Deléham, Feb 23 2012
G.f.: 2 / (1 + 2*x + (1 - 4*x)^(1/2) - 2*x*y). - Michael Somos, Jun 01 2016

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003

cp's OEIS Frontend

A126093 Inverse binomial matrix applied to A110877.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Sage

Formula

A065600 Triangle T(n,k) giving number of Dyck paths of length 2n with exactly k hills (0 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A294527 Number of Dyck paths of length 2n with exactly 2 hills.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A374835 Number of ternary paths of length 3*n having exactly 1 hill.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula