Set partition with some conditions

Question

This is the problem I am trying.

Define $S_k(n)$ to be the number of partitions of the set $[n]$ so that if $i$ and $j$ are in the same block, then $|i-j| > k$ holds. Show that $S_k(n) = B(n - k)$, for all $n \geq k$.

I first tried to find a bijection and also tried to find a recursive formula for the left hand side, but wasn't succesful. Can anyone help with this question?

Answer 1

In what follows, $[a,b]$ will always refer to the integer interval $\{a,a+1,\dots,b-1,b\}$, when $a\le b$.

I shall give a bijective proof of this equality. Suppose we are given a partition, $P$, of $[n-k]$. We shall output a partition, $P'$, of $[n]$, with the property that any two numbers in the same part are at distance more than $k$.

The $k$ numbers in the interval $[n-k+1,n]$ will be initially placed in $k$ new parts, each in a distinct part. Call a number $x\in [n-k]$ bad if there exists a $y$ in the same $P$-part as $x$ such that $x < y\le x + k$. The idea is that any bad numbers in $P$ will be moved to one of the $k$ new parts. We must do this carefully so that these two conditions are satisfied:

1. $P'$ is valid, in the sense that any two numbers in the same part are more than $k$ apart.

2. Our process is reversible, so we can remember where the numbers were moved from, and recover $P$ from $P'$.

For each part in $P$, we first group the numbers into "bad chains" as follows. We say that $x$ is linked to $y$ if they are in the same part and $|x-y|\le k$. The connected components of this linking relation are our bad chains. Each bad chain has a maximal element, which I will call the "leader." Note that the leader itself is not bad, because by definition, a number is bad if there is another number above it which is too close, but the leader is greatest in the chain, so has nothing above it.

The rules for moving the bad numbers is this:

For each bad number $x$ in $P$, let $\ell$ be the leader of $x$'s bad chain. If $\ell\equiv x\pmod{k+1}$, then $x$ will remain in its current part. Otherwise, $x$ is moved to the part containing the unique number $z$ in $[n-k+1,n]$ for which $$n+1-z\equiv \ell-x\pmod {k+1}$$

Finally, I shall prove the required points (1.) and (2.).

1. We have removed all bad numbers from the original parts, so we need only prove there are no numbers in the new parts that are too close. The only exceptions are the bad numbers $x$ with a leader $\ell$ for which $x\equiv \ell$, but these remaining bad numbers are all in the same equivalence class modulo $k+1$, so the remaining numbers are spaced far enough apart.

   For any $x$ moved to a part containing $z\in [n-k+1,n]$, we have $|x-z|>k$. This is because $\ell \le n-k$, so $$z-x\ge z-(n-k)+\ell-x\equiv 0\pmod {k+1}.$$Since the quantity $z-(n-k)+\ell-x$ is stricly positive, and equivalent to zero mod $k+1$, this quantity must be at least $k+1$, we we have shown $|z-x|\ge k+1$.

   Furthermore, for any $x_1,x_2$ in the same bad chain, we must have $x_1\equiv x_2\pmod {k+1}$, which implies $|x_1-x_2|\ge k+1$.

2. Looking at the outputted partition $P'$, you can determine all numbers that were originally bad by looking at the numbers in the parts containing the numbers in the interval $[n-k+1,n]$. This allows you to reconstruct the bad chains, by looking at the connected components of the relation of "at-most-$k$-apart" on these bad numbers. Letting $x$ be the largest number in such a chain, you can then recover the leader of the chain by solving the equation $n+1-z\equiv \ell-x$ for $\ell$, where $\ell$ must be chosen from the interval $[x+1,x+2,\dots,x+k]$. This allows you to return all of the numbers in the new parts to the original parts, so my claimed bijection is indeed reversible.