Permutation ou combinaison : Quelle est la différence entre la formule de permutation et la formule de combinaison ?

Permutation ou combinaison : Quelle est la différence entre la formule de permutation et la formule de combinaison ?

Voici la version courte.

Prenons comme exemple la sonnerie des cloches dans une église.

Une permutation est un ordonnancement des cloches. Vous déterminez le meilleur ordre pour les faire sonner.

Une combinaison est le choix des cloches. Vous choisissez les cloches à faire sonner. Si vous avez trop de cloches, vous les choisissez d’abord, puis vous pensez à les ordonner.

Cela donne lieu à l’identité familière : (n P r) = (n C r) * r!

La façon d’ordonner réléments parmi n est de choisir d’abord réléments parmi n, puis d’ordonner les réléments (r! )

Et, cela signifie (n P r) = n! / (n-r)! et (n C r) = n! / ( (n-r)! * r! )

Mais voulez-vous savoir comment vous en souvenir pour toujours ?

Je suis un grand fan de la pensée des premiers principes. Pour comprendre un problème, il faut aller au cœur du problème, et raisonner à partir de là.

Ne pas faire cela est généralement la source de la confusion : si je ne comprends pas comment les choses fonctionnent, je ne sais pas où accrocher les concepts. Mon cadre mental n’est pas complet, alors je décide de simplement m’en souvenir.

Comme vous pouvez l’imaginer, ce n’est pas idéal. Donc, de temps en temps, je me livre à un exercice consistant à dériver les choses de la source, et à construire l’intuition de la façon dont les choses fonctionnent.

Cette fois-ci, nous construisons l’intuition des permutations et des combinaisons.

Par exemple, savez-vous pourquoi la formule d’une combinaison est (n C r) ? D’où cela vient-il ? Et pourquoi utilise-t-on ici les factorielles ?

Commençons par la source. Les factorielles, permutations et combinaisons sont nées de mathématiciens jouant ensemble, un peu comme Steve Jobs et Steve Wozniak ont fondé Apple en jouant ensemble dans leur garage.

Tout comme la façon dont Apple est devenue une entreprise rentable à part entière, la simple factorielle, !, est devenue l’atome de tout un domaine des mathématiques : la combinatoire.

Oublions tout, commençons à penser de bas en haut.

Le premier cas d’utilisation intéressant connu est venu des églises au 17ème siècle.

Vous êtes-vous demandé comment les cloches sont sonnées dans les églises ? Il y a une machine qui les « sonne » dans l’ordre. On est passé aux machines parce que les cloches sont trop grosses. De plus, il y a des tonnes de cloches.

Comment les gens ont-ils trouvé la meilleure séquence pour les faire sonner ? Et s’ils voulaient changer les choses ? Comment pouvaient-ils trouver le meilleur son ? Chaque clocher avait jusqu’à 16 cloches!

On ne pouvait pas changer la vitesse à laquelle on pouvait sonner une cloche – les machines ne sonnaient qu’une cloche par seconde. La seule chose que vous pouviez faire était de changer l’ordre des cloches. Donc, ce défi consistait à trouver le meilleur ordre.

Pourrait-on, en cours de route, trouver aussi tous les ordres possibles ? Nous voulons connaître tous les ordres possibles pour savoir si cela vaut la peine de les essayer tous.

Un sonneur de cloches, Fabian Stedman a relevé ce défi.

Il a commencé avec 2 cloches. Quels sont les différents ordres dans lesquels il pourrait faire sonner ces cloches ?

1 et 2.
ou
2 et 1.

C’était logique. Il n’y avait pas d’autre moyen.

Et si on utilisait 3 cloches ?

1, 2, et 3.
1, 3, et 2.

Puis en commençant par la deuxième cloche,

2, 1, et 3.
2, 3, et 1.

Puis en commençant par la troisième cloche,

3, 1, et 2.
3, 2, et 1.

Total, 6.

Il a alors réalisé que cela ressemblait beaucoup à deux cloches !

S’il fixait la première cloche, alors le nombre de façons d’ordonner les deux cloches restantes était toujours de deux.

Combien de façons pouvait-il fixer la première cloche ? N’importe laquelle des 3 cloches pourrait être la bonne !

Ok, il a continué. Il a ensuite atteint 5 cloches.

C’est là qu’il a réalisé que faire les choses à la main est peu maniable. Vous n’avez qu’un temps limité dans la journée, vous devez faire sonner des cloches, vous ne pouvez pas être coincé à dessiner toutes les cloches possibles. Y avait-il un moyen de résoudre cela rapidement ?

Il est revenu à sa perspicacité.

S’il avait 5 cloches, et qu’il réparait la première cloche, tout ce qu’il avait à faire était de trouver comment commander 4 cloches.

Pour 4 cloches ? Eh bien, s’il avait 4 cloches, et qu’il a réparé la première cloche, tout ce qu’il avait à faire était de trouver comment commander 3 cloches.

