[Math] Inclusion/exclusion, at least and exactly arrangements

combinationscombinatoricsdiscrete mathematicsinclusion-exclusion

The question wants to count certain arrangements of the word "ARRANGEMENT":

a) find exactly 2 pairs of consecutive letters?

b) find at least 3 pairs of consecutive letters?

I have the answer given from the tutor but it doesn't make sense to me.

Let's start with the base case:

$S_2 = \frac{(11-2\times2+2)!}{(2!)^{(4-2)}}\binom{4}{2}$：All possible combinations for 2 pairs of consecutive letters are known.

$S_3 = \frac{(11-2\times3+3)!}{(2!)^{(4-3)}}{4\choose3}$：All possible combinations for 3 pairs of consecutive letters are known.

$S_4 = (11-2\times4+4)!\binom{4}{4}=7!$：All possible combinations for 4 pairs of consecutive letters are known.

The equation for exactly m conditions：$E_m = S_m – {m + 1\choose1}S_{m+1} + {m + 2\choose2}S_{m+2}$.

The equation for at least m conditions：$L_m = S_m – {m \choose1}S_{m+1} + {m + 1\choose2}S_{m+2}$.

Answer for (a)：$E_2 = S_2 – {3\choose1}S_3 + {4\choose3}S_4$.

Answer for (b)：$L_3 = S_3 – {3\choose1}S_4$.

For (a), I don't understand why we need to multiply $\binom{3}{1}$ with $S_3$ and $\binom{4}{3}$ with $S_4$?

If we have ${S_3}$ that satisfies the requirement for ${S_2}$ (as three pairs would include two pairs), then wouldn't ${E_2} = S_2 – S_3$?

For (b), wouldn't the answer just be ${S_3}$ since we it contains the combination for every triple pair?

I don't understand the given formula used for ${E_m}$ and ${L_m}$, mainly the combinatorics part because it looks to me that we already handled that combinations in the calculations of ${S_2}$, ${S_3}$, ${S_4}$.

Could someone please explain the formula and why the answers are as such?

Thanks!

EDIT: I got the question from https://www.youtube.com/watch?v=D1T3xy_vtxU&index=8&list=PLDDGPdw7e6Aj0amDsYInT_8p6xTSTGEi2 – start the video at (4.35) for the question

Best Answer

Terms used in the answer:

  1. $A_k$: The set of elements has (at least) property indexed $k$.
  2. IEP for Inclusion-Exclusion Principle.
  3. Exactly-none IEP: exactly none of the indexed properties got selected via IEP. i.e.

\begin{align} \bigcap_{k=1}^{m}{\overline{A_k}} \end{align}

Long answer to understand the two coefficients:

  1. Let's define $S_m$: It's a shorthand to simplify the formula of IEP. Assume there are $n$ properties in total, and $I$ is an index set, then we can pick any $m\le n$: $$\begin{align} S_m&=\sum\left|\textrm{an intersection of }m\textrm{ sets}\right|\\ &=\sum_{|I|=m}\left|\bigcap_{j\in I}A_j\right| \end{align}$$

  2. $E_0$ gives exactly-none IEP: (Let $S_0=U$): $$ \begin{align}E_0 &=\sum_{j=0}^n(-1)^{j-0}{j\choose 0}S_j\\ &=\sum_{j=0}^{n}(-1)^{j}S_j\\ &=\left|\bigcap_{j=1}^n\bar{A_j}\right|.\\ \end{align} $$

    for each $S_j$, the coefficient is $(-1)^j$:

    $$\begin{align} E_0&=\sum_{j=m}^n(-1)^{j-m}{j\choose m}S_j, m=0\\ &=\sum_{j=0}^n(-1)^{j-0}{j\choose 0}S_j\\ &=\sum_{j=0}^{n}(-1)^{j}S_j. \end{align} $$

    The ${j\choose m}$ disappears in $E_0$. But for $E_m$, we got more than that. So maybe there are more than one exactly-none IEPs in $E_m$?

  3. My attempt to explain $E_m$:

    $$ E_0=\sum_{j=m}^n(-1)^{j-m}{j\choose m}S_j\\ $$

    3.1. Observe the first term, $j=m$. Now $S_m$ gives:

    $$\begin{align} S_m&=\sum_{|I|=m}\left|\bigcap_{j\in I}A_j\right|\\ &=A_{1,2,...,m} + A_{1,2,...,(m-1),(m+1)} + ... + A_{(n-m+1),(n-m+2),...,n}\\ \end{align}\\ $$

    3.2. Now we calculate $E_0$ once for each term $A_{...}$ as the universe. So we have: (The notation $E_{0,U}$ where $U$ means the universe defined for the calculation)

    $$\begin{align} E_{0,A_{1,2,...,m}}&=\sum_{j=m+1}^n(-1)^{j-m}S_j\\ E_{0,A_{1,2,...,(m-1),(m+1)}}&=\sum_{j=m+1}^n(-1)^{j-m}S_j\\ \vdots\\ E_{0,A_{(n-m+1),(n-m+2),...,n}}&=\sum_{j=m+1}^n(-1)^{j-m}S_j\\ \end{align} $$

    you might have many questions at this stage:

    Q1:

    Those $A_{...}$ might overlap some of the others?

    Yes. But if each $E_{0, A_{\dots}}$ work, no overlapping. Because $E_m$ means exactly-m properties when the calculation is complete.

    Q2:

    Each $E_0$, ignoring those $(-1)^{j-m}$, have $1$ for each term. Now you're trying to convince me that applying it many times will create ${j\choose m}$, a variable for each term in the resulting $E_m$? By intuition, if you apply it, say $5$ times, you should have a $5$ for each term?

    Yes. I don't know how to explain this either for now.

  4. Now, the strangest step, I cannot believe it too:

    Let's try to calculate how many $S_j$ are needed when $j$ is given. This is equivalent to finding how many universes include each of them. So here is the term:

    $$ {j\choose m} $$

    given any $j$ properties, you choose $m$ of them, you find one universe, i.e. one left-hand-side on the list of 3.2. that includes it on the right-hand-side. This explains the mysterious ${j\choose m}$ of $E_m$.

  5. On the other hand, The formula of $L_m$(Count the elements included in $\ge m$ sets) is: $$\begin{align} L_m&=\sum_{k=m}^nE_k\\ &=\sum_{k=m}^n\sum_{j=k}^n(-1)^{j-k}\binom{j}{k}S_j\\ &=\sum_{j=m}^n(-1)^j\sum_{k=m}^j(-1)^k\binom{j}{k}S_j\\ &=\sum_{j=m}^n(-1)^j\sum_{k=m}^j(-1)^k\left[(-1)^{k-m}\binom{-1}{k-m}\right]\binom{j}{j-k}S_j\\ &=\sum_{j=m}^n(-1)^{j-m}\binom{j-1}{j-m}S_j\quad\quad\square \end{align}$$

    So $L_m$ does sum up the coefficients of $E_m$.

The rigorous version of the explanation can be found on the linked question: Combinatorics meaning of $L_m=\sum_{j=m}^{n}(-1)^{j-m}\binom{j-1}{m-1}S_j$.

Related Question