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
|