login
The number of simple permutations of length n which avoid 1243 and 2431.
1

%I #21 Jul 22 2018 14:36:46

%S 1,2,0,2,4,10,21,44,89,178,352,692,1355,2648,5171,10100,19744,38646,

%T 75761,148772,292653,576678,1138240,2250152,4454679,8830640,17525991,

%U 34820264,69244864,137815978,274487517,547035452,1090790465,2176043098,4342753696,8669805020,17313228899

%N The number of simple permutations of length n which avoid 1243 and 2431.

%H Jay Pantone, <a href="http://arxiv.org/abs/1309.0832">The Enumeration of Permutations Avoiding 3124 and 4312</a>, arXiv:1309.0832 [math.CO], (2013)

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_4">Permutation classes avoiding two patterns of length 4</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3,-4,3,2).

%F G.f.: (x-2*x^2-5*x^3+12*x^4+x^5-8*x^6-3*x^7)/((1-2*x)*(1-x-x^2)^2).

%F a(n) = -2*A000045(n+1) +A191830(n+2) +2^(n-3), n>2. - _R. J. Mathar_, Dec 06 2013

%t Join[{1, 2}, LinearRecurrence[{4, -3, -4, 3, 2}, {0, 2, 4, 10, 21}, 40]] (* _Jean-François Alcover_, Jul 22 2018 *)

%o (PARI) x='x+O('x^66); Vec((x-2*x^2-5*x^3+12*x^4+x^5-8*x^6-3*x^7)/((1-2*x)*(1-x-x^2)^2)) \\ _Joerg Arndt_, Jun 19 2013

%Y The number of all permutations which avoid 1243 and 2431 is A165534.

%K nonn

%O 1,2

%A _Jay Pantone_, Jun 06 2013