

A172068


Triangular array T(n,k) = the number of nstep 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.6797, 1968


LINKS

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


FORMULA

T(2n,k) = binomial(2nk, nk)*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(nk, rk)*2^k, 2*T(n1, 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



