A120986 -id:A120986 - 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).

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

Emeric Deutsch, Jun 24 2005

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.
Row reverse of A120986. Described in A173020 as generalized Runyon numbers R_{n,k}^(2).
(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

			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;
  ...

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.

Cf. A000108, A001764, A025174, A120986.

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

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

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[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 *)

T(n,k) = binomial(n, k)*binomial(2*n, k-1)/n; \\ Andrew Howroyd, Nov 06 2017

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

T <- function(n, k) {
  choose(n, k)*choose(2*n, k - 1)/n
} # Indranil Ghosh, Nov 07 2017

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

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

A102537 Triangle T(n,k) read by rows: (1/n) * C(2n+k,k-1) * C(n,k); n, k >= 1.

Original entry on oeis.org

1, 1, 3, 1, 8, 12, 1, 15, 55, 55, 1, 24, 156, 364, 273, 1, 35, 350, 1400, 2380, 1428, 1, 48, 680, 4080, 11628, 15504, 7752, 1, 63, 1197, 9975, 41895, 92169, 100947, 43263, 1, 80, 1960, 21560, 123970, 396704, 708400, 657800, 246675, 1, 99, 3036, 42504

Offset: 1

Ralf Stephan, Jan 14 2005

Number of dissections of a convex (2n+2)-gon by k-1 noncrossing diagonals into (2j+2)-gons, 1 <= j <= n-1.
Apparently, a signed, refined version of this array is given on page 65 of the Einziger link, related to the antipode of a Hopf algebra. - Tom Copeland, May 19 2015
The f-vectors of the simplicial noncrossing hypertree complexes of McCammond (p. 15). The reduced Euler characteristics are the signed Catalan numbers A000108. - Tom Copeland, May 19 2017
The rows seem to give (up to sign) the coefficients in the expansion of the integer-valued polynomial ((x+1)*(x+2)*...*(x+2n+1))*((x+n+2)*(x+n+3)*...*(x+2n)) / ((2n+1)!*(n)!) in the basis made of the binomial(x+i,i). - F. Chapoton, Nov 01 2022
Chapoton's observation above is correct: the precise expansion is ((x+1)*(x+2)*...*(x+2n+1))*((x+n+2)*(x+n+3)*...*(x+2n)) / ((2n+1)!*n!) = Sum_{k = 1..n} (-1)^(k+1)*T(n,n+1-k)*binomial(x+3*n+1-k, 3*n+1-k), as can be verified using the WZ algorithm. For example, n = 3 gives (x+1)*(x+2)*(x+3)*(x+4)*(x+5)*(x+6)*(x+7)*(x+5)(x+6)/(7!*3!) = 12*binomial(x+9,9) - 8*binomial(x+8,8) + binomial(x+7,7). - Peter Bala, Jun 25 2023

			Triangle begins
  1;
  1,  3;
  1,  8,   12;
  1, 15,   55,    55;
  1, 24,  156,   364,    273;
  1, 35,  350,  1400,   2380,   1428;
  1, 48,  680,  4080,  11628,  15504,   7752;
  1, 63, 1197,  9975,  41895,  92169, 100947,  43263;
  1, 80, 1960, 21560, 123970, 396704, 708400, 657800, 246675;

Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150).
H. Einziger, Incidence Hopf algebras: Antipodes, forest formulas, and noncrossing partitions, Dissertation (2010), George Washington University.
J. McCammond, Noncrossing Hypertrees, 2015.
Jean-Christophe Novelli and Jean-Yves Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
Jean-Christophe Novelli and Jean-Yves Thibon, Noncommutative Symmetric Functions and Lagrange Inversion II: Noncrossing partitions and the Farahat-Higman algebra, arXiv:2106.08257 [math.CO], 2021-2022.
E. Tzanaki, Polygon dissections and some generalizations of cluster complexes, arXiv:math/0501100 [math.CO], 2005.

Left-hand columns include A005563. Right-hand columns include essentially A001764 and A013698.
Row sums are in A003168.
Cf. A000108, A120986.
Cf. A243662 for rows reversed.

