login
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.
3
0, 0, 0, 0, 2, 218, 3070, 32972, 336196, 3533026, 39574122, 477773658, 6222603756, 87162325448, 1307616361026, 20922578066742, 355686650877778, 6402370841198538, 121645089807861208, 2432901968797138968, 51090942024922288784, 1124000727228733213002
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
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 A332568 A274466
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