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