General Leibniz rule Explained

Introduction

I was initially trying to help on interpreting the general Leibniz rule on stackexcange.com, in particular, how to read the peculiar: $$\sum_{k_1+k_2+\cdots+k_m=n}$$ summation notation used in the General Leibniz rule. As the answer grew longer I decided to make an article out of it. Understanding this notation will also help to read the Multinomial theorem, and as links to combinatorics. Reader should be already familiar with the basic sigma notation $\sum_{i=0}^{m}$

Short explanation

$\sum_{k_1+k_2+\cdots+k_m=n}$ is the sum of all possible combinations of $\{k_1, \ k_2,\ \cdots, k_m\}$ that satisfy ${k_1+k_2+\cdots+k_m=n}$, for instance:

$$\sum_{\underbrace{k_1+k_2=2}_{\Large \text{equation}}} (k_1, k_2) = \overbrace{\underbrace{(2,0)}_{\text{solution 1}}}^{2+0=2} + \overbrace{\underbrace{(0,2)}_{\text{solution 2}}}^{0+2=2} + \overbrace{\underbrace{(1,1)}_{\text{solution 3}}}^{1+1=2}$$

Here $k_m$ must be positive integers i.e. $k_m \in \mathbb N$ and their sum must be equal to $n$.

Long explanation

$$\sum_{k_1+k_2+\cdots+k_m=n}$$

Describes a sum of terms $(\cdots + \cdots + \cdots)$ just like $\sum_{i=0}^{m}$ does. However, the number of terms is not explicitly written in this version. The number of all possible combinations the set $\{k_1, \ k_2,\ \cdots, k_m\}$ can make, while satisfying ${k_1+k_2+\cdots+k_m=n}$, is the number of terms. In addition, similar to using the $i$ in each terms of $\sum_{i=0}^{m}$, in this version each term can then freely use the value of the set $\{k_1, \ \cdots, k_m\}$.

This notation implies we have to solve the following equation:

$$k_1+k_2+\cdots+k_m=n$$

Where $k_1, k_2,\cdots,k_m$ are positive integers. $\sum_{k_1+k_2+\cdots+k_m=n}$ is then understood to be the sum of all tuples that solve the equation, for instance:

$$\begin{array}{ll} & \{k_1=n, \quad k_2=0,\quad \cdots, \quad k_m=0\} \\ + & \{k_1=0, \quad k_2=n,\quad \cdots, \quad k_m=0\} \\ + & \quad \quad \quad \quad \quad \quad \cdots \end{array}$$

for $m=3$, $k=3$ the sum looks like:

$$\sum_{k_1+k_2+k_3=3}$$

Which means we must solve for:

$$k_1+k_2+k_3=3$$

This is a combinatorics problem but since we work with an easy example let's first derive all possibilities by hand:

    k1 k2 k3
    --------
    0  0  3
    0  3  0
    3  0  0
    1  1  1
    2  0  1
    2  1  0
    1  2  0
    0  2  1
    0  1  2
    1  0  2

Translated as order of derivatives:

