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

%I

%S 0,0,0,0,2,218,3070,32972,336196,3533026,39574122,477773658,

%T 6222603756,87162325448,1307616361026,20922578066742,355686650877778,

%U 6402370841198538,121645089807861208,2432901968797138968,51090942024922288784,1124000727228733213002

%N 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.

%C 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.

%H Alois P. Heinz, <a href="/A124188/b124188.txt">Table of n, a(n) for n = 1..450</a>

%H Rodica Simion and Frank W. Schmidt, <a href="http://dx.doi.org/10.1016/S0195-6698(85)80052-4"> Restricted Permutations</a>, European Journal of Combinatorics, 6, Issue 4 (1985), 383-406.

%F 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.

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

%p with(combinat):

%p a:= n-> `if`(n<5, 0, n! -6*binomial(2*n, n)/(n+1) +5*2^n

%p +4*binomial(n, 2) -14*n -2*fibonacci(n+1) +20):

%p seq(a(n), n=1..30);

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

%o (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

%o (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

%K nonn

%O 1,5

%A Nicole Holder, David Simpson and _Anant Godbole_, Dec 06 2006

%E Edited by _Alois P. Heinz_, May 25 2011

%E a(22) from _Vincenzo Librandi_, Dec 03 2015

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 September 20 02:17 EDT 2019. Contains 327207 sequences. (Running on oeis4.)