# What is the generating function for the number of Multisets

What is the generating function for the number of Multisets chosen from an $\ n-element \$ set so that each element appears at least $\ j \$ times and less than $\ m \$ times ?

The generating function is

$\binom{n}{0} x^0+\binom{n}{1} x +\binom{n}{2} x^2+........+ \binom{n}{j} x^j+......+ =\frac{1}{(1-x)^n} \$

But how can I include the given constraints?

I am confused about doing the problem.

Help me out this combinatorics problem.

Let the $n$ element set be $\{1,2,\dotsc,n\}$. Let $x_i$ be the number of times the element $i$ appears in a multiset of size $k$. Without constraints the number of multisets of size $k$ from an $n$ element set denoted $\left(\!\!{n\choose k}\!\!\right)$ is number of solutions to $$x_1+x_2+\dotsb+x_n=k \quad (x_i\geq0)\tag{1}.$$ In this case we note that $$(1-x)^{-n}=(1+x+x^2+\dotsb)^n=\sum_{k=0}^\infty\left(\sum_{\sum_{i}^nx_i=k\, (x_i\geq0)} x^{x_1+\dotsb+x_n}\right)=\sum_{k=0}^\infty\left(\!\!{n\choose k}\!\!\right)x^k$$ The number of multisets of size $k$ from an $n$ element set with constraints that each element appears at least $j$ times and less than $m$ times (denoted $a(n,k)$, is the number of solutions to $$x_1+x_2+\dotsb+x_n=k \quad (j\leq x_i\leq m-1)$$ The generating function corresponding to $a(n,k)$ using similar reasoning as before is $$(x^j+\dotsb+x^{m-1})^n=\sum_{k=0}^\infty a(n,k) x^k\tag{2}$$ You may express the LHS using the formula for a finite geometric series.