A168502 -id:A168502 - cp's OEIS frontend

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

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

			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

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.

Cf. A167999, A168502.

print(n,len([p for p in permutations(n) if len(p.longest_increasing_subsequences())==1]))
# Manfred Scheucher, Jun 06 2015

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

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

A167999 A permutation pi on [1,2,....n] has k(pi) longest increasing subsequences associated with it; 1<= k(pi)<= f(n) for some function f. The given sequence enumerates sum_pi k(pi).

Original entry on oeis.org

1, 3, 10, 46, 264, 1773, 13719, 120770, 1190358, 12961563, 154466259, 2000471830, 27980585221

Offset: 1

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

We also have data for the number of permutations pi that have k(pi)=r for r>=1.

A. Godbole, Publications (lists some related sequences)
Manfred Scheucher, C Code

Cf. A167995, A168502.

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

A258683 Total number of permutations on {1,2,...,n} that have a unique longest increasing subsequence and a unique longest decreasing subsequence.

Original entry on oeis.org

1, 0, 0, 0, 2, 16, 120, 938, 8014, 74060, 748628, 8163156, 96429784

Offset: 1

Manfred Scheucher, Jun 07 2015

By definition, a(n) <= A167995(n).

			the two permutation of {1,2,...,5}:
{2, 5, 3, 1, 4}
{4, 1, 3, 5, 2}
8 of the 16 permutations of {1,2,...,6} (others reversed):
{1, 3, 6, 4, 2, 5}
{1, 5, 2, 4, 6, 3}
{2, 3, 6, 4, 1, 5}
{2, 5, 3, 1, 4, 6}
{2, 6, 3, 1, 4, 5}
{2, 6, 5, 3, 1, 4}
{3, 6, 4, 2, 1, 5}
{3, 6, 4, 2, 5, 1}

Manfred Scheucher, C Code

Cf. A167995, A167999, A168502.

def A258683(n):
    return len([p for p in permutations(n) if len(p.longest_increasing_subsequences())* len(p.reverse().longest_increasing_subsequences())==1])
# Manfred Scheucher, Jun 07 2015

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

Extensions

A167999 A permutation pi on [1,2,....n] has k(pi) longest increasing subsequences associated with it; 1<= k(pi)<= f(n) for some function f. The given sequence enumerates sum_pi k(pi).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A258683 Total number of permutations on {1,2,...,n} that have a unique longest increasing subsequence and a unique longest decreasing subsequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage