Mathématiques discrètes - Théorie du comptage
Dans la vie quotidienne, il est souvent nécessaire de connaître le nombre de tous les résultats possibles d'une série d'événements. Par exemple, de combien de manières un jury composé de 6 hommes et 4 femmes peut-il être choisi parmi 50 hommes et 38 femmes? Combien de numéros PAN à 10 lettres différents peuvent être générés de sorte que les cinq premières lettres soient des lettres majuscules, les quatre suivantes sont des chiffres et le dernier est à nouveau une lettre majuscule. Pour résoudre ces problèmes, la théorie mathématique du comptage est utilisée.Counting englobe principalement la règle de comptage fondamentale, la règle de permutation et la règle de combinaison.
Les règles de somme et de produit
le Rule of Sum et Rule of Product sont utilisés pour décomposer des problèmes de comptage difficiles en problèmes simples.
The Rule of Sum- Si une séquence de tâches $ T_1, T_2, \ dots, T_m $ peut être effectuée respectivement de façon $ w_1, w_2, \ dots w_m $ (la condition est qu'aucune tâche ne peut être effectuée simultanément), alors le nombre de façons faire une de ces tâches est $ w_1 + w_2 + \ dots + w_m $. Si nous considérons deux tâches A et B disjointes (ie $ A \ cap B = \ emptyset $), alors mathématiquement $ | A \ cup B | = | A | + | B | $
The Rule of Product- Si une séquence de tâches $ T_1, T_2, \ dots, T_m $ peut être effectuée dans $ w_1, w_2, \ dots w_m $ manières respectivement et que chaque tâche arrive après l'occurrence de la tâche précédente, alors il y a $ w_1 \ times w_2 \ times \ dots \ times w_m $ façons d'effectuer les tâches. Mathématiquement, si une tâche B arrive après une tâche A, alors $ | A \ fois B | = | A | \ fois | B | $
Exemple
Question- Un garçon vit à X et veut aller à l'école à Z. De son domicile X, il doit d'abord atteindre Y puis Y à Z. Il peut aller de X à Y par 3 lignes de bus ou 2 lignes de train. De là, il peut choisir entre 4 lignes de bus ou 5 lignes de train pour rejoindre Z. Combien de moyens y a-t-il pour aller de X à Z?
Solution- De X à Y, il peut aller de 3 $ + 2 = 5 $ (règle de somme). Par la suite, il peut aller de Y à Z de manière 4 $ + 5 = 9 $ (règle de somme). Par conséquent, de X à Z, il peut aller dans 5 $ \ fois 9 = 45 $ voies (règle du produit).
Permutations
UNE permutationest un arrangement de certains éléments dans lesquels l'ordre compte. En d'autres termes, une permutation est une combinaison ordonnée d'éléments.
Exemples
A partir d'un ensemble S = {x, y, z} en prenant deux à la fois, toutes les permutations sont -
$ xy, yx, xz, zx, yz, zy $.
Nous devons former une permutation de nombres à trois chiffres à partir d'un ensemble de nombres $ S = \ lbrace 1, 2, 3 \ rbrace $. Différents nombres à trois chiffres seront formés lorsque nous organiserons les chiffres. La permutation sera = 123, 132, 213, 231, 312, 321
Nombre de permutations
Le nombre de permutations de 'n' choses différentes prises 'r' à la fois est noté $ n_ {P_ {r}} $
$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$
où $ n! = 1.2.3. \ points (n - 1) .n $
Proof - Qu'il y ait 'n' éléments différents.
Il y a n nombre de façons de remplir la première place. Après avoir rempli la première place (n-1), il reste un nombre d'éléments. Par conséquent, il existe (n-1) façons de remplir la deuxième place. Après avoir rempli la première et la deuxième place, il reste (n-2) nombre d'éléments. Par conséquent, il existe (n-2) façons de remplir la troisième place. Nous pouvons maintenant généraliser le nombre de façons de remplir la r-ième place comme [n - (r – 1)] = n – r + 1
Donc, le non total. de façons de faire le plein de la première place à la r-ième place -
$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $
$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ points 3.2.1] / [(nr) (nr-1) \ points 3.2.1] $
Par conséquent,
$ n_ {P_ {r}} = n! / (nr)! $
Quelques formules importantes de permutation
S'il y a n éléments dont $ a_1 $ sont semblables d'un certain type, $ a_2 $ sont semblables d'un autre genre; $ a_3 $ sont semblables au troisième genre et ainsi de suite et $ a_r $ sont du genre $ r ^ {th} $, où $ (a_1 + a_2 + ... a_r) = n $.
Alors, le nombre de permutations de ces n objets est = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.
Nombre de permutations de n éléments distincts prenant n éléments à la fois = $ n_ {P_n} = n! $
Le nombre de permutations de n éléments différents prenant r éléments à la fois, lorsque x choses particulières occupent toujours des places définies = $ n-x_ {p_ {rx}} $
Le nombre de permutations de n éléments différents lorsque r éléments spécifiés se rencontrent toujours est - $ r! (n − r + 1)! $
Le nombre de permutations de n éléments différents lorsque r éléments spécifiés ne se rencontrent jamais est - $ n! - [r! (n − r + 1)!] $
Le nombre de permutations circulaires de n éléments différents pris x éléments au temps = $ ^ np_ {x} / x $
Le nombre de permutations circulaires de n choses différentes = $ ^ np_ {n} / n $
Quelques problèmes
Problem 1 - À partir d'un lot de 6 cartes différentes, de combien de façons pouvons-nous la permuter?
Solution- Comme nous prenons 6 cartes à la fois dans un jeu de 6 cartes, la permutation sera $ ^ 6P_ {6} = 6! = 720 $
Problem 2 - De combien de manières les lettres du mot «READER» peuvent-elles être arrangées?
Solution - Il y a un mot de 6 lettres (2 E, 1 A, 1D et 2R.) Dans le mot «READER».
La permutation sera $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $
Problem 3 - Comment les lettres du mot «ORANGE» peuvent-elles être disposées de manière à ce que les consonnes n'occupent que les positions paires?
Solution- Il y a 3 voyelles et 3 consonnes dans le mot 'ORANGE'. Nombre de façons d'arranger les consonnes entre elles $ = ^ 3P_ {3} = 3! = 6 $. Les 3 places vacantes restantes seront remplies par 3 voyelles dans $ ^ 3P_ {3} = 3! = 6 $ voies. Par conséquent, le nombre total de permutation est de 6 $ \ fois 6 = 36 $
Combinaisons
UNE combination est la sélection de certains éléments donnés dans lequel l'ordre n'a pas d'importance.
Le nombre de toutes les combinaisons de n choses, prises r à la fois est -
$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$
Problem 1
Trouvez le nombre de sous-ensembles de l'ensemble $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ ayant 3 éléments.
Solution
La cardinalité de l'ensemble est de 6 et nous devons choisir 3 éléments dans l'ensemble. Ici, la commande n'a pas d'importance. Par conséquent, le nombre de sous-ensembles sera $ ^ 6C_ {3} = 20 $.
Problem 2
Il y a 6 hommes et 5 femmes dans une pièce. De combien de façons pouvons-nous choisir 3 hommes et 2 femmes dans la pièce?
Solution
Le nombre de façons de choisir 3 hommes parmi 6 hommes est de $ ^ 6C_ {3} $ et le nombre de façons de choisir 2 femmes parmi 5 femmes est de $ ^ 5C_ {2} $
Par conséquent, le nombre total de voies est - $ ^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ fois 10 = 200 $
Problem 3
De combien de façons pouvez-vous choisir 3 groupes distincts de 3 étudiants sur un total de 9 étudiants?
Solution
Numérotons les groupes comme 1, 2 et 3
Pour choisir 3 élèves pour le 1 er groupe, le nombre de façons - $ ^ 9C_ {3} $
Le nombre de façons de choisir 3 élèves pour le deuxième groupe après avoir choisi le premier groupe - $ ^ 6C_ {3} $
Le nombre de façons de choisir 3 étudiants pour 3 ème groupe après avoir choisi 1 er et 2 e groupe - $ ^ 3C_ {3} $
Par conséquent, le nombre total de voies $ = ^ 9C_ {3} \ fois ^ 6C_ {3} \ fois ^ 3C_ {3} = 84 \ fois 20 \ fois 1 = 1680 $
Identité de Pascal
L'identité de Pascal, dérivée pour la première fois par Blaise Pascal au 17ème siècle, déclare que le nombre de façons de choisir k éléments parmi n éléments est égal à la somme du nombre de façons de choisir (k-1) éléments parmi (n-1) éléments et le nombre de façons de choisir des éléments parmi n-1 éléments.
Mathématiquement, pour tout entier positif k et n: $ ^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $
Proof -
$$ ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $$
$ = \ frac {(n-1)! } {(k-1)! (nk)! } + \ frac {(n-1)! } {k! (nk-1)! } $
$ = (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!}) $
$ = (n-1)! \ frac {n} {k! (nk)! } $
$ = \ frac {n! } {k! (nk)! } $
$ = n_ {C_ {k}} $
Principe du casier
En 1834, le mathématicien allemand Peter Gustav Lejeune Dirichlet énonça un principe qu'il appela le principe du dessinateur. Maintenant, il est connu comme le principe du casier.
Pigeonhole Principledéclare que s'il y a moins de pigeonniers que le nombre total de pigeons et que chaque pigeon est mis dans un pigeonnier, alors il doit y avoir au moins un pigeonnier avec plus d'un pigeon. Si n pigeons sont placés dans m casiers où n> m, il y a un trou avec plus d'un pigeon.
Exemples
Dix hommes sont dans une pièce et participent à des poignées de main. Si chaque personne serre la main au moins une fois et qu'aucun homme ne serre la main du même homme plus d'une fois, alors deux hommes ont participé au même nombre de poignées de main.
Il doit y avoir au moins deux personnes dans une classe de 30 dont les noms commencent par le même alphabet.
Le principe d'inclusion-exclusion
le Inclusion-exclusion principlecalcule le nombre cardinal de l'union de plusieurs ensembles non disjoints. Pour deux ensembles A et B, le principe énonce -
$ | A \ coupe B | = | A | + | B | - | A \ cap B | $
Pour trois ensembles A, B et C, le principe énonce -
$ | A \ tasse B \ tasse C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C | $
La formule généralisée -
$ | \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ limits_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limits_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ dots + (- 1) ^ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 | $
Problem 1
Combien d'entiers de 1 à 50 sont des multiples de 2 ou 3 mais pas les deux?
Solution
De 1 à 100, il y a 50 $ / 2 = 25 $ nombres qui sont des multiples de 2.
Il y a 50 $ / 3 = 16 $ nombres qui sont des multiples de 3.
Il y a des nombres de 50 $ / 6 = 8 $ qui sont des multiples de 2 et 3.
Donc, $ | A | = 25 $, $ | B | = 16 $ et $ | A \ cap B | = 8 $.
$ | A \ coupe B | = | A | + | B | - | A \ cap B | = 25 + 16 - 8 = 33 $
Problem 2
Dans un groupe de 50 étudiants, 24 aiment les boissons froides et 36 aiment les boissons chaudes et chaque étudiant aime au moins une des deux boissons. Combien aiment le café et le thé?
Solution
Soit X l'ensemble des étudiants qui aiment les boissons froides et Y l'ensemble des personnes qui aiment les boissons chaudes.
Donc, $ | X \ cup Y | = 50 $, $ | X | = 24 $, $ | Y | = 36 $
$ | X \ cap Y | = | X | + | Y | - | X \ bonnet Y | = 24 + 36 - 50 = 60 - 50 = 10 $
Par conséquent, il y a 10 étudiants qui aiment le thé et le café.