#---------------------------------------------- # Function Definitions #---------------------------------------------- # C counts the number of lattice paths from x0 to x of length n C <- function(n,x0,x){ k = (n +(x-x0))/2; out = 0; if( any(k == 0:n) ){ out = choose(n,k); } return(out) } #---------------------------------------------- # F applies Pascal's rule n times to the vectors x0, v0 F <- function(n,x0,v0,x){ out = array(dim = c(1,length(x))); for(j in 1:length(x)){ out[j] = 0; for(k in 1:length(x0)){ out[j] = out[j] + v0[k]*C(n,x0[k],x[j]) } } return(out); } #---------------------------------------------- # Returns an array of F applied i = 0, 1, 2,..., n times ArrayF<-function(n,x0,v0,x){ out = array(dim = c(n+1,length(x))); for(i in 0:n){out[i+1,] = F(i,x0,v0,x);} return(out) } #---------------------------------------------- PlotPascal <- function(n,x0,v0,x){ pathArray = ArrayF(n,x0,v0,x); plot(NULL, xlim=c(min(x),max(x)), ylim=c(0,n), ylab="n", xlab="x"); grid(lwd = 2); for(j in 1: length(x)){ for(i in 0: n){ if(pathArray[i+1,j] !=0){ text(x[j],i,paste(pathArray[i+1,j])); }; }; }; } #---------------------------------------------- # End Function Definitions #---------------------------------------------- x0 = c(0); # Example 1. Pascal's Triangle. v0 = c(1); n = 12; # First 12 rows x = -n:n; PlotPascal(n,x0,v0,x); #---------------------------------------------- x0 = c(-1, 1); # Example 2. Using Virtual Pascal's Triangle v0 = c(-1, 1); # to count lattice paths. n = 12; x = (-n-1):(n+1); PlotPascal(n,x0,v0,x); #----------------------------------------------------- a = 8; b = 5; # Example 3. Ballot Problem. paths = F(a+b-1,c(1),c(1),c(a-b))[1,1]; paths; goodpaths = F(a+b-1,c(-1,1),c(-1,1),c(a-b))[1,1]; goodpaths; paste('Probability A always ahead of B = ', (a/(a+b))*(goodpaths/paths)); paste('Check answer. (a-b)/(a+b) = ', (a-b)/(a+b)); #-----------------------------------------------------