2
$\begingroup$

Using letters from the alphabet $A = \{a, b, c, d, e, f, g\}$, how many words of length $5$ are possible when repetition is allowed but the letters must occur in alphabetical order?

Not sure how to tackle this one in the case that repetition is allowed. Any hints? Thanks! :)

$\endgroup$
  • $\begingroup$ As a pure curiosity: If you take the first eight letters of the alphabet without repetition, $\text{a, b, c, d, e, f, g, h}$, they cannot be rearranged to spell a single word. However, try to solve the following: Trade one of these eight letters for two new letters, $\text{o, u}$, and the result can be rearranged into a single nine letter word. (I find this interesting because there are two different solutions ... and no extra solutions arise by allowing the trade to be for any two letters...) $\endgroup$ – Benjamin Dickman Jul 25 '16 at 15:13
7
$\begingroup$

The question can be rephrased as:

How many different sums $n_a+n_b+n_c+n_d+n_e+n_f+n_g=5$ are there for nonnegative integers $n_a,n_b,n_c,n_d,n_e,n_f,n_g$?

E.g. possibility $2+0+1+1+1+0+0=5$ corresponds with word "aacde".

This can be solved with stars and bars.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yes ! but could you provide a result showing the application here ? $\endgroup$ – user354674 Jul 25 '16 at 10:32
  • $\begingroup$ What do you mean by "a result" in this context. I can provide the anwer that makes use of stars and bars if that's what you mean, but the OP asked for hints. If there is any familiarity with stars and bars then everything must be clear. Actually the other answer that you commented gives an answer. $\endgroup$ – drhab Jul 25 '16 at 10:38
  • $\begingroup$ I wanted to verify that you removed the last position for the bar ( or the first ). $\endgroup$ – user354674 Jul 25 '16 at 10:47
  • $\begingroup$ @igael It is matter of starting with $11$ open spots: $\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ$. Then $6$ of these spots are selected to be a bar and $5$ to be a star. The example in my answer: $\star\star\mid\mid\star\mid\star\mid\star\mid\mid$. There is no such thing as removing first or last bar. $\endgroup$ – drhab Jul 25 '16 at 10:57
  • 1
    $\begingroup$ OP's question is "How many possible words can be made from...". I don't see a number that answers that here. $\endgroup$ – Keeta - reinstate Monica Jul 25 '16 at 13:31
3
$\begingroup$

You can just go through the various partitions of $5$:

$$\{5\},\{4,1\},\{3,2\},\{3,1,1\},\{2,2,1\},\{2,1,1,1\},\{1,1,1,1,1\}$$

and work out the choices for each; respectively:

$$7, 7\cdot 6, 7\cdot 6, 7 {6\choose 2}, 7{6\choose 2}, 7 {6\choose 3},{7\choose 5}$$

and add those possibilities together.


Alternatively you can think of placing 6 "next letter" flags $\fbox >$ among and around 5 'report letter' flags $\fbox x$, eg:

$$\fbox >,\fbox x, \fbox >, \fbox >, \fbox x, \fbox x, \fbox >, \fbox x, \fbox >, \fbox >,\fbox x$$

here giving $bddeg$. Then it is just a matter of choosing which of the $11$ flags are which.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Count the number of ways $5$ balls can be placed in $7$ bins marked $a-g$, using stars and bars

A result of $\;\;\fbox{2}\fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{1}\fbox{1}\;$, e.g. means obtaining $aadfg$.

Thus $\binom{5+7-1}{7-1}$ ways

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ very nice application ! but depending of you convention of relation, the bar must be before or after the letter it selects but not both ( I mean you have to ignore one element ) $\endgroup$ – user354674 Jul 25 '16 at 10:26
  • $\begingroup$ @igael The number of stars at the left of the utmost left bar corresponds with the number of letters "a" in the word (in the result mentioned in this answer $2$).The number of stars at the right of the utmost right bar corresponds with the number of letters "g" in the word (in the result mentioned in this answer $1$). They could also (both) take value $0$. $\endgroup$ – drhab Jul 25 '16 at 11:10
  • $\begingroup$ @drhab in this case , you must use only a to f , 6 stars with 5 bars. $\endgroup$ – user354674 Jul 25 '16 at 11:15
  • $\begingroup$ No $5$ stars (corresponding with the length of the word) and $6$ bars (corresponding with the fact that $6$ bars take care of a split up in $7$ (the number of letters in $\{a,b,c,d,e,f,g\}$) segments). $\endgroup$ – drhab Jul 25 '16 at 11:25
  • $\begingroup$ 2 ways to apply, stars in bins or stars indexed by the number of bars before. The results are the same. Since I was exclusively thinking to my choice, I was mis interpreting the application in the case of the other choice $\endgroup$ – user354674 Jul 25 '16 at 12:07
0
$\begingroup$

Hint: There's only one way to write a given set of 5 letters in alphabetical order. This allows us to deduce that there is a bijection between the number of words you can make with the conditions you want and the number of size 5 subsets of $\{a,b,c,d,e,f,g\}$ (with repitition allowed).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hope this helps, feel free to ask for clarification! $\endgroup$ – Zestylemonzi Jul 25 '16 at 8:08
0
$\begingroup$

Although all the other ideas presented here are great (i.e. the stars and bars method), I want to give a different approach to this question. To start, let us consider the same problem, but with two letters.

In this case, if the first letter is a, the second letter can be any of the 7 letters.

If the first letter is b, the second letter can be the 6 letters after a.

If the first letter is c, the second letter can be the 5 letters after b.

If we keep doing this, we will eventually reach the case where the first letter is g, and the second letter can only be g. As you can see, for an alphabet with $n$ letters, the number of two letter words is just the $nth$ Triangular Number, which is given by the formula $n(n+1)/2$. Now let us consider three letter words.

If the first letter is a, then the second letter can be any letter from a to g, which we can consider to be a two letter word with an alphabet $A=\{a,b,c,d,e,f,g\}$, which is the two letter word case. We therefore have $\frac{7*(7+1)}2=28$ combinations for the case starting with a.

If the first letter is b, then the alphabet for the rest of the word is $\{b,c,d,e,f,g\}$ and it has $\frac{6*(6+1)}2=21$ combinations.

If the first letter is c, then the alphabet for the rest of the word is $\{c,d,e,f,g\}$ and it has $\frac{5*(5+1)}2=15$ combinations.

If we add up all these combinations, we will get the $7th$ Tetrahedral Number, which is the sum of the first $7$ Triangular Numbers. The formula for the $nth$ Tetrahedral Number is $\frac{n*(n+1)*(n+2)}6$.

There are several important things to realize here:

  1. Each word may be thought of as adding a letter to the beginning of the previous word.
  2. The first letter of a word determines the alphabet for the rest of the word.
  3. The number of possible words of length $n$ is the sum of the number of possible words with $n-1$ letters and an alphabet of size 1 to $n$.
  4. The sum of the first $n$ triangular numbers is the $nth$ tetrahedral number, the sum of the first $n$ tetrahedral numbers is the $nth$ $4$-simplex number, and generally the sum of the first $n$ $a$-simplex number is the $nth$ $a+1$-simplex number.

https://en.wikipedia.org/wiki/Simplex

https://en.wikipedia.org/wiki/Figurate_number

Finally, from this we can see that the answer to the general problem with an alphabet with size $a$ and a word length of $n$ is the $nth$ $a$-simplex number, which has a formula $\binom{n+a-1}{a}$, which you will notice is the same answer as everyone else has given.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.