A321316 -id:A321316 - cp's OEIS frontend

A321277 One half of the sum over all permutations of [n] of the absolute difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.

0, 1, 2, 12, 61, 367, 2805, 23372, 213317, 2189823, 24882811, 305633678, 4037554628, 57447084699, 877263905683, 14276260437624, 246201450585329, 4487236144246511, 86286209907252739, 1746559569805617910, 37106502447954647906, 825196425771658993531

Offset: 1

Alois P. Heinz, Nov 01 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..80
Wikipedia, Longest increasing subsequence

Cf. A003316, A321273, A321274, A321275, A321276, A321278, A321316.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*abs(l[1]-nops(l))/2:
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

a(n) = (1/2) * Sum_{k=1-n..n-1} abs(k) * A321316(n,k).

A321278 One half of the sum over all permutations of [n] of the squared difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.

Original entry on oeis.org

0, 1, 4, 18, 105, 699, 5285, 45128, 431223, 4540775, 52268029, 653096124, 8810538490, 127622293057, 1975379879871, 32537074533872, 568268861724191, 10490690233451583, 204118868130889733, 4174977363687339452, 89554055679215605982, 2010207472655266461533

Offset: 1

Alois P. Heinz, Nov 01 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..80
Wikipedia, Longest increasing subsequence

Cf. A003316, A321273, A321274, A321275, A321276, A321277, A321316.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*(l[1]-nops(l))^2/2:
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

a(n) = (1/2) * Sum_{k=1-n..n-1} k^2 * A321316(n,k).

A303697 Number T(n,k) of permutations p of [n] whose difference between sum of up-jumps and sum of down-jumps equals k; triangle T(n,k), n>=0, min(0,1-n)<=k<=max(0,n-1), read by rows.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 4, 5, 4, 5, 4, 1, 1, 11, 19, 19, 20, 19, 19, 11, 1, 1, 26, 82, 100, 101, 100, 101, 100, 82, 26, 1, 1, 57, 334, 580, 619, 619, 620, 619, 619, 580, 334, 57, 1, 1, 120, 1255, 3394, 4339, 4420, 4421, 4420, 4421, 4420, 4339, 3394, 1255, 120, 1

Offset: 0

Alois P. Heinz, Apr 28 2018

An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here.

			Triangle T(n,k) begins:
:                               1                             ;
:                               1                             ;
:                          1,   0,   1                        ;
:                     1,   1,   2,   1,   1                   ;
:                1,   4,   5,   4,   5,   4,   1              ;
:           1,  11,  19,  19,  20,  19,  19,  11,   1         ;
:      1,  26,  82, 100, 101, 100, 101, 100,  82,  26,  1     ;
:  1, 57, 334, 580, 619, 619, 620, 619, 619, 580, 334, 57, 1  ;

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

Row sums give A000142.

Cf. A000295, A001720, A005165, A008292, A081285, A153229, A291680, A291684, A291722, A316292, A316293, A321316.

b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,
      add(b(u-j, o+j-1)*x^(-j), j=1..u)+
      add(b(u+j-1, o-j)*x^( j), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=ldegree(p)..degree(p)))(
        `if`(n=0, 1, add(b(j-1, n-j), j=1..n))):
seq(T(n), n=0..12);

b[u_, o_] := b[u, o] = Expand[If[u+o == 0, 1,
     Sum[b[u-j, o+j-1] x^-j, {j, 1, u}] +
     Sum[b[u+j-1, o-j] x^j, {j, 1, o}]]];
T[0] = {1};
T[n_] := x^n Sum[b[j-1, n-j], {j, 1, n}] // CoefficientList[#, x]& // Rest;
T /@ Range[0, 12] // Flatten (* Jean-François Alcover, Feb 20 2021, after Alois P. Heinz *)

T(n,0) = A153229(n) for n > 0.
T(n,1) = A005165(n-1) for n > 0.
T(n+1,n-1) = A000295(n).
T(n,k) = T(n,-k).
Sum_{k=0..n-1} k^2 * T(n,k) = A001720(n+2) for n>1.

A321313 Number of permutations of [n] with equal lengths of the longest increasing subsequence and the longest decreasing subsequence.

