A172068 Triangular array T(n,k) is the number of n-step one-dimensional walks that return to the origin exactly k times.

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

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

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

Adjacent sequences: A172065 A172066 A172067 * A172069 A172070 A172071

Keyword

nonn,tabf

Author

Geoffrey Critzer, Jan 24 2010

Status

approved