how many different strings can be made from the letters on orono using some or all of its letters
I know how to find the strings with all letters : 5!/3! but how do I find out the stings of different lengths?
Hello sssIt doesn't take long to work out the number for each different length and add them up:
As you say, length 5: $\displaystyle \frac{5!}{3!} = 20$
Length 4 can contain 3 or 2 o's.
- With 3 o's + 1 other, there is a choice 2 for the other letter, so the number is $\displaystyle 2 \times\frac{4!}{3!}=8$.
- With 2 o's both the other letters must be used, so that's $\displaystyle \frac{4!}{2!}=12$.
Length 3:
- 3 o's: $\displaystyle 1$
- 2 o's + 1 other: $\displaystyle 2\times \frac{3!}{2!}=6$
- 1 o + 2 others: $\displaystyle \frac{3!}{1!}=3$
Length 2:
- 2 o's: $\displaystyle 1$
- 1 or 0 o's: $\displaystyle {^3P_2} = 6$
Length 1: $\displaystyle 3$
So I reckon that's $\displaystyle 20+8+12+1+6+3+1+6+3=60$.
That's a nice round number so I don't know if anyone knows of a quicker method?
Grandad
A little slip in arithmetic above...
I don't have a real shortcut, but I can't resist pointing out that the "easy way" if you are familiar with generating functions is to find the exponential generating function.
I.e., let $\displaystyle a_r$ be the number of words of length r and define $\displaystyle g(x) = \sum_{r=0}^{\infty} a_r x^r / r!$. Then it's easy (if you know how) to see that
$\displaystyle g(x) = (1 + x)^2 (1 + x + x^2 / 2! + x^3 / 3!)$
which on expansion yields
$\displaystyle g(x) = 1 + 3 x + 7 x^2 / 2! + 13 x^3/3! + 20 x^4/4! + 20 x^5/5!$
From this you can read off the number of words of length 1-5: 3, 7, 13, 20, 20.
This isn't much help for someone who doesn't know anything about generating functions, I guess, except it may give an incentive to learn.
Personally, I think generating functions are neat-- I guess you can tell that.