A167995 -id:A167995 - cp's OEIS frontend

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

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

A331883 The number of permutations in the symmetric group S_n in which it is possible to find two disjoint increasing subsequences each with length equal to the length of the longest increasing subsequence of the permutation.

Original entry on oeis.org

0, 1, 1, 5, 26, 132, 834, 6477, 56242

Offset: 1

Ildar Gainullin, Jan 30 2020

Only permutations whose longest increasing subsequence is at most n/2 need to be considered.

			a(3) = 1 because the only permutation whose longest increasing subsequence is 1 is [3,2,1] and this contains two disjoint increasing subsequences of length 1.
The a(4) = 5 permutations are:
  [2,1,4,3],
  [2,4,1,3],
  [3,1,4,2],
  [3,4,1,2],
  [4,3,2,1].

Wikipedia, Longest increasing subsequence problem

Cf. A047874, A047887, A167995.

cp's OEIS Frontend

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

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

A331883 The number of permutations in the symmetric group S_n in which it is possible to find two disjoint increasing subsequences each with length equal to the length of the longest increasing subsequence of the permutation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs