Number ways of arranging dots and lines with restriction

Question

I have this problem where I need to calculate the following:

For x dots and y lines, how many arrangements are possible such that no more than n dots are together?

Can anyone help me out?

Answer 1

First put all the lines, like this | | | | |

Then, out of y lines,$y+1$ gaps will be created (including end spaces). Maximum number of dots in each gap is $n$. Now, let the number of dots in $i$th gap is $x_i$. Required number of ways is the number of non-negative solutions of the equation $$x_1+x_2+...+x_{y+1}=x$$ Where $x_i\leq n \forall i$, now you can easily do it by finding the coefficient of $m^x$ in the expansion of $(1+m+m^2+...+m^n)^{y+1}$.

Hope it is helpful:)