A002057 -id:A002057 - cp's OEIS frontend

A259476 Cayley's triangle of V numbers; triangle V(n,k), n >= 4, n <= k <= 2*n-4, read by rows.

1, 2, 4, 3, 14, 14, 4, 32, 72, 48, 5, 60, 225, 330, 165, 6, 100, 550, 1320, 1430, 572, 7, 154, 1155, 4004, 7007, 6006, 2002, 8, 224, 2184, 10192, 25480, 34944, 24752, 7072, 9, 312, 3822, 22932, 76440, 148512, 167076, 100776, 25194, 10, 420, 6300, 47040, 199920, 514080, 813960, 775200, 406980, 90440, 11, 550, 9900, 89760, 471240, 1534896, 3197700, 4263600, 3517470, 1634380, 326876

Offset: 4

N. J. A. Sloane, Jul 03 2015

			Triangle begins:
  1;
     2, 4;
        3, 14, 14;
            4, 32, 72,  48;
                5, 60, 225, 330,  165;
                    6, 100, 550, 1320, 1430, 572;
  ...

A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff.

Diagonals give A002057, A002058, A002059, A002060.

Row sums give A065096 (with a different offset).

V := proc(n,x)
    local X,g,i ;
    X := x^2/(1-x) ;
    g := X^n ;
    for i from 1 to n-2 do
        g := diff(g,x) ;
    end do;
    x^2*g*2*(n-1)/n! ;
end proc;
A259476 := proc(n,k)
    V(k-n+2,x) ;
    coeftayl(%,x=0,n+2) ;
end proc:
for n from 4 to 14 do
    for k from n to 2*n-4 do
        printf("%d,",A259476(n,k)) ;
    end do:
    printf("\n") ;
end do: # R. J. Mathar, Jul 09 2015

T[n_, m_] := 2 Binomial[m, n] Binomial[n-2, m-n+2]/(n-2);
Table[T[n, m], {n, 4, 14}, {m, n, 2n-4}] // Flatten (* Jean-François Alcover, Apr 15 2023, after Vladimir Kruchinin *)

T(n,m):=if n<4 then 0 else (2*binomial(m,n)*binomial(n-2,m-n+2))/(n-2); /* Vladimir Kruchinin, Jan 27 2022 */

G.f.: (1-x*y*(1+2*y)-sqrt(1-2*x*y*(1+2*y)+x^2*y^2))^2/(4*y^4*(1+y)^2). - Vladimir Kruchinin, Jan 27 2022

T(n,m) = 2*C(m,n)*C(n-2,m-n+2)/(n-2), n>=4. - Vladimir Kruchinin, Jan 27 2022

A268370 Number of North-East lattice paths from (0,0) to (n,n) that have exactly three east steps below the subdiagonal y = x-1.

Original entry on oeis.org

5, 24, 95, 356, 1309, 4784, 17472, 63920, 234498, 863056, 3187041, 11807740, 43885725, 163601760, 611625660, 2292665760, 8615485590, 32451382800, 122499978510, 463369822344, 1756113365874, 6667436894624, 25357090075600, 96589604043296, 368478056090340, 1407687015207200, 5384924914890213

Offset: 4

Ran Pan, Feb 03 2016

nonn

This sequence is related to paired pattern P_1 in Pan and Remmel's link.

Ran Pan, Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.

Cf. A120989, A002057, A000108.

G.f.: -((-1 + f(x) + 2*x)^2*(-1 + f(x) + 2*(f(x) - 2*x)*x))/(8*x^2), where f(x) = sqrt(1 - 4*x).

A097608 Triangle read by rows: number of Dyck paths of semilength n and having abscissa of the leftmost valley equal to k (if no valley, then it is taken to be 2n; 2<=k<=2n).

Original entry on oeis.org

1, 1, 0, 1, 2, 1, 1, 0, 1, 5, 3, 3, 1, 1, 0, 1, 14, 9, 9, 4, 3, 1, 1, 0, 1, 42, 28, 28, 14, 10, 4, 3, 1, 1, 0, 1, 132, 90, 90, 48, 34, 15, 10, 4, 3, 1, 1, 0, 1, 429, 297, 297, 165, 117, 55, 35, 15, 10, 4, 3, 1, 1, 0, 1, 1430, 1001, 1001, 572, 407, 200, 125, 56, 35, 15, 10, 4, 3, 1, 1, 0, 1

