Want to make creations as awesome as this one?

Transcript

Start

Prof. Laura Garozzo

ELEMENTI DI CALCOLO COMBINATORIO

Premessa

Il calcolo combinatorio fornisce gli strumenti di calcolo per determinare il numero di raggruppamenti diversi che si possono formare con un numero k di oggetti presi da un insieme contenenti n oggetti, o elementi, a1 ,a2 ,a3 ,a4 , … an-1, an

TIPI DI RAGGRUPPAMENTI

DISPOSIZIONI: quando l’ordine dei k elementi è importante. PERMUTAZIONI: casi particolari di disposizioni (k = n) COMBINAZIONI: quando l’ordine degli elementi non ha alcuna importanza.

SEMPLICI: quando gli oggetti sono tutti diversiCON RIPETIZIONE: quando gli oggetti vi figurano una o più volte

I Raggruppamenti possono essere:

DISPOSIZIONI

DISPOSIZIONI SEMPLICI

Si chiamano Disposizioni semplici di classe k i raggruppamenti composti da k elementi che si possono formare a partire da un insieme di n elementi, dove tali raggruppamenti differiscono tra loro o per la loro natura o per l’ordine. ( k <=n )

Fattoriale

Il numero di DISPOSIZIONI SEMPLICI di n oggetti distinti presi k per volta è dove n! è il fattoriale del numero n.

VideoEsercizio

DISPOSIZIONI SEMPLICI - ESEMPIO

A B C

A B D

A C D

B C D

DA DB DC

CA CB CD

BA BC BD

AB AC AD

Il n° di disposizioni semplici di 4 oggetti distinti presi a 2 a 2 è: D4,2 = 4!/(4-2)! = 4!/2!= 4‧3 = 12

DATE LE 4 LETTERE A,B,C,D QUANTI SONO I GRUPPI DI DUE LETTERE CHE DIFFERISCONO TRA LORO PER ORDINE O NATURA?

e non è necessariamente n > k

DISPOSIZIONI CON RIPETIZIONE

Il numero di DISPOSIZIONI CON RIPETIZIONE di n oggetti distinti presi k per volta è

DISPOSIZIONI CON RIPET. - ESEMPIO

VideoEsercizio

A B C D

A B C D

A B C D

A B C D

DA DB DC DD

CA CB CC CD

BA BB BC BD

AA AB AC AD

Il n° di disposizioni con ripetizione di 4 oggetti distinti presi a 2 a 2 è: D’4,2 = 42 = 16

DATE LE 4 LETTERE A,B,C,D QUANTI SONO I GRUPPI di DUE LETTERE CHE DIFFERISCONO TRA LORO PER ORDINE O NATURA CON RIPETIZIONE?

