91Ó°ÊÓ

Permutations with Repeated Elements-Problems 15 and 16: The word CARRIER has seven letters. But there are fewer than \(7 !\) permutations, because in any arrangement of these seven letters the three \(R\) 's are interchangeable. If these \(R\) 's were distinguishable, there would be \(3 !\), or \(6,\) ways of arranging them. This implies that only \(\frac{1}{6}\) (that is, \(\frac{1}{3 !}\) ) of the \(7 !\) permutations are actually different. So the number of permutations is $$ \frac{7 !}{3 !}=840 $$ There are four \(I^{\prime}\) 's, four \(S\) 's, and two \(P\) 's in the word MISSISSIPPI, so the number of different permutations of its letters is $$ \frac{111}{4 ! 4 ! 2 !}=34,650 $$ Nine pennies are lying on a table. Five show heads and four show tails. In how many different ways, such as "HHTHTTHHT," could the coins be lined up if you consider all the heads to be identical and all the tails to be identical?

Step by step solution

01

Understand the Problem

We need to find the number of distinct permutations of a set of items that have repeating elements. The formula for permutations with repeated elements is: $$ \frac{n!}{n_{1}!\cdot n_{2}! \cdot \ldots \cdot n_{k}!} $$ where n is the total number of items, and \(n_{1}, n_{2}, \ldots, n_{k}\) are the frequencies of each distinct repeating element.

02

Apply the formula to CARRIER

The word CARRIER has 3 Rs which are repeated. We apply the formula using the total number of letters n=7 and the frequency of R is 3, so we have: $$ \frac{7!}{3!} =\frac{7\times6\times5\times4\times3!}{3!} = 7\times6\times5\times4 = 840 $$

03

Apply the formula to MISSISSIPPI

The word MISSISSIPPI has 11 letters, with 4 Is, 4 Ss, and 2 Ps repeating. Using the formula, we get: $$ \frac{11!}{4!4!2!} =\frac{11\times10\times9\times8\times7\times6\times5\times3!}{4!4!2!} =\frac{11\times10\times9\times8\times7\times6\times5}{4\times3\times2\times4\times3\times2\times2} = 34,650 $$

04

Calculate permutations for the pennies

There are 5 identical heads (H) and 4 identical tails (T). The total number of pennies is 9. Using the same formula, the permutations will be: $$ \frac{9!}{5!4!} = \frac{9\times8\times7\times6\times5!}{5!\times4\times3\times2\times1} = \frac{9\times8\times7\times6}{4\times3\times2} = 126 $$

Unlock Step-by-Step Solutions & Ace Your Exams!

• Full Textbook Solutions

  Get detailed explanations and key concepts

• Unlimited Al creation

  Al flashcards, explanations, exams and more...

• Ads-free access

  To over 500 millions flashcards

• Money-back guarantee

  We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91Ó°ÊÓ!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

Combinatorics

Combinatorics is the branch of mathematics focusing on counting, arranging, and analyzing configurations of objects following certain rules. It covers a variety of concepts from simple combinations and permutations to the more complex ideas like graph theory and partition theory.

In the context of permutations with repeated elements, combinatorics allows us to calculate the number of distinct ways we can arrange items, taking into account that some of the items may be identical. This is particularly useful when dealing with problems like figuring out how many unique sequences can be formed from a word with repeating letters or arranging items with symmetry.

Factorial Notation

Factorial notation is integral to understanding combinatorics, specifically in calculating permutations and combinations. The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n. For example,
\[5! = 5 \times 4 \times 3 \times 2 \times 1 = 120.\]

Zero factorial is defined as \(0! = 1\), an important convention that simplifies many mathematical formulas. Factorials grow very rapidly with increasing numbers, making them a powerful tool in counting permutations where order matters.

Permutation Formula

The permutation formula is the mathematical representation used to calculate the number of ways to order a set of items. For distinct items, it is simply n!, where n is the number of items to arrange. However, when items repeat, the formula needs to account for indistinguishable arrangements.

The formula used for permutations with repeated items is
\[\frac{n!}{n_{1}! \times n_{2}! \times \ldots \times n_{k}!}\]
where n is the total number of items and \(n_{1}, n_{2}, \ldots, n_{k}\) are the frequencies of each distinct repeating item. This formula prevents us from overcounting arrangements where the repeating items are considered interchangeable.

Arrangement of Items

When arranging items, especially in permutations with repeated elements, we are interested in the order of these items. The central concept is that if two items are identical, switching them does not create a new, unique arrangement.

For example, the arrangement 'ABBA' has two 'A's and two 'B's. Swapping the 'B's with each other doesn't change the sequence, hence it is not considered a new permutation. This principle reduces the total number of unique permutations and is precisely why the formula \( \frac{n!}{n_{1}! \times n_{2}! \times \ldots \times n_{k}!}\) includes the division by the factorials of the counts of each repeating element.