Suppose $S$ is a infinite set and $R\subset S$ is also infinite. Now, we want to find the number of multisets $(M,\nu)$, with $M\subset S, |(M,\nu)|=n$, and having an additional property that for every $x\in M$ with $2\nmid \nu(x)$, we must have, $x\in R$. How can we find the number of all such multisets $(M,\nu)$ of cardinality $n$. I have no clue how to tackle this. I am looking for a generating function for $f(n)$, where $f(n)$ denotes the required number for every $n\in \mathbb{N}$.

Suppose, if we omit the additional property, that is, if we try to find all multisets $(M,\nu)$ with cardinality $n$, then it is simply the coefficient of $u^n$ in

$$\prod_{u\in S} (1+u+u^2+\ldots)=\prod_{u\in S}(1-u)^{-1}$$ I don't understand how to get my result, by using the above, or otherwise.

Note: A multiset is a pair $(M,\nu)$, where $M$ is a set, and $\nu:M\to \mathbb{N}$. By cardinality of $(M,\nu)$, we mean $\sum_{x\in M}\nu(x)$.

Thank you for any kind of help!


1 Answer 1


In other words, every element $x\in M\cap (S\setminus R)$ has even multiplicity $\nu(x)$, while the multiplicity of elements of $M\cap R$ is unrestricted.

Then, the generating functions is \begin{split} \sum_{n\geq 0} f(n) x^n &= \prod_{u\in S\setminus R} (1+x^2+x^4+\dots)\prod_{u\in R} (1+x+x^2+\dots) \\ &= \prod_{u\in S\setminus R} (1-x^2)^{-1} \prod_{u\in R} (1-x)^{-1} \\ & = (1-x^2)^{-|S\setminus R|}(1-x)^{-|R|} \\ &= (1+x)^{-|S\setminus R|}(1-x)^{-|S|}. \end{split}

This, however, makes sense only for finine sets $S$ and $R$, since if they are infinite, so is $f(n)$.


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.