Re-arrangements of $(1,1,2,2,3,3,4,4)$ with $(1,2,3,4)$ as a subsequence

Question

In how many ways is it possible to re-arrange the sequence $(1,1,2,2,3,3,4,4)$, such that $(1,2,3,4)$ is a subsequence of it?

In case the question is not clear: what is the number of functions $f\negthinspace : [8]\to [4]$, such that for all $j \in [4]$ there exist exactly two elements $i_1,i_2\in [8]$ s.t. $f(i_1)=f(i_2)=j$, and s.t. there exists $i_1<i_2<i_3<i_4$ in $[8]$ with $f(i_1)<f(i_2)<f(i_3)<f(i_4)$?

I have tried to solve this using the inclusion-exclusion principle, but I couldn't really find the appropriate sets to take. I also tried to give it a recursive formula, but again failed.

I brute-force calculated the final result to be $641$.

EDIT: the code I used is

import numpy as np
from collections import Counter

def has_subsequence(sequence, subseq, start_index=0):
    if len(subseq) == 1:
        return sequence.find(subseq[0], start_index) >= 0
    if len(sequence) <= len(subseq):
        return sequence == subseq

    char_index = sequence.find(subseq[0], start_index)
 
    if char_index == -1:
        return False
    return has_subsequence(sequence, subseq[1:], char_index + 1)

def count_perms_of_00112233_with_substring_0123():
    count = 0
    for sequence in (np.base_repr(i, base=4).zfill(8) for i in range(4**8 + 1)):
        if all(count_i == 2 for count_i in Counter(sequence).values()):
            if has_subsequence(sequence, "0123"):
                count += 1

    print("Number of valid sequences:", count)

Answer 1

Here is an inclusion-exclusion approach: $$\sum_{k=0}^4 (-1)^k\binom{4}{k}\binom{8}{k+4}(4-k)! = 641$$ The idea is to choose $k$ of the elements among $\{1,2,3,4\}$ to appear twice (and the other $4-k$ once), choose $k+4$ of the $8$ positions to place these elements in ascending order, and then permute the remaining $8-(k+4)=4-k$ (distinct) elements arbitrarily.

---

Here's a bit more explanation. A naive count of permutations of $(1,1,2,2,3,3,4,4)$ that contain $(1,2,3,4)$ as a subsequence would choose the $4$ positions in $\binom{8}{4}$ ways and then permute the remaining $4$ elements in $4!$ ways, yielding $\binom{8}{4} 4! = 70\cdot 24 = 1680$. Pictorially, we have $$\_1\_2\_3\_4\_,$$ where each $\_$ corresponds to a nonnegative number of elements.

But this overcounts when $(1,2,3,4)$ appears more than once. To correct for this overcount, consider $4$ cases: $$ \_1\_1\_2\_3\_4\_ \\ \_1\_2\_2\_3\_4\_ \\ \_1\_2\_3\_3\_4\_ \\ \_1\_2\_3\_4\_4\_ $$ In each case, choose the $5$ positions in $\binom{8}{5}$ ways and then permute the remaining $3$ elements in $3!$ ways, yielding $4\binom{8}{5} 3! = 4\cdot 56\cdot 6 = 1344$. So a naive correction to the original overcount would yield $1680-1344=336$.

But we have overcorrected when $(1,2,3,4)$ appears more than twice. So add back in the counts for the following $\binom{4}{2}=6$ cases: $$ \_1\_1\_2\_2\_3\_4\_ \\ \_1\_1\_2\_3\_3\_4\_ \\ \_1\_1\_2\_3\_4\_4\_ \\ \_1\_2\_2\_3\_3\_4\_ \\ \_1\_2\_2\_3\_4\_4\_ \\ \_1\_2\_3\_3\_4\_4\_ $$ In each case, choose the $6$ positions in $\binom{8}{6}$ ways and then permute the remaining $2$ elements in $2!$ ways, yielding $\binom{4}{2}\binom{8}{6} 2! = 6\cdot 28\cdot 2 = 336$. Our count so far is $1680-1344+336=672$.

But we have overcorrected in the following $\binom{4}{3}=4$ cases: $$ \_1\_1\_2\_2\_3\_3\_4\_ \\ \_1\_1\_2\_2\_3\_4\_4\_ \\ \_1\_1\_2\_3\_3\_4\_4\_ \\ \_1\_2\_2\_3\_3\_4\_4\_ $$ In each case, choose the $7$ positions in $\binom{8}{7}$ ways and then permute the remaining $1$ element in $1!$ way, yielding $\binom{4}{3}\binom{8}{7} 1! = 4\cdot 8\cdot 1 = 32$. Our count so far is $1680-1344+336-32=640$.

Finally, add back $\binom{4}{4}\binom{8}{8} 0!=1$ for $11223344$, yielding $1680-1344+336-32+1=641$.

Answer 2

RobPratt's answer skips over some details. My answer attempts to fill in most of these steps.

---

Let $\newcommand{\A}{\mathcal A}\A$ denote the set of four-element subsets of $[8]$. For each $A\in \A$, let $S_A$ be the set of rearrangements of $11223344$ (hereafter: words) such that the subsequence $1234$ appears at the spots of $A$. The goal is to compute $|\bigcup_{A\in \A} S_A|$. To do this, we use PIE, but it will be a bit more difficult than most PIE problems.

