Re: Math fun.

Is this of any help?

$n\$d   1       2       3       4       5       6       7
1       1       1       1       1       1       1       1
2       4       5       6       7       8       9       10
3       10      15      21      28      36      45      55
4       20      35      56      84      120     165     220
5       35      70      126     210     330     495     715
6       56      126     252     462     792     1287    2002
7       84      210     462     924     1716    3003    5005
8       120     330     792     1716    3432    6435    11440
9       165     495     1287    3003    6435    12870   24310
10      220     715     2002    5005    11440   24310   48620
11      286     1001    3003    8008    19448   43758   92378
12      364     1365    4368    12376   31824   75582   167960
13      455     1820    6188    18564   50388   125970  293930
14      560     2380    8568    27132   77520   203490  497420
15      680     3060    11628   38760   116280  319770  817190
16      816     3876    15504   54264   170544  490314  1307504
17      969     4845    20349   74613   245157  735471  2042975
18      1140    5985    26334   100947  346104  1081575 3124550
19      1330    7315    33649   134596  480700  1562275 4686825
20      1540    8855    42504   177100  657800  2220075 6906900
[download]

The above was produced using the following program:

use strict;
use warnings;

use List::Util qw( sum );

{
   my %memoize;

   sub calcIt {
      my ($n, $d) = @_;
      return $memoize{"$n:$d"} ||= (
         ($d
            ? sum map { calcIt($_, $d-1) } 1..$n
            : $n * ( $n + 1 ) / 2
         )
      );
   }
}

{
   my $N = 20;
   my $D = 7;

   print('$n\\$d');
   for my $d (1..$D) {
      print("\t$d");
   }
   print("\n");

   for my $n (1..$N) {
      print("$n");
      for my $d (1..$D) {
         print("\t", calcIt($n, $d));
      }
      print("\n");
   }
}
[download]

You can really appreciate the effect of memoization here.

Comment on Re: Math fun. Select or Download Code

Replies are listed 'Best First'.
Re^2: Math fun. by xdg (Monsignor) on Feb 13, 2007 at 20:43 UTC
If you add a column of 1's on the left (and a column of sums of 1 .. N after the 1..N column), you get Pascal's triangle, and thus the link to combinatorics: `1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 1 3 6 10 15 21 28 36 45 55 1 4 10 20 35 56 84 120 165 220 1 5 15 35 70 126 210 330 495 715 1 6 21 56 126 252 462 792 1287 2002 1 7 28 84 210 462 924 1716 3003 5005 1 8 36 120 330 792 1716 3432 6435 11440` [download] Update: added missing 3rd column as per eric256's observation Fcn(D,N) => (5,10) seems to correspond to Choose(16,7) where Choose(n,k) is n!/k!(n-k)! Likewise, Fcn(5,20) seems to correspond to Choose(26,7). More generically, it looks like your function can be reduced to Choose(D+N+1,D+2) Of course, you still have recursion in the computation of the factorial, so I don't think you can quite avoid it entirely. -xdg Code written by xdg and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.	[reply] [d/l]
Re^3: Math fun. by ikegami (Patriarch) on Feb 13, 2007 at 20:51 UTC
Aye, I've already posted that solution, with an efficient implementation.	[reply]
Re^3: Math fun. by eric256 (Parson) on Feb 13, 2007 at 23:42 UTC
That is not pascals triangle...if it were wouldn't it be symmetrical? `1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 20` [download] ___________ Eric Hodges	[reply] [d/l]
Re^4: Math fun. by xdg (Monsignor) on Feb 14, 2007 at 01:04 UTC
Er, yes. I left out a column in preparing the post, apparently. Updated above. -xdg Code written by xdg and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.	[reply]