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!
Paths in a full graph
1
$\begingroup$
combinatorics
graph-theory
-
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
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$
-
1Clever. Thanks a lot! – 2012-03-23