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)\}$

  • $\begingroup$ Yes, Thank you, you are of-course right. Do you have a direction on how to generalize it to any p? $\endgroup$ – 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.

  • $\begingroup$ Does it have a closed analytic expression? $\endgroup$ – Evyaa Jun 26 '14 at 7:17
  • $\begingroup$ T(n,k) = binomial(n - 2*(k - 1)),k). $\endgroup$ – Geoffrey Critzer Jun 26 '14 at 13:14
  • $\begingroup$ 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. $\endgroup$ – Evyaa Jun 26 '14 at 13:24

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.