login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
0, 0, 0, 0, 2, 218, 3070, 32972, 336196, 3533026, 39574122, 477773658, 6222603756, 87162325448, 1307616361026, 20922578066742, 355686650877778, 6402370841198538, 121645089807861208, 2432901968797138968, 51090942024922288784, 1124000727228733213002 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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.

LINKS

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.

FORMULA

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.

EXAMPLE

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).

MAPLE

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);

MATHEMATICA

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 *)

PROG

(MAGMA) [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

(PARI) 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

CROSSREFS

Sequence in context: A202741 A239529 A101393 * A261936 A274466 A307511

Adjacent sequences:  A124185 A124186 A124187 * A124189 A124190 A124191

KEYWORD

nonn

AUTHOR

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

EXTENSIONS

Edited by Alois P. Heinz, May 25 2011

a(22) from Vincenzo Librandi, Dec 03 2015

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 August 25 06:07 EDT 2019. Contains 326323 sequences. (Running on oeis4.)