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,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 A332568 A274466

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