1. ## counting

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?

2. Hello sss
Originally Posted by sss
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?
It 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?

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$...6

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+6+1+6+3=60$. ...63

That's a nice round number so I don't know if anyone knows of a quicker method?

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.