A meaningful sum of multinomials

Question

Consider paths that touch $n$ nodes of a complete graph, and let's number these nodes from $1$ to $n$.

The number of paths that pass $m_1$ times through node $1$, $m_2$ times through node $2$, etc., seems to be given by

$$\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},$$

How would you tackle this sum, perhaps with some useful identity?

$\textit{Edited 13/09}$ (added motivation before formula).

Answer 1

I assume that all of $m_1, m_2, \ldots, m_n$ are positive; otherwise, the sum is divergent.

In the $n = 1$ case, the sum equals $0$ if $m_1 > 1$, and equals $1$ if $m_1 = 1$.

In the $n = 2$ case, the sum equals:

• $2$ if $m_1 = m_2$;

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

• $0$ otherwise.

The proof is not too difficult; essentially, you need to rewrite $\dfrac{\left(t_1+t_2\right)!}{t_1!t_2!}$ as $\sum\limits_{a\in \mathbb{N}} \dbinom{t_1}{a}\dbinom{t_2}{a}$ using the Vandermonde convolution, and then your sum becomes

$\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}}$; but $\dbinom{u-2}{u}$ is $1$ if $u=0$, is $-1$ if $u=1$, and is $0$ if $u \geq 2$, whence the claim follows with some casework. I can go into details in the unlikely case that the $n=2$ case proves to be the interesting one.

I don't have a good guess for $n\geq 3$. Big numbers certainly do appear in those cases. Here is some stupid Sage code:

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)]

The result is:

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

Maybe relevant: http://oeis.org/A095660

Answer 2

It is interesting to notice that, if one generalizes Garij Grinberg's method to $n>2$, his index $a$ becomes a matrix which sums up to the same values on rows and columns.

To show this, let us define the multinomial coefficient as

$$ { 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.$$

A generalized multinomial Vandermonde convolution has been introduced by H.W. Gould (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} }$$

where the sum is taken over all $a_{ij}$ ($i=1,\ldots, s; j=1, \ldots, p$) such that $a_{1l} + a_{2l} + ... + a_{sl} = r_l$, for $l=1,\ldots, p$.

We may now apply this with $p=s=n$, and $x_i = r_i = t_i$. Our sum becomes

$$\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}$$

where the $a_{ij} $ ($i=1,\ldots,n$, $j=1,\ldots,n$) are nonnegative integers subjected to the double constraint $\sum_{i=1}^n a_{ij} = t_j$ (which comes from the theorem) and $\sum_{j=1}^n a_{ij} = t_i$ (necessary for the multinomial coefficients to be nonzero).

We can now leave out the summation over $t_i$ by imposing the constraint that, in the sum over $\{a_{ij} \}$, $\sum_j a_{ij} = \sum_j a_{ji}$ for $i=1, \ldots, n$.

We rewrite the sum as

$$\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 }$$

Now notice that the diagonal term $a_{ii}$ cancels out from the constraint $\sum_j a_{ij} = \sum_j a_{ji}$, which can be written as $\sum_{j\neq i} a_{ij} = \sum_{j\neq i} a_{ji}$.

So we can sum over the $a_{ii}$ regardless of the constraint. In each sum over $a_{ii}$ we may switch to the index $t_i = a_{ii} + b_i$, where $b_i : =\sum_{j\neq i} a_{ij} $. This gives terms that look precisely as the braced terms in GarijGrinberg's formula, only with the old index $a$ replaced by $b_i$. Performing the sums gives:

$$\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} $$

where the sum is over all $a_{ij}$ ($i\neq j$) such that $\sum_{i\neq j} a_{ij} = \sum_{i\neq j} a_{ji}$.

Usinge now the identity ${ u-2 \choose u} = \delta_{0,u} - \delta_{1,u}$, we obtain:

$$\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)$$

As mentioned, this sum is supposed to give the number of paths through a complete graph that involve $n$ nodes (numbered from $1$ to $n$) and touch node $i$ exactly $m_i$ times.

Therefore a possible interpretation of the formula (correct me if I'm wrong) could be that $a_{ij} $ is the number of transitions from node $i$ to node $j$ within each path. The factor ${ a_{i1} + a_{i2} +\ldots + a_{in} \choose a_{i1},a_{i2}, \ldots, a_{in}} $ seems to count the ways of ordering these transitions.

In an infinite path, the number of transitions to node $i$ is equal to the number of transitions from node $i$, so $\sum_j a_{ij} = \sum_j a_{ji} $. To keep into account the finite size of the path, we have a factor $ \left( \delta_{b_i, m_i} + \delta_{b_i, m_i-1}\right)$ that allows the number of occurrences of the node to be greater by one unit than the sum of transitions to and from the node.

Though the formula is clearer in this form, it is still easier to compute in the other form, because one has $n$ sums instead of $(n-1)^2 -n$. Unless there is a way to simplify this new form, perhaps using the fact that the $b_i$ are not independent.