2
$\begingroup$

Given this question, what about the special case when the start point and end point are the same? I ask it here instead because I am looking for the mathematical solution to counting these different paths.

Another change in my case is that we must move at every step. How many such different paths can be found and what would be the most efficient approach? I guess this would be a random walk of some sort?

My thinking so far is, since we must always return to our starting point, thinking about $n/2$ might be easier. Then at every step, except at step $n/2$, we have 6 choices to move. At $n/2$ we have a different amount of choices depending on if $n$ is even or odd. We also have a different amount of choices depending on where we are (what previous choices we made). For example if $n$ is even and we went straight out, we only have one choice at $n/2$, going back. But if $n$ is even and we didn't go straight out, we have more choices.

It is all the cases at this turning point that I have trouble getting straight.

Am I on the right track?

To be clear, I just want to count the paths. So I guess we are looking for some conditioned permutation?

$\endgroup$

1 Answer 1

0
$\begingroup$

Each step is in one of the six directions 0º, 60º, 120º, 180º, 240º, 300º. Let $n_i$ be the number of steps in the direction $60i$ degrees. You can show that a path will return to its start if and only if $$ n_0-n_3 =n_2-n_5=n_4-n_1\tag1 $$ Of the $6^n$ possible walks, you must count the number of walks which satisfy the above condition. The following sum which computes this: $$ \sum_{k=-\lfloor{n/3}\rfloor}^{\lfloor{n/3}\rfloor}\sum_{a+b+c=n}\binom{n}{a,b,c}\binom{a}{\frac{k+a}{2}}\binom{b}{\frac{k+b}{2}}\binom{c}{\frac{k+c}{2}} $$ The above is correct as long as you use the convention that $\binom{m}{i}$ is zero whenever $i$ is not a nonnegative integer. Essentially, $a$ corresponds to $n_0+n_3$, $b$ to $n_2+n_5$ and $c$ to $n_0+n_3$, while $k$ is the common value of $(1)$.

Edit: Another way to express the above summation is $$ \sum_{k=-\lfloor{n/3}\rfloor}^{\lfloor{n/3}\rfloor}\sum_{a=0}^n\sum_{b=0}^{n-a}\binom{n}{a,b,c}\binom{a}{\frac{k+a}{2}}\binom{b}{\frac{k+b}{2}}\binom{n-a-b}{\frac{k+n-a-b}{2}} $$

$\endgroup$
6
  • $\begingroup$ Good answer! I just have trouble interpreting the sum notations. Are non-integer $k$ fine? And the second sum, from and to what does it sum? Sorry, I have not used anything but the standard sum notation $\sum_{i=0}^{n}x_i$. An explanation of these sums and the answer would be complete to me. Thanks! $\endgroup$
    – Skillzore
    Apr 19, 2018 at 19:38
  • $\begingroup$ Good question, my notation was very unclear. k has to be an integer, so it the bounds should be n/3 rounded down. For the second sum, what it means is that you enumerate all choices of three nonnegative integers a,b,c which satisfy a+b+c=0, and add up the inside function applied to all of them. I can edit in a better explanation later $\endgroup$ Apr 19, 2018 at 19:44
  • $\begingroup$ Alright, thanks! Now I get it. Yes, please edit and I will accept your answer. $\endgroup$
    – Skillzore
    Apr 19, 2018 at 19:53
  • $\begingroup$ Oh, sorry. Spoke too quickly, your comment says $a+b+c=0$, but the sum in your answer says $a+b+c=n$, which one is it? $\endgroup$
    – Skillzore
    Apr 19, 2018 at 19:57
  • $\begingroup$ Whoops, I meant a+b+c=n $\endgroup$ Apr 19, 2018 at 19:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .