How many seven-element subsets of $\{1, 2, 3, \ldots, 56\}$ do not contain three consecutive numbers? 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?

 A: 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$$
A: Let $f(k,m)$ be the number of $k$-element subsets of $\{1,\dots,m\}$ not containing three consecutive integers, so that the OP is asking for the value of $f(7,56)$.
Given any subset $S$ counted by $f(k,m)$, let $z$ be its largest element. If $z-1\notin S$, then $S=T\cup\{z\}$ where $T$ is counted by $f(k-1,z-2)$. If $z-1\in S$, then $z>1$ and $z-2\notin S$ by assumption, and so $S=U\cup\{z-1,z\}$ where $U$ is counted by $f(k-2,z-3)$. Therefore
$$
f(k,z) = f(k-1,-1) + \sum_{2\le z\le m} \big( f(k-1,z-2) + f(k-2,z-3) \big).
$$
Together with trivial values such as $f(0,m)=1$ for all $m$, this provides a recursive way to calculate $f$ (and, if one wished, a generating function).
Running the recursion yields $f(7,56) = 217{,}337{,}400$, verifying Daniel Mathias's answer.
A: I found a very satisfying generalization of this problem.
Define $f(n,r,s)=$ "the number of $r$ element subsets of $\{1,...,n\}$ that do not contain a streak of $s$ consecutive numbers". Then $$f(n,r,s)= {\binom{n-r+1}{r}}_s \tag{1}$$ where, for $p>1$,  $${\binom{m}{k}}_p \text{ for } \ 0\le k\le m(p-1) \text{ and } m\ge0$$ are the coefficients of the "Pascal $p$-Triangle". In other words, they are the coefficients of the expansion of $(1+x+x^2+...+x^{p-1})^m\ .\ $ (In this notation then, the regular binomial coefficient is $\binom{m}{k} = {\binom{m}{k}}_2$ and the regular Pascal's Triangle is the "Pascal $2$-Triangle".) In a Pascal $p$-Triangle, the $m=1$ row consists of $p$ ones. In subsequent rows, each element is the sum of the $p$ entries centered above it. In other words, the coefficients in a Pascal $p$-Triangle obey this recursion, $$ \binom{m}{k}_p = \binom{m-1}{k}_p + \binom{m-1}{k-1}_p + \dots + \binom{m-1}{k-p+1}_p \tag{2}$$
To show $(1)$, first, by an argument similar to the one in Greg Martin's answer, show that $f$, by its definition, follows this recursion, $$ f(n,r,s)=f(n-1,r,s)+f(n-2,r-1,s)+\dots+f(n-s,r-s+1,s) \tag{3}$$ Then, use $(2)$ to show that $f$ as defined in $(1)$ meets $(3)$. Verifying the previous answers, running the recursion yields $f(56,7,3)= 217337400$.
