|
|
A238978
|
|
Number of ballot sequences of length n with exactly 3 fixed points.
|
|
2
|
|
|
0, 0, 0, 1, 1, 3, 9, 28, 93, 321, 1168, 4404, 17328, 70408, 296436, 1284768, 5740804, 26332788, 124066608, 598625296, 2958281328, 14941136784, 77111251408, 406028059968, 2180584156176, 11930067296848, 66468429865344, 376770132276288, 2172036623279488
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
The fixed points are in the first 3 positions.
Also the number of standard Young tableaux with n cells such that the first column contains 1, 2, and 3, but not 4. An alternate definition uses the first row.
|
|
LINKS
|
|
|
FORMULA
|
See Maple program.
a(n) ~ sqrt(2)/16 * exp(sqrt(n)-n/2-1/4) * n^(n/2) * (1 + 7/(24*sqrt(n))). - Vaclav Kotesovec, Mar 07 2014
Recurrence (for n>=5): (n-4)*(n^3 - 10*n^2 + 27*n - 26)*a(n) = (n^4 - 14*n^3 + 67*n^2 - 150*n + 152)*a(n-1) + (n-5)*(n-3)*(n^3 - 7*n^2 + 10*n - 8)*a(n-2). - Vaclav Kotesovec, Mar 08 2014
|
|
EXAMPLE
|
a(3) = 1: [1,2,3].
a(4) = 1: [1,2,3,1].
a(5) = 3: [1,2,3,1,1], [1,2,3,1,2], [1,2,3,1,4].
a(6) = 9: [1,2,3,1,1,1], [1,2,3,1,1,2], [1,2,3,1,1,4], [1,2,3,1,2,1], [1,2,3,1,2,3], [1,2,3,1,2,4], [1,2,3,1,4,1], [1,2,3,1,4,2], [1,2,3,1,4,5].
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<4, n*(n-1)*(n-2)/6,
((4*n^3-54*n^2+216*n-254) *a(n-1)
+(n-5)*(3*n^3-31*n^2+84*n-30) *a(n-2)
-(n-5)*(n-6)*(n^2-3*n-8) *a(n-3)) /
((n-3)*(3*n^2-33*n+86)))
end:
seq(a(n), n=0..40);
|
|
MATHEMATICA
|
b[n_, l_List] := b[n, l] = If[n <= 0, 1, b[n - 1, Append[l, 1]] + Sum[If[i == 1 || l[[i - 1]] > l[[i]], b[n - 1, ReplacePart[l, i -> l[[i]] + 1]], 0], {i, 1, Length[l]}]]; a[n_] := If[n == 3, 1, b[n - 4, {2, 1, 1}]]; a[n_ /; n < 3] = 0; Table[Print["a(", n, ") = ", an = a[n]]; an, {n, 0, 40}] (* Jean-François Alcover, Feb 06 2015, after Maple *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|