2

There is a game in which there is a point P and k other points on a plane. To win, we must draw directed lines starting from point P and ending at point P with exactly n number of lines to be drawn. P can also come in between.

Example: $n=2$, $k=4$ suppose points are $k_1$, $k_2$, $k_3$, $k_4$. possible combinations of winning: $$ P\to k_1\to P $$ $$ P\to k_2\to P $$ $$ P\to k_3\to P $$ $$ P\to k_4\to P $$ Hence answer is $4$.

Example: $n=3$, $k=2$ suppose points are $k_1$, $k_2$. possible combinations of winning: $$ P\to k_1\to k_2\to P $$ $$ P\to k_2\to k_1\to P $$ Hence answer is $2$.

Example: $n=4$, $k=2$. suppose points are $k_1$ and $k_2$. $$ P\to k_1\to P\to k_2\to P $$ $$ P\to k_1\to k_2\to k_1\to P $$ $$ P\to k_1\to P\to k_1\to P $$ $$ P\to k_2\to P\to k_2\to P $$ $$ P\to k_2\to P\to k_1\to P $$ $$ P\to k_2\to k_1\to k_2\to P $$ Hence answer is $6$.

How do I generalize the result for arbitrary $n$ and $k$?

Stahl
  • 23,212
Amit Tiwari
  • 97

1 Answers1

1

Strip off the beginning and terminal $p$. So we want to count the sequences of length $n-2$ that do not begin or end with $p$, and such that successive terms of the sequence are different.

For fixed $k$, let $g_k(n)$ be the number of such sequences (good sequences) of length $n-2$.

We find a recurrence for $g_k$. Any good sequence $s$ of length $n-2$ can be extended to a good sequence of length $n-1$ by adding any one of the $k-1$ objects that $s$ does not end with.

The only other way to make a good sequence of length $n-1$ is to take a good sequence of length $n-3$, then append a $p$, and then any of the $k$ objects. Thus $$g_k(n+1)=(k-1)g_k(n)+kg_k(n-1).$$ The above recurrence is linear homogeneous with constant coefficients. So it can be solved by the method of characteristic equations. In this case the equation is $x^2-(k-1)x-k$. The solutions of the recurrence are therefore of the shape $A_kk^n+B_k(-1)^n$, where we choose $A_k$ and $B_k$ to satisfy the initial conditions.

These initial conditions can be taken to be $g_k(2)=k$, and $g_k(3)=k(k-1)$. Now we can compute $A_k$ and $B_k$, and get a closed-form formula for $g_k(n)$. It turns out that $A_k=\frac{1}{1+k}$ and $B_k=\frac{k}{1+k}$. Thus $$g_k(n)=\frac{k^n}{1+k}+(-1)^n\frac{k}{1+k}.$$

Remark: The characteristic equation is so simple that we are undoubtedly missing something obvious. But it is sometimes hard to look for a nicer solution once one has found a solution.

André Nicolas
  • 507,029
  • thanks for the solution. it is really elegant. I had never thought that this could be solved with in this manner. I have never done this kind of questions. – Amit Tiwari Apr 06 '13 at 09:13
  • could you suggest me some book that deals with this kind of basics for computer science student? – Amit Tiwari Apr 06 '13 at 09:14
  • @AmitTiwari: I am unfortunately not keeping up with the good online stuff available, nor really with books, particularly the more CompSci oriented ones. This might be a good question for you to ask on MSE. (It may have been asked before.) It would be good to make the question as explicit as possible. – André Nicolas Apr 06 '13 at 19:51