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?

Printable View

- October 2nd 2009, 12:10 AMssscounting
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? - October 2nd 2009, 02:21 AMGrandad
Hello sssIt doesn't take long to work out the number for each different length and add them up:

As you say, length 5:

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 .
- With 2 o's both the other letters must be used, so that's .

Length 3:

- 3 o's:
- 2 o's + 1 other:
- 1 o + 2 others:

Length 2:

- 2 o's:
- 1 or 0 o's:

Length 1:

So I reckon that's .

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

Grandad - October 2nd 2009, 03:22 PMawkward
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 be the number of words of length r and define . Then it's easy (if you know how) to see that

which on expansion yields

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)