Intereting Posts

Mapping between subgroups by an isomorphism.
Prove: $\int_0^1 \frac{\ln x }{x-1} d x=\sum_1^\infty \frac{1}{n^2}$
Asymptotes of $\Gamma(\frac{1}{2} +ix)$ when $\vert x \vert \to \infty$
Function in $C^{\infty} (\mathbb{R})$ with geometric sequence
Showing there is no ring whose additive group is isomorphic to $\mathbb{Q}/\mathbb{Z}$
How to prove $\int_1^\infty\frac{K(x)^2}x dx=\frac{i\,\pi^3}8$?
Prove that $A^TD-C^TB=I$
If $f(x)\in\Bbb Z_p $ is irreducible with $p$ prime and $\deg f(x)=n$ then $\Bbb Z_p /〈f(x)〉$ is a field with $p^n$ elements.
Integral $\int_0^{\pi/2} \theta^2 \log ^4(2\cos \theta) d\theta =\frac{33\pi^7}{4480}+\frac{3\pi}{2}\zeta^2(3)$
About Math notation: the set of the $n^{th}$ natural numbers
Is there a way of working with the Zariski topology in terms of convergence/limits?
Clarification on how to prove polynomial representations exist for infinite series
Best measure theoretic probability theory book?
polynomial approximation in Hardy space $H^\infty$
Let $f$ be entire and suppose that $\text{Im} f\ge0$. Show that $\text{Im} f$ is constant.

Let $P$ and $Q$ be two finite multisets of the same cardinality $n$.

Question: How many bijections are there from $P$ to $Q$?

I will define a *bijection* between $P$ and $Q$ as a multiset $\Phi \subseteq P \times Q$ satisfying the properties:

- Express $1 + \frac {1}{2} \binom{n}{1} + \frac {1}{3} \binom{n}{2} + \dotsb + \frac{1}{n + 1}\binom{n}{n}$ in a simplifed form
- Distributing $k$ objects in $n$ containers - Probability distribution for Combinatorial problems
- How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?
- Closed Form Expression of sum with binomial coefficient
- How many different $4$ letter words can you create from the characters of “parallelogram”?
- Number of Unique Sequences with Circular Shifts

- $\Phi=\{(p_1,q_1),(p_2,q_2),\ldots,(p_n,q_n)\}$,
- $P=\{p_1,p_2,\ldots,p_n\}$, and
- $Q=\{q_1,q_2,\ldots,q_n\}$.

For example, suppose $P=\{1,1,1,3\}$ and $Q=\{1,1,2,2\}$. Then there are two bijections between these multisets: $\{(1,1),(1,1),(1,2),(3,2)\}$ and $\{(1,1),(3,1),(1,2),(1,2)\}$.

There seems to be two natural ways we could attempt to do this:

- Use $S_{|P|}$ to act on $P$.
- Use $S_{|P|} \times S_{|Q|}$ to act on $P \times Q$.

In either case, the action induces an action on the set of bijections from $P$ to $Q$. However, it seems difficult to find the size of the stabiliser subgroup (in either case).

[*Motivation*: A formula for the number of bijections would help me with a program I’m writing, in which I’m summing over all bijections from $P$ to $Q$ (which happen to be number partitions). I hope to use symmetry breaking to reduce the redundant iterations.]

*Addendum* (motivated by hardmath’s comment, and so I can add the [graph-theory] tag):

A rephrasing of this question is:

Question: What is the number of bipartite multigraphs, with vertex bipartition $V_1 \cup V_2$, whose vertices have prescribed degrees?

For the above question to be non-zero, we require $\sum_{v \in V_1} \mathrm{deg}(v)=\sum_{v \in V_2} \mathrm{deg}(v)$, where $\mathrm{deg}(v)$ is the degree of vertex $v$,counting multi-edges with their multiplicity.

In the above example, $V_1=\{1,3\}$, with degrees $3$ and $1$, respectively, and $V_2=\{1′,2’\}$, with degrees $2$ and $2$, respectively. The two bipartite multigraphs have edge multisets $\{\{1,1’\},\{1,1’\},\{1,2’\},\{3,2’\}\}$ and $\{\{1,1’\},\{3,1’\},\{1,2’\},\{1,2’\}\}$.

- Is First Order Logic (FOL) the only fundamental logic?
- Number of ways to distribute indistinguishable balls into distinguishable boxes of given size
- Coloring $\mathbb R^n$ with $n$ colors always gives us a color with all distances.
- How to use stars and bars?
- Probability that no two consecutive heads occur?
- In the card game Set, what's the probability of a Set existing in n cards?
- How many positive integers $ n$ with $1 \le n \le 2500$ are prime relative to $3$ and $5$?
- Combinatorial interpretation of a sum identity: $\sum_{k=1}^n(k-1)(n-k)=\binom{n}{3}$
- How many integer solutions to a linear combination, with restrictions?
- $16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

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:

Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes

but the ratio of upper to lower bounds is some positive power of $n^{m+k}$ in terms of our notation.

- The kernel of $R \to A \otimes_R B$ is nil
- Prove that the following series is convergent for all $z\in\Bbb C$ such that $|z|<1$.
- Right continuous version of a martingale
- Newton's method for square roots 'jumps' through the continued fraction convergents
- Difficulty in evaluating a limit: $\lim_{x \to \infty} \frac{e^x}{\left(1+\frac{1}{x}\right)^{x^2}}$
- Evaluating $\sum\limits_{n=0}^{20} \frac{(-1)^{n}2^{n+1}}{3^{n}},$
- Brainteaser: Player A has £1, Player B £99. They flip a coin. The loser pays the other £1. Expected number of games before one is bankrupt?
- Let $f:R\rightarrow S$ be a ring homomorphism. Prove or disprove: if $f$ is onto and $R$ is an integral domain, then $S$ is an integral domain
- What (and how many) pieces does the Banach-Tarski Paradox break a sphere into?
- Relationship between l'Hospital's rule and the least upper bound property.
- What are the last two digits of $77^{17}$?
- Let $G$ be a group, where $(ab)^3=a^3b^3$ and $(ab)^5=a^5b^5$. Prove that $G $ is an abelian group.
- Prove that a set of connectives is inadequate
- Calculate summation of square roots
- For $E (X – EX)^2$ to exist, do we need $EX$ to exist and be finite?