He aquí un esbozo de cómo una oportunidad única de recorrer ("búsqueda") el bijections entre dos multisets de igual cardinalidad, decir $P$ $Q$ tanto de tamaño $n$.
Considerar las particiones de $n$ representada por tanto multisets. En el ejemplo dado, $P$ es $1+3 = 4$, e $Q$ es $2+2 = 4$.
Ahora cualquier sumandos iguales puede ser intercambiado, así, con $Q$ a la del ejemplo, la transposición de las funciones de $q_1 = 1$ $q_2 = 2$ da distintas bijections menos un bijection trata de forma idéntica. Esto, en principio, suena como algo que podría ser difícil de controlar, pero como veremos puede ser administrado como un interior paso del algoritmo de búsqueda.
Vamos a centrarnos en el hecho de contar el bipartito gráficos con múltiples aristas en $U \cup V$ donde $U$ el conjunto subyacente de $P$ $V$ el conjunto subyacente de $Q$ se supone que son distintos, y donde vértice grados contando multiplicidad de aristas de acuerdo en cuanto a la multiplicidad de elementos en $P$ $Q$ resp.
Es decir, que $a_1 \leq a_2 ... \leq a_m$ ser los sumandos de $n$ en la partición representado por $P$, y deje $b_1 \leq b_2 ... \leq b_k$ ser la respectiva sumandos para $Q$. Pedimos el número de $T((a_1,a_2,...,a_m),(b_1,b_2,...,b_k))$ de los grafos bipartitos con múltiples aristas que dan cuenta de la prescrita vértice grados en $U \cup V$.
Para calcular de manera eficiente $T(A,B)$ y de construcción de estos distintos gráficos, será de utilidad para hacer referencia a otra representación, es decir, el $m \times k$ biadjacency de la matriz de la gráfica, en cuyas filas corresponden a los elementos de $U$ y las columnas a los elementos de la $V$, ordenado sistemáticamente como a sus respectivos sumandos. Tenga en cuenta que a diferencia de la 0/1 las entradas de una matriz de adyacencia de un simple gráfico, aquí nuestras entradas son no negativos entradas, que las filas sumas $a_i$ y la columna sumas $b_j$ son prescritos.
La idea es decidir el más grande de fila suma de la distribución del $a_m$ en fila $m$, en consonancia con la disposición de las columnas de sumas. Habiendo hecho esto, la columna de sumas de dinero se ajusta (fila y la suma de $a_m$ se cae), y entonces se procede con el cálculo recursivo de $T(A',B')$. Tenga en cuenta que $T(A,B) = T(B,A)$ es simétrica, y que en cada etapa es preferible trabajar con cualquier tupla de menor longitud. En la recursividad, vamos a colocar una entrada de Una, pero nos podría caer más de una entrada de B debido a decrecer a cero algunos columna de sumas.
Cuando por fin llegar a una sola fila suma, que la distribución es forzado como el resto de la columna de sumas, pero solo las entradas que debe por la construcción de acuerdo en cuanto a la fila suma necesaria. En este punto, el biadjacency de la matriz se ha rellenado completamente, y sólo queda ver si algunas filas o columnas correspondientes a la igualdad de sumandos en el original particiones puede ser permutada en una forma que da soluciones distintas.
Vamos a ilustrar con el ejemplo dado, que nos pide encontrar maneras para llenar un $2 \times 2$ biadjacency matriz de modo que la fila sumas de dinero se $1,3$ y el de las columnas de sumas de dinero se $2,2$. Resulta que esto se puede hacer con números enteros no negativos de una sola manera:
$$\begin{pmatrix}
1 & 0 \\
1 & 2
\end{pmatrix} $$
Así que aquí sólo hay un gráfico bipartito (con múltiples aristas) que disponga de la necesaria vértice grados, pero desde las dos columnas de haber sumas iguales son distintas, estas por lo tanto puede ser intercambiado a dar dos conjunto múltiple bijections.
Este recursiva idea fue aplicada a contar sencillo bipartita de gráficos por A. Guénoche (1990):
El recuento y la selección al azar bipartito gráficos fijos grados
Addendum:
El enfoque esbozado simplifica. En lugar de servilmente la construcción de exactamente la nonisomorphic grafos bipartitos
(con múltiples aristas) de haber especificado el vértice grados, es más simple y más natural sólo para elegir las filas de la manera
esbozó sin tener que preocuparse acerca de su identidad (o la identidad/nonidentity de columnas con la misma columna de sumas).
Esto evita la necesidad de post-facto de procesamiento con la fila y la columna de permutaciones.
Me quedé con una persistente sospecha de que este fue el caso incluso como escribí arriba, pero la epifanía llegó sólo después de la publicación. El
enfoque más sencillo encuentra el nonisomorphic bipartito gráficos con vértices etiquetados, y así identifica el conjunto múltiple bijections
que se quería.
Además de esto despeja el camino para reconocer que lo que vamos a contar son comúnmente llamado (al menos en las estadísticas) tablas de contingencia, es decir, matrices rectangulares de números enteros no negativos cuya sumas de fila y columna de sumas que se especifican en forma compatible, $\sum a_i = n = \sum b_j$. Contando con ellos, dado m de filas y k columnas de sumas, parece ser un problema difícil, si es alta "grados de libertad" están involucrados.
Barvinok (2008) da de los límites para el número de tablas de contingencia y estudio de la literatura:
Asintótica las Estimaciones para el Número de Tablas de Contingencia, el Entero de los Flujos y Volúmenes de Transporte Polytopes
pero la relación de superior a inferior límites es algo de poder positivo de las $n^{m+k}$ en términos de nuestra notación.
