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è.