Et il savait comment faire !

Donc, ordre de 5 cloches = 5 * ordre de 4 cloches.

Ordre de 4 cloches = 4 * ordre de 3 cloches

Ordre de 3 cloches = 3 * ordre de 2 cloches.

… Vous voyez le modèle, n’est-ce pas ?

Fait amusant : C’est la clé d’une technique de programmation appelée récursion.

Il l’a fait aussi. Bien que cela lui ait pris beaucoup plus de temps, puisque personne près de lui n’avait déjà découvert cela.

Il a donc compris que l’ordre de 5 cloches = 5 * 4 * 3 * 2 * 1.

Cette formule d’ordre, en 1808, est devenue connue sous le nom de factorielle.

Nous pensons à la notation factorielle comme à la base, mais l’idée existait bien avant d’avoir un nom. Ce n’est que lorsque le mathématicien français Christian Kramp a remarqué qu’elle était utilisée à quelques endroits qu’il l’a nommée la factorielle.

Cette mise en ordre des cloches est appelée une permutation.

Une permutation est une mise en ordre d’éléments.

Lorsqu’on apprend quelque chose, je pense qu’il est utile de regarder les choses sous tous les angles différents, pour solidifier la compréhension.

Et si on essayait de dériver la formule ci-dessus directement, sans essayer de réduire le problème à un plus petit nombre de cloches ?
Nous avons 5 espaces, non ?

Combien de façons pouvons-nous choisir la première cloche ? 5, car c’est le nombre de cloches que nous avons.

La deuxième cloche ? Eh bien, nous avons utilisé une cloche en la plaçant en première position, il nous reste donc 4 cloches.

La troisième cloche ? Eh bien, nous avons choisi les deux premières, donc il ne reste que 3 cloches parmi lesquelles choisir.

La quatrième cloche ? Il ne reste que 2 cloches, donc 2 possibilités.
La cinquième cloche ? Il n’en reste qu’une, donc 1 option.

Et voilà, le nombre total d’ordonnancements est de 5 * 4 * 3 * 2 * 1

On a donc notre première formule générale.

Le nombre de façons de commander N articles est N!

Maintenant, nous sommes confrontés à un problème différent. Le roi a ordonné que de nouvelles cloches soient fabriquées pour chaque église. Certaines sont belles, d’autres sont correctes, d’autres encore vous rendront sourds. Mais chacune est unique. Chacune produit son propre son. Une cloche assourdissante entourée de belles cloches peut sonner majestueusement.

Mais, notre clocher contient encore 5 cloches, donc nous devons trouver la meilleure commande parmi les 8 cloches que les artisans clocheurs ont fabriquées.

En utilisant la logique ci-dessus, nous pouvons procéder.

Pour la première cloche, nous pouvons choisir n’importe laquelle des 8 cloches.

Pour la deuxième cloche, nous pouvons choisir n’importe laquelle des 7 cloches restantes… et ainsi de suite.

A la fin, nous obtenons 8 * 7 * 6 * 5 * 4ordonnances possibles de 8 cloches dans 5 espaces.

Si vous êtes familier avec la version de la formule de (n P r), qui est n! / (n-r)!, ne vous inquiétez pas, nous allons dériver cela assez tôt, aussi !

Une mauvaise façon de la dériver est de multiplier le numérateur et le dénominateur par 3 ! Dans notre exemple ci-dessus –

nous obtenons 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.

Mais cela ne nous aide pas à comprendre pourquoi cette formule fonctionne. Avant d’en arriver là, jetons un coup d’œil au choix des choses, ou à la Combinaison.

La Combinaison

Maintenant que nous savons comment ordonner les choses, nous pouvons comprendre comment choisir les choses !

Regardons le même problème. Il y a un clocher avec 5 cloches, et vous avez 8 cloches. Cependant, en ce moment, vous ne voulez pas déterminer l’ordre des cloches (rappelez-vous que c’est ce qu’est une permutation).

Au lieu de cela, vous voulez choisir les 5 meilleures cloches, et laisser quelqu’un d’autre avec un meilleur goût en musique déterminer l’ordre. En fait, nous décomposons le problème en deux parties : D’abord, nous déterminons quelles cloches choisir. Ensuite, nous déterminons comment ordonner les cloches choisies.

Comment choisir les cloches ? C’est la « combinaison » des permutations et des combinaisons.

La combinaison est une sélection. Vous êtes sélectif. Vous choisissez 5 cloches parmi les 8 que vos artisans ont fabriquées.

Puisque nous savons comment commander des cloches, nous allons utiliser cette information pour savoir comment choisir des cloches. Cela vous semble impossible ? Attendez de voir les belles mathématiques impliquées.

Imaginons que toutes les cloches sont en ligne.

Avant de trouver toutes les façons de choisir les cloches, concentrons-nous sur une façon de choisir les cloches.

