Thread: 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?

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:

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

Originally Posted by Grandad

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

Length 2:

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

Length 1:

So I reckon that's 6+1+6+3=60" alt="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?

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