1,1

1,2

1,3

1,4,6

1,5,10

1,6,15,20

1,7,21,35

1,8,28,56,70

.. etc

Or connect using:

1,1

1,2

1,3

1,4,6

1,5,10

1,6,15,20

1,7,21,35

1,8,28,56,70

.. etc

karinfromnosundApril 29 2008, 19:41:24 UTC 8 years ago

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

...

Basically, every number is the sum of the two above it. One possible function to generate them could be: c(i,j) = c(i,j-1) + c(i-1, j-1), with appropiate definitions of i and j.

karinfromnosundApril 29 2008, 19:44:34 UTC 8 years ago

ginaspiderApril 29 2008, 20:02:29 UTC 8 years ago

madcaptenorApril 29 2008, 20:14:51 UTC 8 years ago Edited: April 29 2008, 20:15:28 UTC

There's a faster algorithm to compute binomial coefficients; it takes O(j) time.

ginaspiderApril 30 2008, 03:22:42 UTC 8 years ago

nekokazeApril 29 2008, 20:24:15 UTC 8 years ago

c(i,j) = Π( ((k+1)-j)/j ) from k=0 to i -- j &neq; 0

c(i,j) = 1 -- j = 0

e.g.

c(8,5) = (9-1)/1 * (9-2)/2 * (9-3)/3 * (9-4)/4

c(8,5) = 8*(7/2)*2*(5/4)

c(8,5) = 70

For an implementation you'd obviously want to multiply by ((k+1)-j), then divide, else you could get into FP issues.

nekokazeApril 29 2008, 20:25:34 UTC 8 years ago

(That'll teach me to not refresh a comment window ten minutes after opening it.)

arvindnApril 30 2008, 04:47:56 UTC 8 years ago

ginaspiderNovember 25 2008, 04:01:13 UTC 7 years ago

ginaspiderwrote inalgorithms: ←raytracerantilamerwrote inalgorithms: →Category theory and query optimization