Une façon est de choisir 5 quelconques au hasard. Cela ne nous aide pas beaucoup à résoudre le problème, alors essayons une autre façon.

On met les cloches en ligne, et on choisit les 5 premières. C’est une façon de choisir les cloches.

Notez que, même si nous changeons la position des 5 premières cloches, le choix ne change pas. Ce sont toujours les mêmes une façon de choisir 5 cloches uniques.

C’est vrai pour les trois dernières cloches aussi.

Maintenant, la belle astuce mathématique – pour cette seule façon de choisir les 5 cloches, quels sont tous les ordonnancements de 8 cloches où nous choisissons exactement ces 5 cloches ? D’après l’image ci-dessus, c’est tous les ordonnancements des 5 cloches (5!) et tous les ordonnancements des trois cloches restantes (3!).

Donc, pour chaque façon unique de choisir 5 cloches, nous avons (5! * 3!) ordonnancements de 8 cloches.

Quel est le total des ordonnancements possibles de 8 cloches ? 8!.

Rappellez-vous, pour chaque choix des 5 premières cloches, nous avons (5! * 3!) ordonnancements de 8 cloches qui donnent le même choix.

Alors, si nous multiplions le nombre de façons de choisir les 5 premières cloches avec tous les ordonnancements possibles d’un choix, nous devrions obtenir le nombre total d’ordonnancements.

Ways to choose 5 bells * orderings of one choice = Total orderings

Donc,

Ways to choose 5 bells = the total possible orderings / total orderings of one choice.

En mathématiques, cela devient :

(8 C 5) = 8! / ( 5! * 3!)

Voilà, nous avons trouvé une explication intuitive pour savoir comment choisir 5 choses parmi 8.

Maintenant, nous pouvons généraliser cela. Si nous avons N choses, et que nous voulons en choisir R, cela signifie que nous traçons une ligne à R.

Ce qui signifie que les éléments restants seront N-R. Donc, pour un choix de R éléments, on a R! * (N-R)!ordonnances qui donnent les mêmes R éléments.

Pour toutes les façons de choisir R éléments, on a N! / (R! * (N-R)!) possibilités.

Le nombre de façons de choisir réléments parmi n est de (n C r) = n! / (r! * (n-r)!)

En termes familiers, (n C r) se prononce aussi n choose r, ce qui aide à solidifier l’idée que les combinaisons servent à choisir des éléments.

La permutation – revisitée

Avec la combinaison faite et dépoussiérée, revenons à la partie 2 de notre travail. Notre cher ami a choisi les 5 meilleures cloches en déterminant toutes les combinaisons possibles de 5 cloches.

C’est notre travail maintenant de trouver la mélodie parfaite en déterminant le nombre de commandes.

Mais, c’est la partie facile. Nous savons déjà comment commander 5 articles. C’est 5!, et nous avons terminé.

Donc, pour permuter (ordonner) 5 éléments sur 8, nous choisissons d’abord 5 éléments, puis nous ordonnons les 5 éléments.

En d’autres termes,

(8 P 5) = (8 C 5) * 5!

Et si nous développons la formule, (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!.

Et, nous avons bouclé la boucle vers notre formule originale, dérivée correctement.

Le nombre de façons d’ordonner réléments sur n est de (n P r) = n! / (n-r)!

Différence entre permutation et combinaison

J’espère que cela rend la différence entre permutations et combinaisons claire comme de l’eau de roche.

Les permutations sont des ordonnancements, tandis que les combinaisons sont des choix.

Pour ordonner N éléments, nous avons trouvé deux façons intuitives de déterminer la réponse. Les deux mènent à la réponse, N!.

Pour permuter 5 éléments sur 8, il faut d’abord choisir les 5 éléments, puis les ordonner. On choisit en utilisant (8 C 5), puis on ordonne les 5 en utilisant 5!.

Et l’intuition pour choisir R parmi N est de calculer tous les ordonnancements (N!) et de diviser par les ordonnancements où le premier R et le dernier N-R restent les mêmes (R! et (N-R)!).

Et, c’est tout ce qu’il y a à faire pour les permutations et les combinaisons.

Toute permutation et combinaison avancée utilise ceci comme base. Combinaison avec remplacement ? Même idée. Permutation avec des éléments identiques ? Même idée, seul le nombre d’ordonnancements change, puisque certains éléments sont identiques.

Si cela vous intéresse, nous pouvons aborder les cas complexes dans un autre exemple. Faites-le moi savoir sur Twitter.

Voyez d’autres articles sur mon blog, et rejoignez la liste de diffusion hebdomadaire.

Notes de fin

1. C’est ainsi que j’imagine qu’il a compris les choses. Ne le prenez pas comme une leçon d’histoire.
2. Les Indiens avaient, au 12ème siècle, 400 ans d’avance sur lui.