# counting

• Oct 1st 2009, 11:10 PM
sss
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?
• Oct 2nd 2009, 01:21 AM
Hello sss
Quote:

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?

• Oct 2nd 2009, 02:22 PM
awkward
Quote:

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. (Happy)