$\binom{n}{r}$ where $r$ can only be chosen in groups of $k$

I just started my learning in combinatorics, and I know that number of ways to choose $r$ items from $n$ items without order is given by $\binom{n}{r}= \frac{n!}{r!(n-r)!}$. However, I couldn't figure out the number of ways to choose $r$ items from $n$ items, where the $r$ chosen items are restricted such that they can be chosen only in groups less than or equal to $k$ $(k<=r)$ each time.

Perhaps my above description is unclear, so let me try to present it in a more concrete way: on a cartesian plane, in each move you can either go $(+1,0)$ or $(0,+1)$ (move in x or y direction for 1 positive unit), how many valid shortest paths (only walking $n$ steps in total) are there from $(0,0)$ to $(r,n-r)$, if you can only walk in the $x$ direction for at most $k$ consecutive times before changing direction?

The number of valid paths of length $n$ consisting of $r$ horizontal $(1,0)$-steps and $n-r$ vertical $(0,1)$-steps with at most $k$ consecutive horizontal steps is \begin{align*} \color{blue}{\sum_{q=0}^{\left\lfloor\frac{r}{k+1}\right\rfloor}\binom{n-(k+1)q}{r-(k+1)q}\binom{n-r+1}{q}(-1)^q}\tag{1} \end{align*} where the symbol $\left\lfloor\cdot\right\rfloor$ denotes the floor function.

Example: Let's look at an example $n=6, r=4, k=2$.

We have a total of $\binom{n}{r}=\binom{6}{4}=15$ paths of length $6$ with four horizontal steps. The restriction $k=2$ gives according to (1) \begin{align*} \sum_{q=0}^{1}\binom{6-3q}{4-3q}\binom{3}{q}(-1)^q&=\binom{6}{4}\binom{3}{0}-\binom{3}{1}\binom{3}{1}\\ &=15-9\\ &\,\,\color{blue}{=6} \end{align*} valid paths. The six valid paths are marked blue in the list below where $a$ encodes a horizontal $(1,0)$-step and $b$ a vertical $(0,1)$-step. \begin{align*} \begin{array}{ccc} \mathrm{aaaabb}\qquad&\qquad \mathrm{abaaab}\qquad&\qquad \mathrm{baaaab}\\ \mathrm{aaabab}\qquad&\qquad \color{blue}{\mathrm{abaaba}}\qquad&\qquad \mathrm{baaaba}\\ \mathrm{aaabba}\qquad&\qquad \color{blue}{\mathrm{ababaa}}\qquad&\qquad \color{blue}{\mathrm{baabaa}}\\ \color{blue}{\mathrm{aabaab}}\qquad&\qquad \mathrm{abbaaa}\qquad&\qquad \mathrm{babaaa}\\ \color{blue}{\mathrm{aababa}}\qquad&&\qquad \mathrm{bbaaaa}\\ \color{blue}{\mathrm{aabbaa}}\qquad \end{array} \end{align*}

The following proof might be somewhat beyond OPs current level. Its just to give an impression how (1) can be shown.

Proof: We use generating functions in order to derive (1) and start with generating functions of binary Smirnov words. These are words with no equal consecutive characters. In terms of paths these are paths with no equal consecutive steps. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.) Encoding $(1,0)$-steps with $x$ and $(0,1)$-steps with $y$ the generating function of Smirnov words is \begin{align*} \left(1-\frac{x}{1+x}-\frac{y}{1+y}\right)^{-1}\tag{2} \end{align*} The coefficient of $x^ry^{n-r}$ in the generating function above gives all words of length $r+(n-r)=n$ with no runs of $(1,0)$-steps or $(0, 1)$-steps with length $>1$. This is a convenient starter but we need some adaptations. At first we note that the runs of $(0,1)$-steps are not restricted. We therefore substitute occurrences of $(0,1)$-steps with one or more $(0,1)$-steps. \begin{align*} y\quad\to\quad y+y^2+y^3+\cdots=\frac{y}{1-y} \end{align*} Each of the wanted paths has at most $k$ horizontal $(1,0)$-steps. We respect this by substituting \begin{align*} x\quad\to\quad x+x^ 2+\cdots+x^k=\frac{x\left(1-x^k\right)}{1-x} \end{align*}

