A167510 The number of bidirectional ballot sequences of length n, i.e., the number of 0-1 sequences of length n such that every prefix and every suffix has more 1's than 0's.

1, 1, 1, 1, 2, 3, 5, 9, 15, 28, 49, 91, 166, 307, 574, 1065, 2016, 3769, 7176, 13532, 25842, 49113, 93995, 179775, 344796, 662676, 1273880, 2457275, 4735080, 9158972, 17691713, 34293541, 66396112, 128922830, 250145886, 486420441, 945623604

Offset

1,5

Comments

Equivalently, the number of "culminating paths", that is, 0-1 sequences of length n-2 such that every prefix has at least as many 1's as 0's, and the difference between the number of 1's and 0's in a prefix is maximal when the prefix is the entire word. - Mireille Bousquet-Mélou, Apr 07 2015

Also, coefficients of the power series for the capacitance of a sphere-plane system, expanded in terms of R/2d where R is the radius of the sphere and d is the distance between the sphere center and the infinite plane. - Scott Crittenden, Dec 15 2017

References

L. Page and N. I. Adams, Principles of Electricity, D. Van Nostrand Co., 1931, p. 105.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

M. Bousquet-Mélou and Y. Ponty, Culminating paths, Discrete Math and Theoretical Computer Science, Vol. 10, No. 2 (2008) 125-152.

B. Hackl, C. Heuberger, H. Prodinger, and S. Wagner, Analysis of Bidirectional Ballot Sequences and Random Walks Ending in their Maximum, arXiv preprint arXiv:1503.08790 [math.CO], 2015.

Y. Zhao, Constructing MSTD sets using bidirectional ballot sequences, arXiv:0908.4442 [math.CO], 2009.

Y. Zhao, Constructing MSTD sets using bidirectional ballot sequences, Journal of Number Theory, Volume 130, Issue 5, May 2010, Pages 1212-1220.

Formula

G.f.: Sum_k t^{k+2}/F_{k-1} where F_k is the sequence of Fibonacci polynomials, given by F_0=F_1=1 and F_k=F_{k-1}-t^2 F_{k-2}. - Mireille Bousquet-Mélou, Apr 07 2015

G.f.: Sum_{k>0} (2*x)^k*p/((1+p)^k-(1-p)^k), with p=sqrt(1-4*x^2). - Benedict W. J. Irwin, Sep 15 2016

Example

For n=6, the three sequences are 111111, 110111, 111011.
The corresponding culminating paths are 1111, 1011, 1101.

Mathematica

Num=30; p=Sqrt[1-4x^2]; Rest[CoefficientList[Series[Sum[(2^n p x^n)/ ((1+p)^n-(1-p)^n), {n, 1, Num}], {x, 0, Num}], x]] (* Benedict W. J. Irwin, Sep 15 2016 *)

Crossrefs

Sequence in context: A178738 A060013 A092424 * A351359 A191701 A066726

Adjacent sequences: A167507 A167508 A167509 * A167511 A167512 A167513

Keyword

nonn

Author

Yufei Zhao (yufei.zhao(AT)gmail.com), Nov 05 2009, Nov 11 2009

Status

approved