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!)
A258041 Number of 312-avoiding derangements of {1,2,...,n}. 1
1, 0, 1, 1, 4, 10, 31, 94, 303, 986, 3284, 11099, 38024, 131694, 460607, 1624451, 5771532, 20640334, 74246701, 268478962, 975436348, 3559204700, 13037907692, 47931423574, 176792821643, 654078238224, 2426705590840, 9026907769955 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

In the Mathematica recurrence below, a(n,k) is the number of 312-avoiding permutations of {1,2,...,n} with no entry moved k places to the right of its "natural" position; thus a(n,0) = a(n). The recurrence for a(n,k) counts these permutations by the position j of 1 in the permutation.

Numerical evidence suggests lim_{n->inf} a(n)/a(n-1) = 4 and lim_{n->inf} A000108(n)/(n*a(n)) ~ .105.

LINKS

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000

Aaron Robertson, Dan Saracino, and Doron Zeilberger, Refined Restricted Permutations, arXiv:math/0203033 [math.CO], 2002.

Aaron Robertson, Dan Saracino, and Doron Zeilberger, Refined Restricted Permutations, Annals of Combinatorics 6 (2002) 427-444.

FORMULA

G.f.: 1/(1 + C(0)x -

         x/(1 + C(1)x^2 -

             x/(1 + C(2)x^3 -

                x/(1 + C(3)x^4 -

                   x/(1 + C(4)x^5 -

                      x/(1 + C(5)x^6 - ...)))))))) [continued fraction] where C(n) = A000108(n) is the n-th Catalan number.

EXAMPLE

a(4) = 4 counts 2143, 2341, 3421, 4321.

MATHEMATICA

a[n_, k_] /; k >= n := CatalanNumber[n]

a[n_, k_] /; 0 <= k < n :=

a[n, k] = Sum[a[j - 1, k + 1] a[n - j, k]  , {j, k}] + Sum[a[j - 1, k + 1] a[n - j, k], {j, k + 2, n}]

a[n_] := a[n, 0]

Table[a[n], {n, 0, 30}]

CROSSREFS

Cf. A000108, A000166, A061547.

Sequence in context: A321143 A095127 A006342 * A289447 A135831 A213106

Adjacent sequences:  A258038 A258039 A258040 * A258042 A258043 A258044

KEYWORD

nonn

AUTHOR

David Callan, May 17 2015

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 July 2 08:02 EDT 2020. Contains 335398 sequences. (Running on oeis4.)