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).
1, 1, 2, 1, 6, 5, 1, 12, 28, 14, 1, 20, 90, 120, 42, 1, 30, 220, 550, 495, 132, 1, 42, 455, 1820, 3003, 2002, 429, 1, 56, 840, 4900, 12740, 15288, 8008, 1430, 1, 72, 1428, 11424, 42840, 79968, 74256, 31824, 4862, 1, 90, 2280, 23940, 122094, 325584, 465120
Offset: 1
Examples
T(3,2)=6 because we have uuduuuudd, uuuduuudd, uuuuduudd, uuuudduud, uuuuududd and uuuuuddud. Triangle starts: 1; 1, 2; 1, 6, 5; 1, 12, 28, 14; 1, 20, 90, 120, 42; 1, 30, 220, 550, 495, 132; 1, 42, 455, 1820, 3003, 2002, 429; ...
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..1275
- Alexander Burstein, Distribution of peak heights modulo k and double descents on k-Dyck paths, arXiv preprint arXiv:2009.00760 [math.CO], 2020.
- Frédéric Chapoton and Philippe Nadeau, Combinatorics of the categories of noncrossing partitions, Séminaire Lotharingien de Combinatoire 78B (2017), Article #37.
- J. Cigler, Some remarks on Catalan families, European J. Combin., 8(3): 261-267.
- J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014-2020. See Fig. 5.
- Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords, Thesis, 2011.
- Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 20.
Crossrefs
Programs
-
Magma
A108767:= func< n,k,m | Binomial(n,k)*Binomial(m*n,k-1)/n >; [A108767(n,k,2): k in [1..n], n in [1..12]]; // G. C. Greubel, Feb 20 2021
-
Maple
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
-
Mathematica
T[n_, k_] := Binomial[n, k]*Binomial[2*n, k - 1]/n; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 11 2017, from Maple *) -
PARI
T(n,k) = binomial(n, k)*binomial(2*n, k-1)/n; \\ Andrew Howroyd, Nov 06 2017
-
Python
from sympy import binomial def T(n, k): return binomial(n, k)*binomial(2*n, k - 1)//n for n in range(1, 21): print([T(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, Nov 07 2017
-
R
T <- function(n, k) { choose(n, k)*choose(2*n, k - 1)/n } # Indranil Ghosh, Nov 07 2017 -
Sage
def A108767(n,k,m): return binomial(n,k)*binomial(m*n,k-1)/n flatten([[A108767(n,k,2) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, Feb 20 2021
Formula
T(n, k) = binomial(n, k)*binomial(2*n, k-1)/n.
T(n, n) = A000108(n) (the Catalan numbers).
Sum_{k=1..n} k*T(n,k) = A025174(n).
G.f.: T-1, where T = T(t, z) satisfies T = 1 + z*T^2*(T - 1 + t).
From Peter Bala, Oct 22 2008: (Start)
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).
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)
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
n-th row polynomial = x * hypergeom([1 - n, -2*n], [2], x). - Peter Bala, Aug 30 2023
Comments