A132889 -id:A132889 - cp's OEIS frontend

A120730 Another version of Catalan triangle A009766.

1, 0, 1, 0, 1, 1, 0, 0, 2, 1, 0, 0, 2, 3, 1, 0, 0, 0, 5, 4, 1, 0, 0, 0, 5, 9, 5, 1, 0, 0, 0, 0, 14, 14, 6, 1, 0, 0, 0, 0, 14, 28, 20, 7, 1, 0, 0, 0, 0, 0, 42, 48, 27, 8, 1, 0, 0, 0, 0, 0, 42, 90, 75, 35, 9, 1, 0, 0, 0, 0, 0, 0, 132, 165, 110, 44, 10, 1

Offset: 0

Philippe Deléham, Aug 17 2006, corrected Sep 15 2006

Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 1, -1, 0, 0, 1, -1, 0, 0, 1, -1, 0, 0, ...] DELTA [1, 0, 0, -1, 1, 0, 0, -1, 1, 0, 0, -1, 1, ...] where DELTA is the operator defined in A084938.
Aerated version gives A165408. - Philippe Deléham, Sep 22 2009
T(n,k) is the number of length n left factors of Dyck paths having k up steps. Example: T(5,4)=4 because we have UDUUU, UUDUU, UUUDU, and UUUUD, where U=(1,1) and D=(1,-1). - Emeric Deutsch, Jun 19 2011
With zeros omitted: 1,1,1,1,2,1,2,3,1,5,4,1,... = A008313. - Philippe Deléham, Nov 02 2011

			As a triangle, this begins:
  1;
  0,  1;
  0,  1,  1;
  0,  0,  2,  1;
  0,  0,  2,  3,  1;
  0,  0,  0,  5,  4,  1;
  0,  0,  0,  5,  9,  5,  1;
  0,  0,  0,  0, 14, 14,  6,  1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Cf. A000007, A000096, A000108, A001405, A001477, A003161, A005586, A005587.
Cf. A008313, A009766, A039598, A039599, A084938, A099376, A105523, A121725.
Cf. A126087, A128386, A121724, A128387, A129123, A132373, A132374, A132375.
Cf. A132889, A151162, A151254, A151281, A156195, A156361, A156362, A156566.
Cf. A156577, A165408, A357654.

A120730:= func< n,k | n gt 2*k select 0 else Binomial(n, k)*(2*k-n+1)/(k+1) >;
[A120730(n,k): k in [0..n], n in [0..13]]; // G. C. Greubel, Nov 07 2022

G := 4*z/((2*z-1+sqrt(1-4*z^2*t))*(1+sqrt(1-4*z^2*t))): Gser := simplify(series(G, z = 0, 13)): for n from 0 to 12 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 12 do seq(coeff(P[n], t, k), k = 0 .. n) end do; # yields sequence in triangular form  # Emeric Deutsch, Jun 19 2011
# second Maple program:
b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, add(b(x-1, y+j), j=[-1, 1])))
    end:
T:= (n, k)-> b(n, 2*k-n):
seq(seq(T(n, k), k=0..n), n=0..14);  # Alois P. Heinz, Oct 13 2022

b[x_, y_]:= b[x, y]= If[y<0 || y>x, 0, If[x==0, 1, Sum[b[x-1, y+j], {j, {-1, 1}}] ]];
T[n_, k_] := b[n, 2 k - n];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Oct 21 2022, after Alois P. Heinz *)
T[n_, k_]:= If[n>2*k, 0, Binomial[n, k]*(2*k-n+1)/(k+1)];
Table[T[n, k], {n,0,13}, {k,0,n}]//Flatten (* G. C. Greubel, Nov 07 2022 *)

def A120730(n,k): return 0 if (n>2*k) else binomial(n, k)*(2*k-n+1)/(k+1)
flatten([[A120730(n,k) for k in range(n+1)] for n in range(14)]) # G. C. Greubel, Nov 07 2022

