Simplifying binomial sum of factorials

Question

When evaluating a multi-indexed derivative (what exactly is not important now) I ran across the sum $$ \sum_{\nu \leq \mu} \frac{\mu!}{\nu!(\mu - \nu)!} |\nu|!|\mu - \nu|!=(|\mu| + 1)! $$ for $\mu$ a Multi index with finite support (i.e. $|\mu| = \sum_{j \geq 1}\mu_j < \infty$). When evaluating the sum numerically, I get the suspicion that this equality holds. However, I have not been able to provide a proof. Can somebody help me with this?

I tried to proof this by induction on the 'dimension' of the multi index $\mu$. The base case is trivial, but I cannot get the inductive step to work: (with $\tilde\mu = (\mu_1 ,\cdots, \mu_{n-1})$ etc.)

$$ \sum_{\nu \leq \mu} \frac{\mu!}{\nu!(\mu - \nu)!} |\nu|!|\mu - \nu|!\\ =\sum_{\nu_n = 0}^{\mu_n} {\mu_n \choose \nu_n} \sum_{\tilde\nu \leq \tilde\mu} \frac{\tilde\mu!}{\tilde\nu!(\tilde\mu - \tilde\nu)!} |\nu|!|\mu - \nu|! $$ From which I cannot apply the induction hypothesis because I cannot seem to isolate $\sum_{\tilde\nu \leq \tilde\mu} \frac{\tilde\mu!}{\tilde\nu!(\tilde\mu - \tilde\nu)!} |\tilde\nu|!|\tilde\mu - \tilde\nu|!$ to apply it.

Even a simple case for $\mu=(\mu_1,\mu_2)$ has me confused. I cannot get $$ \sum_{\nu_1 = 0}^{\mu_1}\sum_{\nu_2 = 0}^{\mu_2}{\mu_1 \choose \nu_1}{\mu_2 \choose \nu_2} (\nu_1+\nu_2)!(\mu_1+\mu_2-\nu_1-\nu_2)! $$ To simplify to $(\mu_1 + \mu_2 + 1)!$ without running into nasty factorials everywhere. For reference, I calculated it numerically by hand for some small examples and for larger examples using python:

import math
import numpy as np

np.random.seed(0)
def fun(mu, processed_mu=[], processed_nu=[]):
    if len(mu) == 0:
        return math.factorial(sum([a - b for a, b in zip(processed_mu, processed_nu)])) * math.factorial(
            sum(processed_nu))
    processed_nu = processed_nu + [0]
    processed_mu = processed_mu + [0]
    summand = 0
    for nu_i in range(mu[0] + 1):
        binomial_coefficient = math.comb(mu[0], nu_i)
        processed_nu[-1] = nu_i
        processed_mu[-1] = mu[0]
        summand = summand + binomial_coefficient * fun(mu[1:], processed_mu, processed_nu)

    return summand

for i in range(10):
    mu_loc = np.random.randint(3, size=10)
    print(f"{mu_loc}: Sum={fun(mu_loc)}, (|\\mu| + 1)!={math.factorial(sum(mu_loc) + 1)}")

[0 1 0 1 1 2 0 2 0 0]: Sum=40320, (|\mu| + 1)!=40320
[0 2 1 2 2 0 1 1 1 1]: Sum=479001600, (|\mu| + 1)!=479001600
[0 1 0 0 1 2 0 2 0 1]: Sum=40320, (|\mu| + 1)!=40320
[1 2 0 1 1 1 0 2 0 2]: Sum=39916800, (|\mu| + 1)!=39916800
(...)

Can anybody help me with this proof? (Or, of course, show me that this is simply not true?)

Extra

Furthermore, I am looking at a similar question for the triple equivalent, hoping that a proof for the first question will help me with this. $$ \sum_{\nu^{(1)}+\nu^{(2)}+\nu^{(3)} = \mu} \frac{\mu!}{\nu^{(1)}!\nu^{(2)}!\nu^{(3)}!} |\nu^{(1)}|!|\nu^{(2)}|!|\nu^{(3)}|! = (1 + \frac{|\mu|}{2})(|\mu|+1)! $$

Answer 1

I can give a combinatorial proof of this identity. Let $\mu=(\mu_1,\dots,\mu_n)$ be a multi-index. Imagine a deck of cards, with $|\mu|+1$ cards total, in $n$ suits. For each $i\in \{1,\dots,n\}$, there are $\mu_i$ distinct cards in the $i^\text{th}$ suit. The remaining card is a joker. The question is, "How many ways are there to arrange the cards in a stack?"

• The obvious answer is $(|\mu|+1)!$, since we need to choose a linear ordering of $|\mu|+1$ distinct cards.

• Let $\nu=(\nu_1,\dots,\nu_n)$ be a multi-index where $\nu\le \mu$. We can further ask, "How many ways are there to stack the deck so that, for each $i\in \{1,\dots,n\}$, there are exactly $\nu_i$ cards of $i^\text{th}$ suit which are above the joker?". We need to choose the cards from the $i^\text{th}$ suit in $\binom{\mu_i}{\nu_i}$ ways, and then linearly order the cards above the joker in $|\nu|!$ ways, and then linearly order the cards the cards below the joker in $|\mu-\nu|!$ ways. The result is $$ \binom{\mu_1}{\nu_1}\cdots \binom{\mu_n}{\nu_n}|\nu|!\cdot |\mu-\nu|!=\frac{\mu!}{\mu!(\mu-\nu)!}|\nu|!\cdot |\mu-\nu|! $$ Summing over all $\nu\le \mu$ gives the total number of ways to stack the deck.

We have shown how both sides of the equation enumerate the number of ways to stack the deck, proving that they are equal.

For your extra identity, you can prove it using a similar idea. Consider a deck with $|\mu|+2$ cards, with $\mu_i$ cards in the $i^\text{th}$ suit, this time with two identical jokers. The details are pretty much the same as the previous proof.