consider the partition {1, ..., 6}, {7, ..., 12}, ..., {43, ..., 48}, {49}. at most 5 elements can be chosen from each of the first 8 parts, and 1 from the last part, for a total of at most $8\cdot 5 +1 = 41$ elements. the set which is the union of {1, ..., 5}, {7, ..., 11}, ..., {43, ..., 47}, and {49} shows that 41 can be achieved. number the first 8 parts of the partition listed above 1 through 8. the argument above shows that a maximal subset is gotten by including 49 and removing exactly one element from each of the parts 1 through 8. for each $i$, $i = 1, ..., 8$, let $a_i$ denote the number of the element of the $i$-th part, counting from the left of that part, which is removed; so, for example, if we remove 11 from part 2, we denote that by $a_2 = 5$, because 11 is the 5th number counting from 7. note that, because we include 49, $a_8 \geq 2$. in addition, note that we must have $a_i \geq a_{i+1}$ for every $i = 1, ..., 7$, or else we're left with a run of at least 6 consecutive integers. conversely, if we have $a_8 \geq 2$ and $a_i \geq a_{i+1}$ for every $i = 1, ..., 7$, the resulting set is a valid set. so our problem becomes to find the number of non-decreasing sequences $a_8 \leq a_7 \leq a_6 \leq ... \leq a_1$ with $2 \leq a_i \leq 6$ for every $i$. if $a_8 = k$ ($2 \leq k \leq 6$), then choosing the remaining 7 $a_i$ is the same as putting 7 objects in $6-k+1$ boxes marked $k, ..., 6$. this can be done in $\binom{7+6-k+1-1}{7} = \binom{13-k}{7}$ ways. the answer is then $\sum_{k=2}^{6} \binom{13-k}{7}$ edit: ...which actually is the same as $\binom{12}{8}$. we could have just gotten that by covering all the $k$'s in one case... by placing 8 objects in 5 boxes marked $2, ..., 6$. anyway, another case of the identity $\binom{n}{n}+\binom{n+1}{n}+...+\binom{m}{n} = \binom{m+1}{n+1}$.