login
Number of permutations on {1,...,n} containing any given pattern alpha in the symmetric group S_3.
203

%I #32 Oct 06 2024 09:15:32

%S 0,0,1,10,78,588,4611,38890,358018,3612004,39858014,478793588,

%T 6226277900,87175616760,1307664673155,20922754530330,355687298451210,

%U 6402373228089300,121645098641568810,2432902001612519580,51090942147243172980,1124000727686125116360

%N Number of permutations on {1,...,n} containing any given pattern alpha in the symmetric group S_3.

%C This is well-defined because for all patterns alpha in S_3 the number of permutations in S_n avoiding alpha is the same (the Catalan numbers). - _Emeric Deutsch_, May 05 2008

%H Alois P. Heinz, <a href="/A056986/b056986.txt">Table of n, a(n) for n = 1..170</a>

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000002/">The number of occurrences of the pattern [1,2,3] inside a permutation of length at least 3</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000220/">The number of occurrences of the pattern [1,3,2] in a permutation</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000218/">The number of occurrences of the pattern [2,1,3] in a permutation</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000219/">The number of occurrences of the pattern [2,3,1] in a permutation</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000217/">The number of occurrences of the pattern [3,1,2] in a permutation</a>

%H R. Simion and F. W. Schmidt, <a href="http://dx.doi.org/10.1016/S0195-6698(85)80052-4">Restricted permutations</a>, European J. Combin., 6, pp. 383-406, 1985.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PermutationPattern.html">Permutation Pattern</a>

%F From _Alois P. Heinz_, Jul 05 2012: (Start)

%F a(n) = A214152(n, 3).

%F a(n) = A000142(n) - A000108(n).

%F a(n) = A000142(n) - A214015(n, 2). (End)

%F E.g.f.: 1/(1 - x) - exp(2*x)*(BesselI(0,2*x) - BesselI(1,2*x)). - _Ilya Gutkovskiy_, Jan 21 2017

%e a(4) = 10 because, taking, for example, the pattern alpha=321, we have 3214, 3241, 1432, 2431, 3421, 4213, 4132, 4231, 4312 and 4321.

%p a:= n-> n! -binomial(2*n, n)/(n+1):

%p seq(a(n), n=1..25); # _Alois P. Heinz_, Jul 05 2012

%t Table[n! -CatalanNumber[n], {n,30}]

%o (PARI) a(n)=n!-binomial(n+n,n+1)/n \\ _Charles R Greathouse IV_, Jun 10 2011

%o (Magma)

%o A056986:= func< n | Factorial(n) - Catalan(n) >;

%o [A056986(n): n in [1..30]]; // _G. C. Greubel_, Oct 06 2024

%o (SageMath)

%o def A056986(n): return factorial(n) - catalan_number(n)

%o [A056986(n) for n in range(1,31)] # _G. C. Greubel_, Oct 06 2024

%Y Cf. A000108, A000142, A138159, A214015, A214152.

%K nonn,easy

%O 1,4

%A _Eric W. Weisstein_