I see from Wikipedia that Binomial coefficient finds the number of k-combinations from a given set of n elements.
In this figure we have 10 3-element subsets of a 5-element set:
In my problem I have a restriction: I can't have more than M consecutive elements in my subsets. For example, in the previous figure if M=2 than I should exclude the 1st row, the 7th one and the last one. I'm interested in the resulting number of rows (in the example, 10-3=7 rows).
How can I count the correct number of rows taking into account this restriction? I imagine something like this:
nRows = C(n,k) - nRowsWithConsecutiveElements(n,k,M)
Starting from $$ \prod\limits_{1 \le \,j\, \le \,n} {\left( {1 + x} \right)} = \left( {1 + x} \right)^n = \sum\limits_{0\, \le \,k\, \le \,n} {\binom{n}{k}x^{\,k} } $$ we know what the binomial coefficient is indicating.
Let's consider then $$ \prod\limits_{1\, \le \,j\, \le \,n} {\left( {1 + x\,y^j } \right)} = \sum\limits_{0\, \le \,k\, \le \,n} {\;\sum\limits_{0\, \le \,\binom{k+1}{2}\, \le \,j\, \le \,k\,n - \binom{k}{2} \, \le \,\binom{n+1}{2}\,} {c_{\,k,\,j} \,x^{\,k} y^{\,j} } } $$ where $c_{\,k,\,j}$ represents the number of partitions of $j$ into exactly $k$ different parts of size at most $n$, i.e. $$ c_{\,k,\,j} = \left| {\left\{ {\left\{ {j_1 ,j_2 , \cdots ,j_k } \right\}:\left\{ \matrix{ 1 \le j_1 < j_2 < \cdots < j_k \le n \hfill \cr j_1 + j_2 + \cdots + j_k = j \hfill \cr} \right.} \right\}} \right| $$
Clearly, putting $y=1$, we will have $$ \sum\limits_{0\, \le \,j\, \le \,\binom{n+1}{2} } {c_{\,k,\,j} } = \binom{n}{k} $$
Now, among the combinations of $k$ integers $j_l$ summing to $j$ we want to count those which include $m$ consecutive integers.
If at least $m$ of the $k$ parts are consecutives, then the inequalities can be reformulated as $$ \eqalign{ & 1 \le j_1 < \cdots < j_l < \underbrace {j_l + 1 < j_l + 2 < \cdots < j_l + m}_m < j_{l + m + 1} < \cdots < j_k \le n \cr & \quad \quad \quad \quad \Downarrow \cr & 1 \le j_1 < \cdots < j_l < j_{l + 1} < \cdots < j_{k - m} \le n - m \cr} $$ while for the sum we have $$ \eqalign{ & j_1 + \cdots + j_l + \underbrace {j_l + 1 + j_l + 2 + \cdots + j_l + m}_m + j_{l + m + 1} + \cdots + j_k = j \cr & \quad \quad \quad \quad \Downarrow \cr & j_1 + \cdots + j_l + j_{l + 1} + \cdots + j_{k - m} = j - \binom{m+1}{2} - m\,j_l \quad \left| \matrix{ \;0\, \le j_l \le n - m \hfill \cr \;\binom{k+1}{2}\, \le j \le kn - \binom{k}{2} \hfill \cr} \right. \cr} $$
So we have the same scheme as above, with the paramaters changed to $$ \left\{ {\matrix{ n \hfill & \to \hfill & {n - m} \hfill \cr k \hfill & \to \hfill & {k - m} \hfill \cr j \hfill & \to \hfill & {j^{\, * } = j - \binom{m+1}{2} - l\,m\quad \left| \matrix{ \;0\, \le l \le n - m \hfill \cr \;0\, \le \,\binom{k+1}{2} \, \le \,j\, \le \,k\,n - \binom{k}{2} \, \le \,\binom{n+1}{2} \, \hfill \cr} \right.} \hfill \cr } } \right. $$ where of course $j^{\, * } $ shall remain non-negative.
In your example for instance, we have $$ \left\{ \matrix{ n = 5\quad k = 3\quad m = 3\quad 6 \le j \le 12 \hfill \cr n - m = 2\quad k - m = 0\quad 0 \le l \le 2 \hfill \cr j^{\, * } = j - \binom{m+1}{2} - l\,m = j - 6 - 3l \hfill \cr} \right. $$ so that among the $\binom{5}{3}=10$ 3-subsets $\{j_1,j_2,j_3\}$ of $\{1,2,\cdots,5\}$, the number of those having three consecutive digits corresponds to the sum of all the $c_{k-m,\, j^{\,*}}$ in
$$ \eqalign{ & \left[ {x^{\,k - m} } \right]\prod\limits_{1\, \le \,j\, \le \,n - m} {\left( {1 + x\,y^{\,j^{\, * } } } \right)} = \left[ {x^{\,0} } \right]\prod\limits_{1\, \le \,j\, \le \,2} {\left( {1 + x\,y^{\,j^{\, * } } } \right)} = \cr & = x^{\,0} \sum\limits_{0\,\, \le \,j\, \le \,0\,} {c_{\,0,\,j^{\, * } } \,y^{\,j^{\, * } } } = 1\,y^{\,0} \quad \to \quad j^{\, * } = 0 \cr} $$ i.e. to the three solutions given by $j=6,9,12$
Finally let's evidentiate the important fact that the product taken into consideration can be written as $$ \eqalign{ & \prod\limits_{1\, \le \,j\, \le \,n} {\left( {1 + x\,y^j } \right)} = \cr & = {1 \over {1 + x}}\prod\limits_{0\, \le \,j\, \le \,n} {\left( {1 + x\,y^j } \right)} = {1 \over {1 + x}}\left( { - x\,;y} \right)_{\,n + 1} = \cr & = \prod\limits_{0\, \le \,j\, \le \,n - 1} {\left( {1 + \left( {xy} \right)\,y^j } \right)} = \left( { - xy\,;y} \right)_{\,n} \cr} $$ where $$ \left( {a\,;q} \right)_{\,n} $$ indicates the q-Pochhammer symbol.
Consequently, the $c_{\, k \, j}$'s can be expressed in term of q-Binomial coefficients.