Algorithmes autour des coefficients binomiaux 1Factorielle d'un entier naturel 1.1À l'aide d'une boucle

xxxxxxxxxx
 
def facto(n):
    f = 1
    for i in range(2,n+1):
        f = f*i
    return f
​
print "1! = ",facto(1)
print "2! = ",facto(2)
print "3! = ",facto(3)
print "4! = ",facto(4)
print "10! = ",facto(10)
​

Exécuter

1.2Par récursivité

xxxxxxxxxx
 
def facto(n):
    if n == 1:
        f = 1
    else:
        f = n*facto(n-1)
    return f
        
print "1! = ",facto(1)
print "2! = ",facto(2)
print "3! = ",facto(3)
print "4! = ",facto(4)
print "10! = ",facto(10)
​

Exécuter

2Coefficients binomiaux 3À l'aide des factorielles On utilise ici la définition : pour tout entier naturel

n

k\leq n

\displaystyle{ {n \choose k} }=\dfrac{n!}{k!(n-k)!}

xxxxxxxxxx
 
def facto(n):
    f = 1
    for i in range(2,n+1):
        f = f*i
    return f
​
def coefBinom(n,k):
    return facto(n)/(facto(k)*facto(n-k))
    
print "3 parmi 5 : ",coefBinom(5,3)
print "4 parmi 9 : ",coefBinom(9,4)
​

Exécuter

3.1À l'aide de la formule de Pascal Pour tout entier

b\geq1

et pour tout

k\leq n

on a :

{n-1 \choose k-1}+{n-1 \choose k}={n \choose k}

xxxxxxxxxx
 
def coefBinom(n,k):
    if n == 1 and (k ==0 or k ==1):
        f = 1
    else:
        f = 0
    
    if n > 1: 
        f = coefBinom(n-1,k-1)+coefBinom(n-1,k)
    return f
    
print "3 parmi 5 : ",coefBinom(5,3)
print "4 parmi 9 : ",coefBinom(9,4)
​

Exécuter