Question

Let A be an alphabet with k characters. How many strings of length n can be produced using A that have the property that there are never two consecutive letters that are equal? For example, let A = { a, b, c }. The only acceptable strings of length 3 would be aba, abc, aca, acb, bab, bac, bca, bcb, cab, cac, cba, and cbc.

Answer 1

Step-by-step explanation: ok, there are two numbers provided, k and n.

you can think on n like a number of sockets.

_ _ _ _ .............. _

1 2 3 4 ............... n

in each socket goes a letter of A, only we cant have two consecutive letters.

So en the first socket we have K possibilities to chose, then in the second, we discard the one we put on the first socket. so we have K-1 possibilities. in the third one we discard the one we put in the second, so again we have K-1, and this goes on and on for the other sockets.

The total strings you can make with this will be the product of all the sockets, wich is:
`K*(K-1)^(n-1)`.