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,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

Cf. A000085, A005425, A238802.

Sequence in context: A239117 A239118 A239119 * A148940 A169781 A162998

Adjacent sequences: A238800 A238801 A238802 * A238804 A238805 A238806

Keyword

nonn,easy

Author

Joerg Arndt and Alois P. Heinz, Mar 05 2014

Status

approved