We obtain using the generating function (2) and the substitutions above the wanted generating function \begin{align*} \color{blue}{A_k(x,y)}&=\left(1-\frac{\frac{x\left(1-x^k\right)}{1-x}}{1+\frac{x\left(1-x^k\right)}{1-x}}-\frac{\frac{y}{1-y}}{1+\frac{y}{1-y}}\right)^{-1}\\ &=\left(1-\frac{x\left(1-x^k\right)}{1-x^{k+1}}-y\right)^{-1}\\ &\,\,\color{blue}{=\frac{1}{1-y\,\frac{1-x^{k+1}}{1-x}}\,\frac{1-x^{k+1}}{1-x}}\tag{3} \end{align*}

Since we are looking for paths with length $n$ with $r$ $(1,0)$-steps, and $n-r$ $(0,1)$-steps, we are looking for the coefficient of $x^{r}y^{n-r}$ in $A_k(x,y)$.

We obtain denoting with $[x^r]$ the coefficient of $x^r$ in a series the number of valid paths as \begin{align*} \color{blue}{[x^{r}y^{n-r}]A_k(x,y)}\tag{4} \end{align*}

We start calculating (4) by expanding (3) in powers of $y$. We obtain

\begin{align*} \color{blue}{[x^{r}}&\color{blue}{y^{n-r}]A_k(x,y)}=[x^{r}y^{n-r}]\frac{1}{1-y\,\frac{1-x^{k+1}}{1-x}}\,\frac{1-x^{k+1}}{1-x}\\ &=[x^{r}y^{n-r}]\sum_{q=0}^\infty\left(\frac{1-x^{k+1}}{1-x}\right)^{q+1}y^q\tag{5.1}\\ &=[x^r]\left(\frac{1-x^{k+1}}{1-x}\right)^{n-r+1}\tag{5.2}\\ &=[x^r]\sum_{q=0}^{\infty}\binom{-(n-r+1)}{q}(-x)^q\left(1-x^{k+1}\right)^{n-r+1}\tag{5.3}\\ &=[x^r]\sum_{q=0}^{\infty}\binom{n-r+q}{q}x^q\left(1-x^{k+1}\right)^{n-r+1}\tag{5.4}\\ &=\sum_{q=0}^r\binom{n-r+q}{q}[x^{r-q}]\left(1-x^{k+1}\right)^{n-r+1}\tag{5.5}\\ &=\sum_{q=0}^r\binom{n-q}{r-q}[x^{q}]\left(1-x^{k+1}\right)^{n-r+1}\tag{5.6}\\ &=\sum_{q=0}^{\left\lfloor\frac{r}{k+1}\right\rfloor}\binom{n-(k+1)q}{r-(k+1)q}[x^{(k+1)q}]\left(1-x^{k+1}\right)^{n-r+1}\tag{5.7}\\ &\,\,\color{blue}{=\sum_{q=0}^{\left\lfloor\frac{r}{k+1}\right\rfloor}\binom{n-(k+1)q}{r-(k+1)q}\binom{n-r+1}{q}(-1)^q}\\ \end{align*} and the claim (1) follows.

Comment:

• In (5.1) we apply the geometric series expansion.

• In (5.2) we select the coefficient of $y^{n-r}$.

• In (5.3) we apply the binomial series expansion of $(1-x)^{-(n-r+1)}$.

• In (5.4) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (5.5) we apply the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$. We also set the upper limit of the series to $r$ since other indices do not contribute.

• In (5.6) we note that in the binomial expansion of $\left(1-x^{k+1}\right)^{n-r+1}$ the powers of $x$ are multiples of $k+1$. We respect this by substituting $q\to(k+1)q$ in (5.7) and select finally the coefficient of $x^{(k+1)q}$.