login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A111279 Number of permutations avoiding the patterns {3241,3421,4321}; number of weak sorting class based on 3241. 3
1, 2, 6, 21, 79, 309, 1237, 5026, 20626, 85242, 354080, 1476368, 6173634, 25873744, 108628550, 456710589, 1922354351, 8098984433, 34147706833, 144068881455, 608151037123, 2568318694867, 10850577045131, 45856273670841 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Is this the same sequence as A026737? - Andrew S. Plewe, May 09 2007

Yes, see the Callan reference "A bijection...". [Joerg Arndt, Feb 29 2016]

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..300

M. Albert, R. Aldred, M. Atkinson, C. Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb. 12 (2005) R31.

David Callan, A bijection for two sequences in OEIS, arXiv:1602.08347 [math.CO], 2016.

David Callan, Toufik Mansour, Five subsets of permutations enumerated as weak sorting permutations, arXiv:1602.05182 [math.CO], 2016.

Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

FORMULA

O.g.f.: (3-13*x+2*x^2+(5*x-1)*sqrt(1-4*x))/(2*(1-4*x-x^2)).

a(n) is the sum of top row terms of M^(n-1), M = an infinite square production matrix with powers of 2 as the left border as follows:

1, 1, 0, 0, 0,...

2, 1, 1, 0, 0,...

4, 1, 1, 1, 0,...

8, 1, 1, 1, 1,...

... - Gary W. Adamson, Nov 14 2011

The top rows of these powered matrics, 1; 1,1; 3,2,1; 11,6,3,1; 43,21,10,4,1; appear also as columns in A026736. - R. J. Mathar, Nov 15 2011

Conjecture: n*a(n) +(16-13*n)*a(n-1)+(55*n-134)*a(n-2) +264-71*n)*a(n-3) +10*(7-2*n)*a(n-4) = 0. - R. J. Mathar, Nov 15 2011

Shorter recurrence: n*(n+5)*a(n) = 2*(4*n^2 + 17*n - 30)*a(n-1) - 3*(5*n^2 + 17*n - 80)*a(n-2) - 2*(n+6)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 18 2012

a(n) ~ (5/2-11/10*sqrt(5))*(sqrt(5)+2)^n. - Vaclav Kotesovec, Oct 18 2012

EXAMPLE

a(4) = 21 since the top row terms of M^3 = (11, 6, 3, 1, 0, 0, 0,...)

MATHEMATICA

Rest[ CoefficientList[ Series[(3 - 13x + 2x^2 + (5x - 1)*Sqrt[1 - 4x])/(2*(1 - 4x - x^2)), {x, 0, 24}], x]] (* Robert G. Wilson v *)

CROSSREFS

Sequence in context: A150196 A148491 A026737 * A150197 A150198 A257562

Adjacent sequences:  A111276 A111277 A111278 * A111280 A111281 A111282

KEYWORD

nonn

AUTHOR

Len Smiley, Nov 01 2005

EXTENSIONS

More terms from Robert G. Wilson v, Nov 04 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 6 08:53 EDT 2020. Contains 333268 sequences. (Running on oeis4.)