|
|
A167995
|
|
Total number of permutations on {1,2,...,n} that have a unique longest increasing subsequence.
|
|
5
|
|
|
1, 1, 3, 10, 44, 238, 1506, 10960, 90449, 834166, 8496388, 94738095, 1148207875, 15031585103, 211388932628
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
LINKS
|
|
|
EXAMPLE
|
For n=3, 123, 231, and 312 are the only three permutations that have precisely one maximal increasing subsequence.
The permutation 35142678 has longest increasing subsequence length 5, but this maximal length can be obtained in multiple ways (35678, 34678, 14678, 12678), hence it is not counted in a(8). - Bert Dobbelaere, Jul 24 2019
|
|
PROG
|
(Sage)
print(n, len([p for p in permutations(n) if len(p.longest_increasing_subsequences())==1]))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|