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.

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

Offset: 1

Author

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

Keywords

• nonn

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.

Examples

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

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.

Programs

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

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

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

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.

Extensions

Edited by Alois P. Heinz, May 25 2011

a(22) from Vincenzo Librandi, Dec 03 2015