How many seven-element subsets of $\{1, 2, 3, \ldots, 56\}$ do not contain three consecutive numbers

combinationscombinatorics

Since a combination is the same as a permutation but the order doesn't matter I have a question, if $7$ numbers are selected from $\{1, 2, 3, \ldots, 56\}$, the number of combinations is about $230$ million. If I remove all the possible seven-element subsets with $3$ consecutive numbers such as $1, 2, 3$, then $2, 3, 4$, and so on until $54, 55, 56$, how many combinations will be left? I did it manually in a txt file: took me a full day. Just checking if I have the right amount, thanks!

How many seven-element subsets of $\{1, 2, 3, \ldots, 56\}$ do not contain three consecutive numbers?

Best Answer

Having difficulty with Inclusion-Exclusion for this problem, I instead found an approach using the distribution of non-distinct objects.

Consider these four cases:

  • Subsets containing three pairs of consecutive numbers, such as $\{1,2,4,5,7,8,10\}$
  • Subsets containing two pairs of consecutive numbers, such as $\{1,2,4,5,7,9,11\}$
  • Subsets containing one pair of consecutive numbers, such as $\{1,2,4,6,8,10,12\}$
  • Subsets containing no consecutive numbers, such as $\{1,3,5,7,9,11,13\}$

In the first case our seven numbers are separated into four groups, and these groups separate the remaining 49 numbers into five groups, three of which will have at least one number: $$\small[x_1\text{ numbers}][g_1][x_2+1\text{ numbers}][g_2][x_3+1\text{ numbers}][g_3][x_4+1\text{ numbers}][g_4][x_5\text{ numbers}]$$ Here $x_1+x_2+x_3+x_4+x_5=46; x_i\ge0$ and this gives $\binom{50}{4}$ ways to choose the sizes of the five groups of numbers not in our subset. There are also $\binom43$ ways to chose which groups from our subset contain two consecutive numbers. This gives us a total of $\binom{50}{4}\binom43$ ways to choose a seven-element subset containing three pairs of consecutive numbers.

Similarly, in the second case we find $\binom{50}{5}\binom52$ ways to choose a seven-element subset containing two pairs of consecutive numbers.

In the third and fourth cases, we find $\binom{50}{6}\binom61$ and $\binom{50}{7}\binom70$ ways to choose our subset.

The total number of ways to choose a seven-element subset no containing three consecutive numbers is:$$\binom{50}{4}\binom43+\binom{50}{5}\binom52+\binom{50}{6}\binom61+\binom{50}{7}\binom70\\[5ex]203300\times 4+2118760\times 10+15890700\times 6+99884400\\[2ex]=217,337,400$$