Let $\mathscr U$ be the set of ordered pairs $(\mathcal B,w)$, where $\newcommand{\B}{\mathcal B}\B$ is an arbitrary subset of $\mathcal A$, and where $w$ is a word which belongs to $\bigcap_{B\in \B}S_B$. I claim that $$ \left|\bigcup_{A\in \A}S_A\right|=\sum_{(\mathcal B,w)\in \mathscr U}(-1)^{|\B|}\tag1 $$ You can check that this is equivalent to PIE; when $|\mathcal B|=k$, we are adding up the contributions of the $k$-fold intersections to the PIE sum, which comes with a sign of $(-1)^k$. However, this sum is much too unwieldy to work with. The genius of Rob's answer is that it only sums over a much smaller, manageable subset, while getting the same answer.

Given $A_1,A_2\in \mathcal A$, we say they are compatible if, for every $x\in \{1,2,3\}$, we have $$ \text{rank}(A_1,x)< \text{rank}(A_2,x+1) \qquad \text{and} \qquad \text{rank}(A_2,x)< \text{rank}(A_1,x+1) $$ Here, $\text{rank}(S,k)$ means the $k^\text{th}$ smallest element of $S$. So, $\text{rank}(S,1)=\text{min}(S)$, while $\text{rank}(S,|S|)=\max S$. For example, the following two sets are incompatible: $$ A_1=\{1,2,6,7\},\qquad A_2=\{3,4,6,7\} $$ Any word in $S_{A_1}\cap S_{A_2}$ looks like $(1,2,1,2,\_,3,4,\_)$. Here is an equivalent, intuitive description of compatibility. If $A_1$ and $A_2$ are compatible, and $w\in S_{A_1}\cap S_{A_2}$, then the numbers at the locations in $w$ defined by $A_1\cup A_2$ will be in weakly increasing order. In the above example, the numbers in $(1,2,1,2,\_,3,4,\_)$ are not in weakly increasing order, hence $A_1$ and $A_2$ are incompatible.

Furthermore, we say that $\B\subset \A$ is compatible if, for all $B_1,B_2\in \mathcal B$, we have $B_1$ and $B_2$ are compatible.

Lemma: $\newcommand\N{\mathcal N}$ Consider the sum $\sum_{(\mathcal N,w)} (-1)^{|\mathcal N|}$, where $(\N,w)$ ranges over all ordered pairs such that $\N\subseteq \A$ is an incompatible family, and where $w\in \bigcap_{N\in \N}S_N$. This sum is equal to zero.

Proof: We will define a sign-reversing involution on the set of ordered pairs $(\N,w)$. This proves the ordered pairs can be partitioned into pairs with opposite sign, implying the alternating summation over them is zero.

If a $\N$ is incompatible, then there exists subsets $N_1,N_2\in \N$, and there exists $x\in \{1,2,3\}$, such that when you let

$$\text{rank}(N_1,x)=i\quad \text{rank}(N_1,x+1)=j\quad \text{rank}(N_2,x)=k\quad \text{rank}(N_2,x+1)=\ell,$$

then you have $i<j<k<\ell$. We define $(N_1,N_2,x)$ to be the lexicographically earliest ordered triple such that this inequality is true. Then, define $$ N_3:= N_1\setminus \{j\}\cup \{\ell\}=N_2\setminus \{k\}\cup \{i\} $$ Recall our example before; for the incompatible pair $N_1=\{1,2,6,7\}$ and $N_2=\{3,4,6,7\}$ (so, necessarily $x=1$), we would have $N_3=\{1,4,6,7\}$. The idea is that, if $w\in S_{N_1}\cap S_{N_2}$, then $w$ is automatically an element of $S_{N_3}$ as well. Therefore, we can safely add or remove $N_3$ from the incompatible family $\N$, while preserving the property that $w\in \bigcap_{N\in \N}S_N$. That is, if we let $\oplus$ denote the symmetric difference operator on sets, then our sign reversing involution is $$ (\N,w)\mapsto (\N\oplus \{N_3\},w) $$$\tag*{$\square$}$

With this lemma under our belt, we see that we can ignore all incompatible families in the sum in $(1)$, without changing the sum. Therefore, the entire sum is equal to the sum which only ranges over compatible families.

Lemma: Consider the sum in $(1)$, except we only sum over ordered pairs $(\mathcal C,w)$ such that $\mathcal C$ is a compatible family and for which $w\in \bigcap_{C\in \mathcal C} S_C$. This sum is equal to $$\sum_{k=0}^4 (-1)^k \binom 4k \binom 8{4+k}(4-k)!$$

Proof sketch: The idea is that, if $\mathcal C$ is a compatible family, and $w$ is in the intersection of the $S_C$'s, then if you look at the spots of $w$ in $\bigcup_{C\in \mathcal C}C$, then the numbers at these spots must be in weakly increasing order. Therefore, choosing a compatible family occupied by a word $w$ goes exactly as described in Rob's answer. You choose $k$ numbers to be duplicated, choose the locations of the numbers in $\binom{8}{k+4}$ ways, and then arbitrarily permute the remaining $(4-k)$ numbers.