cp's OEIS Frontend

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

%I A172068 #26 Sep 08 2022 08:45:50
%S A172068 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,
%T A172068 140,120,80,32,252,252,224,168,96,32,504,504,448,336,192,64,924,924,
%U A172068 840,672,448,224,64,1848,1848,1680,1344,896,448,128,3432,3432,3168
%N A172068 Triangular array T(n,k) is the number of n-step one-dimensional walks that return to the origin exactly k times.
%C A172068 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.
%D A172068 W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, 3rd ed. New York: Wiley, pp. 67-97, 1968
%H A172068 Alois P. Heinz, <a href="/A172068/b172068.txt">Rows n = 0..200, flattened</a>
%F A172068 T(2n,k) = binomial(2n-k, n-k)*2^k; T(2n+1,k) = 2*T(2n,k). - _David Callan_, May 01 2013
%e A172068 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}
%e A172068 Triangle begins:
%e A172068    1;
%e A172068    2;
%e A172068    2,  2;
%e A172068    4,  4;
%e A172068    6,  6,  4;
%e A172068   12, 12,  8;
%e A172068   20, 20, 16,  8;
%e A172068   40, 40, 32, 16;
%p A172068 T:= (n, k)-> `if`(irem(n, 2, 'r')=0, binomial(n-k, r-k)*2^k, 2*T(n-1,k)):
%p A172068 seq(seq(T(n,k), k=0..iquo(n,2)), n=0..20); # _Alois P. Heinz_, May 07 2013
%t A172068 Table[Table[ Length[Select[Map[Accumulate, Strings[{-1, 1}, n]], Count[ #, 0] == k &]], {k, 0, Floor[n/2]}], {n, 0, 20}] // Grid
%o A172068 (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
%o A172068 (Magma)
%o A172068 function T(n,k)
%o A172068   if (n mod 2) eq 0 then return 2^k*Binomial(n-k, Floor(n/2)-k);
%o A172068   else return 2^(k+1)*Binomial(n-k-1, Floor((n-1)/2)-k);
%o A172068   end if; return T; end function;
%o A172068 [T(n,k): k in [0..Floor(n/2)], n in [0..20]]; // _G. C. Greubel_, Dec 05 2019
%o A172068 (Sage)
%o A172068 def T(n, k):
%o A172068     if (mod(n,2)==0): return 2^k*binomial(n-k, (n/2)-k)
%o A172068     else: return 2^(k+1)*binomial(n-k-1, ((n-1)/2)-k)
%o A172068 [[T(n, k) for k in (0..floor(n/2))] for n in (0..20)] # _G. C. Greubel_, Dec 05 2019
%o A172068 (GAP)
%o A172068 T:= function(n,k)
%o A172068     if Mod(n,2)=0 then return 2^k*Binomial(n-k, Int(n/2)-k);
%o A172068     else return 2^(k+1)*Binomial(n-k-1, Int((n-1)/2)-k);
%o A172068     fi; end;
%o A172068 Flat(List([0..20], n-> List([0..Int(n/2)], k-> T(n,k) ))); # _G. C. Greubel_, Dec 05 2019
%Y A172068 The first two columns corresponding to k=0 and k=1 are A063886.
%K A172068 nonn,tabf
%O A172068 0,2
%A A172068 _Geoffrey Critzer_, Jan 24 2010