login
Total number of permutations on {1,2,...,n} that have a unique longest increasing subsequence.
5

%I #45 Jul 05 2024 11:11:01

%S 1,1,3,10,44,238,1506,10960,90449,834166,8496388,94738095,1148207875,

%T 15031585103,211388932628

%N Total number of permutations on {1,2,...,n} that have a unique longest increasing subsequence.

%H Miklos Bona and Elijah DeJonge, <a href="https://arxiv.org/abs/2003.10640">Pattern avoiding permutations and involutions with a unique longest increasing subsequence</a>, arXiv:2003.10640 [math.CO], 2020.

%H Manfred Scheucher, <a href="/A167995/a167995.c.txt">C Code</a>

%H Nicholas Van Nimwegen, <a href="https://arxiv.org/abs/2303.02808">A Combinatorial Proof for 132-Avoiding Permutations with a Unique Longest Increasing Subsequence</a>, arXiv:2303.02808 [math.CO], 2023. Mentions this sequence.

%H Nicholas Van Nimwegen, <a href="https://ajc.maths.uq.edu.au/pdf/89/ajc_v89_p397.pdf">Unique longest increasing subsequences in 132-avoiding permutations</a>, Australasian J. Comb. (2024) Vol. 89, Part 3. 397-399.

%e For n=3, 123, 231, and 312 are the only three permutations that have precisely one maximal increasing subsequence.

%e 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

%o (Sage)

%o print(n,len([p for p in permutations(n) if len(p.longest_increasing_subsequences())==1]))

%o # _Manfred Scheucher_, Jun 06 2015

%Y Cf. A167999, A168502.

%K nonn,nice,more

%O 1,3

%A _Anant Godbole_, Stephanie Goins, Brad Wild, Nov 16 2009

%E a(9)-a(13) from _Manfred Scheucher_, Jun 06 2015

%E a(14)-a(15) from _Bert Dobbelaere_, Jul 24 2019