login
A172068
Triangular array T(n,k) is 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
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
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
PROG
(PARI) T(n, k) = if(Mod(n, 2)==0, 2^k*binomial(n-k, (n/2)-k), 2^(k+1)*binomial(n-k-1, ((n-1)/2)-k) ); \\ G. C. Greubel, Dec 05 2019
(Magma)
function T(n, k)
if (n mod 2) eq 0 then return 2^k*Binomial(n-k, Floor(n/2)-k);
else return 2^(k+1)*Binomial(n-k-1, Floor((n-1)/2)-k);
end if; return T; end function;
[T(n, k): k in [0..Floor(n/2)], n in [0..20]]; // G. C. Greubel, Dec 05 2019
(Sage)
def T(n, k):
if (mod(n, 2)==0): return 2^k*binomial(n-k, (n/2)-k)
else: return 2^(k+1)*binomial(n-k-1, ((n-1)/2)-k)
[[T(n, k) for k in (0..floor(n/2))] for n in (0..20)] # G. C. Greubel, Dec 05 2019
(GAP)
T:= function(n, k)
if Mod(n, 2)=0 then return 2^k*Binomial(n-k, Int(n/2)-k);
else return 2^(k+1)*Binomial(n-k-1, Int((n-1)/2)-k);
fi; end;
Flat(List([0..20], n-> List([0..Int(n/2)], k-> T(n, k) ))); # G. C. Greubel, Dec 05 2019
CROSSREFS
The first two columns corresponding to k=0 and k=1 are A063886.
Sequence in context: A134318 A246452 A104295 * A289195 A353711 A008331
KEYWORD
nonn,tabf
AUTHOR
Geoffrey Critzer, Jan 24 2010
STATUS
approved