login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A172068 Triangular array T(n,k) = the number of n-step one dimensional walks that return to the origin exactly k times. 1
1, 2, 2, 2, 4, 4, 6, 6, 4, 12, 12, 8, 20, 20, 16, 8, 40, 40, 32, 16, 70, 70, 60, 40, 16, 140, 140, 120, 80, 32, 252, 252, 224, 168, 96, 32, 504, 504, 448, 336, 192, 64, 924, 924, 840, 672, 448, 224, 64, 1848, 1848, 1680, 1344, 896, 448, 128, 3432, 3432, 3168 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

In a ballot count of n total votes cast for two candidates, T(n,k) is the number of counts in which exactly k ties occur during the counting process (disregarding the initial tie of 0 to 0) and considering every possible outcome of votes.

REFERENCES

W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, 3rd ed. New York: Wiley, pp.67-97, 1968

LINKS

Alois P. Heinz, Rows n = 0..200, flattened

FORMULA

T(2n,k) = binomial(2n-k, n-k)*2^k; T(2n+1,k) = 2*T(2n,k). [David Callan, May 01 2013]

EXAMPLE

T(5,2) = 8 because there are eight possible vote count sequences in which five votes are cast and the count becomes tied two times during the counting process: {-1, 0, -1, 0, -1}, {-1, 0, -1, 0, 1}, {-1, 0, 1, 0, -1}, {-1, 0, 1, 0, 1}, {1, 0, -1, 0, -1}, {1, 0, -1, 0, 1}, {1, 0, 1, 0, -1}, {1, 0, 1, 0, 1}

Triangle begins:

1;

2;

2, 2;

4, 4;

6, 6, 4;

12, 12, 8;

20, 20, 16, 8;

40, 40, 32, 16;

MAPLE

T:= (n, k)-> `if`(irem(n, 2, 'r')=0, binomial(n-k, r-k)*2^k, 2*T(n-1, k)):

seq(seq(T(n, k), k=0..iquo(n, 2)), n=0..20); # Alois P. Heinz, May 07 2013

MATHEMATICA

Table[Table[ Length[Select[Map[Accumulate, Strings[{-1, 1}, n]], Count[ #, 0] == k &]], {k, 0, Floor[n/2]}], {n, 0, 20}] // Grid

CROSSREFS

The first two columns corresponding to k=0 and k=1 are A063886.

Sequence in context: A134318 A246452 A104295 * A289195 A008331 A173388

Adjacent sequences:  A172065 A172066 A172067 * A172069 A172070 A172071

KEYWORD

nonn,tabf

AUTHOR

Geoffrey Critzer, Jan 24 2010

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 22 10:29 EDT 2019. Contains 322330 sequences. (Running on oeis4.)