0
$\begingroup$

Given length of word $l$ and number of characters available $n$. Find the total number of words that can be formed using available characters of length $l$.

Example:
$l=2$
available char $(0,1)$
$n=2$
words $\rightarrow$ $00$, $01$, $10$, $11$
$l=3$
$n=2$
words $\rightarrow$ $000$, $001$, $010$, $011$, $100$, $101$, $110$, $111$

$\endgroup$
2
  • $\begingroup$ i tried but not get any successful formula :( or pattern $\endgroup$ – user85857 Aug 9 '13 at 8:23
  • $\begingroup$ Do you know about the product rule? $\endgroup$ – Tomas Aug 9 '13 at 8:25
2
$\begingroup$

Hint: you can think about this problem in two ways. Both lead to the same answer.

  1. You have $l$ places in a word and you can independently choose one of the $n$ letters for each place.
  2. Suppose you know how many words of length $l-1$. Each word of length $l$ can be constructed as a word of length $l-1$ concatenated with some letter at the end. So, for each word you have $n$ options of choosing the last letter. You get a recurrent formula $W_l = n \cdot W_{l-1}$.

I think these two patterns will help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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