|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|