Matematica discreta - Teoria del conteggio
Nella vita quotidiana, molte volte è necessario scoprire il numero di tutti i possibili risultati per una serie di eventi. Ad esempio, in quanti modi può essere scelta una giuria composta da 6 uomini e 4 donne tra 50 uomini e 38 donne? Quanti numeri PAN di 10 lettere differenti possono essere generati in modo tale che le prime cinque lettere siano alfabeti maiuscoli, le quattro successive siano cifre e l'ultima sia di nuovo maiuscola. Per risolvere questi problemi, viene utilizzata la teoria matematica del conteggio.Counting comprende principalmente la regola di conteggio fondamentale, la regola di permutazione e la regola di combinazione.
Le regole della somma e del prodotto
Il Rule of Sum e Rule of Product sono usati per scomporre problemi di conteggio difficili in problemi semplici.
The Rule of Sum- Se una sequenza di attività $ T_1, T_2, \ dots, T_m $ può essere eseguita rispettivamente in $ w_1, w_2, \ dots w_m $ (la condizione è che nessuna attività possa essere eseguita simultaneamente), allora il numero di modi per fare una di queste attività è $ w_1 + w_2 + \ dots + w_m $. Se consideriamo due attività A e B che sono disgiunte (cioè $ A \ cap B = \ emptyset $), allora matematicamente $ | A \ cup B | = | A | + | B | $
The Rule of Product- Se una sequenza di attività $ T_1, T_2, \ dots, T_m $ può essere eseguita rispettivamente in $ w_1, w_2, \ dots w_m $ e ogni attività arriva dopo l'occorrenza dell'attività precedente, allora ci sono $ w_1 \ volte w_2 \ times \ dots \ times w_m $ modi per eseguire le attività. Matematicamente, se un'attività B arriva dopo un'attività A, allora $ | A \ volte B | = | A | \ times | B | $
Esempio
Question- Un ragazzo vive a X e vuole andare a scuola a Z. Da casa sua X deve prima raggiungere Y e poi Y a Z. Può andare da X a Y con 3 linee di autobus o 2 linee di treno. Da lì, può scegliere 4 linee di autobus o 5 linee di treno per raggiungere Z. Quanti modi ci sono per andare da X a Z?
Solution- Da X a Y, può andare in $ 3 + 2 = 5 $ modi (regola della somma). Successivamente, può andare da Y a Z in $ 4 + 5 = 9 $ modi (regola della somma). Quindi da X a Z può andare in $ 5 \ times 9 = 45 $ (Regola del prodotto).
Permutazioni
UN permutationè una disposizione di alcuni elementi in cui l'ordine è importante. In altre parole, una permutazione è una combinazione ordinata di elementi.
Esempi
Da un insieme S = {x, y, z} prendendo due alla volta, tutte le permutazioni sono -
$ xy, yx, xz, zx, yz, zy $.
Dobbiamo formare una permutazione di tre cifre da un insieme di numeri $ S = \ lbrace 1, 2, 3 \ rbrace $. Quando sistemiamo le cifre, verranno formati diversi numeri a tre cifre. La permutazione sarà = 123, 132, 213, 231, 312, 321
Numero di permutazioni
Il numero di permutazioni di 'n' cose diverse prese 'r' alla volta è indicato con $ n_ {P_ {r}} $
$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$
dove $ n! = 1.2.3. \ punti (n - 1) .n $
Proof - Lascia che ci siano 'n' diversi elementi.
Ci sono molti modi per riempire il primo posto. Dopo aver riempito il primo posto (n-1) rimane il numero di elementi. Quindi, ci sono (n-1) modi per riempire il secondo posto. Dopo aver riempito il primo e il secondo posto, rimane (n-2) il numero di elementi. Quindi, ci sono (n-2) modi per riempire il terzo posto. Possiamo ora generalizzare il numero di modi per riempire la r-esima posizione come [n - (r – 1)] = n – r + 1
Quindi, il totale no. di modi per fare il pieno dal primo posto fino al r-esimo posto -
$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $
$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ dots 3.2.1] / [(nr) (nr-1) \ dots 3.2.1] $
Quindi,
$ n_ {P_ {r}} = n! / (nr)! $
Alcune importanti formule di permutazione
Se ci sono n elementi di cui $ a_1 $ sono simili di qualche tipo, $ a_2 $ sono simili di un altro tipo; $ a_3 $ sono simili di terzo tipo e così via e $ a_r $ sono di $ r ^ {th} $ tipo, dove $ (a_1 + a_2 + ... a_r) = n $.
Quindi, il numero di permutazioni di questi n oggetti è = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.
Numero di permutazioni di n elementi distinti che prendono n elementi alla volta = $ n_ {P_n} = n! $
Il numero di permutazioni di n elementi dissimili che prendono r elementi alla volta, quando x cose particolari occupano sempre posti definiti = $ n-x_ {p_ {rx}} $
Il numero di permutazioni di n elementi dissimili quando r le cose specificate si uniscono sempre è - $ r! (n − r + 1)! $
Il numero di permutazioni di n elementi dissimili quando r specificate cose non si uniscono mai è - $ n! - [r! (n − r + 1)!] $
Il numero di permutazioni circolari di n diversi elementi presi x elementi alla volta = $ ^ np_ {x} / x $
Il numero di permutazioni circolari di n cose diverse = $ ^ np_ {n} / n $
Alcuni problemi
Problem 1 - Da un mazzo di 6 carte diverse, in quanti modi possiamo permutarlo?
Solution- Dato che stiamo prendendo 6 carte alla volta da un mazzo di 6 carte, la permutazione sarà $ ^ 6P_ {6} = 6! = 720 $
Problem 2 - In quanti modi possono essere disposte le lettere della parola "READER"?
Solution - La parola "READER" contiene 6 lettere (2 E, 1 A, 1D e 2R.).
La permutazione sarà $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $
Problem 3 - In che modo le lettere della parola "ARANCIONE" possono essere disposte in modo che le consonanti occupino solo le posizioni pari?
Solution- Ci sono 3 vocali e 3 consonanti nella parola "ARANCIONE". Numero di modi per disporre le consonanti tra di loro $ = ^ 3P_ {3} = 3! = 6 $. I restanti 3 posti vacanti saranno riempiti da 3 vocali in $ ^ 3P_ {3} = 3! = 6 $ modi. Quindi, il numero totale di permutazioni è $ 6 \ volte 6 = 36 $
Combinazioni
UN combination è la selezione di alcuni elementi dati in cui l'ordine non ha importanza.
Il numero di tutte le combinazioni di n cose, prese r alla volta è -
$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$
Problem 1
Trova il numero di sottoinsiemi dell'insieme $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ con 3 elementi.
Solution
La cardinalità dell'insieme è 6 e dobbiamo scegliere 3 elementi dall'insieme. Qui, l'ordine non ha importanza. Quindi, il numero di sottoinsiemi sarà $ ^ 6C_ {3} = 20 $.
Problem 2
Ci sono 6 uomini e 5 donne in una stanza. In quanti modi possiamo scegliere 3 uomini e 2 donne dalla stanza?
Solution
Il numero di modi per scegliere 3 uomini da 6 uomini è $ ^ 6C_ {3} $ e il numero di modi per scegliere 2 donne da 5 donne è $ ^ 5C_ {2} $
Quindi, il numero totale di modi è - $ ^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200 $
Problem 3
In quanti modi puoi scegliere 3 gruppi distinti di 3 studenti da un totale di 9 studenti?
Solution
Numeriamo i gruppi come 1, 2 e 3
Per la scelta di 3 studenti per 1 ° gruppo, il numero di modi - $ ^ 9C_ {3} $
Il numero di modi per scegliere 3 studenti per il 2 ° gruppo dopo aver scelto il 1 ° gruppo - $ ^ 6C_ {3} $
Il numero di modi per scegliere 3 studenti per 3 ° gruppo dopo aver scelto 1 ° e 2 ° gruppo - $ ^ 3C_ {3} $
Quindi, il numero totale di modi $ = ^ 9C_ {3} \ times ^ 6C_ {3} \ times ^ 3C_ {3} = 84 \ times 20 \ times 1 = 1680 $
Identità di Pascal
L'identità di Pascal, derivata per la prima volta da Blaise Pascal nel XVII secolo, afferma che il numero di modi per scegliere k elementi da n elementi è uguale alla somma del numero di modi per scegliere (k-1) elementi da (n-1) elementi e il numero di modi per scegliere gli elementi da n-1 elementi.
Matematicamente, per qualsiasi numero intero positivo k e 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}} $
Principio della casella
Nel 1834, il matematico tedesco Peter Gustav Lejeune Dirichlet, affermò un principio che chiamò principio del cassetto. Ora, è noto come il principio della casella.
Pigeonhole Principleafferma che se ci sono meno caselle del numero totale di piccioni e ogni piccione viene messo in una tana, allora deve esserci almeno una casella con più di un piccione. Se n piccioni vengono messi in m caselle dove n> m, c'è un buco con più di un piccione.
Esempi
Dieci uomini sono in una stanza e stanno prendendo parte alle strette di mano. Se ogni persona stringe la mano almeno una volta e nessun uomo stringe la mano allo stesso uomo più di una volta, due uomini hanno preso parte allo stesso numero di strette di mano.
Ci devono essere almeno due persone in una classe di 30 i cui nomi iniziano con lo stesso alfabeto.
Il principio di inclusione-esclusione
Il Inclusion-exclusion principlecalcola il numero cardinale dell'unione di più insiemi non disgiunti. Per due set A e B, il principio afferma:
$ | A \ tazza B | = | A | + | B | - | A \ cap B | $
Per tre insiemi A, B e C, il principio afferma:
$ | A \ cup B \ cup C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C | $
La formula generalizzata -
$ | \ 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
Quanti numeri interi da 1 a 50 sono multipli di 2 o 3 ma non entrambi?
Solution
Da 1 a 100, ci sono $ 50/2 = 25 $ numeri che sono multipli di 2.
Ci sono $ 50/3 = 16 $ numeri che sono multipli di 3.
Ci sono $ 50/6 = 8 $ numeri che sono multipli di 2 e 3.
Quindi, $ | A | = 25 $, $ | B | = 16 $ e $ | A \ cap B | = 8 $.
$ | A \ tazza B | = | A | + | B | - | A \ cap B | = 25 + 16 - 8 = 33 $
Problem 2
In un gruppo di 50 studenti 24 gradiscono le bevande fredde e 36 gradiscono le bevande calde e ogni studente gradisce almeno una delle due bevande. A quanti piacciono sia il caffè che il tè?
Solution
Che X sia l'insieme di studenti a cui piacciono le bevande fredde e Y l'insieme di persone che amano le bevande calde.
Quindi, $ | X \ cup Y | = 50 $, $ | X | = 24 $, $ | Y | = 36 $
$ | X \ cap Y | = | X | + | Y | - | X \ cup Y | = 24 + 36-50 = 60-50 = 10 $
Quindi, ci sono 10 studenti a cui piacciono sia il tè che il caffè.