Original entry on oeis.org

1, 0, 4, 4, 36, 256, 1282, 9864, 99976, 970528, 9702848, 113092200, 1500063930, 20985500212, 305177475748, 4733232671056, 79461918315024, 1427464201289584, 26955955609799728, 531536672155429792, 10980840178654738496, 238597651836121062824, 5446220581860028853936

Offset: 1

Alois P. Heinz, Nov 03 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..80
Wikipedia, Longest increasing subsequence

Column k=0 of A321316.

Cf. A000142, A003316, A321314, A321315.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> `if`(l[1]=nops(l), h(l)^2, 0):
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

h[l_] := With[{n = Length[l]}, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[j > l[[k]], 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
f[l_] := If[l[[1]] == Length[l], h[l]^2, 0];
g[n_, i_, l_] := If[n == 0 || i == 1, f[Join[l, Table[1, {n}]]], g[n, i - 1, l] + g[n - i, Min[i, n - i], Append[l, i]]];
a[n_] := g[n, n, {}];
Array[a, 25] (* Jean-François Alcover, Aug 31 2021, after Alois P. Heinz *)

a(n) = n! - 2 * A321314(n).
a(n) = A321315(n) - A321314(n).
a(n) = A321316(n,0).

A321314 Number of permutations of [n] where the length of the longest increasing subsequence is larger than the length of the longest decreasing subsequence.

Original entry on oeis.org

0, 1, 1, 10, 42, 232, 1879, 15228, 131452, 1329136, 15106976, 182954700, 2363478435, 33096395494, 501248446126, 8094778608472, 138112754890488, 2487454752219208, 47344572399516136, 950682668010605104, 20055050996527350752, 442701537970743308588, 10202898078512473893032

Offset: 1

Alois P. Heinz, Nov 03 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..80
Wikipedia, Longest increasing subsequence

Cf. A000142, A003316, A321313, A321315, A321316.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> `if`(l[1] `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

h[l_] := With[{n = Length[l]}, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[j > l[[k]], 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
f[l_] := If[l[[1]] < Length[l], h[l]^2, 0];
g[n_, i_, l_] := If[n == 0 || i == 1, f[Join[l, Table[1, {n}]]], g[n, i - 1, l] + g[n - i, Min[i, n - i], Append[l, i]]];
a[n_] := g[n, n, {}];
Array[a, 25] (* Jean-François Alcover, Aug 31 2021, after Alois P. Heinz *)

a(n) = Sum_{k=1..n-1} A321316(n,k).
a(n) = (n! - A321313(n))/2.
a(n) = A321315(n) - A321313(n).

A321315 Number of permutations of [n] where the length of the longest increasing subsequence is larger than or equal to the length of the longest decreasing subsequence.

Original entry on oeis.org

1, 1, 5, 14, 78, 488, 3161, 25092, 231428, 2299664, 24809824, 296046900, 3863542365, 54081895706, 806425921874, 12828011279528, 217574673205512, 3914918953508792, 74300528009315864, 1482219340166034896, 31035891175182089248, 681299189806864371412, 15649118660372502746968

Offset: 1

Alois P. Heinz, Nov 03 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..80
Wikipedia, Longest increasing subsequence

Cf. A003316, A321313, A321314, A321316.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> `if`(l[1]>=nops(l), h(l)^2, 0):
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

a(n) = Sum_{k=0..n-1} A321316(n,k).

a(n) = A321313(n) + A321314(n).

cp's OEIS Frontend

A321277 One half of the sum over all permutations of [n] of the absolute difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A321278 One half of the sum over all permutations of [n] of the squared difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A303697 Number T(n,k) of permutations p of [n] whose difference between sum of up-jumps and sum of down-jumps equals k; triangle T(n,k), n>=0, min(0,1-n)<=k<=max(0,n-1), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A321313 Number of permutations of [n] with equal lengths of the longest increasing subsequence and the longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A321314 Number of permutations of [n] where the length of the longest increasing subsequence is larger than the length of the longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A321315 Number of permutations of [n] where the length of the longest increasing subsequence is larger than or equal to the length of the longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula