cp's OEIS Frontend

A108767 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).

%I A108767 #79 Feb 26 2024 11:01:11
%S A108767 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 A108767 1820,3003,2002,429,1,56,840,4900,12740,15288,8008,1430,1,72,1428,
%U A108767 11424,42840,79968,74256,31824,4862,1,90,2280,23940,122094,325584,465120
%N A108767 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 A108767 Row sums yield A001764.
%C A108767 From _Peter Bala_, Sep 16 2012: (Start)
%C A108767 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 A108767 Row reverse of A120986. Described in A173020 as generalized Runyon numbers R_{n,k}^(2).
%C A108767 (End)
%C A108767 From _Alexander Burstein_, Jun 15 2020: (Start)
%C A108767 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 A108767 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 A108767 An apparent refinement is A338135. - _Tom Copeland_, Oct 12 2020
%H A108767 Andrew Howroyd, <a href="/A108767/b108767.txt">Table of n, a(n) for n = 1..1275</a>
%H A108767 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 A108767 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 A108767 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 A108767 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 A108767 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 A108767 Tad White, <a href="https://arxiv.org/abs/2401.01462">Quota Trees</a>, arXiv:2401.01462 [math.CO], 2024. See p. 20.
%F A108767 T(n, k) = binomial(n, k)*binomial(2*n, k-1)/n.
%F A108767 T(n, n) = A000108(n) (the Catalan numbers).
%F A108767 Sum_{k=1..n} k*T(n,k) = A025174(n).
%F A108767 G.f.: T-1, where T = T(t, z) satisfies T = 1 + z*T^2*(T - 1 + t).
%F A108767 From _Peter Bala_, Oct 22 2008: (Start)
%F A108767 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 A108767 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 A108767 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 A108767 n-th row polynomial = x * hypergeom([1 - n, -2*n], [2], x). - _Peter Bala_, Aug 30 2023
%e A108767 T(3,2)=6 because we have uuduuuudd, uuuduuudd, uuuuduudd, uuuudduud, uuuuududd and uuuuuddud.
%e A108767 Triangle starts:
%e A108767   1;
%e A108767   1,  2;
%e A108767   1,  6,   5;
%e A108767   1, 12,  28,   14;
%e A108767   1, 20,  90,  120,   42;
%e A108767   1, 30, 220,  550,  495,  132;
%e A108767   1, 42, 455, 1820, 3003, 2002, 429;
%e A108767   ...
%p A108767 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 A108767 T[n_, k_] := Binomial[n, k]*Binomial[2*n, k - 1]/n;
%t A108767 Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Nov 11 2017, from Maple *)
%o A108767 (PARI) T(n,k) = binomial(n, k)*binomial(2*n, k-1)/n; \\ _Andrew Howroyd_, Nov 06 2017
%o A108767 (Python)
%o A108767 from sympy import binomial
%o A108767 def T(n, k): return binomial(n, k)*binomial(2*n, k - 1)//n
%o A108767 for n in range(1, 21): print([T(n, k) for k in range(1, n + 1)]) # _Indranil Ghosh_, Nov 07 2017
%o A108767 (R)
%o A108767 T <- function(n, k) {
%o A108767   choose(n, k)*choose(2*n, k - 1)/n
%o A108767 } # _Indranil Ghosh_, Nov 07 2017
%o A108767 (Sage)
%o A108767 def A108767(n,k,m): return binomial(n,k)*binomial(m*n,k-1)/n
%o A108767 flatten([[A108767(n,k,2) for k in (1..n)] for n in (1..12)]) # _G. C. Greubel_, Feb 20 2021
%o A108767 (Magma)
%o A108767 A108767:= func< n,k,m | Binomial(n,k)*Binomial(m*n,k-1)/n >;
%o A108767 [A108767(n,k,2): k in [1..n], n in [1..12]]; // _G. C. Greubel_, Feb 20 2021
%Y A108767 Cf. A000108, A001764, A025174, A120986.
%Y A108767 Runyon numbers R_{n,k}^(m): A010054 (m=0), A001263 (m=1), this sequence (m=2), A173020 (m=3).
%K A108767 nonn,tabl
%O A108767 1,3
%A A108767 _Emeric Deutsch_, Jun 24 2005