[Solved]: How to make this recursive relationship nonrecursive?

Problem Detail: 

I need to make a recursive relationship for a function f(m, n) nonrecursive to make it more efficient and succinct in my code.

I stumbled across an important recurrence relationship dealing with the number of vertices, edges, faces, and solids (m-polytopes) in an n-cube which is based off of a simpler algorithm for an n-simplex which uses Pascal's triangle:

For a simplex: nCm gives you the number of m-polytopes (m = 1 for points, 2 for lines, 3 for faces) in an n-simplex (1-simplex is a line, 2-simplex is a triangle, 3-simplex is a tetrahedron).

The pattern between the n-simplex m-polytopes and the n-cube m-polytopes are very similar:

Here is the n-cube up to 10 10-polytopes:                                                             9-polytopes:                                                           1 8-polytopes:                                                     1    16 7-polytopes:                                               1    14   112 6-polytopes:                                         1    12    84   448 5-polytopes:                                   1    10    60   280  1120 4-polytopes:                             1     8    40   160   560  1792 3-polytopes:                       1     6    24    80   240   672  1792 2-polytopes:                 1     4    12    32    80   192   448  1024 1-polytopes:           1     2     4     8    16    32    64   128   256 Here is the n-simplex up to 10 10-polytopes:                                                             9-polytopes:                                                           1 8-polytopes:                                                     1     9 7-polytopes:                                               1     8    36 6-polytopes:                                         1     7    28    84 5-polytopes:                                   1     6    21    56   126 4-polytopes:                             1     5    15    35    70   126 3-polytopes:                       1     4    10    20    35    56    84 2-polytopes:                 1     3     6    10    15    21    28    36 1-polytopes:     1     1     2     3     4     5     6     7     8     9 

And here is the c code that generated that:

#include <stdio.h>  #define TOP 10  // nothing to see here int factorial(int n) {     if (n < 2)         return 1;     else         return n * factorial(n - 1); } // a recursive implementation for the number of  // m-polytopes in an n-cube int ncubeRecursive(int n, int m) {     if (n == 0 && m == 0)         return 1;     else if(n < 0 || m < 0)         return 0;     else     {         return (ncubeRecursive(n - 1, m - 1) + 2 * ncubeRecursive(n - 1, m));     } } // missing a nonrecursive algorithm // YOUR JOB TO FIX THIS   // a recursive implementation for the number of // m-polytopes in an n-simplex int nsimplexRecursive(int n, int m) {     if (n == 0 && m == 0)         return 1;     else if(n < 0 || m < 0)         return 0;     else     {         return (nsimplexRecursive(n - 1, m - 1) + nsimplexRecursive(n - 1, m));     } } // a nonrecursive algorithm int nsimplexNonrecursive(int n, int m) {     return factorial(n)/(factorial(n - m) * factorial(m)); }  int main() {     printf("Here is the n-cube up to %i\n", TOP);     for (int n = TOP; n > 0; --n)     {         printf("%i-polytopes:", n);         for (int m = 0; m < TOP; ++m)         {             int val = ncubeRecursive(m, n);             if (val == 0)                 printf("%6c", ' ');             else                 printf("%6i", val);         }         printf("\n");     }     printf("Here is the n-simplex up to %i\n", TOP);     for (int n = TOP; n > 0; --n)     {         printf("%i-polytopes:", n);         for (int m = 0; m < TOP; ++m)         {             int val = nsimplexNonrecursive(m, n);             if (val == 0)                 printf("%6c", ' ');             else                 printf("%6i", val);         }         printf("\n");     }      return 0; } 

Does anyone here see a non-recursive pattern? I just don't know how to analyze a recursive relationship like this for a function that takes to inputs like f(m, n) instead of just f(x).

Asked By : michaelsnowden

Answered By : Yuval Filmus

For the $n$-cube, you are interested in A013609 (see the link), in which the following explicit formula is given: $$ f(m,n) = \binom{m}{n} 2^n. $$ (Your indexing could be slightly different.)

Tip: Whenever you have a recurrence relation and looking for a closed form, calculate a few entries and look it up in the OEIS. That's how I found the formula.

For the $n$-simplex, as you mention, this is just Pascal's triangle.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22869

3.2K people like this

 Download Related Notes/Documents