1
$\begingroup$

enter image description here

The distance between point $A$ and $B$ is $7$ units. The initial position is $A$. How many ways to reach point $B$ in $21$ steps. Each step can be either one unit forward or one unit backward.

I tried in the following way :

$a = $ No of forward steps used.

$b = $ No of backward steps used.

We need $a+b = 21 \;\;\;\; $ and $\;\;\;a - b = 7$.

Solving these $\;\; b = 7$. Now, I thought, how many ways these $b$ backward steps can be used? I could not use generating function to select $b$ steps out of $7$ available locations because permutation is also possible. I also tried $2$ state dynamic programming and wrote a program.

But I want a more formal way of counting.

$\endgroup$
  • 1
    $\begingroup$ Also, are we allowed to go past A or B, or must we stay between them? $\endgroup$ – Franklin Pezzuti Dyer May 19 '17 at 20:42
  • $\begingroup$ ok, I am adding my initial try and we must stay within A and B. $\endgroup$ – Debashish May 19 '17 at 20:43
  • 1
    $\begingroup$ One way to proceed is via the adjacency matrix $M$ of the graph; the number of paths will be some particular element of $M^{21}$. (But this is almost certainly overkill.) Edit: It may be overkill, but it's easy enough to implement in WolframAlpha (link). From this, one obtains 28101 in the corner. $\endgroup$ – Semiclassical May 19 '17 at 20:53
2
$\begingroup$

I just made a spreadsheet with columns for each point and rows for the number of steps. The entry in each cell is the number of ways to be at that column in the number of steps that is the row. All the internal columns have the sum of the two neighboring columns in the row above because to arrive at the third dot you can come from the second or fourth. Points A and B just have the same number as one point inboard on the previous round. I find $28101$.

$\endgroup$
2
$\begingroup$

$28101$ using a dynamic programming approach (Python script):

@memoize
def F(steps_remaining, B, cur_pos=0):
    if (steps_remaining == 0):
        return (cur_pos == B)
    ways = 0
    if cur_pos > 0:
        ways += F(steps_remaining - 1, B, cur_pos - 1)
    if cur_pos < B:
        ways += F(steps_remaining - 1, B, cur_pos + 1)
    return ways

print(F(21, 7)) #28101
$\endgroup$
  • $\begingroup$ :) I did the same thing to check the answer and got $28101$. Thanks. Is there no way of counting it mathematically? $\endgroup$ – Debashish May 19 '17 at 21:02
  • 1
    $\begingroup$ @Debashish Each system (holding one variable or the other constant, as long as their parities match) yields a linear recurrence. I don't have time at the moment to look into it more deeply, but it's possible that there's a nice pattern between the coefficients that gives rise to something a little more compact. For instance, when $B=7$ we have recurrence $F(n) = 7F(n-1) - 15F(n-2) + 10F(n-3) - F(n-4)$ with $F(0)=0, F(1)=1, F(2)=7, F(3)=34$ where $n = (s - 7)/2 + 1$ and $s \geq 7$ is an odd number of steps. The characteristic polynomial has complex roots so a closed-form could be messy. $\endgroup$ – Marcus Andrews May 19 '17 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.