$\binom{n+k-1}{k}$
Hello. The above formula refers to the number of k-element multisets whose elements all belong to [n]. I am unsure of the proof, particularly the proof involving bijections. Could someone provide the proof?
[Math] The number of k-element multisets whose elements all belong to [n]
combinatoricselementary-number-theoryproof-writing
Related Solutions
Here's a sketch of how one can uniquely traverse ("search") the bijections between two multisets of equal cardinality, say $P$ and $Q$ both of size $n$.
Consider the partitions of $n$ represented by both multisets. In the given example, $P$ represents $1+3 = 4$, and $Q$ represents $2+2 = 4$.
Now any equal summands can be swapped, so with $Q$ of the example, transposing the roles of $q_1 = 1$ and $q_2 = 2$ gives distinct bijections unless a bijection treats them identically. This initially sounds like something that would be hard to get a handle on, but as we shall see it can be managed as an inner step of the search algorithm.
Let's focus on counting the bipartite graphs with multiple edges on $U \cup V$ where $U$ the underlying set of $P$ and $V$ the underlying set of $Q$ are assumed disjoint, and where vertex degrees counting multiplicity of edges agree as to the multiplicity of items in $P$ and $Q$ resp.
That is, let $a_1 \leq a_2 ... \leq a_m$ be the summands of $n$ in the partition represented by $P$, and let $b_1 \leq b_2 ... \leq b_k$ be the respective summands for $Q$. We ask for the number $T((a_1,a_2,...,a_m),(b_1,b_2,...,b_k))$ of bipartite graphs with multiple edges that realize the prescribed vertex degrees on $U \cup V$.
To efficiently compute $T(A,B)$ and construct these distinct graphs, it will be helpful to refer to yet another representation, namely the $m \times k$ biadjacency matrix of the graph, whose rows correspond to the elements of $U$ and columns to the elements of $V$, ordered consistently as to their respective summands. Note that unlike the 0/1 entries of an adjacency matrix of a simple graph, here our entries are nonnegative entries such that the rows sums $a_i$ and column sums $b_j$ are as prescribed.
The idea is to decide the largest row sum's distribution $a_m$ into row $m$, consistent with the available columns sums. Having done so the column sums are adjusted (and row sum $a_m$ is dropped), and one then proceeds with recursive computation of $T(A',B')$. Note that $T(A,B) = T(B,A)$ is symmetric, and that at each stage it is preferable to work with whichever tuple has shortest length. In the recursion, we will drop one entry of A, but we might drop more than one entry of B due to decrementing to zero some column sums.
When we eventually reach a single row sum, that distribution is forced as the remaining column sums are but single entries that must by construction agree as to the row sum required. At this point the biadjacency matrix has been populated fully, and it remains only to see if some rows or columns corresponding to equal summands in the original partitions may be permuted in a way that gives distinct solutions.
Let's illustrate with the given example, which asks us to find ways to populate a $2 \times 2$ biadjacency matrix such that the row sums are $1,3$ and the columns sums are $2,2$. It turns out this can be done with nonnegative integers in only one way:
$$\begin{pmatrix} 1 & 0 \\ 1 & 2 \end{pmatrix} $$
So here there is only one bipartite graph (with multiple edges) having the required vertex degrees, but since the two columns having equal sums are distinct, these can therefore be swapped to give two multiset bijections.
This recursive idea was applied to counting simple bipartite graphs by A. Guénoche (1990):
Counting and selecting at random bipartite graphs with fixed degrees
Addendum:
The approach sketched above simplifies. Instead of slavishly constructing exactly the nonisomorphic bipartite graphs (with multiple edges) having specified vertex degrees, it is simpler and more natural just to choose rows in the manner outlined without worrying about their identity (or the identity/nonidentity of columns having equal column sums). This avoids a need for post-facto processing with row and column permutations.
I kept having a nagging suspicion that this was the case even as I wrote it up, but the epiphany came only after posting. The simpler approach finds the nonisomorphic bipartite graphs with labelled vertices, and so identifies the multiset bijections that are wanted.
Moreover this clears the way to recognize that what we're counting are commonly called (at least in statistics) contingency tables, i.e. rectangular arrays of nonnegative integers whose row sums and column sums are specified in a compatible way, $\sum a_i = n = \sum b_j$. Counting them, given m row and k column sums, seems to be a difficult problem if high "degrees of freedom" are involved.
Barvinok (2008) gives bounds for the number of contingency tables and survey the literature:
but the ratio of upper to lower bounds is some positive power of $n^{m+k}$ in terms of our notation.
We denote with $a[n], n\geq 1$ the number of special sequences and with $b[n], n\geq 1$ the number of special sequences where each element contains $n$ as greatest element. We observe $a[n]$ contains all special sequences of $a[n-1]$ together with all special sequences $b[n], (n>1)$.
We have \begin{align*} &a[1]=b[1]=\left|\{(1)\}\right|=1\\ &a[n]=a[n-1]+b[n ] \qquad\qquad n> 1 \end{align*}
In order to find $b[n]$ we need to analyse the prime factor decomposition of $n$. We create a small knowledge base of numbers which we need to factorise $K=1,\ldots,22$.
Let $p,q$ be primes. We obtain \begin{align*} b[p]&=\left|\{(p),(1,p)\}\right|=2\\ b[p^2]&=\left|\{(p^2),(1,p^2),(p,p^2),(1,p,p^2)\}\right|=4\\ b[p^3]&=\left|\{(p^3),(1,p^3),(p,p^3),(p^2,p^3),(1,p,p^3),(1,p^2,p^3),(1,p,p^2,p^3)\}\right|=8\\ b[p^4]&=2^4=16\\ b[pq]&=\left|\{(pq),(1,pq),(p,pq),(q,pq),(1,p,pq),(1,q,pq)\}\right|=6\\ b[p^2q]&=\left|\{(p^2q),(1,p^2q),(p,p^2q),(q,p^2q),(p^2,p^2q),(pq,p^2q),\right.\\ &\qquad(1,p,p^2q),(1,q,p^2q),(1,p^2,p^2q),(1,pq,p^2q),\\ &\qquad(p,p^2,p^2q),(p,pq,p^2q),(q,pq,p^2q),\\ &\qquad\left.(1,p,p^2,p^2q),(1,p,pq,p^2q),(1,q,pq,p^2q))\}\right|=16\\ \end{align*}
Now it's time to harvest. We obtain \begin{align*} \color{blue}{a[15]}&=a[14]+b[13]=a[13]+b[12]+b[13]\\ &=a[1]+\sum_{j=2}^{13}b[j]\\ &=1+\sum_{j\in\{2,3,5,7,11,13\}}b[j]+\sum_{j\in\{4,9\}}b[j]+\sum_{j\in\{6,10,14,15\}}b[j]+b[8]+b[12]\\ &=1+6b[p]+2b[p^2]+4b[pq]+b[p^3]+b[p^2q]\\ &=1+12+8+24+8+16\\ &\,\,\color{blue}{=69}\\ \color{blue}{a[19]}&=a[15]+b[16]+b[17]+b[18]+b[19]\\ &=69+b[2^4]+b[17]+b[3^2\cdot 2]+b[19]\\ &=69+b[p^4]+2b[p]+b[p^2q]\\ &=69+16+4+16\\ &\,\,\color{blue}{=105}\\ \color{blue}{a[22]}&=a[19]+b[20]+b[21]+b[22]\\ &=105+b[2^2\cdot5]+b[3\cdot7]+b[2\cdot11]\\ &=105+b[p^2q]+2b[pq]\\ &=105+16+12\\ &\,\,\color{blue}{=133}\\ \end{align*}
Note: Interestingly, the sequence $\left(a[n]\right)_{n\geq 1}=(1,3,5,9,11,17,19,27,31,\ldots)$ doesn't seem to be archived in OEIS, but the sequence $\left(b[n]\right)_{n\geq1}=(1,2,2,4,2,6,2,8,4,6,2,16,2,\ldots)$ is archived in OEIS as A067824.
Best Answer
For any $k$-element multiset of $[n]$,
Let $a_i=\#\text{of occurrences of}~i~\text{in the multiset}$
We have then $a_1+a_2+\dots+a_n = k$ and each $a_i$ is a non-negative integer.
The set of solutions to the above equation are in direct bijection with the $k$-element multisets of $[n]$ using an obvious bijection: $(a_1,a_2,\dots,a_n) \leftrightarrow \{a_1\cdot 1,a_2\cdot 2,\dots,a_n\cdot n\}$ using multiplicity notation for multisets.
Now, the non-negative integer solutions to $a_1+a_2+\dots+a_n=k$ can be seen via "stars and bars", relating such a solution as a sequence of $n-1$ bars and $k$ stars. The bijection being
So, the question has been reduced to how many sequences of length $n-1+k$ have exactly $n-1$ $B$'s and $k$ $S$'s. The answer being $\binom{n-1+k}{n-1}=\binom{n-1+k}{k}$