In continuation to King on chessboard question

Short summary of first part - we have chessboard and king on a1. King can ONLY move one space up, or one space right. There is exactly $\binom{7+7}{7}=3432$ ways king can arrive at h8

Setting is exactly the same, but with quirk that our hypotetical king cannot move onto some square in the middle of the board, lets say - king cannot step on d6.

My idea was to count all possible routes to c5, then to have two choices: twice right or twice up, and then count all routes from c7 and e5 to h8.

Then it occured to me, that king doesnt NECESSARILY has to go through c5 at all. Ie RRRRRRRUUUUUUU is route which is absolutely valid, yet uncounted in my thoughts.

What am I missing here?

  • I suggest you do a recursion and skip that spot. – Jorge Fernández Jan 20 '16 at 15:13
  • Please do not capatalize on certain words. It is not necessary. – Arbuja Jan 20 '16 at 15:15
up vote 2 down vote accepted

You know there are a total of $\binom{14}{7}$ paths so by complementary counting you need to find those who pass through d6 and then subtract them from the total number .

Let's take a path that passes through d6 .Now break the path into two parts :

$1)$ The part from a1 to d6

$2)$ The part from d6 to h8

Now just as in the original problem :

  • To land on d6 you must make three steps up and five steps right so there are $\binom{3+5}{3}$ ways to form the first part of the path.

  • To continue from d6 to h8 you must make four steps up and two steps right so there are $\binom{4+2}{2}$ ways to form the second part of the path .

This means there are : $$\binom{8}{3} \cdot \binom{6}{2}$$ paths that pass through d6 and thus there are :

$$\binom{14}{7}-\binom{8}{3} \cdot \binom{6}{2}$$ paths that don't pass through d6 .

  • but of course! many thanks. my brain.. aint combinatorial – Timo Junolainen Jan 20 '16 at 15:26

Use your previous technique to count the paths that go through d6, then subtract them from your previous result. To go through d6, you first go from a1 to d6, then from d6 to h8

It is possible to count these paths using recursion, it in fact the same recursion as the recursion for binomial coefficients, if we manipulate the recursion accordingly we can solve this problem efficiently and in larger generality, the way to do this is basically to ignore the unwanted squares:

$$\begin{array}{cccccccc} 1 &&8 &&36 &&120 &&204 &&414 &&960 &&2172 &&\\ 1 &&7 &&28 &&84 &&84 &&210 &&546 &&1212 &&\\ 1 &&6 &&21 &&56 &&\color{red}{0} &&126 &&336 &&666 &&\\ 1 &&5 &&15 &&35 &&70 &&126 &&210 &&330 &&\\ 1 &&4 &&10 &&20 &&35 &&56 &&84 &&120 &&\\ 1 &&3 &&6 &&10 &&15 &&21 &&28 &&36 &&\\ 1 &&2 &&3 &&4 &&5 &&6 &&7 &&8 &&\\ 1 &&1 &&1 &&1 &&1 &&1 &&1 &&1 &&\\ \end{array}$$

However , the true value of this is when we want to add more unpassable squares:

$$\begin{array}{cccccccc} 1 &&8 &&26 &&60 &&94 &&154 &&282 &&544 &&\\ 1 &&7 &&18 &&34 &&34 &&60 &&128 &&262 &&\\ 1 &&6 &&11 &&16 &&\color{red}0 &&26 &&68 &&134 &&\\ 1 &&5 &&5 &&5 &&10 &&26 &&42 &&66 &&\\ 1 &&4 &&\color{red}0 &&\color{red}0 &&5 &&16 &&16 &&24 &&\\ 1 &&3 &&6 &&\color{red}0 &&5 &&11 &&\color{red}0 &&8 &&\\ 1 &&2 &&3 &&4 &&5 &&6 &&7 &&8 &&\\ 1 &&1 &&1 &&1 &&1 &&1 &&1 &&1 &&\\ \end{array}$$

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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