Quanti numeri di 6 cifre, tutte pari e diverse da zero, si possono scrivere?

    DISPOSIZIONI - Esercizi

    Un club ha 15 membri. In quanti modi possono essere scelti un presidente, un vice-presidente e un segretario (supponendo che nessun membro possa avere piu`di una carica)?

      Quante sono le combinazioni possibili per un lucchetto a 5 cifre?

        DISPOSIZIONI - Esercizi

        Quanti sono i numeri di 4 cifre tutte distinte e non nulle nel sistema decimale?

          Soluzione

          Soluzione

          DISPOSIZIONI - Esercizi

          Quante parole anche prive di significato si possono formare con 3 lettere dell’alfabeto italiano tutte diverse tra loro?In quanti modi diversi 7 persone si possono sedere su 5 poltrone allineate di un cinema?Quanti numeri di 3 cifre anche uguali tra loro si possono costruire con i primi 5 numeri naturali?In quanti modi si possono scegliere, tra 10 ragazzi, un portiere, un arbitro e un attaccante?

          PERMUTAZIONI

          PERMUTAZIONI SEMPLICI

          Le permutazioni semplici di n oggetti distinti sono tutti i possibili raggruppamenti contenenti la totalità degli n oggetti che differiscono solo per l’ordine. Sono un caso particolare di disposizioni Dn,k dove n = k

          Quanti numeri di 4 cifre, fra loro diversi, si possono formare con le cifre 1, 3, 5, 7 ?

          P3 = D3,3 = n! = 3‧2‧1 = 6

          PERMUTAZIONI - Esempi

          Costruire e contare tutti i possibili anagrammi della parola «APE» A P E - A E P - P A E - P E A - E A P - E P A

          PERMUTAZIONI CON RIPETIZIONE

          Nel caso in cui tra gli n oggetti sono presenti oggetti uguali in numero α, β, γ, etc, tra tutte le permutazioni possibili dobbiamo escludere quelle che si ripetono come ordine e tipo di oggetto. In questo caso il numero delle permutazioni possibili è dato dalla formula:

          Info

          PERMUTAZIONI CON RIPETIZIONE - Esempi

          ALA - ALA - AAL - AAL - LAA - LAA

          COSTRUIRE E CONTARE GLI ANAGRAMMI (anche privi di senso) DELLA PAROLA «ALA»

          PERMUTAZIONI - Esercizi

          Tra tutti i numeri di 10 cifre tutte diverse tra loro, quanti sono i multipli di 10?

              Click sul numero per le soluzioni

              Calcolare il numero di anagrammi distinti che si possono costruire con la parola MATEMATICAUn negoziante deve eseguire 5 consegne di merce acquistata da clienti abitanti in 56 zone diverse della città. Determinare il numero di modi differenti di eseguire le consegneQuanti numeri naturali diversi di 6 cifre si possono formare con le cifre del numero 775551 ?

              PERMUTAZIONI - Esercizi

              Quanti sono gli anagrammi possibili della parola MAMMA?

                  COMBINAZIONI

                  COMBINAZIONI SEMPLICI

                  Si chiamano combinazioni tutti i raggruppamenti formati da k oggetti che si possono formare a partire da n elementi (con k < n) tenendo conto che ogni gruppo si differenzia da un altro solo per la natura degli elementi componenti e non per il loro ordine

                  Approfondimenti:Coefficienti binomialie Binomio di Newton

                  Il numero di combinazioni semplici si indica anche con il simbolo che si legge “n su k”, ed è detto “coefficiente binomiale” di ordine n e di classe k

                  Si tratta di combinazioni semplici di n = 4 oggetti di classe k = 2

                  A B C

                  A B D

                  A C D

                  B C D

                  DA DB DC

                  CA CB CD

                  BA BC BD

                  AB AC AD

                  COMBINAZIONI - Esempio

                  DATE LE 4 LETTERE A, B, C, D QUANTE SONO LE COPPIE DISTINTE CHE SI POSSONO FORMARE CHE DIFFERISCONO SOLO PER LA NATURA DEGLI ELEMENTI CHE LI COMPONGONO E NON PER L’ORDINE?

                  COMBINAZIONI CON RIPETIZIONE

                  Si chiamano combinazioni con ripetizione le combinazioni in cui un elemento può comparire più volte o meglio può essere ripetuto più volte all’interno di un raggruppamento. In generale il numero di COMBINAZIONI CON RIPETIZIONE è dato dalla formula:

                    COMBINAZ. con RIP. - Esempio

                    a a a a a b a b b b b b

                    DATE LE 2 LETTERE a,b QUANTE SONO LE COMBINAZIONI CON RIPETIZIONE DI TALI OGGETTI PRESI A 3 A 3?

                    COMBINAZIONI - Esercizi

                    Quanti ambi, terne e quaterne si possono formare con i 90 numeri del Lotto?

                        Schema riassuntivo

                        ESERCIZI SVOLTI

                        FATTORIALE DI UN NUMERO

                        FATTORIALE

                        Il fattoriale di un numero positivo n è una funzione avente come dominio N ed è il prodotto di tutti gli interi positivi minori o uguali ad n.

                        Back

                        0! = 1

                        Si può scrivere in modo ricorsivo Per convenzione si pone:

                        COEFFICIENTE BINOMIALE

                        COEFFICIENTE BINOMIALE

                        Il coefficiente binomiale (che si legge “n su k”) è un numero intero non negativo definito dalla seguente formula: con k, n numeri interi; 0 ≤ k ≤ n

                        PROPRIETÀ DEL COEFFICIENTE BINOMIALE

                        ALTRE PROPRIETÀ DEL COEFFICIENTE BINOMIALE

                        COEFFICIENTI BINOMIALI E IL BINOMIO DI NEWTON

                        IL TRIANGOLO DI TARTAGLIA

                        Analizzando il calcolo della generica potenza di un binomio è evidente che tutti gli sviluppi sono dei polinomi omogenei e completi, di grado uguale all’esponente della potenza. Ordinando gli sviluppi secondo le potenze decrescenti di uno dei due monomi, si nota che i loro coefficienti sono numeri del seguente schema, chiamato Triangolo di Tartaglia

                        (a + b)1 = a + b(a + b)2 = a2 + 2ab + b2(a + b)3 = a3 + 3a2b + 3ab2 + b3

                        Il coefficiente binomiale è utile nello sviluppo della potenza di un binomio. Si considerino due numeri reali qualunque . Sono già note le formule:

                        Back

                        Ebbene, qualunque siano i due numeri a e b e qualunque sia n intero positivo, si ha

                        Questo triangolo può essere riscritto con lo sviluppo della potenza secondo Newton che fa uso delle combinazioni:

                        Abbiamo n = 5, α = 3 (lettera M), β = 2 (lettera A),

                            1 - SOLUZIONE

                            D10,3 = 10!/3!

                            Calcoliamo ad esempio il numero di anagrammi della parola ESSERE.E1S1S2E2RE3Le permutazioni possibili sono 6! = 720, ma teniamo presente che, ad es., E1RE2S1S2E3 ed E2RE3S2S1E1sono la stessa parola. In qualunque modo si permutano le tre E, mantenendole nelle stesse posizioni, si ottiene lo stesso anagramma. Le tre E si possono permutare in 3! modi diversi. Dobbiamo dividere quindi il totale delle permutazioni per 3!Stesso discorso per le 2 S che si possono permutare in 2! modi diversi. In definitiva le permutazioni possibili sono 6!/3!2!

                            Soluzione
                            P3 = 4! = 24
                            D7,5 = 7!/5!

                            Abbiamo n = 10, α = 2 (lettera M), β = 3 (lettera A), γ = 2 (lettera T)

                                2 - SOLUZIONE

                                D'5,3 = 53

                                SOLUZIONE

                                Si osservi che ogni riga inizia e termina con 1 e gli altri valori si ottengono come somma dei due elementi sovrastanti.

                                SOLUZIONE

                                D21,3 = 21!/3!