A167999 -id:A167999 - 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

A168502 For each permutation of {1,2,...,n} one or more integers might not be part of any longest increasing subsequence (LIS) of that permutation. The sequence lists the number of permutations for which ceiling(n/2) is not part of any LIS. For example, if n=4, 2 is not in any LIS of the two permutations (1342) and (3421).

Original entry on oeis.org

0, 0, 0, 2, 15, 122, 990, 9210, 91013, 1001285, 11774254, 150849588, 2059781391

Offset: 1

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

The sequence lists the minimal term of members of the array n=1 {0} n=2 {0,0} n=3 {1,0,1} n=4 {6,2,2,6} n=5 {37,18,15,18,37} n=6 {257,153,122,122,153,257} n=7{1998,1338,1081,990,1081,1338,1998} n=8 {17280,12449,10298,9210,9210,10298,12449,17280}. The j-th row above lists the number of permutations on {1,2,...,j} for which 1,2,3,...,j are not part of any LIS. An alternative sequence would list the maximal terms in the rows above as 0,0,1,6,37,257,1998,17280,...

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

Cf. A167995, A167999.

a(9)-a(13) from Manfred Scheucher, Jun 08 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

A258690 Total number of longest increasing runs in all permutations of [n].

Original entry on oeis.org

1, 1, 3, 8, 32, 167, 1096, 8117, 67859, 627649, 6394781, 71201812, 861677250, 11270215084, 158564826122, 2389093936957, 38396351412220, 655832914215010, 11865953978478454, 226724258401651143, 4562163514498852598, 96430112680094188086, 2136024671422363671272

Offset: 0

Alois P. Heinz, Jun 07 2015

nonn

a(0) = 1 by convention.

a(n) >= n! = A000142(n).

			a(1) = 1: (1).
a(2) = 3: (12), (2)(1).
a(3) = 8: (123), (13)2, 2(13), (23)1, 3(12), (3)(2)(1).

Alois P. Heinz, Table of n, a(n) for n = 0..100

Cf. A000142, A008304, A167999.

b:= proc(u, o, l, m, c) option remember;  `if`(u+o=0, `if`(l>m, 1,
      `if`(lm, 1, `if`(l b(n, 0$4):
seq(a(n), n=0..25);

b[u_, o_, l_, m_, c_] := b[u, o, l, m, c] = If[u + o == 0, If[l > m, 1,
     If[l < m, c, c + 1]], Sum[b[u - j, o + j - 1, 1, Max[l, m],
     If[l > m, 1, If[l < m, c, c + 1]]], {j, 1, u}] +
           Sum[b[u+j-1, o-j, l+1, m, c], {j, 1, o}]];
a[n_] :=  b[n, 0, 0, 0, 0];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 15 2022, after Alois P. Heinz *)

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

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

A258690 Total number of longest increasing runs in all permutations of [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica