1
$\begingroup$

Given a complete graph with $4$ nodes, and one node is labeled $X$, find how many paths of length $N$ (might visit a node more than once) begin, end or both begin and end with $X$. This is not a homework question!

  • 0
    First, what is a full graph? I'd suggest to use precisely defined terms instead of inventing new ones. Those who provided answers, please correct questions so they are properly formulated end expressed using mathematical terms.2013-01-08
  • 1
    @mloskot Sorry! I had written this a while ago, and I got the terminology wrong. Will fix it ASAP.2013-01-09

1 Answers 1

3

There are $4\cdot 3^{N-1}$ paths of length $N$ as you can start anywhere ($4$ choices) and then each move has $3$ choices. There are also $3^{N-1}$ that start at $X$ and $3^{N-1}$ that end at $X$. To evaluate how many there are that start and end at $X$, let $A(n)$ be the number of $n$ length strings that start and end with $X$ and $B(n)$ be the number of $n$ length strings that start with $X$ and end with something else. Then $A(2)=0, B(2)=3, A(n)=B(n-1), B(n)=2B(n-1)+3A(n-1)$. This gives $A(n) = \frac {3^{n-1} \pm 3}4$ where the $\pm$ sign is $+$ if $n$ is odd. So the total number is $2\cdot3^{N-1}-\frac {3^{n-1} \pm 3}4$

  • 1
    Thanks for your answer. "There are $3^{N-2}$ that start and end at $X$" I don't think that's true, because the previous-to-last element in the sequence might get chosen as X, thus eliminating the possibility of it ending with $X$.2012-03-23
  • 1
    @Abody97: corrected.2012-03-23
  • 1
    Clever. Thanks a lot!2012-03-23