$$\sum_{k_1+k_2+k_3=3} f^{k_1}.g^{k_2}.h^{k_3} =$$

    f(x)  g(x)  h(x)
    ----------------
    f     g     h'''   +
    f     g'''  h      +
    f'''  g     h      + 
    f'    g'    h'     +
    f''   g     h'     +
    f''   g'    h      +
    f'    g''   h      +
    f     g''   h'     +
    f     g'    h''    +
    f'    g     h''    +

Underlying combinatorics

The number of solutions of the Diophantine equation $k_1+k_2+k_3=3$ can be computed thanks to the famous formula:

$$\begin{align} \quad \binom{m + n - 1}{n} = \binom{3+3-1}{3} = \binom{5}{3} = \frac{5!}{3! \cdot (5 - 3)!} = \frac{5!}{3! \cdot 2!} = 10 \end{align}$$

In combinatorics $\binom{m + n - 1}{n}$ represents "the total number of unordered *combination* with repetition". It's a mouth-full to say let's pick $n$ objects among a choice of $m$ bins (each bin contain the same type of objects). Example with 3 bins:

• bin A: full of 'k1' objects
• bin B: full of 'k2' objects
• bin C: full of 'k3' objects

And we can pick only $m=3$ objects, therefore we have 10 combinations:

                    k1  k2  k3
    aaa ->  3a  ->  3   0   0
    bbb ->  3b  ->  0   3   0
    ccc ->  3c  ->     ...
    abc -> ...
    aac 
    aab 
    abb 
    acc
    bbc
    bcc

$$\underbrace{ \overbrace{k_1}^{\text{bin A}} + \overbrace{k_2}^{\text{bin B}} + \overbrace{k_3}^{\text{bin C}} }_{m \text{ bins}} = \overbrace{\underbrace{3}_{n}}^{\text{number of objects to pick}}$$

Coefficients

From there we are only missing the multinomial coefficients which we can derive with:

$${n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!} = \frac{(k_1+k_2+ \cdots + k_m)!}{k_1!\, k_2! \cdots k_m!}$$

For 3 terms:

$$\sum_{k_1+k_2+k_3=3} {n \choose k_1, k_2, k_3} f^{k_1}.g^{k_2}.h^{k_3}$$

       f(x)  g(x)  h(x)
       ----------------
       f     g     h'''   +
       f     g'''  h      +
       f'''  g     h      + 

    6  f'    g'    h'     +

    3  f''   g     h'     +
    3  f''   g'    h      +
    3  f'    g''   h      +
    3  f     g''   h'     +
    3  f     g'    h''    +
    3  f'    g     h''    +

Explicit formulation with nested sums

As pointed out by @Arthur's answer, this summation notation can be made more explicit:

$$\sum_{k_1+k_2+\cdots+k_m=n} (k_1, k_2, \cdots, k_m) \\ ~\\ = \\ ~\\ \sum_{k_1=0}^n \ \sum_{k_2=0}^{n-k_1} \ \sum_{k_3=0}^{n-(k_1+k_2)} \cdots \quad \sum_{k_{m-1}=0}^{n-(k_1+k_2+\cdots+k_{m-2})} (k_1, k_2, \cdots, \overbrace{n-(k_1+k_2+\cdots+k_{m-1})}^{k_m})$$

Let's apply the above formulation to our case:

$$\sum_{k_1+k_2+k_3=3} (k_1, k_2, k_3)= \sum_{k_1=0}^n\sum_{k_2=0}^{n-k_1} (k_1, k_2, \overbrace{(n-k1+k2))}^{k_3}$$

Algorithm for 3 terms

Thanks to the explicit nested sum expression, it is possible to compute all possible combinations. In addition, this JavaScript code may be more legible to programmers than the sigma sums:

let n = 3
for(var k1 = 0; k1 <= n; k1++ ){
    for(var k2 = 0; k2 <= (n-k1); k2++ ){
        var k3 = n - (k1+k2);
	    console.log(k1+" : "+k2+" : "+k3);
   }
}

This will output in the console:

    "0 : 0 : 3"
    "0 : 1 : 2"
    "0 : 2 : 1"
    "0 : 3 : 0"
    "1 : 0 : 2"
    "1 : 1 : 1"
    "1 : 2 : 0"
    "2 : 0 : 1"
    "2 : 1 : 0"
    "3 : 0 : 0"

General algorithm

You can compute all combinations in the general case as well. This JavaScript recursive function prints out the order of each term. It works for any n and any number of terms nb_terms = $|\{k_1, k_2, \cdots, k_m\}|$:

// list_k : a list containing [k1, k2, ..., km]
function diophantine(n, nb_terms, k_prev, list_k){		
    if( nb_terms <= 1 ){
    	var k_terminal = n - (k_prev);
        // add to tail:
        list_k.push(k_terminal); 
        // Print result:
        let str = "";
        for(k of list_k ){
            str = str + k + " : ";        
        }
		console.log(str.slice(0, -3));
        return;
    }

    for(var k = 0; k <= n-k_prev; k++ )
        diophantine(n, (nb_terms-1), (k+k_prev), list_k.concat(k));
}

