Count specific semi-consequtive subsets of a set - general formula?

22 Views Asked by At

Given a set of consequtive integer numbers {1,2,3,...36} and considering all 376992 5-number combinations out of this set, how can we count following:

number of 5-number combinations having 3 numbers like this

  1. +1, +2 pattern: (1,2,4) or (2,3,5) or ... or (33,34,36)

  2. +2, +2 pattern

  3. +2, +3 pattern

  4. +n, +k pattern

    Is it possible to generalize?

1

There are 1 best solutions below

4
On

If I understand correctly, you want to get all the subsets of 5 elements where you have 3 numbers following the pattern. The number of ways to get 3 numbers that follow the pattern is equal to: $$36 - n - k$$ This means that you need to figure out what is the highest value that you can pick in such a way that the second and third numbers are still in the initial set. From the remaining numbers, you need to pick 2, in order to form a set of 5 elements, and this can be done in: $$\binom{33}{2}$$ So the total number of sets that follow the rule is: $$(36 - n - k) \binom{33}{2}$$

This assumes that when you have a pattern like: +2, +4, having {1,2,3,4,5} is still a valid set because {1,3,5} follow the pattern.