Enumeration problem

wik_chick88 · #1 $Old$ 09-04-2008, 09:00 AM

hey im having trouble getting started on this question:

how many strings of at least one and at most three characters from the alphabet have their characters in alphabetical order? repeated characters are allowed and strings such as aab are in alphabetical order.

i figured with only one character strings, the number of alphabetically-ordered strings is 26, because each string will only have 1 letter, thus n alphabetical order.

im getting stuck with 2 and 3 characters in the string. i considered starting with each letter in the string, but that was going to take too long. i know it has something to do with commutations/pemutations...
with 2 character strings, i guess u could do sum of (26-r) from r=0 to 25...cause for the first letter r=0 (ie. a) there are 26 ways, r=1 (b), there are 25 ways etc...but this doesnt have anything to do with commutations/permutations??

please help!!!

Plato · #2 $Old$ 09-04-2008, 09:25 AM

$\sum\limits_{k = 1}^3 {{26+k-1} \choose k}$
Can you explain why this works?

wik_chick88 · #3 $Old$ 09-05-2008, 07:43 AM

well that formula looks like the one for unordered repetitions. but where does the sum of come from? and why k from 1 to 3? is that because u have at least 1 and at most 3 strings of characters? how did u separate the alphabetically arranged from the non-alphabetically arranged? im so confused...

Soroban · #4 $Old$ 09-05-2008, 09:08 AM

Hello, wik_chick88!

I had to make lists ... and look for patterns.

Quote:

How many strings of at least one and at most three characters
from the alphabet have their characters in alphabetical order?
Repeated characters are allowed and strings such as $aab$ are in alphabetical order.

One-letter strings

You are right . . . there are ${\color{blue}26}$ possible one-letter strings.

Two-letter strings

$\begin{array}{cc}& \text{choices for} \\ \text{1st letter} & \text{2nd letter} \\ \hline a\,\_ & 26 \\ b\,\_ & 25 \\ c\,\_ & 24 \\ \vdots & \vdots \\ y\,\_ & 2 \\ z\,\_ & 1 \end{array}$

Two-letter strings: . $1 + 2 + 3 + \cdots + 26 \;=\;T_{26} \;=\;\frac{26\cdot27}{2} \;=\;{\color{blue}351}$

Three-letter strings

$\begin{array}{cc}aa\_ & 26 \\ ab\_ & 25 \\ ac\_ & 24 \\ \vdots & \vdots \\ ay\_ & 2 \\ az\_ & 1 \end{array}$ . . $\begin{array}{cc}bb\_ & 25 \\ bc\_ & 24 \\ bd\_ & 23 \\ \vdots& \vdots \\ by\_ & 2 \\ bz\_ & 1 \end{array}$ . . $\begin{array}{cc}cc\_ & 24 \\ cd\_ & 23 \\ ce\_ & 22 \\ \vdots & \vdots \\ cy\_ & 2 \\ cz\_ & 1 \end{array}$ . . $\cdots$ . . $\begin{array}{cc}ww\_ & 4 \\wx\_ & 3 \\ wy\_ & 2 \\ wz\_ & 1\end{array}$ . . $\begin{array}{cc}xx\_ & 3 \\xy\_ & 2 \\ xz\_ & 1 \end{array}$ . . $\begin{array}{cc}yy\_ & 2 \\ yz\_ & 1 \end{array}$ . . $\begin{array}{cc}zz\_ & 1 \end{array}$

Reading from the right, we have:

$(1) + (1+2) + (1+2 +3) + \cdots + (1+2+3+\cdots+26)$

. . $= \;T_1 + T_2 + T_3 + \cdots + T_{26} \;=\;\frac{26\cdot27\cdot28}{3!} \;=\;{\color{blue}3276}$ 3-letter strings

Answer: . $26 + 351 + 3276 \;=\;\boxed{3653}$

Plato · #5 $Old$ 09-05-2008, 09:56 AM

Quote:

Originally Posted by wik_chick88 $View Post$

well that formula looks like the one for unordered repetitions. but where does the sum of come from?

Exactly, we do use unordered repetitions to solve these problems.
Let me give you another problem to demonstrate the concept.
How many way can we select five letters from the alphabet allowing repetitions: ${{5+26-1} \choose {5}}$ . Correct?
If you are given any collection for five letters, say any five Scrabble pieces, you can always arrange those pieces in alphabetical order. Can you not?
Therefore, we have just counted the number of five letters strings appearing in alphabetical order.
Now the sum is for one, two, or three strings.

wik_chick88 · #6 $Old$ 09-08-2008, 07:11 AM

ok. im pretty sure the question is ordered ie. the first letter has to stay the first letter. so i made the lists, saw the patterns and worked out how many strings would be possible. BUT the next question is how many strings of at least one and at most n characters from the alphabet have the characters in alphabetical order? you used T1, T2,...,T26 in your answer what is the definition of Tn? Thanks for all your help!

Plato · #7 $Old$ 09-08-2008, 10:31 AM

Quote:

Originally Posted by wik_chick88 $View Post$

ok. im pretty sure the question is ordered ie. the first letter has to stay the first letter. so i made the lists, saw the patterns and worked out how many strings would be possible. BUT the next question is how many strings of at least one and at most n characters from the alphabet have the characters in alphabetical order? you used T1, T2,...,T26 in your answer what is the definition of Tn? Thanks for all your help!

Well of course they are ordered!
But the point here is that we count the number of unordered selections each of which we can then in turn order.
The selection <B,A,L,L,O,O,N> can be ordered into ABLLNOO.
That selection is one of ${{7+26-1} \choose {7}}=3365856$ possible selections of seven choices of letters allowing repeats.
But that is also the number of seven letter ‘words’ having their letters is alphabetical order.

Thus the answer to the second part, “n characters from the alphabet have the characters in alphabetical order”, is ${{n+26-1} \choose {n}}$ .
Now you add $k=1,..,n$ .

wik_chick88 · #8 $Old$ 09-09-2008, 06:13 AM

thanks guys for all ur help now i understand what to do and i can explain it in my own words!! THANKS!!!

asw-88 · #9 $Old$ 09-17-2008, 06:52 AM

I stil don't understand what T1 + T2 + T3... is suppose to stand for and thus don't understand how you came to the conclusion that it equals 26x27x28/3!

\

If possible can you please explain this!
Thanks Soroban!