A321314 -id:A321314

Search: a321314 -id:a321314

Displaying 1-3 of 3 results found.

page 1

A321316

Number T(n,k) of permutations of [n] whose difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence equals k; triangle T(n,k), n >= 1, 1-n <= k <= n-1, read by rows.

+10
7

1, 1, 0, 1, 1, 0, 4, 0, 1, 1, 0, 9, 4, 9, 0, 1, 1, 0, 16, 25, 36, 25, 16, 0, 1, 1, 0, 25, 81, 125, 256, 125, 81, 25, 0, 1, 1, 0, 36, 196, 421, 1225, 1282, 1225, 421, 196, 36, 0, 1, 1, 0, 49, 400, 1225, 4292, 9261, 9864, 9261, 4292, 1225, 400, 49, 0, 1

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,7

LINKS

Alois P. Heinz, Rows n = 1..80, flattened

Wikipedia, Longest increasing subsequence

FORMULA

T(n,k) = T(n,-k).

Sum_{k=1..n-1} T(n,k) = A321314(n).

Sum_{k=0..n-1} T(n,k) = A321315(n).

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

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

EXAMPLE

: 1 ;

: 1, 0, 1 ;

: 1, 0, 4, 0, 1 ;

: 1, 0, 9, 4, 9, 0, 1 ;

: 1, 0, 16, 25, 36, 25, 16, 0, 1 ;

: 1, 0, 25, 81, 125, 256, 125, 81, 25, 0, 1 ;

: 1, 0, 36, 196, 421, 1225, 1282, 1225, 421, 196, 36, 0, 1 ;

MAPLE

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*x^(l[1]-nops(l)) :

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])):

b:= proc(n) option remember; g(n$2, []) end:

T:= (n, k)-> coeff(b(n), x, k):

seq(seq(T(n, k), k=1-n..n-1), n=1..10);

MATHEMATICA

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_] := h[l]^2*x^(l[[1]] - Length[l]);

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

b[n_] := b[n] = g[n, n, {}];

T[n_, k_] := Coefficient[b[n], x, k];

Table[Table[T[n, k], {k, 1 - n, n - 1}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Feb 27 2021, after Alois P. Heinz *)

CROSSREFS

Column k=0 gives A321313.

Row sums give A000142.

T(n+1,n-2) gives A000290.

Cf. A303697, A321277, A321278, A321314, A321315.

KEYWORD

nonn,tabf

AUTHOR

Alois P. Heinz, Nov 03 2018

STATUS

approved

A321313

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

+10
4

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..80

Wikipedia, Longest increasing subsequence

FORMULA

a(n) = n! - 2 * A321314(n).

a(n) = A321315(n) - A321314(n).

a(n) = A321316(n,0).

MAPLE

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

MATHEMATICA

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

CROSSREFS

Column k=0 of A321316.

Cf. A000142, A003316, A321314, A321315.

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Nov 03 2018

STATUS

approved

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.

+10
4

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..80

Wikipedia, Longest increasing subsequence

FORMULA

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

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

MAPLE

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

CROSSREFS

Cf. A003316, A321313, A321314, A321316.

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Nov 03 2018

STATUS

approved

page 1

Search completed in 0.004 seconds