Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
@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

1 Answer 1

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

Your Answer

 
discard

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.