Offset: 1

Emeric Deutsch, Aug 30 2004, Dec 22 2004

A valley point is a path vertex that is preceded by a downstep and followed by an upstep (or by nothing at all). T(n,k) is the number of Dyck n-paths whose first valley point is at position k, 2<=k<=2n. - David Callan, Mar 02 2005
Row n has 2n-1 terms.
Row sums give the Catalan numbers (A000108).
Columns k=2 through 7 are respectively A000108, A000245, A071724, A002057, A071725, A026013. The nonzero entries in the even-indexed columns approach A088218 and similarly the odd-indexed columns approach A001791.

			Triangle begins
\ k..2...3...4...5...6...7....
n
1 |..1
2 |..1...0...1
3 |..2...1...1...0...1
4 |..5...3...3...1...1...0...1
5 |.14...9...9...4...3...1...1...0...1
6 |.42..28..28..14..10...4...3...1...1...0...1
7 |132..90..90..48..34..15..10...4...3...1...1...0...1
T(4,3)=3 because we have UU(DU)DDUD, UU(DU)DUDD and UU(DU)UDDD, where U=(1,1), D=(1,-1) (the first valley, with abscissa 3, is shown between parentheses).

Cf. A000108, A000245.

G:=t^2*z*C*(1-t*z)/(1-t^2*z)/(1-t*z*C): C:=(1-sqrt(1-4*z))/2/z: Gser:=simplify(series(G,z=0,11)): for n from 1 to 10 do P[n]:=coeff(Gser,z^n) od: seq(seq(coeff(P[n],t^k),k=2..2*n),n=1..10);

G.f.=t^2*zC(1-tz)/[(1-t^2*z)(1-tzC)], where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

G.f. Sum_{2<=k<=2n}T(n, k)x^n*y^k = ((1 - (1 - 4*x)^(1/2))*y^2*(1 - x*y))/(2*(1 - ((1 - (1 - 4*x)^(1/2))*y)/2)*(1 - x*y^2)). With G:= (1 - (1 - 4*x)^(1/2))/2, the gf for column 2k is G(G^(2k+1)(G-x)-x^(k+1)(1-G))/(G^2-x) and for column 2k+1 is G(G-x)(G^(2k+2)-x^(k+1))/(G^2-x). - David Callan, Mar 02 2005

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 23 2007

A317555 Triangle read by rows: T(n,k) is the number of preimages of the permutation 21345...n under West's stack-sorting map that have k+1 valleys (1 <= k <= floor((n-1)/2)).

Original entry on oeis.org

1, 4, 12, 2, 32, 16, 80, 80, 5, 192, 320, 60, 448, 1120, 420, 14, 1024, 3584, 2240, 224, 2304, 10752, 10080, 2016, 42, 5120, 30720, 40320, 13440, 840, 11264, 84480, 147840, 73920, 9240, 132, 24576, 225280, 506880, 354816, 73920, 3168

Offset: 3

Colin Defant, Sep 14 2018

If pi is any permutation of [n] with exactly 1 descent, then the number of preimages of pi under West's stack-sorting map that have k+1 valleys is at most T(n,k).

			Triangle begins:
    1;
    4;
   12,    2;
   32,   16;
   80,   80,   5;
  192,  320,  60;
  448, 1120, 420, 14;
  ...
T(1,1) = 1 because the permutation 213 has one preimage under West's stack-sorting map (namely, 231), and this permutation has 2 valleys.

C. Defant, Preimages under the stack-sorting algorithm, arXiv:1511.05681 [math.CO], 2015-2018.
C. Defant, Preimages under the stack-sorting algorithm, Graphs Combin., 33 (2017), 103-122.
C. Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.

Row sums give A002057.

