Number of ‘acceptable’ pairs in card drawing game

Not a complete answer, but it might help.

---

Let $[n]=\{1,2,\ldots,n\}$ . The deck of cards is represented by the multiset $D_n=[n]\cup[n]$. For each $m$, let $S_m^n$ be a partitioning of $D_n$ into subsets of $2$, and $S^n=\bigcup_m S_m^n$ (note that the order in which the pairs are drawn doesn't actually matter, so it isn't necessary to count the permutations).

Call the $m^\text{th}$ partitioning $k$-acceptable iff, for all $\{i,j\}\in S_m^n$, $|i-j|\le k$, and $k$-unacceptable otherwise. The task is now to find the total number of partitionings (the largest $m$) for each $n$, and the subset of $k$-acceptable partitionings.

The first part is relatively easy. I'm not great with combinatorics, so I just used the formula from this question, played with Mathematica, and searched the OEIS until I got this:

$$|S^n|=(2n-1)!!$$

For the second part, let $A_k^n$ be the set of $k$-acceptable partitionings of $D_n$. Then, the probability that a particular partitioning is $k$-acceptable is:

$$P(k,n)=\frac{|A_k^n|}{|S^n|}=\frac{|A_k^n|}{(2n-1)!!}$$

All that's left is to determine the size of $A_k^n$.

Note:

Assuming that I haven't made any mistakes, if Christopher Well's answer is correct and $P(1,3)=\frac{1}{3}$, then $|A_1^3|=5$.