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
-
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);
A064314
Total length of longest increasing runs in all permutations of n elements.
Original entry on oeis.org
1, 3, 12, 55, 299, 1900, 13942, 115932, 1078361, 11092265, 125040100, 1532995992, 20310212672, 289186696338, 4404156016584, 71441907922793, 1229835421590959, 22393298253477006, 430019590699868644, 8685717780508953928, 184088653170341473400, 4085097253151506682170
Offset: 1
This sequence treats runs of adjacent elements,
A003316 treats subsequences of not necessarily adjacent elements.
-
b:= proc(u, o, t, k) option remember; `if`(t=k, (u+o)!,
`if`(max(t, u)+o add(b(0, n, 0, k), k=1..n) -n*b(0, n, 0, n+1):
seq(a(n), n=1..25); # Alois P. Heinz, Oct 16 2013
-
nn=30;f[list_]:=Total[Table[list[[i]]*i,{i,1,Length[list]}]];a[r_]:=Apply[Plus,Table[Normal[Series[y x^(r+1)/(1-Sum[y x^i,{i,1,r}]),{x,0,nn}]][[n]]/(n+r)!,{n,1,nn-r}]]/.y->-1;Map[f,Map[Select[#,#>0&]&,Transpose[Prepend[Table[Drop[Range[0,nn]! CoefficientList[Series[1/(1-x-a[n+1])-1/(1-x-a[n]),{x,0,nn}],x],1],{n,1,28}],Table[1,{nn}]]]]] (* Geoffrey Critzer, Feb 25 2014 *)
A275576
Sums of lengths of longest (strictly) increasing subsequences of all n^n length-n lists of integers from {1,2,...,n}.
Original entry on oeis.org
1, 5, 45, 524, 7450, 125992, 2472197, 55163096, 1379215566, 38203654070, 1161476316583, 38452206880034, 1376997068182450, 53036098532973584, 2186272797635061105, 96043562430904351024, 4479387734051244791950, 221051522602427094486042
Offset: 1
For n = 2 there are 4 such sequences: (1,1), (1,2), (2,1), and (2,2).
The corresponding lengths of longest (strictly) increasing subsequences of these is 1, 2, 1, 1, so a(2) = 5.
Cf.
A003316, which computes the same thing for permutations.
Cf.
A275577, which computes the same thing for not necessarily strictly increasing subsequences.
A275577
Sums of lengths of longest (not necessarily strictly) increasing subsequences of all n^n length-n lists of integers from {1,2,...,n}.
Original entry on oeis.org
1, 7, 63, 716, 10050, 167707, 3246985, 71601112, 1772086842, 48644809445, 1466863148619, 48202848917302, 1714563272612502
Offset: 1
For n = 2 there are 4 such sequences: (1,1), (1,2), (2,1), and (2,2).
The corresponding lengths of longest (not necessarily strictly) increasing subsequences of these is 2, 2, 1, 2, so a(2) =7.
Cf.
A003316, which computes the same thing for permutations.
Cf.
A275576, which computes the same thing for strictly increasing subsequences.