I stumbled upon this https://en.wikipedia.org/wiki/General_Leibniz_rule on the nth derivative of products of functions. I am wondering if anyone is knowledgeable enough to state the nth derivative for 3 functions.
The notation it gives under the "more than two factors" section makes no sense to me because there is no upper part of the sum to sum to and makes no effort to explain why that is the case. What does the notation mean?
On
$\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$.
$$ \sum_{k_1+k_2+\cdots+k_m=n} $$
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'' +
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:
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}} $$
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'' +
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} $$
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"
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, []);
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.
$$ \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} $$
$$ \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} $$
$$ \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} $$
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} $$
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' = ''
The notation $$ \sum_{k_1+k_2+\cdots+k_m=n} $$ means "take all different combinations of $k_1,k_2,\ldots,k_m$ that sum to $n$ and add together the different results". (It is implicitly understood that the $k_i$ are non-negative integers.)
It is a simplification of $$ \sum_{k_1=0}^n\sum_{k_2=0}^{n-k_1}\cdots\sum_{k_{m-1}=0}^{n-(k_1+k_2+\cdots+k_{m-2})} $$ with the understanding that $k_m$ is equal to $n-(k_1+k_2+\cdots+k_{m-1})$