Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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. – mloskot Jan 8 '13 at 19:42
@mloskot Sorry! I had written this a while ago, and I got the terminology wrong. Will fix it ASAP. – Chris Jan 9 '13 at 7:33
up vote 3 down vote accepted

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$

share|cite|improve this answer
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$. – Chris Mar 23 '12 at 17:53
@Abody97: corrected. – Ross Millikan Mar 23 '12 at 18:12
Clever. Thanks a lot! – Chris Mar 23 '12 at 18:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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