Flatten[Table[Table[Sum[Sum[(2^(i - 2 j + 1)) Binomial[i - 1, 2 j - 2]CatalanNumber[j - 1] (2^((n - 1 - i) - 2 (m + 1 - j) + 1)) Binomial[(n - 1 - i) - 1, 2 (m + 1 - j) - 2] CatalanNumber[(m + 1 - j) - 1], {j, 1, m}], {i, 1, n - 2}], {m, 1, Floor[(n - 1)/2]}], {n, 1, 10}]]

T(n,k) = Sum_{i=1..n-2} Sum_{j=1..k} V(i,j) * V(n-1-i,m+1-j), where V(i,j) = 2^{i-2j+1} * (1/j) * binomial(i-1, 2j-2) * binomial(2j-2, j-1) are the numbers found in the triangle A091894.

A335050 Array read by descending antidiagonals, T(n,k) is the number of nodes in the pill tree with initial conditions (n,k), for n and k >= 0.

Original entry on oeis.org

1, 2, 3, 3, 7, 8, 4, 12, 21, 22, 5, 18, 40, 63, 64, 6, 25, 66, 130, 195, 196, 7, 33, 100, 231, 427, 624, 625, 8, 42, 143, 375, 803, 1428, 2054, 2055, 9, 52, 196, 572, 1376, 2805, 4860, 6916, 6917, 10, 63, 260, 833, 2210, 5016, 9877, 16794, 23712, 23713

Offset: 0

Michel Marcus, May 21 2020

See Bayer and Brandt for a description of the pill tree.

			The array begins:
    1    2    3    4     5     6 ...
    3    7   12   18    25    33 ...
    8   21   40   66   100   143 ...
   22   63  130  231   375   572 ...
   64  195  427  803  1376  2210 ...
  196  624 1428 2805  5016  8398 ...
  ...

Margaret Bayer and Keith Brandt, The Pill Problem, Lattice Paths and Catalan Numbers, preprint, Mathematics Magazine, Vol. 87, No. 5 (December 2014), pp. 388-394.
Keith Brandt and Kaleb Waite, Using recursion to solve the pill problem, Journal of Computing Sciences in Colleges, Volume 24, Issue 5, May 2009.
Charlotte A. C. Brennan and Helmut Prodinger, The pills problem revisited, preprint, Quaest. Math., 26(4):427-439, 2003.
Donald E. Knuth, John McCarthy, Walter Stromquist, Daniel H. Wagner, and Tim Hesterberg, Problem E3429. Big pills and little pills, The American Mathematical Monthly, 99(7):684, 1992.

Cf. A000108, A014138 (column 1), A120304 (column 2).

Cf. A002057 (first differences of column 3).

T(n,k) = sum(j=0, n, binomial(2*j+k+2, j+1) - binomial(2*j+k+2, j));

T(0,k) = k+1; T(n,0) = 1 + T(n-1,1); T(n,k) = 1 + T(n-1,k+1) + T(n,k-1) for n and k > 0.

T(n,k) = Sum_{j=0..n} (binomial(2*j+k+2, j+1) - binomial(2*j+k+2, j)).

A339028 Triangle T(n,m) = 3(m+1)C(n+m+3,m)C(2n+2,n-m)/((n+m+3)*C(n+1,m)).

Original entry on oeis.org

1, 3, 3, 9, 12, 9, 28, 42, 42, 28, 90, 144, 162, 144, 90, 297, 495, 594, 594, 495, 297, 1001, 1716, 2145, 2288, 2145, 1716, 1001, 3432, 6006, 7722, 8580, 8580, 7722, 6006, 3432, 11934, 21216, 27846, 31824, 33150, 31824, 27846, 21216, 11934, 41990, 75582, 100776, 117572, 125970, 125970, 117572, 100776, 75582, 41990

Offset: 0

Vladimir Kruchinin, Nov 20 2020

			1,
3,3,
9,12,9,
28,42,42,28,
90,144,162,144,
90,297,495,594,594,495,297

Cf. A000108, A000245, A002057 (row sums), A168256, A120406,

Maxima
```
T(n,m):=if n
				
```

G.f. ((sqrt(1-4*x*y)-sqrt(1-4*x))/(2*(x-x*y)))^3.

