NonConsecutiveSubsetsSolution

Arrange the elements of $S$ in a sequence from $1$ to $n$. Taking a $p$-subset of $S$ containing no consecutive integers can be visualized by circling the corresponding numbers in the sequence. Noting that there is at least one uncircled number between two circled ones.

Now, take $n-p$ white balls and $p$ black balls. Put $p-1$ white balls aside and arrange the remaining $n-p+1$ white and black balls into a sequence. Then insert the $p$ white balls into the sequence so that exactly one goes in between two black balls. This make a sequence of $n$ balls, positioned at $1$ to $n$. The positions of the black balls make a $p$-subset of the $S$ having no consecutive integers.

Thus, the number of the original problem is equivalent to counting the number of arrangements of $n-p+1$ balls with $n-2p+1$ white balls and $p$ black balls. This is ${n-p+1}\choose{p}$.

For example, take $n=6$ and $p=3$, look at the following comparison:

whole set S	subset T	all 6 balls<br>(o: white, x: black)	2 white balls<br> removed
123456	135	xoxoxo	xxxo
123456	136	xoxoox	xxox
123456	146	xooxox	xoxx
123456	246	oxoxox	oxxx