Factorielle et combinaison.

[LFC²]

Bonjour,
Quelle est la formule qui permet de calculer k parmi n ?
Merci d'avance,
LFC².

[titine]

n!/(k!(n-k)!)

[mathelot]

Plussoyons

(1)


(2)


La formule de Titine (2) est plutôt pour les applications théoriques
car le dénominateur est symétrique en (k,(n-k))


la (1) est pour les calculs pratiques car la fraction est beaucoup plus simplifiée sans les facteurs
supplémentaires et inutiles (n-k)!

exemple:

trois facteurs au numérateur en décroissant à partir de 5, trois également au dénominateur

la façon dont ce quotient se simplifie, en règle générale, n'est pas connue,
malgré plusieurs millénaires d'existence de ces coefficients binomiaux.

tu as une formule récurrente qui permet de passer d'une ligne à l'autre dans le triangle








permet par symétrie pour k de ne pas dépasser( la moitié de )+1


exemple de tableau

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

etc..

[sylvainc2]

Il y a une autre méthode pour calculer C(n,k). Pour n suffisamment grand, elle peut être plus efficace.

On construit une liste des nombres premiers de 2 à n, avec un crible d'Eratosthene par exemple. Ensuite il faut déterminer l'exposant de chacun. Il y a une règle simple: pour chacun de ces nombres premiers p, l'exposant est le nombre d'emprunts à faire dans le calcul de n-k en base p.

Voir par exemple:
http://www.numbertheory.org/php/binomial.html

[mathelot]

qu'est ce qu'est le nombre d'emprunts ?

[sylvainc2]

Quand on calcule par exemple 30-19 en base 10, on commence par les chiffres à droite: vu que 0 < 9 on doit emprunter une dizaine au chiffre 3. Ca s'appelle un emprunt, non?

Bon, par exemple, pour le calcul de C(15,4)=1365: les nombres premiers de 2 à 15 sont 2,3,5,7,11,13:

- en base 2: 15 s'écrit 1111 et 4 = 0101; dans le calcul de 1111-0101 on doit faire 0 emprunt donc l'exposant de 2 est 0.
- en base 3: 15=120 et 4=011 et 120-011= 1 emprunt donc l'exposant est 1.
- en base 5: 15=30 et 4=04 et 30-04=1 emprunt: exposant = 1.
- en base 7: 15=21 et 4=04 et 21-04=1 emprunt: exposant = 1.
- en base 11: 15=14 et 4=04 et 14-04 = 0 emprunt: exposant = 0
- en base 13: 15=12 et 4=04 = 12-04 = 1 emprunt: exposant 1

donc C(15,4)=2^0 * 3^1 * 5^1 * 7^1 * 11^0 * 13^1 = 1365

On peut accélérer le calcul comme ceci: pour chaque nombre premier p de 2 à n:

- si p > n-k: l'exposant est forcément 1 donc pas besoin de le calculer, on inclut automatiquement ce p dans le produit.

- si n/2 < p <= n-k: l'exposant est forcément 0 donc on n'inclut pas ce p dans le produit.

- si sqrt(n) < p <= n/2: l'exposant est soit 0 ou 1, et ca dépend seulement du chiffre le plus à droite de n et k écrits en base p. C'est le cas de 5 et 7 dans mon exemple, on compare seulement le chiffre à droite de 15 et 4 pour déterminer l'exposant: 0<4 --> exposant=1.

- finalement, si p <= sqrt(n), il faut faire le calcul pour tous les chiffres de n et k, mais on sait que le maximum sera le nombre de chiffres de n en base p, moins 1, parce que c'est le maximum d'emprunts qu'on devra possiblement faire dans le calcul de n-k.

Cette méthode semble compliquée, mais à partir d'un certain n, ca va être vraiment plus rapide.

[LFC²]

Désolé pour la réponse tardive mais merci de vos réponses ! :we: