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 ?
Answer:
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.