QB5
15 marks
Permutations & Arrangements
Permutation Properties and Enumeration (Abstract)
View
An alien script has $n$ letters $b_{1}, \ldots, b_{n}$. For some $k < n/2$ assume that all words formed by any of the $k$ letters (written left to right) are meaningful. These words are called $k$-words. Such a $k$-word is considered sacred if:
i) no letter appears twice and,
ii) if a letter $b_{i}$ appears in the word then the letters $b_{i-1}$ and $b_{i+1}$ do not appear. (Here $b_{n+1} = b_{1}$ and $b_{0} = b_{n}$.)
For example, if $n = 7$ and $k = 3$ then $b_{1}b_{3}b_{6}, b_{3}b_{1}b_{6}, b_{2}b_{4}b_{6}$ are sacred 3-words. On the other hand $b_{1}b_{7}b_{4}, b_{2}b_{2}b_{6}$ are not sacred. What is the total number of sacred $k$-words? Use your formula to find the answer for $n = 10$ and $k = 4$.