

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


COMMENTS

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


LINKS

Table of n, a(n) for n=1..15.
Miklos Bona, Elijah DeJonge, Pattern avoiding permutations and involutions with a unique longest increasing subsequence, arXiv:2003.10640 [math.CO], 2020.
Manfred Scheucher, C Code


EXAMPLE

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: A096804 A113059 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



