# Restricted number of k non-consecutive combinations out of n

Assume we need to choose $k$ numbers out of $[1...n]$ so no two numbers are consecutive. I know the number of such combinations is given by$\binom {n-k+1}{k}$. Assume the numbers are given by $r_1<r_2...<r_k$ when the difference between $r_{i+1}$ and $r_i$ is always higher than $2$. Now, I want to restrict the combinations so that for $p=1$ $(r_{i+1},r_i)$ pairs, the difference between them will be at least $t=3$ (and not at least 2).

Example: for $p=1$ and $t=3$ The number of combinations is given by $\binom {n-k+1}{k}$-$(n-2k+2)$ because we subtract all the combinations in which all the differences are exactly 2.

How can it be generalized to any $p$ and/or any $t$?

For $t=3$ I thought about counting the combinations by $\binom {n-k+1-p}{k}$ so we can insert the $p$ "dummies" in each combination but it seems it doesn't work and doesn't coincide with the example for $p=1$.

Thank you

We will show the particular case when $p=k-1$.

Any selection of $k$ numbers from $\{1,2,\dots ,n-(t-1)(k-1)\}$ gives you a suitable combination when you add $t-1$ to the second smallest element, $2(t-1)$ to the third smallest element$\dots$ $(t-1)(k-1)$ to the largest alement. Using the inverse process (substracting instead of adding) on a suitable sequence will always give you a set in $\{1,2,3,\dots ,(n-(k-1)(t-1)\}$

• Yes, Thank you, you are of-course right. Do you have a direction on how to generalize it to any p? – Evyaa Jun 25 '14 at 19:10

Table[Table[Binomial[n - 2 (k - 1), k], {k, 0, Floor[(n + 2)/3]}], {n, 0, 10}] // Grid

Table[Table[ Length[Select[Tuples[{0, 1}, n], FreeQ[#, {_, 1, 0, 1, }] && FreeQ[#, {, 1, 1, _}] && Count[#, 1] == k &]], {k, 0, Floor[n + 2]/3}], {n, 0, 10}] // Grid

nn = 10; CoefficientList[ Series[1/(1 - x)/(1 - y x^3/(1 - x)), {x, 0, nn}], {x, y}] // Grid

These three Mathematica codes return the same triangular array of numbers, T(n,k): the number of size k subsets of {1,2,...,n} such that the difference between any two elements is at least 3.

• Does it have a closed analytic expression? – Evyaa Jun 26 '14 at 7:17
• T(n,k) = binomial(n - 2*(k - 1)),k). – Geoffrey Critzer Jun 26 '14 at 13:14
• Oh. In that case it is a special case of Bananarama's solution for t=3. The big question is can we have an analytic expression so the difference between p pairs is at least 3 (and not any two elements)? Thanks. – Evyaa Jun 26 '14 at 13:24