Show that the number of subsets of $\{1,\cdots, n\}$ with size $k$ and where the difference between consecutive pairs of elements is never equal to $2$ is $\sum_{j=0}^{k-1} {k-1\choose j}{n-k-j+1\choose n-2j-k}.$

I got that the desired number is equal to $\sum_{j=0}^{k-1} {k-1\choose j} \sum_{i=j}^{2j} {j\choose i- j}(-1)^i {n-k-i+k\choose n-k-i}$ as follows, but this may be incorrect. Let $C_k$ be the set of ordered pairs $(A, n)$ so that $A$ is a $k$-subset of $\{1,\cdots, n\}$ where the difference between consecutive pairs of elements is never equal to $2$. Then each difference vector (e.g. the difference vector corresponding to the pair $(\{a_1,\cdots, a_k\},n)$ would be $(a_1,a_2-a_1,\cdots, a_k-a_{k-1}, n-a_k)$) would have a first element that's a positive integer, a nonnegative integer as the last argument, and $k-1$ differences in between, none of which are $2$. This gives the generating series $\dfrac{x}{1-x}\cdot (x+\frac{x^3}{1-x})^{k-1} (\frac{1}{1-x}) = x^k (1-x+x^2)^{k-1} (1-x)^{-(k+1)}.$ The coefficient of $x^n,$ denoted $[x^n]x^k (1-x+x^2)^{k-1} (1-x)^{-(k+1)}, $ is thus \begin{align} [x^{n-k}] (1-x+x^2)^{k-1} (1-x)^{-(k+1)} &= \sum_{i\geq 0} \big([x^i] (1-x+x^2)^{k-1}\big) \big([x^{n-k-i}](1-x)^{-(k+1)}\big)\\ &= \sum_{i\geq 0} \left([x^i] \sum_{j=0}^{k-1} {k-1\choose j}(x^2-x)^j \right) {n-i\choose k}\\ &= \sum_{i\geq 0} \left([x^i]\sum_{j=0}^{k-1} {k-1\choose j}(-x)^j \sum_{m=0}^j {j\choose m} (-x)^m\right)\binom{n-i}k\\ &= \sum_{i\geq 0} \left([x^i] \sum_{j=0}^{k-1} \sum_{m=0}^{k-1} {k-1\choose j}{j\choose m} (-1)^{j+m} x^{j+m}\right){n-i\choose k}\\ &=\sum_{i\geq 0} \left(\sum_{j=0}^{k-1} {k-1\choose j}{j\choose i-j}\right)(-1)^i {n-i\choose k}\\ &= \sum_{j=0}^{k-1} {k-1\choose j}\sum_{i=j}^{2j} {j\choose i-j} (-1)^i {n-i\choose k}, \end{align} but apparently $\sum_{i=j}^{2j} {j\choose i-j} (-1)^i {n-i\choose k} \neq {n-k-j+1\choose n-2j-k},$ and despite checking this over many times, I am unable to figure out what went wrong. I used the binomial theorem and summation properties. Another possibility, though possibly even messier, would be to split the generating series up as $(1-\frac{x^2}{1-x})^k\cdot \dfrac{1}{(1-x-x^2)(1-x)}.$


I’ve not yet worked through the generating function argument, but I can prove the desired result directly.

If $\{a_1,\ldots,a_k\}$ is a $k$-element subset of $[n]$ such that $a_1<\ldots<a_k$, and $a_{i+1}-a_i\ne 2$ for $i=1,\ldots,k-1$, say that there is a gap at $i$ if $a_{i+1}-a_i>1$. Let $A(n,k)$ be the set of $\{a_1,\ldots,a_k\}\subseteq[n]$ such that if $a_1<\ldots<a_k$, then $a_{i+1}-a_i\ne 2$ for $i=1,\ldots,k-1$. For $j=0,\ldots,k-1$ let $A(n,k,j)$ be the set of members of $A(n,k)$ having exactly $j$ gaps. I claim that


Suppose that $S=\{a_1,\ldots,a_k\}\in A(n,k,j)$. Let $J$ be the set of indices at which $S$ has a gap. If $a_i,\ldots,a_j$ is a maximal string of consecutive integers, imagine gluing it together to form a single object, and if $j\in J$, include $a_j+1$ and $a_j+2$ as well; every member of $J$ will be accounted for in this way, and there will be one more object containing $a_k$. Each remaining member of $[n]$ is treated as a single object. We now have $j+1$ objects containing members of $S$ and $n-k-2j$ singleton objects, for a total of $n-k-j+1$ distinct objects. Any $j+1$ of them can be the objects that contain members of $S$, so there are $\binom{n-k-j+1}{j+1}$ members of $A(n,k,j)$ having gaps at the indices in $J$.

Example: Let $n=10$, $k=4$, and $j=2$; the members of $A(10,4,2)$ having gaps at $i=1$ and $i=2$ are $$\begin{align*}&\{1,4,7,8\}, \{1,4,8,9\},\{1,4,9,10\},\{2,5,8,9\}\\&\{2,5,9,10\},\{2,6,9,10\},\{1,5,8,9\},\{1,5,9,10\}\\&\{1,6,9,10\},\text{ and }\{2,6,9,10\}\,.\end{align*}$$ For $\{2,6,9,10\}$ the $5$ objects are $\{1\},\{2,3,4\},\{5\},\{6,7,9\}$, and $\{9,10\}$. For $\{2,3,6,10\}$, with gaps at $2$ and $3$, the $5$ objects are $\{1\},\{2,3,4,5\}$, $\{6,7,8\}$, $\{9\}$, and $\{10\}$.

There are $\binom{k-1}j$ possible choices for the set $J$ of indices at which $S$ has a gap, so altogether

$$\begin{align*} |A(n,k,j)|&=\binom{k-1}j\binom{n-k-j+1}{j+1}\\ &=\binom{k-1}j\binom{n-k-j+1}{n-2j-k}\,, \end{align*}$$

and the result follows by summing over the possible values of $j$.

  • $\begingroup$ This may sound stupid, but I can't get $6$ objects when $n=12, k=5, j=2$ for the subset $\{4,5,6,9,12\}.$ I think one of the objects should be $\{12\}$, and the rest should be $\{9,10,11\}, \{6,7,8\}, \{4,5\}, \{1\}, \{2\},\{3\}.$ What am I doing wrong? $\endgroup$ Aug 26 '20 at 15:00
  • $\begingroup$ @FredJefferson: That’s my fault for not explaining it more clearly: a string of consecutive members of $S$ that ends in a gap should be taken with the gap, so that here the pieces are $\{1\}$, $\{2\}$, $\{3\}$, $\{4,5,6,7,8\}$, $\{9,10,11\}$, and $\{12\}$. I’ll try to rewrite it to make that clearer. $\endgroup$ Aug 26 '20 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.