Proof of Conjecture for paths in hypercube lattices

Problem:

1. hypercubical lattice in D dimensions
2. start from O = (0,0...)
3. allowed moves are only of the form (0,0,+, 0,0, ...)
4. End point of path is (N1, N2,...ND)

What is the number of paths?

Answer:
The multinomial coefficient
(N1+N2 ... ND)C(N1)(N2)...(ND) = (N1+N2...+ND)! / ( N1! N2! ...ND!)

Proof:
Let the whole number valued coordinate axes be n_i, i = 1...D.
The end point lies on the hyperplane \sum(n_i) = \sum(N_i).
One has to choose \sum(N_i) times to get to that hyperplane, from between D choices each time (the choice of direction to move in).
To get to the point (N_1, N_2..., N_D), exactly  N_i choices have to have been in the i- direction.
Hence the number of paths is the number of ways of choosing the above partition from its sum.

In 3D, this is the number of ways of choosing 3 Easts, 5 Norths and 2 Ups from 10 choices to reach the point 3E, 5N and 2U.

Hence the multinomial coefficient. QED

As a little extra: lets say we were only interested in paths between diagonally opposite points of the D-hypercube, say (0,0,...) and (N,N,...).

Then the number of paths is (D*N)!/(N!)**D, which was my conjecture two days ago!!!


Now, the Analytical answer can be produced with 2 lines more of code: one to read the dimension from the command line, the other to read the coordinates of the end point.

The codeCounting program would need a bit more, a couple of for loops to write out the D-dimensional python code (if needed) and then to call it. 

But the amount of time it is going to take is going to be ...  HELP?

Last point for today: The factorial function can be extended to complex plane except negative integers by the Gamma function.

So now I can legitimately answer the question: How many paths are there to a say integer diagonal point in a fractional dimension?

Answer = Gamma(N*D +1)/(N!)**D.

_ : Who cares about your perspective? What practical value can it possibly have?

Here goes: Play fast and loose with "fractional" = "fractal". Now we actually have something we can visualize: paths on a square Sierpinski gasket e.g.

And the practical use? Conjecture: The structure of the web or networks on the web is fractal. There is fractal behaviour even in Statistical Natural Language Processing, Benoit Mandelbrot did important work on it in the 50's.

Lets say that the LinkedIN network is fractal. Maybe the above could be of some use in counting paths, for a better calculation of the clustering coefficient of an egonet.

From the perspective of SNLP, simple extensions of the above counting processes lead to the distributions of sizes of stochastically generated words, e.g with truncation on choice of ' '. 

Ranjeet