Number of multisets with at most twice the same element

combinationscombinatoricsmultisets

I know that the number of multisets of cardinality $K$ with elements taken from the set $\{1,…,N\}$ is $\binom{N+K-1}{K}$.

I only want to consider the multisets such that an element appears at most twice. How do I count them?

Is there a general formula for multisets such that an element appears at most $M$ times?

Best Answer

The generating function for number $f(K,N,M)$ of multisets of cardinality $K$ from $\{1,\ldots,N\}$ with each element appearing at most $M$ times is

$$ g_{N,M}(z) = \sum_{K=0}^\infty f(K,N,M) z^K = (1+z+\ldots+z^M)^N = \left(\frac{1-z^{M+1}}{1-z}\right)^N$$

Now $$(1-z^{M+1})^N = \sum_{n=0}^N (-1)^n {N \choose n} z^{(M+1)n}$$ while $$(1-z)^{-N} = \sum_{k=0}^\infty {N +k-1 \choose N-1} z^k$$ so we get $$ f(K,N,M) = \sum_{n=0}^{\min(N,\lfloor K/(M+1) \rfloor)} (-1)^n {N \choose n} {N+K-(M+1)n-1 \choose N-1}$$