Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many arrangements can be made by the letters of the word "DEFINITION"

  • a) if the letter 'i' do not occupy the first or last place,
  • b) if the 'i'-s are together?

How to approach this problem?

share|improve this question
    
See here for a few ideas: math.stackexchange.com/q/58849 –  t.b. Dec 31 '11 at 6:45
add comment

3 Answers 3

up vote 4 down vote accepted

a) We are making a $10$-letter word. We are told that all the occurrences of the letter I must be on the "inside." There are therefore $\binom{8}{3}$ ways to choose where the I's will go. For every decision about where the I's go, there are $\binom{7}{2}$ ways to decide where the N's go. For every decision about the I's and N's, there are $5!$ ways to arrange the remaining letters in the $5$ remaining vacant places, for a total of $$\binom{8}{3}\binom{7}{2}5! \quad\text{words.}$$

b) The I's must be together, so let's tie them together into a single "megaletter" like this: $\overline{\text{III}}$. We are forming $8$-letter words from the "letters" D, E, F, $\overline{\text{III}}$, N, N, O, and T.

The location of the two N's can be chosen in $\binom{8}{2}$ ways. For each choice of location for the N's, there are $6!$ ways to arrange the remaining "letters" in the $6$ remaining open slots, giving a total of $$\binom{8}{2}6!\quad\text{words.}$$

Comment: As a general heuristic, one should try to deal with the most restrictive conditions first. In part a), it is important to place the $I$'s first. If we place too many other letters first, for some placements it may no longer be true that there is "room" for the I's on the inside.

Another strategy (which we did not use) is to overcount in a systematic way, and then take care of the overcounting. So in part b), we could put a red sticker on one of the N's, to make the N's temporarily into different letters. Then the resulting $8$ distinct "letters" (including red N, and $\overline{\text{III}}$), can be arranged in $8!$ ways. For every word $\mathcal{W}$, there is exactly one other word that differs from $\mathcal{W}$ only in the placement of the $N's$. When we remove the red stickers, any such word pair collapses into one, giving a total of $8!/2$ words.

share|improve this answer
add comment

DEFINITION has 10 letters. However, there are repetitions. In particular, there are 2 N's and 3 I's. Thus we can't just use binomial coefficients and the 'choose' notation.

Instead, we use "multinomial coefficients."

Let's count the number of ways directly, using only binomial coefficients. Without restrictions on individual letter placement, suppose we just had 10 symbols. To account for the letter I, we want to know how many ways we can choose 3 of the 10 symbols and call them I. This can be done in $10 \choose 3$ ways. From the remaining, to account for the N's, we want to know how many ways we can choose 2 of the 7 remaining symbols and call them N. This can be done in $7 \choose 2$ ways. Then we have $5 \choose 1$ ways to place D, $4 \choose 1$ ways to place E, and so on. Then we have considered the number of ways to scramble the letters from DEFINITION.

Putting this together, we get ${10 \choose 3} { 7 \choose 2}{5 \choose 1}{4 \choose 1}{3\choose 1}{ 2 \choose 1}{1 \choose 1} = \dfrac{10! \cdot 7! \cdot 5! \cdot 4! \cdot 3! \cdot 2! \cdot 1!}{3!7! \cdot2!5! \cdot1!4! \cdot1!3! \cdot 1!2! \cdot 1!1! \cdot 1!0!}$

$= \dfrac{10!}{3!2!}$

And this has the special notation ${ 10 \choose 3,2,1,1,1,1,1}$

For part a, rework this idea. For part b, consider the single 'letter' "iii" instead of three individual letters.

share|improve this answer
add comment

At the basic level, you need to apply the so-called

Multiplication Principle:

Suppose two experiments are to be performed in succession. Suppose that the first experiment has exactly $n_1$ possible outcomes. Suppose that the second experiment always has exactly $n_2$ outcomes (regardless of what happened in experiment~1). Then the total number of outcomes from performing both experiments is $n_1\cdot n_2$.

Or rather, the generalization of the above to the case where $m$ experiments are performed in succession:

Generalized Multiplication Principle: Suppose that $m$ experiments are to be performed in succession. If, for each admissable $i$, the $i^{\rm th}$ experiment has $n_i$ outcomes regardless of what occurred in the experiments before, then the total number of outcomes from performing all the experiments is $n_1\cdot n_2\cdot n_3\cdot\,\cdots\,\cdot n_m$.

To apply the above to a particular problem, you must envision the given process, in your case winding up with a rearangement of the letters in "definition", as having been obtained from a series of actions, or choices (the "experiments" above). You then figure out in how many ways each choice can be made and then multiply these numbers.


For your problem where the letters of "definition" are rearanged with the restriction that the $i$'s are not at the ends, you could do the following:

1) choose where the three $i$'s go (they can't be at the ends)

2) choose where the two $n$'s go

3) choose where the next unused letter (the $d$, say) goes

$\ \vdots$

7) choose where the last letter (the $o$, say) goes.

Note the first step. There are three indistinguishable $i$'s, so we arrange those as a group so to speak. Also note that the above series of choices will indeed produce all the desired rearangements of the letters in "definition" (in particular, we arrange the $i$'s first to ensure this).


Now towards figuring out the number of ways to do each step, you may think of filling in ten slots. Each slot gets a letter.

For experiment 1), we select three slots and place the $i$'s in them.

Pause here: with the restriction that the $i$'s are not on the end, this means we select three slots from the 8 "non-end"-slots. The number of ways of doing this, as one can show, is ${8\cdot7\cdot6\over 6}$.

So there are ${8\cdot7\cdot6\over 6}$ outcomes for experiment 1).

For experiment 2), we select 2 of the remaining 7 slots in which to put the two $n$'s

There are $7\cdot6\over 2$ outcomes for experiment 2).

Ok, the hard part's over. In each of the remaining experiments, we are choosing one of the remaining slots in which to put the letter.

There are $5$ outcomes for experiment 3).

There are $4$ outcomes for experiment 4).

There are $3$ outcomes for experiment 5).

There are $2$ outcomes for experiment 6).

There are $1$ outcomes for experiment 7).

So the total number of desired rearangements is $$ {8\cdot7\cdot6\over 6}\cdot{7\cdot6\over 2}\cdot5\cdot4\cdot3\cdot2\cdot1. $$


For your second problem, take the same sequence of experiment. The number of outcomes for experiment 1 would be 8 (if all the $i$'s are together, there are 8 choices of slots for the left-most $i$).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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