login
A238803
Number of ballot sequences of length 2n with exactly n fixed points.
2
1, 1, 3, 9, 29, 99, 357, 1351, 5343, 21993, 93923, 414969, 1892277, 8887291, 42912261, 212676951, 1080355463, 5617772049, 29868493827, 162204146857, 898874710797, 5078665886931, 29232738375653, 171294038649639, 1021117638212079, 6188701520663929
OFFSET
0,3
COMMENTS
The fixed points are in the positions 1,2,...,n.
Also the number of standard Young tableaux with 2n cells where n is the length of the maximal consecutive sequence 1,2,...,k in the first column. An alternate definition uses the first row.
All terms are odd because the counted structures come in pairs with exactly one exception.
Except for a(0), first differences of A005425. - Ivan N. Ianakiev, Sep 01 2019
LINKS
Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..750
Wikipedia, Young tableau
FORMULA
a(n) = ((2*n-1)*a(n-1)+n*(n-2)*a(n-2))/(n-1) for n>1, a(0) = a(1) = 1.
a(n) = A238802(2*n,n).
a(n) = Sum_{k=0..n} C(n-1,k) * A000085(n-k).
a(n) ~ exp(2*sqrt(n)-n/2-1) * n^(n/2) / sqrt(2) * (1 - 1/(6*sqrt(n))). - Vaclav Kotesovec, Mar 07 2014
EXAMPLE
For n=3 we have the following a(3) = 9 ballot sequences: [1,2,3,1,1,1], [1,2,3,1,2,3], [1,2,3,1,1,2], [1,2,3,1,2,1], [1,2,3,1,4,1], [1,2,3,1,4,2], [1,2,3,1,1,4], [1,2,3,1,2,4], [1,2,3,1,4,5].
Their corresponding tableaux are:
: 1456 14 : 145 146 : 146 14 : 145 14 : 14 :
: 2 25 : 26 25 : 2 26 : 2 25 : 2 :
: 3 36 : 3 3 : 3 3 : 3 3 : 3 :
: : : 5 5 : 6 6 : 5 :
: : : : : 6 :
MAPLE
a:= proc(n) option remember; `if`(n<2, 1,
((2*n-1) *a(n-1) +n*(n-2) *a(n-2)) / (n-1))
end:
seq(a(n), n=0..35);
MATHEMATICA
RecurrenceTable[{a[0]==a[1]==1, a[n]==((2n-1)a[n-1]+n(n-2)a[n-2])/(n-1)}, a, {n, 30}] (* Harvey P. Dale, Jun 25 2014 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Joerg Arndt and Alois P. Heinz, Mar 05 2014
STATUS
approved