The number of permutations in the symmetric group S_n in which it is possible to find two disjoint increasing subsequences each with length equal to the length of the longest increasing subsequence of the permutation.
(history;
published version)
Discussion
Fri Feb 07
03:08
Peter Luschny: Ildar, could you put your C++ program on a separate sheet and upload it?
Sun Feb 09
07:24
Ildar Gainullin: Sure, for example here it is: https://pastebin.com/iQ2rJjGD
Wed Feb 12
08:20
Alois P. Heinz: please add more terms ...
LINKS
Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem">Longest increasing subsequence problem</a>
Discussion
Thu Feb 06
16:25
Andrew Howroyd: This sequence is missing cross-refs. We really don't like sequences without cross-refs (the world is never a green field). Is there a sequence that gives the number of permutations whose longest increasing subsequence is at most n/2? Otherwise can you find something else relevant?
16:33
Ildar Gainullin: Yeah, for example this one: https://oeis.org/A047874
NAME
The number of permutations in the symmetric group S_n in which it is possible to find two disjoint increasing subsequences without shared elements and each with length equal to the length of the longest increasing subsequence of the permutation.
COMMENTS
All a(n)=5 possible Only permutations for whose longest increasing subsequence is at most n=4 are:/2 need to be considered.
[2,1,4,3]
[2,4,1,3]
[3,1,4,2]
[3,4,1,2]
[4,3,2,1]
EXAMPLE
a(3) = 1 because the only permutation whose longest increasing subsequence is 1 is [3,2,1] and this contains two disjoint increasing subsequences of length 1.
The a(4) = 5 permutations are:
[2,1,4,3],
[2,4,1,3],
[3,1,4,2],
[3,4,1,2],
[4,3,2,1].
Discussion
Thu Feb 06
16:22
Andrew Howroyd: I've made some wording changes to the name to clarify (I had to add quite a lot more words, perhaps someone will think of a more elegant way to say this, but it is better to be clear).
NAME
The number of permutations in the symmetric group S_n in which it is possible to find two longest increasing subsequences without any common shared elements and each with length equal to the length of the longest increasing subsequence of the permutation.
Discussion
Thu Feb 06
15:53
Ildar Gainullin: well, because you want to find two LONGEST increasing subsequences.
15:54
Ildar Gainullin: in [3,2,1] you can do it as you said
in all other permutations with n=3 you can't because LIS is >=2
15:55
Andrew Howroyd: ok, I'm really not understanding this sequence at all. Why is [4,3,2,1] one of the permutations for a(4)? It doesn't have two increasing subsequences of length 2? Please explain - either by words or example. At the moment we are just guessing (and not understanding)
15:57
Ildar Gainullin: for [4,3,2,1] the longest increasing subsequence is of length 1.
And you can find two non-intersecting increasing subsequences with such lengths :(
16:03
Andrew Howroyd: got it.