1

there are $k$ different things and the task is to arrange them at $n$ places such that no adjacent things are of the same type and first and last things are of the same type. An example for: $k=3,n=4$

1 , 2 ,3 ,1

2 ,3 ,1 ,2

3 ,1 ,2 ,3

so on as one can notice, the first and last are of the same type and there can be multiple occurrences of a number, with adjacent numbers being different. What is the total number such possible arrangements ?

Any help is appreciated.

Avaneesh Kumar
  • 39

1 Answers1

2

Hint: Let's recast the problem as making an $n-1$ place word from an alphabet of $k$ characters such that no adjacent characters are the same and the last one is not the same as the first (why is this equivalent?).

Then define $A(p-1)$ as the number of these strings of length $p$ and $B(p-1)$ as the number of strings of length $p-1$ with no neighboring characters matching, but the first and last are the same. Can you write two coupled recurrences?

You want $A(n-1)$

Added: Start with the number of length 2 strings. For $A(2)$ we can start with $k$ for the first letter. Then we have $k-1$ choices for the second. This gives $A(2)=k(k-1)$ corresponding to strings of the pattern aba. $B(2)=0$ because the two characters would have to match. How many ways are there to extend an $A$ string by 1 character? To extend a B string by one character to make an A string? You should wind up with two equations $A(n)=()A(n-1)+()B(n-1)$ and $B(n)=()A(n-1)$ where there is no second term in $B(n)$ because you can't extend a $B$ string into a $B$ string (why?)

Ross Millikan
  • 374,822
  • u are absolutly correct bt m nt able to genrate recurance equqtion can u please write it here??? or sir please provide a good link frm where i can read this all... please :) – Avaneesh Kumar Apr 07 '13 at 04:17
  • @AvaneeshKumar: If you can't write them, how can you know I am correct? If you have want to make a $k$ length string with different front and back, how many ways are there to extend an $A$ string of length $k-1$? How many ways to extend a $B$ string of length $k-1$? – Ross Millikan Apr 07 '13 at 04:21
  • total with different neighboring - total of font and back same :)sir i knew tht it is a recurance problem tht y i supported u.... – Avaneesh Kumar Apr 07 '13 at 04:25
  • @AvaneeshKumar: That is a different approach than I am suggesting. It might well work. Try it-if it gets you all the way, you are done. If not, show where you got and ask for help from there. You might also try what I suggested and see if it gets you to the solution. If not, again show what you have found and ask for further assistance. – Ross Millikan Apr 07 '13 at 04:43
  • sure sir.... m trying and soon will connect with u... :) – Avaneesh Kumar Apr 07 '13 at 04:51
  • sure sir.... m trying and soon will connect with u... :)@ Ross m struggling here- like i have k+1 different characters to be filled at n+2 places , now i fixed one at startinting defenatly ending char will be the same, so 2 and n can not be that particular char.. so lets such solution be S(n)..... at first case we assume that there is the same char at n-1 so we can fill nth position with k chars so S(n)=k*S(n-2)+....the next m strugling when when there z different char at n-1 as well as at n.... please help.. ") – Avaneesh Kumar Apr 07 '13 at 05:05