Distribute n integers into m (non distinct) bins without creating consecutive triples I have $[n] := \{0, 1, \cdots, n-1\}$ integers and $m$ bins (we don't distinguish bins). How many possible ways to distribute $m$ integers from $[n]$ into $m$ bins are there such that the distributions have no consecutive triple?
In other words, how many subsets of size $m$ are there in $[n]$ which don't contain 3 consecutive integers ($6, 4, 5$ is a consecutive triple but $1, 2, 4$ isn't)?
Some subsets for $m=7$ and $n = 20$:


*

*{0, 1, 3, 4, 6, 7, 9} has no consecutive triple  

*{1, 3, 6, 18, 19, 10, 2} has a consecutive triple (1, 2, 3)

*{10, 15, 18, 19, 0, 5, 8} has no consecutive triple

 A: Let $A(n,m)$ be the number of ways to choose $m$ integers from $[n]$ without a consecutive triple. Clearly $A(n,m) = \binom{n}{m}$ when $m < 3$, and $A(n,m) = 0$ when $m > \left\lceil\frac23 n\right\rceil$.
For larger $m$ it might be easier to invert the question. How many subsets $S$ of size $m$ are there which do have 3 consecutive integers?
Suppose that the lexicographically first consecutive triple is $k,k+1,k+2$.
Case $k = 0$: any selection of $m-3$ elements from the remaining $n-3$ works, so we have $\binom{n-3}{m-3}$ subsets.
Case $0 < k \le n - 3$: clearly $k-1$ is not in $S$. Suppose that $i$ elements from $[k-1]$ are in $S$: they don't contain a triple, so there are $A(k-1,i)$ ways to choose them. The remaining $m-i-3$ elements of $S$ are chosen freely from the remaining $n-k-3$ elements of $[n]$.
Putting those together, $$\binom{n}{m} - A(n,m) = \binom{n-3}{m-3} + \sum_{k=1}^{n-3} \sum_{i=0}^{\left\lceil\frac{2(k-1)}{3}\right\rceil} A(k-1,i) \binom{n-k-3}{m-i-3}$$
This allows closed forms for small $m$. E.g. $$\begin{eqnarray}
A(n,3) & = & \binom{n}{4} - \binom{n-3}{1} - \sum_{k=1}^{n-3} A(k-1,0) \binom{n-k-3}{0} \\
& = & \binom{n}{3} - n + 2 \\
A(n,4) & = & \binom{n}{4} - \binom{n-3}{1} - \sum_{k=1}^{n-3} A(k-1,0) \binom{n-k-3}{1} + A(k-1,1) \binom{n-k-3}{0}\\
& = & \binom{n}{4} - (n-3) - \sum_{k=1}^{n-3} n-4\\
& = & \binom{n}{4} - (n-3)^2
\end{eqnarray}$$
etc. I wouldn't be especially optimistic about finding a closed form for general $m$, but I haven't really tried.
