0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.