OFFSET
1,3
COMMENTS
Row sums yield A001764.
From Peter Bala, Sep 16 2012: (Start)
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.
(End)
From Alexander Burstein, Jun 15 2020: (Start)
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.
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)
An apparent refinement is A338135. - Tom Copeland, Oct 12 2020
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.
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
EXAMPLE
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;
...
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 *)
PROG
(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
(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
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jun 24 2005
STATUS
approved