login
Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(1,1), d=(1,-2) and have k peaks (i.e., ud's).
9

%I #79 Feb 26 2024 11:01:11

%S 1,1,2,1,6,5,1,12,28,14,1,20,90,120,42,1,30,220,550,495,132,1,42,455,

%T 1820,3003,2002,429,1,56,840,4900,12740,15288,8008,1430,1,72,1428,

%U 11424,42840,79968,74256,31824,4862,1,90,2280,23940,122094,325584,465120

%N Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(1,1), d=(1,-2) and have k peaks (i.e., ud's).

%C Row sums yield A001764.

%C From _Peter Bala_, Sep 16 2012: (Start)

%C The number of 2-Dyck paths of order n with k peaks (Cigler). A 2-Dyck path of order n is a lattice path from (0,0) to (2*n,n) with steps (0,1) (North) and (1,0) (East) that never goes below the diagonal {2*i,i} 0 <= i <= n. A peak is a consecutive North East pair.

%C Row reverse of A120986. Described in A173020 as generalized Runyon numbers R_{n,k}^(2).

%C (End)

%C From _Alexander Burstein_, Jun 15 2020: (Start)

%C T(n,k) is the number of paths from (0,0) to (3n,0) that stay on or above the horizontal axis, with unit steps u=(1,1) and d=(1,-2), that have n+1-k peaks at even height.

%C T(n,k) is also the number of paths from (0,0) to (3n,0) that stay on or above the horizontal axis, with unit steps u=(1,1) and d=(1,-2), that have n-k peaks at odd height. (End)

%C An apparent refinement is A338135. - _Tom Copeland_, Oct 12 2020

%H Andrew Howroyd, <a href="/A108767/b108767.txt">Table of n, a(n) for n = 1..1275</a>

%H Alexander Burstein, <a href="https://arxiv.org/abs/2009.00760">Distribution of peak heights modulo k and double descents on k-Dyck paths</a>, arXiv preprint arXiv:2009.00760 [math.CO], 2020.

%H Frédéric Chapoton and Philippe Nadeau, <a href="http://www.mat.univie.ac.at/~slc/wpapers/FPSAC2017/37%20Chapoton%20Nadeau.pdf">Combinatorics of the categories of noncrossing partitions</a>, Séminaire Lotharingien de Combinatoire 78B (2017), Article #37.

%H J. Cigler, <a href="https://doi.org/10.1016/S0195-6698(87)80030-6">Some remarks on Catalan families</a>, European J. Combin., 8(3): 261-267.

%H J.-C. Novelli and J.-Y. Thibon, <a href="http://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv preprint arXiv:1403.5962 [math.CO], 2014-2020. See Fig. 5.

%H Chao-Jen Wang, <a href="http://people.brandeis.edu/~gessel/homepage/students/wangthesis.pdf">Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords</a>, Thesis, 2011.

%H Tad White, <a href="https://arxiv.org/abs/2401.01462">Quota Trees</a>, arXiv:2401.01462 [math.CO], 2024. See p. 20.

%F T(n, k) = binomial(n, k)*binomial(2*n, k-1)/n.

%F T(n, n) = A000108(n) (the Catalan numbers).

%F Sum_{k=1..n} k*T(n,k) = A025174(n).

%F G.f.: T-1, where T = T(t, z) satisfies T = 1 + z*T^2*(T - 1 + t).

%F From _Peter Bala_, Oct 22 2008: (Start)

%F Define a functional I on formal power series of the form f(x) = 1 + ax + bx^2 + ... by the following iterative process. Define inductively f^(1)(x) = f(x) and f^(n+1)(x) = f(x*f^(n)(x)) for n >= 1. Then set I(f(x)) = Limit_{n -> oo} f^(n)(x) in the x-adic topology on the ring of formal power series; the operator I may also be defined by I(f(x)) := 1/x*series reversion of x/f(x).

%F The o.g.f. for the array of Narayana numbers A001263 is I(1 + t*x + t*x^2 + t*x^3 + ...) = 1 + t*x + (t + t^2)*x^2 + (t + 3*t^2 + t^3)*x^3 + ... . The o.g.f. for the current array is IoI(1 + t*x + t*x^2 + t*x^3 + ...) = 1 + t*x + (t + 2*t^2)*x^2 + (t + 6*t^2 + 5*t^3)*x^3 + ... . Cf. A132081 and A141618. Alternatively, the o.g.f. of this array can be obtained from a single application of I, namely, form I(1 + t*x^2 + t*x^4 + t*x^6 + ...) = 1 + t*x^2 + (t + 2*t^2)*x^4 + (t + 6*t^2 + 5*t^3)*x^6 + ... and then replace x by sqrt(x). This is a particular case of the general result that forming the n-fold composition I^(n)(f(x)) and then replacing x with x^n produces the same result as I(f(x^n)). (End)

%F O.g.f. is series reversion with respect to x of x/((1+x)*(1+x*u)^2). Cf. A173020. - _Peter Bala_, Sep 12 2012

%F n-th row polynomial = x * hypergeom([1 - n, -2*n], [2], x). - _Peter Bala_, Aug 30 2023

%e T(3,2)=6 because we have uuduuuudd, uuuduuudd, uuuuduudd, uuuudduud, uuuuududd and uuuuuddud.

%e Triangle starts:

%e 1;

%e 1, 2;

%e 1, 6, 5;

%e 1, 12, 28, 14;

%e 1, 20, 90, 120, 42;

%e 1, 30, 220, 550, 495, 132;

%e 1, 42, 455, 1820, 3003, 2002, 429;

%e ...

%p T:=(n,k)->binomial(n,k)*binomial(2*n,k-1)/n: for n from 1 to 10 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

%t T[n_, k_] := Binomial[n, k]*Binomial[2*n, k - 1]/n;

%t Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Nov 11 2017, from Maple *)

%o (PARI) T(n,k) = binomial(n, k)*binomial(2*n, k-1)/n; \\ _Andrew Howroyd_, Nov 06 2017

%o (Python)

%o from sympy import binomial

%o def T(n, k): return binomial(n, k)*binomial(2*n, k - 1)//n

%o for n in range(1, 21): print([T(n, k) for k in range(1, n + 1)]) # _Indranil Ghosh_, Nov 07 2017

%o (R)

%o T <- function(n, k) {

%o choose(n, k)*choose(2*n, k - 1)/n

%o } # _Indranil Ghosh_, Nov 07 2017

%o (Sage)

%o def A108767(n,k,m): return binomial(n,k)*binomial(m*n,k-1)/n

%o flatten([[A108767(n,k,2) for k in (1..n)] for n in (1..12)]) # _G. C. Greubel_, Feb 20 2021

%o (Magma)

%o A108767:= func< n,k,m | Binomial(n,k)*Binomial(m*n,k-1)/n >;

%o [A108767(n,k,2): k in [1..n], n in [1..12]]; // _G. C. Greubel_, Feb 20 2021

%Y Cf. A000108, A001764, A025174, A120986.

%Y Runyon numbers R_{n,k}^(m): A010054 (m=0), A001263 (m=1), this sequence (m=2), A173020 (m=3).

%K nonn,tabl

%O 1,3

%A _Emeric Deutsch_, Jun 24 2005