[[1/n * Binomial(2*n+k,k-1) * Binomial(n,k): k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, May 20 2015

Table[1/n*Binomial[2 n + k, k - 1] Binomial[n, k], {n, 10}, {k, n}] // Flatten (* Michael De Vlieger, May 20 2017 *)

A110608 Number triangle T(n,k) = binomial(n,k)*binomial(2n,n-k).

Original entry on oeis.org

1, 2, 1, 6, 8, 1, 20, 45, 18, 1, 70, 224, 168, 32, 1, 252, 1050, 1200, 450, 50, 1, 924, 4752, 7425, 4400, 990, 72, 1, 3432, 21021, 42042, 35035, 12740, 1911, 98, 1, 12870, 91520, 224224, 244608, 127400, 31360, 3360, 128, 1, 48620, 393822, 1145664, 1559376

Offset: 0

Paul Barry, Jul 30 2005

First column is A000984. Second column is A110609 = n^2*A000108. Row sums are A005809.

			Triangle begin
n\k|   0     1     2    3   4   5
---------------------------------
0  |   1
1  |   2     1
2  |   6     8     1
3  |  20    45    18    1
4  |  70   224   168   32   1
5  | 252  1050  1200  450  50   1
...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Cf. A000108, A000984, A005809 (row sums), A008459, A110609 (column 2), A120986.

Flatten[Table[Table[Binomial[n,k]Binomial[2n,n-k],{k,0,n}],{n,0,10}]] (* Harvey P. Dale, Aug 10 2011 *)

B(x,y):=(sqrt(-x*(4*x^2*y^3+(-12*x^2-8*x)*y^2+(12*x^2-20*x+4)*y-4*x^2+x))/(2*3^(3/2))-(x*(18*y+9)-2)/54)^(1/3);
C(x,y):=-B(x,y)-(x*(3*y-3)+1)/(9*B(x,y))-1/3;
A(x,y):=x*diff(C(x,y),x)*(-1/C(x,y)+1/(1+C(x,y)));
taylor(A(x,y),x,0,7,y,0,7); /* Vladimir Kruchinin, Sep 24 2018 */

for(n=0,10, for(k=0,n, print1(binomial(n,k)*binomial(2*n,n-k), ", "))) \\ G. C. Greubel, Sep 01 2017

From Peter Bala, Oct 13 2015: (Start)
n-th row polynomial R(n,t) = [x^n] ( (1 + t*x)*(1 + x)^2 )^n.
Cf. A008459, whose n-th row polynomial is equal to [x^n] ( (1 + t*x)*(1 + x) )^n.
exp( Sum_{n >= 1} R(n,t)*x^n/n ) = 1 + (2 + t)*x + (5 + 6*t + t^2)*x^2 + ... is the o.g.f. for A120986. (End)

A338135 Irregular triangle read by rows: Row p gives number of non-overlapping clusters of 2q-plets joining 2p points on a circle, i.e., number of noncrossing partitions from A134264 with h_k for k odd replaced by zero.

Original entry on oeis.org

1, 1, 2, 1, 6, 5, 1, 8, 4, 28, 14, 1, 10, 10, 45, 45, 120, 42, 1, 12, 12, 6, 66, 132, 22, 220, 330, 495, 132, 1, 14, 14, 14, 91, 182, 91, 91, 364, 1092, 364, 1001, 2002, 2002, 429

Offset: 1

Tom Copeland, Oct 11 2020

This combinatorial problem arises in relating connected and disconnected Green functions associated to a "zero-dimensional" quantum field theory presented by Brezin et al. in "Planar Diagrams" via Eqn. 31 on p. 42.
Appears to be a refinement of A120986 and A108767 in that summing the coefficients of partitions with the same sum of exponents gives the rows or reverse rows of the two entries; for example, row 4 here becomes x + 8 xx + 4 x^2 + 28 x^2x + 14 x^4 = x + 12 x^2 + 28 x^3 + 14 x^4, which is row 4 of A108767. In short, replace each g_k or (k) by x in the formula section here to obtain the coarser entry or its reverse from this refined entry, apparently.
This also gives the relationship between moments and free cumulants in free probability theory restricted to an even number of noncrossing partitions as given by restricting the similar enumeration formuia on p. 34 of Novak and LaCroix to b_{2n} = G_{2n} and K_{2q} = g_{2q}. This is consistent with setting h_k to zero for odd k in A134264, e.g., doing so for the coefficients of t^7 for g(t) there gives G_6 here.
A125181 is another version of A134264, providing interpretations in terms of Dyck paths and trees.

			row 1: G_2  = g_2
row 2: G_4  = g_4  +  2 g_2^2
row 3: G_6  = g_6  +  6 g_2 g_4 +  5 g_2^3
row 4: G_8  = g_8  +  8 g_2 g_6 +  4 g_4^2   +  28 g_2^2 g_4 + 14 g_2^4
row 5: G_10 = g_10 + 10 g_2 g_8 + 10 g_4 g_6 +  45 g_2^2 g_6 + 45 g_2 g_4^2
              + 120 g_2^3 g_4  + 42 g_2^5
_____________
In the notation of Abramowitz and Stegun p. 831 with indices of the partitions above divided by 2;
R_1  = (1)
R_2  = (2)  +  2 (1)^2
R_3  = (3)  +  6 (1) (2) +  5 (1)^3
R_4  = (4)  +  8 (1) (3) +  4 (2)^2   +  28 (1)^2 (2) + 14 (1)^4
R_5  = (5)  + 10 (1) (4) + 10 (2) (3) +  45 (1)^2 (3) + 45 (1) (2)^2
        + 120 (1)^3 (2) + 42 (1)^5
______________

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
E. Brezin, C. Itzykson, G. Parisi, and J. B. Zuber, Planar Diagrams, Comm. Math. Phys., 59, p. 35-51, Springer-Verlag, 1978, (link via Project Euclid).
Freddy Cachazo and Bruno Giménez Umbert, Connecting Scalar Amplitudes using The Positive Tropical Grassmannian, arXiv:2205.02722 [hep-th], 2022.
J. Novak and M. LaCroix, Three lectures on free probability, arXiv:1205.2097 [math.CO], 2012.

Cf. A000108, A120986, A108767, A125181, A134264.

Table[(2 n)!/((2 n + 1 - Length@p)! Product[r!, {r, Last /@ Tally[p]}]), {n, 5}, {p, Sort[Sort /@ IntegerPartitions[n]]}] // Flatten (* Andrey Zabolotskiy, Mar 07 2024 *)

Under the constraint 2p = Sum_{q} 2q r_q, then G_{2p} = Sum_{r_q >= 0} [(2p)! / (2p + 1 - Sum_{q} r_q)! ] (g_2^r_1 /(r_1)!) (g_4^r_2 / (r_2)!) ... (g_{2q}^r_q / (r_q)!) where g_{2k} are the connected Green functions.
With R_p = G_{2p} and N_q = g_{2q}, then R_p = Sum_{r_q >= 0} [(2p)! / (2p + 1 - Sum_{q} r_q)! ] (N_1^r_1 /(r_1)!) (N_2^r_2 / (r_2)!) ... (N_{q}^r_q / (r_q)!) where N_q are the partitions in Abramowitz and Stegun on p. 831.
Coefficients of the final terms g_{2}^p = (1)^p are the Catalan numbers A000108.

Rows 6-7 from Andrey Zabolotskiy, Mar 07 2024

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

R

Sage

Formula

A102537 Triangle T(n,k) read by rows: (1/n) * C(2n+k,k-1) * C(n,k); n, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

A110608 Number triangle T(n,k) = binomial(n,k)*binomial(2n,n-k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

A338135 Irregular triangle read by rows: Row p gives number of non-overlapping clusters of 2q-plets joining 2p points on a circle, i.e., number of noncrossing partitions from A134264 with h_k for k odd replaced by zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions