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,3

Links

Table of n, a(n) for n=1..15.

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.

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]))
# Manfred Scheucher, Jun 06 2015

Crossrefs

Cf. A167999, A168502.

Sequence in context: A113059 A331156 A240172 * A000608 A333018 A259352

Adjacent sequences: A167992 A167993 A167994 * A167996 A167997 A167998

Keyword

nonn,nice,more

Author

Anant Godbole, Stephanie Goins, Brad Wild, Nov 16 2009

Extensions

a(9)-a(13) from Manfred Scheucher, Jun 06 2015

a(14)-a(15) from Bert Dobbelaere, Jul 24 2019

Status

approved