WisFaq!

Aantal combinatie berekenen bij grote n

Hoe bereken ik met de computer C(n,k) of n!/(n-k)!k! voor n173?

Wim Vandeweerdt
11-10-2003

Antwoord

Je kan voorkomen dat je tussenresultaten het bereik van de getallen in jouw programmeertaal overstijgen door afwisselend vermenigvuldigingen en delingen uit te voeren (in plaats van eerst alle vermenigvuldigingen om n! te bepalen)

C(n,k)
= n!/[(n-k)!k!]
= n/1 . (n-1)/2 . ... . (n-k+1)/k

In een of andere pseudocode bekom je dan

temp=1
for j = 1 to k
   temp=temp*(n+1-j)
   temp=temp/j
next j
C=temp

Merk vooral op dat je door eerst te vermenigvuldigen en dan pas te delen je in het domein van de "integers" kan blijven, maw de variabele temp zal op elk moment in de subroutine geheel zijn (kan je dit zelf bewijzen?)

Voor nog veel grotere argumenten kan je overschakelen op logaritmen, of, niet geheel los daar van, de benaderingsformule van Stirling voor faculteiten.

cl
12-10-2003