I played around a bit with the word-counting approach, which seems to have given me some promising results.

Each walk of length

in

dimensions that starts at the origin corresponds to a word of length

from the alphabet

.

For instance, if you're interested in walks from

to

in

steps, consider the word

, where

.

The

and

characters correspond to steps in the positive and negative directions in dimension

, respectively. The

:es are characters (directions) yet to be selected from

. If we walk in the order prescribed from left to right in

, by the time we reach the

:es, we will have reached

in our walk.

If we consider the first two

:es from the left, we can replace them with any pair of

and

(for fixed

) and still be in

after these two additional steps. Repeating this for each consecutive pair of

:es, assuming that we have an even number of

:es, the resulting string describes a walk from the origin to

in

steps.

In this particular example, it is realized that we can represent a selection of three pairs of

and

as the sum 3+0+0 (three pairs from the first dimension, none from the remaining two). Similarly, 0+2+1 represents a selection of no pairs of

and

, two pairs of

and

, and one pair of

and

(thus 0+2+1 gives rise to the string

Each such sum with three summands (where the summands are nonnegative integers that sum to half the number of

:es) gives us a walk to

represented by distinct letters.

By counting the number of permutations of all words that arise from all such sums (3+0+0, 0+3+0, 0+0+3, 2+0+1, 2+1+0, 0+2+1, 1+2+0, 0+1+2, 1+0+2, 1+1+1), we get the total number of walks we seek (since no other walks of this type exist).

For this example, we get that the number of walks that we seek, N, is

(Number of walks arising from 3+0+0) + (Number of walks arising from 0+3+0) + ... + (Number of walks arising from 1+1+1) =

Dividing N by the total number of walks in 20 steps (

) yields the probability that we end up in

after 20 steps.

This example is easily extended to the general case. For instance, using the notation

we get that the probability that we end up in

after

steps is given by

where the sum is taken over all nonnegative integers

such that

"Stephen Wolfram is the creator of Mathematica and is widely regarded as the most important innovator in scientific and technical computing today." - Stephen Wolfram