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