A376319 A Catalan-like sequence formed by summing the truncation of the terms of the fourth convolution of the Catalan Triangle where the number of row terms are truncated to ceiling((n+4)*log(3)/log(2)) - (n+4).

Original entry on oeis.org

1, 4, 14, 34, 103, 228, 665, 2096, 4787, 14239, 31330, 91728, 199328, 580128, 1834665, 4223092, 12667903, 28207395, 83435822, 267154051, 623837740, 1891453021, 4265101202, 12735718304, 28359351604, 84126071303, 270338873771, 634653510356, 1933488496208

Offset: 1

Rob Bunce, Sep 20 2024

a(1) = 1, all other rows are summed following application of the truncation formula.

Equivalent to truncation of A002057 starting from the n(4) term.

			When n=6, number of terms is restricted to 6, dropping 2 terms from the standard triangle; ceiling((6+4)*log(3)/log(2)) - (6+4) = 6.
When n=9, number of terms is restricted to 8, dropping 3 terms; ceiling((9+4)*log(3)/log(2)) - (9+4) = 8.
etc.
Truncating A002057 at this point, with dropped terms indicated by - and summing the remaining triangle terms in the normal way results in:
 n   sum   truncated triangle terms
 1     1 = 1;
 2     4 = 1, 1,  1,   1;
 3    14 = 1, 2,  3,   4,   4;
 4    34 = 1, 3,  6,  10,  14,    -;
 5   103 = 1, 4, 10,  20,  34,   34,    -;
 6   228 = 1, 5, 15,  35,  69,  103,    -,    -;
 7   665 = 1, 6, 21,  56, 125,  228,  228,    -,    -;
 8  2096 = 1, 7, 28,  84, 209,  437,  665,  665,    -, -;
 9  4787 = 1, 8, 36, 120, 329,  766, 1431, 2096,    -, -, -;
10 14239 = 1, 9, 45, 165, 494, 1260, 2691, 4787, 4787, -, -, -;
...

Cf. A009766, A000108, A002057, A374244, Half Catalan A000992.

lista(nn) = {
my(terms(j)=ceil((j+4)*log(3)/log(2)) - (j+4));
my(T=vector(nn));
my(S=vector(nn));
for(y=1, nn,
  if(y==1,
      T[1]=[1];
      S[1]=1		
    ,
      my(k=terms(y));
      T[y]=vector(k);
      for(i=1, k, if(i==1,T[y][i]=1,if(i<=length(T[y-1]),T[y][i]=T[y-1][i]+T[y][i-1],T[y][i]=T[y][i-1])));
      S[y]=vecsum(T[y])
    );
  );
S;
}

Same as for a normal fourth convolution Catalan triangle T(n,k), read by rows, each term is the sum of the entries above and to the left, i.e., T(n,k) = Sum_{j=0..k} T(n-1,j) but where j is limited to the truncated length.

cp's OEIS Frontend

A259476 Cayley's triangle of V numbers; triangle V(n,k), n >= 4, n <= k <= 2*n-4, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A268370 Number of North-East lattice paths from (0,0) to (n,n) that have exactly three east steps below the subdiagonal y = x-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A097608 Triangle read by rows: number of Dyck paths of semilength n and having abscissa of the leftmost valley equal to k (if no valley, then it is taken to be 2n; 2<=k<=2n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

Extensions

A317555 Triangle read by rows: T(n,k) is the number of preimages of the permutation 21345...n under West's stack-sorting map that have k+1 valleys (1 <= k <= floor((n-1)/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A335050 Array read by descending antidiagonals, T(n,k) is the number of nodes in the pill tree with initial conditions (n,k), for n and k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A339028 Triangle T(n,m) = 3*(m+1)*C(n+m+3,m)*C(2*n+2,n-m)/((n+m+3)*C(n+1,m)).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maxima

Formula

A376319 A Catalan-like sequence formed by summing the truncation of the terms of the fourth convolution of the Catalan Triangle where the number of row terms are truncated to ceiling((n+4)*log(3)/log(2)) - (n+4).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A339028 Triangle T(n,m) = 3(m+1)C(n+m+3,m)C(2n+2,n-m)/((n+m+3)*C(n+1,m)).