Running the algorithm for $k_1+k_2+k_3+k_4 = 5$ and print out solution in the console:

console.log("Diophantine: ");
diophantine(/*n=*/5, /*nb_terms*/4, 0, []);

Examples for 3 terms

Developing a few examples by hand (not necessarily from the general Leibniz rule) may help see some patterns and help you get insights (you can use software like wxMaxima to do the developments for you if you are lazy like me), this is also useful to double check your interpretation of the formula.

1st order

$$\Big(f(x) \ g(x) \ h(x)\Big)' = \begin{array}{llll} & f(x) & g(x) & h'(x) & + \\ & f(x) & g'(x)& h(x) & + \\ & f'(x)& g(x) & h(x) \end{array}$$

2nd order

$$\Big(f(x) g(x) \ h(x)\Big)'' = \begin{array}{llll} & & f(x) & g(x) & h''(x) & + \\ & & f(x) & g''(x) & h(x) & + \\ & & f''(x) & g(x) & h(x) & + \\ \\ & 2 & f(x) & g'(x) & h'(x) & + \\ & 2 & f'(x) & g(x) & h'(x) & + \\ & 2 & f'(x) & g'(x) & h(x) & + \\ \end{array}$$

3rd order

$$\Big(f(x) g(x) \ h(x)\Big)''' = \begin{array}{llll} & & f(x) & g(x) & h'''(x) & + \\ & & f(x) & g'''(x)& h(x) & + \\ & & f'''(x) & g(x) & h(x) & + \\ \\ & 3 & f(x) & g'(x) & h''(x) & + \\ & 3 & f'(x) & g''(x) & h(x) & + \\ & 3 & f''(x) & g(x) & h'(x) & + \\ \\ & 3 & f(x) & g''(x) & h'(x) & + \\ & 3 & f'(x) & g(x) & h''(x) & + \\ & 3 & f''(x) & g'(x) & h(x) & + \\ \\ & 6 & f'(x) & g'(x) & h'(x) & + \\ \end{array}$$

Trinomial

Notice the correspondence with this trinomial where a power of 'zero' means we don't differentiate, a power of 'one' represent the first derivative and so on:

$$(x + y + z)^3 = \begin{array}{llll} & x^3 & & & + \\ & & y^3 & & + \\ & & & z^3 & + \\ 3 & x^2 & y & & + \\ 3 & x^2 & & z & + \\ 3 & & y^2 & z & +\\ 3 & x & y^2 & & + \\ 3 & & y & z^2 & + \\ & x & z^2 & & + \\ 6 & x & y & z & \end{array}$$

Example for 4 terms

Say you have 4 functions that you differentiate to the 2nd order $(f . g . h . i )''$. Then you want to find all the patterns that satisfy $k_1+k_2+k_3+k_4=2$ where k would be the order of differentiation, below I illustrate how orders sum together:

    f   g   h   i
    --------------
    f'' g   h   i    = ''
    f   g'' h   i    = ''
    f   g   h'' i    = ''
    f   g   h   i''  = ''

    f'  g'  h   i    = ''
    f   g'  h'  i    = ''
    f   g   h'  i'   = ''

    f'  g   h'  i    = ''
    f'  g   h   i'   = ''
    f   g'  h   i'   = ''

Reference

• https://math.stackexchange.com/questions/3062223/sum-of-each-combination
• http://mathonline.wikidot.com/the-trinomial-theorem
• http://mathonline.wikidot.com/nonnegative-integral-solutions-to-simple-equations

Special case:

• https://en.wikipedia.org/wiki/Trinomial_expansion
• https://sahilmohnani.wordpress.com/2013/03/27/the-trinomial-theorem-and-pascals-tetrahedron/
• https://www2.edc.org/makingmath/mathprojects/pascal/Image23.gif

No comments

Name

Email (optional field, I won't disclose or spam but it's necessary to notify you if I respond to your comment)

All html tags except <b> and <i> will be removed from your comment. You can make links by just typing the url or mail-address.

Anti-spam question:
√4 + 40 = ?

Q: What's hard going in and soft and sticky coming out?
A: Chewing gum.