A167995 Total number of permutations on {1,2,...,n} that have a unique longest increasing subsequence.
1, 1, 3, 10, 44, 238, 1506, 10960, 90449, 834166, 8496388, 94738095, 1148207875, 15031585103, 211388932628
Offset: 1
Examples
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
Links
- Miklos Bona and Elijah DeJonge, Pattern avoiding permutations and involutions with a unique longest increasing subsequence, arXiv:2003.10640 [math.CO], 2020.
- Manfred Scheucher, C Code
- Nicholas Van Nimwegen, A Combinatorial Proof for 132-Avoiding Permutations with a Unique Longest Increasing Subsequence, arXiv:2303.02808 [math.CO], 2023. Mentions this sequence.
- Nicholas Van Nimwegen, Unique longest increasing subsequences in 132-avoiding permutations, Australasian J. Comb. (2024) Vol. 89, Part 3. 397-399.
Programs
-
Sage
print(n,len([p for p in permutations(n) if len(p.longest_increasing_subsequences())==1])) # Manfred Scheucher, Jun 06 2015
Extensions
a(9)-a(13) from Manfred Scheucher, Jun 06 2015
a(14)-a(15) from Bert Dobbelaere, Jul 24 2019