login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 7 20:58 EDT 2022. Contains 355994 sequences. (Running on oeis4.)