A238803 Number of ballot sequences of length 2n with exactly n fixed points.

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

Author

Joerg Arndt and Alois P. Heinz, Mar 05 2014

Keywords

• nonn
• easy

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

Examples

			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  :
		

Links

• Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..750
• Wikipedia, Young tableau

Crossrefs

Cf. A000085, A005425, A238802.

Programs

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 *)

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