G.f.: G(t,z) = 4*z/((2*z-1+sqrt(1-4*t*z^2))*(1+sqrt(1-4*t*z^2))). - Emeric Deutsch, Jun 19 2011
Sum_{k=0..n} x^k*T(n,n-k) = A001405(n), A126087(n), A128386(n), A121724(n), A128387(n), A132373(n), A132374(n), A132375(n), A121725(n) for x=1,2,3,4,5,6,7,8,9 respectively. [corrected by Philippe Deléham, Oct 16 2008]
T(2*n,n) = A000108(n); A000108: Catalan numbers.
From Philippe Deléham, Oct 18 2008: (Start)
Sum_{k=0..n} T(n,k)^2 = A000108(n) and Sum_{n>=k} T(n,k) = A000108(k+1).
Sum_{k=0..n} T(n,k)^3 = A003161(n).
Sum_{k=0..n} T(n,k)^4 = A129123(n). (End)
Sum_{k=0..n}, T(n,k)*x^k = A000007(n), A001405(n), A151281(n), A151162(n), A151254(n), A156195(n), A156361(n), A156362(n), A156566(n), A156577(n) for x=0,1,2,3,4,5,6,7,8,9 respectively. - Philippe Deléham, Feb 10 2009
From G. C. Greubel, Nov 07 2022: (Start)
T(n, k) = 0 if n > 2*k, otherwise binomial(n, k)*(2*k-n+1)/(k+1).
Sum_{k=0..n} (-1)^k*T(n,k) = A105523(n).
Sum_{k=0..n} (-1)^k*T(n,k)^2 = -A132889(n), n >= 1.
Sum_{k=0..floor(n/2)} T(n-k, k) = A357654(n).
T(n, n-1) = A001477(n).
T(n, n-2) = [n=2] + A000096(n-3), n >= 2.
T(n, n-3) = 2*[n<5] + A005586(n-5), n >= 3.
T(n, n-4) = 5*[n<7] - 2*[n=4] + A005587(n-7), n >= 4.
T(2*n+1, n+1) = A000108(n+1), n >= 0.
T(2*n-1, n+1) = A099376(n-1), n >= 1. (End)

A126217 Triangle read by rows: T(n,k) is the number of 321-avoiding permutations of {1,2,...,n} having longest increasing subsequence of length k (0<=k<=n).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 4, 1, 0, 0, 4, 9, 1, 0, 0, 0, 25, 16, 1, 0, 0, 0, 25, 81, 25, 1, 0, 0, 0, 0, 196, 196, 36, 1, 0, 0, 0, 0, 196, 784, 400, 49, 1, 0, 0, 0, 0, 0, 1764, 2304, 729, 64, 1, 0, 0, 0, 0, 0, 1764, 8100, 5625, 1225, 81, 1, 0, 0, 0, 0, 0, 0, 17424, 27225, 12100, 1936, 100, 1, 0, 0, 0, 0, 0, 0, 17424, 88209, 75625, 23716, 2916, 121, 1

Offset: 0

Emeric Deutsch, Dec 22 2006

The row sums are the Catalan numbers (A000108). T(2n,n) = (C(n))^2 = A001246(n), where the C(n) are the Catalan numbers.

Also T(n,k) = Number of Dyck paths of semilength n with midpoint height = 2*k - n. David Scambler, Nov 25 2010

			T(4,2) = 4 because we have 2143, 3142, 2413 and 3412.
Triangle starts:
  1;
  0, 1;
  0, 1, 1;
  0, 0, 4,  1;
  0, 0, 4,  9,  1;
  0, 0, 0, 25, 16,  1;
  0, 0, 0, 25, 81, 25, 1;
  ...
T(4,2) = 4 because 2*2 - 4 = zero and Dyck 4-paths with midpoint height of zero are UUDDUUDD, UUDDUDUD, UDUDUUDD and UDUDUDUD.

Alois P. Heinz, Rows n = 0..150, flattened
E. Deutsch, A. J. Hildebrand and H. S. Wilf, Longest increasing subsequences in pattern-restricted permutations, The Electronic Journal of Combinatorics, 9(2), 2003, #R12.

Cf. A000108, A001246, A001700, A071799, A132889.

T(n+1,n) gives A000290.

T:=proc(n,k) if floor((n+1)/2)<=k and k<=n then ((2*k-n+1)*binomial(n+1,k+1)/(n+1))^2 else 0 fi end: for n from 0 to 13 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

t[n_, k_] := If[n<=2k, ((2k-n+1)*Binomial[n+1, n-k]/(n+1))^2, 0]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Amiram Eldar, Nov 26 2018 *)

T(n,k)=if(n<=2*k,(2*k-n+1)*binomial(n+1,n-k)\(n+1))^2  \\ M. F. Hasler, Nov 24 2010

T(n,k) = ((2*k - n + 1)*C(n+1,n-k)/(n + 1))^2 if floor((n+1)/2) <= k <= n; T(n,k) = 0 otherwise. [N.B.: floor((n+1)/2) <= k  <=>  n/2 <= k.]
Sum_{k=n+1..2*n+1} (-1)^(n+k+1) * T(2*n+1,k) = binomial(2*n+1,n) = A001700(n). - Peter Bala, Nov 03 2024
From Alois P. Heinz, Nov 04 2024: (Start)
Sum_{k=0..n} k * T(n,k) = A132889(n).
2 * Sum_{k=0..2n} (2n-k) * T(2n,k) = A071799(n) for n>=1. (End)

Row and column 0 inserted by Alois P. Heinz, Nov 04 2024

cp's OEIS Frontend

A120730 Another version of Catalan triangle A009766.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula