Anant Godbole - 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

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

Original entry on oeis.org

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

A124188 Number of 3-good permutations on {1,2,...,n}, i.e., permutations that contain each of the six patterns {123, 132, 213, 231, 312, 321} as a subsequence.

Original entry on oeis.org

0, 0, 0, 0, 2, 218, 3070, 32972, 336196, 3533026, 39574122, 477773658, 6222603756, 87162325448, 1307616361026, 20922578066742, 355686650877778, 6402370841198538, 121645089807861208, 2432901968797138968, 51090942024922288784, 1124000727228733213002

Offset: 1

Nicole Holder, David Simpson and Anant Godbole, Dec 06 2006

nonn

A permutation of the integers {1,2,....,n} is k-good if each of the k! patterns on k integers is contained as a subsequence of the permutation. For example, with k=2, there are n!-2 permutations that contain both a "12" and a "21" pattern as a subsequence.

			a(5) = 2 because 2 permutations of {1,2,3,4,5} are 3-good: (2,5,3,1,4), (4,1,3,5,2).

Alois P. Heinz, Table of n, a(n) for n = 1..450
Rodica Simion and Frank W. Schmidt, Restricted Permutations, European Journal of Combinatorics, 6, Issue 4 (1985), 383-406.

[0,0,0,0] cat [ Factorial(n) -6*Binomial(2*n,n)/(n+1) +5*2^n +4*Binomial(n,2) -14*n -2*Fibonacci(n+1) +20: n in [5..30]]; // Vincenzo Librandi, Dec 03 2015

with(combinat):
a:= n-> `if`(n<5, 0, n! -6*binomial(2*n, n)/(n+1) +5*2^n
        +4*binomial(n, 2) -14*n -2*fibonacci(n+1) +20):
seq(a(n), n=1..30);

Join[{0, 0, 0, 0}, Table[n! - 6 Binomial[2 n, n]/(n + 1)+ 5 2^n + 4 Binomial[n, 2] - 14 n - 2 Fibonacci[n + 1] + 20, {n, 5, 25}]] (* Vincenzo Librandi, Dec 03 2015 *)

a(n) = if(n<5, 0, n! - 6*binomial(2*n, n)/(n+1) + 5*2^n + 4*binomial(n, 2) - 14*n - 2*fibonacci(n+1) + 20); \\  Altug Alkan, Dec 03 2015

a(n) = n! -6*C(2*n,n)/(n+1) +5*2^n +4*C(n,2) -14*n -2*A000045(n+1) +20, n>4.

Edited by Alois P. Heinz, May 25 2011

a(22) from Vincenzo Librandi, Dec 03 2015

A117717 Maximal number of regions obtained by a straight line drawing of the complete bipartite graph K_{n,n}.

Original entry on oeis.org

0, 2, 13, 45, 116, 250, 477, 833, 1360, 2106, 3125, 4477, 6228, 8450, 11221, 14625, 18752, 23698, 29565, 36461, 44500, 53802, 64493, 76705, 90576, 106250, 123877, 143613, 165620, 190066, 217125, 246977, 279808, 315810, 355181, 398125, 444852, 495578, 550525

Offset: 1

Patricia A. Carey and Anant Godbole, Apr 13 2006

This sequence is in the same spirit as A000127 where a formula is given for the maximal number of regions obtained by a straight line drawing of the complete graph K_n with the vertices located on the perimeter of a circle. This yields the often quoted sequence A000127.

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A000127.

[(n-1)^2*(n^2+4)/4: n in [1..40]]; // Vincenzo Librandi, Sep 09 2011

A117717 := proc(n)
    (n-1)^2*(n^2+4)/4 ;
end proc:
seq(A117717(n),n=1..10) ; # R. J. Mathar, Sep 15 2013

Table[n^2-2n+Binomial[n,2]^2+1,{n,40}] (* or *) LinearRecurrence[ {5,-10,10,-5,1},{0,2,13,45,116},40] (* Harvey P. Dale, Oct 16 2012 *)

a(n) = n^2 - 2n + C(n,2)^2 + 1
a(n) = (n-1)^2*(n^2+4)/4. - Vincenzo Librandi, Sep 09 2011
G.f.: x^2*(2+3*x+x^3)/(1-x)^5. - Colin Barker, Feb 15 2012
a(n)=5*a(n-1)-10*a(n-2)+ 10*a(n-3)- 5*a(n-4)+a(n-5), n>5. - Harvey P. Dale, Oct 16 2012

More terms from Harvey P. Dale, Oct 16 2012

cp's OEIS Frontend

User: Anant Godbole

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

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

A124188 Number of 3-good permutations on {1,2,...,n}, i.e., permutations that contain each of the six patterns {123, 132, 213, 231, 312, 321} as a subsequence.

Views

Author

Keywords

Comments

Examples

Links

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A117717 Maximal number of regions obtained by a straight line drawing of the complete bipartite graph K_{n,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions