Una suma significativa de multinomios

Question

Considere los caminos que tocan $n$ nodos de un gráfico completo, y numeremos estos nodos de $1$ a $n$ .

El número de caminos que pasan $m_1$ veces a través del nodo $1$ , $m_2$ veces a través del nodo $2$ etc., parece estar dada por

$$\sum_{\vec{t}\in \mathbb{N}^n } \frac{(t_1 + t_2 + \cdots + t_n)!}{t_1! t_2! \cdots t_n!} \prod_{i=1}^n (-1)^{m_i - t_i} { m_i -1 \choose t_i-1},$$

¿Cómo abordaría esta suma, quizás con alguna identidad útil?

$\textit{Edited 13/09}$ (motivación añadida antes de la fórmula).

Answer 1

Es interesante observar que, si se generaliza el método de Garij Grinberg a $n>2$ , su índice $a$ se convierte en una matriz que suma los mismos valores en filas y columnas.

Para demostrarlo, definamos el coeficiente multinomial como

$$ { x \choose x_1,x_2,...,x_n } = \left\{ \begin{array}{rl} \frac{x!}{x_1! x_2! \ldots x_n!} \text{ if }x = \sum_{i=1}^{n} x_i \\ 0 \text{ otherwise} \end{array}\right.$$

H.W. Gould introdujo una convolución multinomial generalizada de Vandermonde (Amer. Math. Monthly 63, 84-91, 1956):

$$ { x_1 + x_2 +\cdots + x_s \choose r_1, r_2, \ldots, r_p } = \sum_{a_{ij}} { x_1 \choose a_{11}, a_{12}, \ldots, a_{1p} } \cdots { x_s \choose a_{s1}, a_{s2}, \ldots a_{sp} }$$

donde la suma se realiza sobre todos los $a_{ij}$ ( $i=1,\ldots, s; j=1, \ldots, p$ ) tal que $a_{1l} + a_{2l} + ... + a_{sl} = r_l$ , para $l=1,\ldots, p$ .

Ahora podemos aplicar esto con $p=s=n$ y $x_i = r_i = t_i$ . Nuestra suma se convierte en

$$\sum_{t_1, \ldots, t_n} \sum_{ \{ a_{ij} \}} \prod_{i=1}^n {t_i \choose a_{i1}, a_{i2}, \ldots, a_{in} } (-1)^{m_i - t_i} {m_i -1 \choose t_i -1}$$

donde el $a_{ij} $ ( $i=1,\ldots,n$ , $j=1,\ldots,n$ ) son enteros no negativos sometidos a la doble restricción $\sum_{i=1}^n a_{ij} = t_j$ (que proviene del teorema) y $\sum_{j=1}^n a_{ij} = t_i$ (necesario para que los coeficientes multinomiales sean distintos de cero).

Ahora podemos dejar de lado la suma sobre $t_i$ imponiendo la restricción de que, en la suma sobre $\{a_{ij} \}$ , $\sum_j a_{ij} = \sum_j a_{ji}$ para $i=1, \ldots, n$ .

Reescribimos la suma como

$$\sum_{\substack{ \{a_{ij} \}_{i,j \in (1,n)} \\ \sum_j a_{ij} = \sum_j a_{ji}}} \prod_{i=1}^n (-1)^{ m_i - \sum_j a_{ij}} { \sum_j a_{ij} \choose a_{i1}, ... , a_{in} } {m_i -1 \choose \sum_j a_{ij} -1 }$$

Ahora, observe que el término diagonal $a_{ii}$ se anula a partir de la restricción $\sum_j a_{ij} = \sum_j a_{ji}$ que puede escribirse como $\sum_{j\neq i} a_{ij} = \sum_{j\neq i} a_{ji}$ .

Así que podemos sumar sobre el $a_{ii}$ independientemente de la restricción. En cada suma sobre $a_{ii}$ podemos pasar al índice $t_i = a_{ii} + b_i$ , donde $b_i : =\sum_{j\neq i} a_{ij} $ . De este modo se obtienen términos que se parecen precisamente a los términos con corchetes de la fórmula de GarijGrinberg, sólo que con el antiguo índice $a$ sustituido por $b_i$ . Realizando las sumas se obtiene:

$$\sum_{\{a_{ij}\}_{i\neq j}} \prod_{i=1}^n \frac{ b_i!}{\prod_{k\neq i} a_{ik}!} (-1)^{m_i + b_i} { m_i - b_i - 2 \choose m_i - b_i} $$

donde la suma es sobre todos los $a_{ij}$ ( $i\neq j$ ) tal que $\sum_{i\neq j} a_{ij} = \sum_{i\neq j} a_{ji}$ .

Utilizando ahora la identidad ${ u-2 \choose u} = \delta_{0,u} - \delta_{1,u}$ obtenemos:

$$\sum_{\substack{ \{a_{ij} \}_{i,j=1 \ldots n} \\ a_{ii}=0, \sum_j a_{ij} = \sum_j a_{ji}\equiv b_i}} \prod_{i=1}^n { a_{i1} + a_{i2} +\ldots + a_{in} \choose a_{i1},a_{i2}, \ldots, a_{in}} \left( \delta_{b_i, m_i} + \delta_{b_i, m_i-1}\right)$$

Como se ha mencionado, se supone que esta suma da el número de caminos a través de un grafo completo que implican $n$ nodos (numerados desde $1$ a $n$ ) y el nodo táctil $i$ exactamente $m_i$ tiempos.

Por lo tanto, una posible interpretación de la fórmula (corregidme si me equivoco) podría ser que $a_{ij} $ es el número de transiciones desde el nodo $i$ al nodo $j$ dentro de cada camino. El factor ${ a_{i1} + a_{i2} +\ldots + a_{in} \choose a_{i1},a_{i2}, \ldots, a_{in}} $ parece contar las formas de ordenar estas transiciones.

En una trayectoria infinita, el número de transiciones al nodo $i$ es igual al número de transiciones desde el nodo $i$ Así que $\sum_j a_{ij} = \sum_j a_{ji} $ . Para tener en cuenta el tamaño finito del camino, tenemos un factor $ \left( \delta_{b_i, m_i} + \delta_{b_i, m_i-1}\right)$ que permite que el número de ocurrencias del nodo sea mayor en una unidad que la suma de las transiciones hacia y desde el nodo.

Aunque la fórmula es más clara en esta forma, sigue siendo más fácil de calcular en la otra forma, porque se tiene $n$ sumas en lugar de $(n-1)^2 -n$ . A menos que haya una manera de simplificar esta nueva forma, tal vez utilizando el hecho de que el $b_i$ no son independientes.

Answer 2

Supongo que todos los $m_1, m_2, \ldots, m_n$ son positivos; en caso contrario, la suma es divergente.

En el $n = 1$ caso, la suma es igual a $0$ si $m_1 > 1$ y es igual a $1$ si $m_1 = 1$ .

En el $n = 2$ caso, la suma es igual:

• $2$ si $m_1 = m_2$ ;

• $1$ si $\left|m_1-m_2\right| = 1$ ;

• $0$ de lo contrario.

La prueba no es demasiado difícil; esencialmente, hay que reescribir $\dfrac{\left(t_1+t_2\right)!}{t_1!t_2!}$ como $\sum\limits_{a\in \mathbb{N}} \dbinom{t_1}{a}\dbinom{t_2}{a}$ utilizando la convolución de Vandermonde, y entonces su suma se convierte en

$\sum\limits_{a \in \mathbb{N}} \underbrace{\left(\sum\limits_{t_1 \in \mathbb{N}} \dbinom{t_1}{a} \left(-1\right)^{m_1-t_1} \dbinom{m_1-1}{t_1-1}\right)}_{= \left(-1\right)^{m_1+a} \dbinom{m_1-a-2}{m_1-a}} \underbrace{\left(\sum\limits_{t_2 \in \mathbb{N}} \dbinom{t_2}{a} \left(-1\right)^{m_2-t_2} \dbinom{m_2-1}{t_2-1}\right)}_{= \left(-1\right)^{m_2+a} \dbinom{m_2-a-2}{m_2-a}}$ ; pero $\dbinom{u-2}{u}$ es $1$ si $u=0$ es $-1$ si $u=1$ y es $0$ si $u \geq 2$ de ahí que la reclamación siga con algunos casos. Puedo entrar en detalles en el improbable caso de que el $n=2$ caso resulta ser el interesante.

No tengo una buena idea para $n\geq 3$ . Los números grandes aparecen ciertamente en esos casos. Aquí hay un estúpido código de Sage:

def s(m1, m2, m3):
    res = 0
    for t1 in range(m1+1):
        for t2 in range(m2+1):
            for t3 in range(m3+1):
                res += binomial(t1+t2+t3, t1+t2) * binomial(t1+t2, t1) * ((-1) ** (m1-t1+m2-t2+m3-t3)) * binomial(m1-1, m1-t1) * binomial(m2-1, m2-t2) * binomial(m3-1, m3-t3)
    return res

print [s(1, 2, i) for i in range(10)]

El resultado es:

[1, 6, 12, 10, 3, 0, 0, 0, 0, 0]

Tal vez sea relevante: http://oeis.org/A095660