1
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .