Surface path counting puzzle?

EDIT: This message used to be longer, I removed irrelevant stuff.

Now, there might be another option, or it may end up being the same.

In 2D, you can simulate restriction (4) just by saying: okay, count the number of possible paths unrestricted. Then subtract all the paths from (1,i) to (a1, a2), and then from (i, 1) to (a2, a1).

But then you have to add back the one from (1,1) to (a1, a2); because you removed it twice.**

**edit from the future: Yes you removed it twice, but you also counted it twice to begin with, so you shouldn't add it back.

To do something similar in 3D, we can try this:

Subtract everything from (1, i, j) to (a1, a2, a3), etc. [From (i, 1, j); from (i, j, 1)]

And add back everything from (1,1, i) to (a1, a2, a3), etc. [From (1,i,1); from (i,1,1)]

And subtract back from (1,1,1) to (a1,a2,a3).

**edit from the future: So, this here is basically garbage.

This is going to do it.

I have to think to make a formula, but it's basically just going to be the above process, formalized.

EDIT: Well, although I think the formula up there can be done in a way that looks pretty, all my tired brain can come up with right now is:

(SUMai)! / (PRODai)! )

** this is the one he gave above; too lazy to write out all the formalities. Then subtract:

- SUM SUM (1 ≤ k ≤ n) (1 ≤ i_k ≤ a_k) [ (SUM[a_k-i_k])! / PROD[(a_k-i_k)!] ]

This takes care of the double counting problem on it's own. It's not as bad as it could be, but the SUMSUM(SUM/PROD) is kind of awkward.

At the same time, this is a very complicated question, so it might be the best you can get.

edit again:

Okay, I had a massive logic fail here. It's not terrible, but it does make the formula a little worse.

A path from (1,1) to (a1, a2) represents TWO bad paths:

(0,1)-(1,1)-path, and (1,0)-(1,1)-path.

The formula above only subtracts one of those paths; so we need a new plan. In general, from any point with k 1s, that path represents k paths.

Note that gets us around an even bigger problem here. If -all- of the coordinates are non-one, those have already been counted in some other way, so all of those paths represent 0 paths. But if all are non-one, then k=0, so we can put this in the formula in a very systematic way. So the error term becomes...

Um, no, this isn't going to work.

Because the real reason why (1,1) represents 2 paths is because there are 2 ways to get there, not because of the 1s. (1,2,1) represents 4*2 paths, not 2: first you have to get to (1,2,0), or (0,2,1). [(1,1,1) is already covered by a different path]

It's pretty bad.

Let P have no zeroes, k ones, no maxed coordinates, and H(P) paths from P to finish.

Then kH(P) represents the number of paths passing through P.

So the simplest formula is BIG - SUM(valid P) [kH(P)].

Of course, H and k are dependent on P, so it's not a very useful formula. But if you don't go through the +/-/+/- stuff I gave before, this is the basic idea you want to follow.

edit final:

Here's the final formula; it is the same as the simple one but with "valid P" and H(P) defined. As such, I don't believe there is any simpler formula without creating some new notation.

SUM[ai]! / PROD[ai!] -

SUM SUM (1 ≤ c ≤ n) (0 < i_c < a_c) [ k*SUM[a_c-i_c]! / PROD[(a_c-i_c)!] ]

Where k is the number of ones among the a_c's.

And if leaving the k defined "outside the formula" doesn't sit well with you, here's a hack that takes advantage of the fact that 1 is the only number that satisfies 1/x = 1:

k = SUM (c) [ floor(1-(1/a_c)) ]

If you substitute that in, then you can plug that in a computer and let it go to town. Of course, if you were putting it in a computer, you could probably also make it search for how many 1s there were among the a_c's, and that would be a lot less expensive in processing time than doing division.

This was a fun problem, and one that makes you think about more complex shapes in higher dimensions in a neat way. Thanks for sharing; hope this helped.

Edit: Excluding point 5, the solution is below.

I have to think more about this...

----------------------------------------------

The answer is (a1 + a2 + ... + an)! / [(a1)! (a2)! ... (an)!].

Any given legal path is in 1-1 correspondence with a permutation (with repetition) of

(a1 + a2 + ... + an) objects with the possibilities of moving in one of n directions (corresponding to the n dimensions); the (a1)!, (a2)!, ..., (an)! factors correspond to a possible over-count of the routes).

---------

It helps to see why this works in 2D (a standard counting problem) and possibly in 3D as well to see why this generalization indeed works.

2-D case (in more detail).

We want to count the number of paths from (0, 0) to (a, b).

We have two directions to go right (R) or up (U).

Between the a - R's and b - U's, we have to make a total of (a + b) moves.

Here are a few legitimate paths:

R...R U...U

U...U R...R

U R... R U... U [the last part having (b-1) U's].

Note that a path corresponds to a permutation of the R's and U's.

Since there are repeated R's and U's, this is a permutation with repetition problem

(think: MISSISSIPPI).

So, there are (a+b)! / (a! b!) such permutations, and thus paths.

-------------------

I hope this helps!

wltt is bypass yet i don't be attentive to something what i did is i observed that the notice had a douple letter and then i presumed what are the main standard double letters in the alphabet. i attempted lining the t with l yet that did no longer artwork, so i lined t up with s and that i've got been on condition that w=p l=a t=s.