The Partial Derivative Puzzle
Solution

There are several ways to think about this question. It's a little scary to think about counting all the "relatives" of say f_xxyyyz.

A recursive approach might suggest itself, by thinking that all 6th order derivatives are created from 5th order derivatives, but the thing that stops you there is that there are several different 5th order derivatives that produce the same 6th order derivative. And the number of 5th order ancestors a 6th order derivative can have will vary depending on the form of the derivative.

So to think about this puzzle, perhaps we should look at the simplest cases.

For one variable, the problem is trivial. There is 1 first-order derivative, 1 second-order derivative, and so on. So our first bit of evidence is

N\K	0	1	2	3	4	5
1	1	1	1	1	1	1

and our formula is

pd(1,k) = 1

For two variables, the problem is simple. There are k+1 distinct partial derivatives of order k. For example, when k=4, we have:

f_xxxx f_xxxy f_xxyy f_xyyy f_yyyy

If we had to, we could use Pascal's triangle to keep track of the derivatives:

                        1
                      1   1 
                    1   2   1
                  1   3   3   1
                1   4   6   4   1
              1   5  10  10   5   1
            1   6  15  20  15   6   1
          1   7  21  35  35  21   7   1
        1   8  28  56  70  56  28   8   1
      

By convention, the rows and columns of Pascal's triangle are numbered beginning with 0. Thus row k of Pascal's triangle has k+1 entries, which we can symbolize by P(k,0) through P(k,k). The entries in row k can be thought of as corresponding to the various partial derivatives of order k. In fact, the actual value of Pascal's triangle there gives us the number of different ways of arriving at the given partial derivative by varying the order of differentiating by x and by y.

If our variables are x and y, and we represent differentiation by powers, then our Pascal triangle looks like this:

                   1
                 x    y
               x2  xy  y2
             x3  x2y  xy2  y3
      

pd(2,k) = k + 1

If we keep Pascal's triangle in mind, we can easily go to three variables. Pascal's pyramid can organize partial derivatives with respect to x, y, z. For example, the level for k=3 of the pyramid would look like

                   x3
                 x2y  x2z
               xy2  xyz  xz2
             y3  y2z  yz2  z3
      

        1, 3, 6, 15, ...
      

pd(3,k) = ( k + 2 ) * ( k + 1 ) / 2

We don't quite have enough data to see what to do with four variables. We could certainly sit down and write out the possibilities and count them. But instead, let's come at the problem from a different angle.

Suppose I told you that I had 10 pennies and 5 match sticks, and that they were lined up in some order. Could you tell me how many different ways that could be done? If we symbolize pennies by "0" and matchsticks by "1", a typical pattern might be

        0 0 1 0 1 0 0 0 0 1 1 0 0 1
      

But we can relate this problem to the one we have. The matchsticks can be thought of as dividers that separate the pennies into groups. To count the number of tenth-order derivatives in four variables, we need three matches to use as dividers, and 10 pennies. Thus, the derivative that we might write as

w³x²z⁵

        000 1 00 1 1 00000
      

But the general formula is simple. If we have m identical matchsticks and p identical pennies, then the number of arrangements is

#(m,p) = (p+m)! / ( m! p! )

pd(n,k) = (k+n-1)! / ( (n-1)! k! )

pd(1,k) = (k+1-1)! / ( (1-1)! k! ) = 1
pd(2,k) = (k+2-1)! / ( (2-1)! k! ) = k+1
pd(3,k) = (k+3-1)! / ( (3-1)! k! ) = (k+2) * (k+1) / 2
pd(4,k) = (k+4-1)! / ( (4-1)! k! ) = (k+3) * (k+2) * (k+1) / 6

Now we see that the array follows its own sort of simple rule. Note that

• the first element in row 4 is a 1,
• the second element (4) is the first element of row 4 (1) plus the second element of row 3 (3)
• the third element (10) is the second element of row 4 (4) plus the third element of row 3 (6), and so on.

pd(n,k) = pd(n,k-1) + pd(n-1,k)

pd(n,k) = pd(n,k-1) * (k+n-1) / k

Now if you look at the table at a 45 degree angle, you realize that we are staring at Pascal's triangle again!. The rows of the table are diagonals of Pascal's triangle. If you think about it for a minute, you will see that the entries of row 4 of our table, which we would write as

pd(4,1), pd(4,2), pd(4,3), pd(4,4), pd(4,5), ...

P(3,0), P(4,1), P(5,2), P(6,3), P(7,4), ...

pd(i,j) = P(i+j-2,j-1)

But we have a formula for the values of P:

P(i,j) = i!/ ( j! * ( i - j )! )

pd(i,j) = P(i+j-2,j-1) = (i+j-2)!/ ( ( j - 1 )! * ( i - 1 )! )