How many ways can you rearrange the letters of the word “CALENDAR” if ‘C’ and ‘A’ must be together

combinatoricspermutations

I'm trying to solve the following questions:

  1. a) You are given the word "CALENDAR". How many ways can you rearrange the letters with the restriction that 'C' and 'A' must be together?

    b) With the same word "CALENDAR", how many ways can you rearrange the letters with the restriction that 'C' and 'A' must be together and 'N' and 'D' cannot be together?

  2. Given the word "POLYNOMIAL", how many ways can you rearrange the letters such that 'P' is next to 'O' and 'N' and 'M' cannot be together.

My approach for 1. a) was as follows:

Step 1: Group 'C' and 'A' together and substitute them with 'X'. Then, the word becomes "XLENDAR."

Step 2: Calculate the permutations of this pseudo 7-letter word while accounting for the fact that 'X' has two permutations for every appearance ('CA' or 'AC').

Number of permutations of "XLENDAR" = $7! \times 2 = 10,080$.

My confusion here is about the repetition of the letter 'A' in the original word "CALENDAR" and how to deal with it.
Consider a sample of the permutations as follows:

A, CA, L, E, N, D, R
AC, A, L, E, N, D, R

This would be double-counting the same permutation if using the formula above, right? How do we deal with this pattern that can appear if the letters 'A' and 'CA' are arranged beside each other as a palindrome? This pattern can shift from the beginning of the word till the end a total of 6 times, so do we subtract 6 from 10,080?

For part b) I grouped 'D' and 'R' together as 'Y' to get XLEYAR. Following the same method as above, I calculated the permutations where 'D' and 'R' do appear together (remembering that both 'X' and 'Y' have 2 permutations each every occurrence).

$6! \times 2 \times 2 = 2880$.

Subtracting these occurrences from the original total should tell me all the permutations that satisfy the condition for 1b). Once again, though, my confusion lies with the repeated 'A' in this calculation.

I've seen some solutions presented as # of permutations $= 10,080 – 2880 = 7200$, but they don't address the repetition in their calculations.

I'd really appreciate some help as I'm not sure where to go from here. Thank you!

Best Answer

Here we consider part 1a) and 1b) of the problem. We use PIE the inclusion-exclusion principle to count the number of valid $8$-letter words built from the letters $C,A,L,E,N,D,A,R$.

Part 1a): Valid words must contain string $AC$ or $CA$.

In order to do the job some kind of bookkeeping is helpful. We consider \begin{align*} &\color{blue}{\left(AC\ .\ .\ .\ .\ .\ .\ .|CA\ .\ .\ .\ .\ .\ .\ .\right)}\tag{1}\\ &\quad\color{blue}{-\left(ACA\ .\ .\ .\ .\ .\right)}\tag{2}\\ \end{align*}

Comment:

  • In (1) we count all $8$-letter words which contain either the substring $AC$ or $CA$ where the remaining six characters are indicated by six dots which gives $2\cdot 7!$.

  • In (2) we add words containing $ACA$ as compensation for those which we've counted twice in (1).

  • No more cases are left to consider.

We obtain according to (1) to (2): \begin{align*} 2\cdot 7!-6!=10\,080-720=\color{blue}{9\,360} \end{align*}

Part 1b): Valid words must contain string $AC$ or $CA$ and must not contain $DN$ or $ND$.

Here we consider \begin{align*} &\color{blue}{\left(AC\ .\ .\ .\ .\ .\ .\ .|CA\ .\ .\ .\ .\ .\ .\ .\right)}\tag{1}\\ &\quad\color{blue}{-\left(ACA\ .\ .\ .\ .\ .\right)}\tag{2}\\ &\quad\color{blue}{-\left(AC\ DN\ .\ .\ .\ .|AC\ ND\ .\ .\ .\ .|CA\ DN\ .\ .\ .\ .|CA\ ND\ .\ .\ .\ .\right)}\tag{3}\\ &\quad\color{blue}{+\left(ACA\ DN\ .\ .\ .|ACA\ ND\ .\ .\ .\right)}\tag{4}\\ \end{align*}

Comment:

  • In (1) and (2) we start as we did in problem 1a).

  • In (3) we subtract all occurrences which contains $AC$ or $CA$ and not $DN$ or $ND$.

  • In (4) we compensate double counts from (3) by adding those once again.

  • No more cases are left to consider.

We obtain according to (1) to (4): \begin{align*} 2\cdot7!-6!-4\cdot 6!+2\cdot 5! &=10\,080-720-2\,880+240\\ &=\color{blue}{6\,720} \end{align*}

Problem 2 can be done similarly.

Related Question