### Re: Binomial Golf

by gumpu (Friar)
 on May 30, 2001 at 11:16 UTC ( #84187=note: print w/replies, xml ) Need Help??

On a related note; a real challenge is also to just compute one of the entries in the table. Especially for higher values.

If we number the table as follows:

```F    1   2   3    4   5   6   7   8  9  10  11   --> m
1    1
2    1   1
3    1   2   1
4    1   3   3    1
5    1   4   6    4   1
6    1   5   10  10   5   1
7    1   6   15  20  15   6   1
8    1   7   21  35  35  21   7   1
9    1   8   28  56  70  56  28   8  1
10   1   9   36  84 126 126  84  36  9   1
11   1   10  45 120 210 252 210 120 45  10   1
|
n

it can be said to define a function F(n,m). For instance:

``` F(1,1)  = 1
F(11,2)  = 10
F(9,5)  = 70

However for higher values of n this function returns very large numbers around the point F(n,n/2). This are the numbers in the center of the table. For instance try computing F(400,200) or F(400,199).

These numbers are so large they do not fit into a floatingpoint number. It's of course possible to use the BigInt package, but that slows down computation, and uses quite some memory. Hence just printing the table for large values of n becomes impossible.

However the numbers around F(n,n), and F(n,1) stay pretty small for large n and could be computed. These are the numbers at the edge of the table. For instance F(400,1) = F(400,400) = 1, and even F(400,5) is computable.

Finding F(n,m) is useful for several statistical and counting problems. However writing a program that efficiently computes F(n,m) for any n,m, is quite a challenge! (At least I found it quite a challenge when I tried to write one.) One approach is to 'walk' the edge of the table towards the entry that needs to be computed. Thereby avoiding the center of the table with all the giant numbers. But there must be a more effecient way to compute F .... any suggestions?

Have Fun

Replies are listed 'Best First'.
Re: Re: Binomial Golf
by Arguile (Hermit) on May 30, 2001 at 15:23 UTC
Check the thread Binomial Expansion there's a really interesting n choose r sub there by ariels and a proof underneath by japhy. (Among other things)
```# copy of said subroutine

sub nCr {
my (\$n, \$r) = @_;
my \$res = 1;
for my \$i (1..\$r) {
\$res *= \$n--;
\$res /= \$i;
}
\$res;
}

Thanks! That's a very elegant solution. I spend a day or so comming up with a program to do the same. And that was about a page long. Very nifty.

Have Fun

Create A New User
Node Status?
node history
Node Type: note [id://84187]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (8)
As of 2018-03-17 15:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (224 votes). Check out past polls.

Notices?