cp's OEIS Frontend

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.

%I A124188 #28 Mar 10 2024 14:20:11
%S A124188 0,0,0,0,2,218,3070,32972,336196,3533026,39574122,477773658,
%T A124188 6222603756,87162325448,1307616361026,20922578066742,355686650877778,
%U A124188 6402370841198538,121645089807861208,2432901968797138968,51090942024922288784,1124000727228733213002
%N 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.
%C A124188 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 A124188 Alois P. Heinz, <a href="/A124188/b124188.txt">Table of n, a(n) for n = 1..450</a>
%H A124188 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 A124188 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 A124188 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 A124188 with(combinat):
%p A124188 a:= n-> `if`(n<5, 0, n! -6*binomial(2*n, n)/(n+1) +5*2^n
%p A124188         +4*binomial(n, 2) -14*n -2*fibonacci(n+1) +20):
%p A124188 seq(a(n), n=1..30);
%t A124188 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 A124188 (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 A124188 (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 A124188 nonn
%O A124188 1,5
%A A124188 Nicole Holder, David Simpson and _Anant Godbole_, Dec 06 2006
%E A124188 Edited by _Alois P. Heinz_, May 25 2011
%E A124188 a(22) from _Vincenzo Librandi_, Dec 03 2015