login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 11 03:20 EDT 2021. Contains 343784 sequences. (Running on oeis4.)