A lottery consists of randomly drawing $6$ balls (without regard to order) from a bin of $44$ balls numbered $1$ through $44$. What is the probability at least one pair of consecutively numbered balls are drawn?
I am interested in understanding why my principle of inclusion-exclusion solution is incorrect. Let $A_i$ be the set of drwas such that ball $i$ is drawn. Then we wish to compute $$ |(A_1 \cap A_2) \cup (A_2 \cap A_3) \cup \ldots \cup (A_{43} \cap A_{44})|. \qquad(\star)$$ Now we do cases: $|A_1 \cap A_2| = \binom{42}{4}$, because we can choose any other two numbers. There are $44-1=43$ consecutive two numbers, so the first term in $(\star)$ will be $43\binom{42}{4}$. The next term will be of the form $|A_1 \cap A_2 \cap A_3|$. There are $44-3=41$ other numbers and we need $3$ of them, so $\binom{41}{3}$ ways to do so. Now suppose we do have three consecutive numbers, say, $123$, then this is counted twice in the first term, because it counts $12$ and $23$, so we have to subtract it $85$ times. Therefore, the second term in $(\star)$ will be $-85\binom{41}{3}$. We can do similarly with the rest to find that: $$43\binom{42}{4} - 85 \binom{41}{3} + 42\binom{40}{2} = 3939650.$$ Note that the cases of $5$ and $6$ consecutive integers are only counted once in the expression above, so we don't need to add or subtract anything.
There are $\binom{44}{6}$ ways to choose any $6$ numbers, so the probability should be $$\frac{3939650}{\binom{44}{6}} = \frac{13775}{24682} \approx 56\%,$$ but this is incorrect. Why? I know that it overcounts, but what does it overcount?
For each $i\in \{1,\dots,5\}$, let $E_i$ be the set of lottery drawings where balls number $i$ and $i+1$ are consecutive numbers, when the balls are sorted from left to right. We want to count $|E_1\cup \dots \cup E_5|$, so we use PIE.
We need a clever representation of lottery drawings in order to make PIE easier. Let $b_1,b_2,\dots,b_6$ be an arbitrary lottery drawing, with $1\le b_1<\dots<b_6\le 44$. These six numbers divide the interval $\{1,\dots,44\}$ into seven gaps (some possibly empty). Let $x_0,x_1,\dots,x_6$ be the sizes of these gaps. That is, $x_i=b_{i+1}-b_i-1$ whenever $i\in \{1,\dots,5\}$, while $x_0=b_1-1$ and $x_6=44-b_6$. Note that $(x_0,\dots,x_6)$ is an integer vector for which $$ x_0+x_1+\dots+x_6=38,\\ x_i\ge 0 $$ We can equivalently specify our lottery drawing using this integer vector. Using stars and bars, the number of solutions is $\binom{38+7-1}{7-1}=\binom{44}6$, which is indeed equal to the number of ways to choose 6 balls out of 44.
I claim that $|E_i|=\binom{43}5$, for each $i\in \{1,\dots,5\}$. Indeed, solutions where the $i^\text{th}$ ball and $(i+1)^\text{st}$ balls are adjacent correspond exactly to vector $(x_0,\dots,x_6)$ where $x_i=0$. The number of solutions to this modified stars and bars problem is just $\binom{38+6-1}{6-1}=\binom{43}5$. Effectively, forcing $x_i=0$ just means there is one fewer variable.
Similarly, when computing the $k$-fold intersections for the PIE method, you find that $$ |E_1\cap \dots \cap E_k|=\binom{44-k}{6-k}, $$ because this is equivalent to requiring $k$ of the variables $x_0,\dots,x_6$ to be zero. Therefore, the result of PIE is $$ |E_1\cup \dots \cup E_6|=\sum_{k=1}^5(-1)^{k-1}\binom 5k\binom{44-k}{6-k} $$ You then need to divide by $\binom{44}6$ to get the probability of at least one pair of consecutive balls.
From NotASalmonFish's answer, we also have the closed form $$ |E_1\cup \dots \cup E_5|=\binom{44}6-\binom{39}6 $$ We can prove this, starting my answer, as follows: $$ \begin{align} \binom{44}6-|E_1\cup \dots \cup E_5| &=\sum_{k=0}^5 (-1)^k \binom5k\binom{44-k}{6-k} \\ &=\sum_{k=0}^5 (-1)^k \binom5k\cdot (-1)^{6-k}\binom{-39}{6-k} \\ &=\binom{-34}{6}=(-1)^6\binom{39}{6}=\binom{39}6. \end{align} $$ Above, we made two uses of the $\binom{n}{k}=(-1)^k\binom{-(n-k+1)}{k}$ formula, and the Chu-Vandermonde identity.