A071799 -id:A071799 - cp's OEIS frontend

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

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

A387635 a(n) = Sum_{k=0..n-1} binomial(2*n, k)^2.

Original entry on oeis.org

0, 1, 17, 262, 3985, 60626, 925190, 14168988, 217721745, 3355615450, 51855874642, 803232328548, 12467572005382, 193873026294052, 3019674502600220, 47101568276955512, 735663252850019217, 11503661742608944170, 180077229781765344602, 2821666487800835457300

Offset: 0

David Radcliffe, Sep 04 2025

a(n) is the number of subsets of {1,...,4n} of size 2n containing at least n+1 elements from {1,...,2n}.

Also the maximum size of a family of 2n-subsets of a 4n-set such that every pairwise intersection has at least two elements. This was conjectured by Erdős, Ko, and Rado, and proved by Ahlswede and Khachatrian.

Rudolf Ahlswede and Levon H. Khachatrian, The complete intersection theorem for systems of finite sets. European J. Combin. 18 (1997), 125-136.
Thomas Bloom, Problem 83, Erdős Problems.
P. Erdős, Chao Ko, and R. Rado, Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) (1961), 313-320.

Cf. A071799, A036910, A002894, A218708.

seq(add(binomial(2*n, k)^2, k=0..(n-1)), n=0..20);
# or
gf := (1/2)*((sqrt(1 + sqrt(1 - 16*x)))/(sqrt(2 - 32*x)) - hypergeom([1/2, 1/2], [1], 16*x)):
ser := series(gf, x, 20): seq(coeff(ser, x, n), n = 0..19);  # Peter Luschny, Sep 05 2025

Table[(Binomial[4n, 2n] - Binomial[2n, n]^2)/2, {n, 0, 20}]
(* or *)
gf[x_] := (Sqrt[1 + Sqrt[1 - 16 x]])/(2 Sqrt[2 - 32 x] ) - EllipticK[16 x]/Pi;
CoefficientList[Series[gf[x], {x, 0, 19}], x]  (* Peter Luschny, Sep 05 2025 *)
(* or *)
CoefficientList[Series[(Sqrt[1 + Sqrt[1 - 16*x]])/(2*Sqrt[2 - 32*x]) - 1/(2*ArithmeticGeometricMean[1, Sqrt[1 - 16*x]]), {x, 0, 19}], x] (* Vaclav Kotesovec, Sep 06 2025 *)

a(n) = (1/2)*(C(4n, 2n) - C(2n, n)^2) = A071799(n)/2.
From Peter Luschny, Sep 05 2025: (Start)
a(n) = A036910(n) - A002894(n).
a(n) = [x^n]((1/2)*((sqrt(1 + sqrt(1 - 16*x)))/(sqrt(2 - 32*x)) - hypergeom([1/2, 1/2], [1], 16*x))).
a(n) = [x^n]((sqrt(1 + sqrt(1 - 16*x)))/(2*sqrt(2 - 32*x)) - EllipticK((4*sqrt(x))^m)/Pi) where m = 1 if the Maple conventions and m = 2 if the Mathematica conventions are followed.
a(n) ~ 16^n/sqrt(8*Pi*n) = A218708*16^n/sqrt(n). (End)
a(n) = [x^n] sqrt(1+sqrt(1-16*x))/(2*sqrt(2-32*x)) - 1/(2*AGM(1,sqrt(1-16*x))). - Vaclav Kotesovec, Sep 06 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions