Questo articolo si concentrerà su una sezione speciale della matematica chiamata combinatoria. Formule, regole, esempi di problem solving: tutto questo lo puoi trovare qui leggendo l'articolo fino alla fine.
Allora, cos'è questa sezione? La combinatoria si occupa del problema del conteggio di qualsiasi oggetto. Ma in questo caso gli oggetti non sono prugne, pere o mele, ma qualcos' altro. La combinatoria ci aiuta a trovare la probabilità di un evento. Ad esempio, quando si gioca a carte, qual è la probabilità che l'avversario abbia una carta vincente? O un esempio del genere: qual è la probabilità che otterrai esattamente il bianco da un sacchetto di venti palline? È per questo tipo di compiti che dobbiamo conoscere almeno le basi di questa sezione della matematica.
Configurazioni combinate
Considerando la questione dei concetti e delle formule di base della combinatoria, non possiamo non prestare attenzione alle configurazioni combinatorie. Sono usati non solo per la formulazione, ma anche per risolvere vari problemi combinatori. Esempi di tali modelli sono:
- posizionamento;
- permutazione;
- combinazione;
- composizione del numero;
- numero diviso.
Parleremo dei primi tre in modo più dettagliato in seguito, ma presteremo attenzione alla composizione e alla suddivisione in questa sezione. Quando parlano della composizione di un certo numero (diciamo, a), intendono la rappresentazione del numero a come somma ordinata di alcuni numeri positivi. E una divisione è una somma non ordinata.
Sezioni
Prima di passare direttamente alle formule della combinatoria e alla considerazione dei problemi, vale la pena prestare attenzione al fatto che la combinatoria, come altre sezioni della matematica, ha le sue sottosezioni. Questi includono:
- enumerativo;
- strutturale;
- estremo;
- Teoria di Ramsey;
- probabilistico;
- topologico;
- infinito.
Nel primo caso, stiamo parlando di combinatoria enumerativa, i problemi considerano l'enumerazione o il conteggio di diverse configurazioni che sono formate da elementi di insiemi. Di norma, a questi insiemi vengono imposte alcune restrizioni (distinguibilità, indistinguibilità, possibilità di ripetizione e così via). E il numero di queste configurazioni viene calcolato usando la regola dell'addizione o della moltiplicazione, di cui parleremo poco dopo. La combinatoria strutturale include le teorie dei grafi e dei matroidi. Un esempio di problema di combinatoria estrema è qual è la dimensione più grande di un grafo che soddisfa le seguenti proprietà… Nel quarto paragrafo abbiamo menzionato la teoria di Ramsey, che studia la presenza di strutture regolari in configurazioni casuali. probabilisticola combinatoria è in grado di rispondere alla domanda: qual è la probabilità che un dato insieme abbia una certa proprietà. Come puoi immaginare, la combinatoria topologica applica metodi in topologia. E infine, il settimo punto - la combinatoria infinita studia l'applicazione dei metodi combinatori agli insiemi infiniti.
Regola aggiunta
Tra le formule della combinatoria se ne possono trovare di abbastanza semplici, con le quali abbiamo familiarità da molto tempo. Un esempio è la regola della somma. Supponiamo di avere due azioni (C ed E), se si escludono a vicenda, l'azione C può essere eseguita in diversi modi (ad esempio, a) e l'azione E può essere eseguita in b modi, quindi ognuno di essi (C o E) può essere eseguita in modi a + b.
In teoria, questo è abbastanza difficile da capire, cercheremo di trasmettere l'intero punto con un semplice esempio. Prendiamo il numero medio di studenti in una classe - diciamo che è venticinque. Tra loro ci sono quindici ragazze e dieci ragazzi. Un assistente è assegnato alla classe ogni giorno. Quanti modi ci sono per assegnare un assistente di classe oggi? La soluzione al problema è abbastanza semplice, ricorreremo alla regola dell'addizione. Il testo dell'incarico non dice che solo i ragazzi o solo le ragazze possono essere in servizio. Pertanto, potrebbe essere una qualsiasi delle quindici ragazze o uno qualsiasi dei dieci ragazzi. Applicando la regola della somma, otteniamo un esempio abbastanza semplice che uno studente della scuola primaria può facilmente far fronte: 15 + 10. Dopo aver calcolato, otteniamo la risposta: venticinque. Cioè, ci sono solo venticinque modiassegna una classe di servizio per oggi.
Regola di moltiplicazione
La regola della moltiplicazione appartiene anche alle formule base della combinatoria. Cominciamo con la teoria. Supponiamo di dover eseguire diverse azioni (a): la prima azione viene eseguita in 1 modi, la seconda - in 2 modi, la terza - in 3 modi e così via fino a quando l'ultima a-azione non viene eseguita in modi sa. Quindi tutte queste azioni (di cui abbiamo un totale) possono essere eseguite in N modi. Come calcolare l'incognita N? La formula ci aiuterà in questo: N \u003d c1c2c3…ca.
Ancora una volta, nulla è chiaro in teoria, passiamo a un semplice esempio di applicazione della regola di moltiplicazione. Prendiamo la stessa classe di venticinque persone, in cui studiano quindici ragazze e dieci ragazzi. Solo che questa volta dobbiamo scegliere due assistenti. Possono essere solo maschi o femmine o un maschio con una femmina. Passiamo alla soluzione elementare del problema. Scegliamo il primo assistente, come abbiamo deciso nell'ultimo paragrafo, otteniamo venticinque opzioni possibili. La seconda persona in servizio può essere una qualsiasi delle persone rimanenti. Avevamo venticinque studenti, ne abbiamo scelto uno, il che significa che qualsiasi delle restanti ventiquattro persone può essere la seconda in servizio. Infine, applichiamo la regola della moltiplicazione e troviamo che i due assistenti possono essere scelti in seicento modi. Abbiamo ottenuto questo numero moltiplicando venticinque e ventiquattro.
Scambia
Ora considereremo un' altra formula combinatoria. In questa sezione dell'articolo, noiParliamo di permutazioni. Considera subito il problema con un esempio. Prendiamo le palle da biliardo, ne abbiamo l'ennesima cifra. Dobbiamo calcolare: quante opzioni ci sono per disporle in fila, cioè per fare un set ordinato.
Iniziamo, se non abbiamo le palle, allora abbiamo anche zero opzioni di piazzamento. E se abbiamo una pallina, anche la disposizione è la stessa (matematicamente, questo può essere scritto come segue: Р1=1). Due palline possono essere disposte in due modi diversi: 1, 2 e 2, 1. Pertanto, Р2=2. Tre palline possono essere disposte in sei modi (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. E se non ci sono tre di queste palle, ma dieci o quindici? Elencare tutte le opzioni possibili è lunghissimo, poi la combinatoria ci viene in aiuto. La formula di permutazione ci aiuterà a trovare la risposta alla nostra domanda. Pn=nP(n-1). Se proviamo a semplificare la formula, otteniamo: Pn=n (n - 1) … 21. E questo è il prodotto dei primi numeri naturali. Tale numero è chiamato fattoriale ed è indicato come n!
Consideriamo il problema. Il leader ogni mattina costruisce il suo distaccamento in linea (venti persone). Ci sono tre migliori amici nel distaccamento: Kostya, Sasha e Lesha. Qual è la probabilità che siano uno accanto all' altro? Per trovare la risposta alla domanda, devi dividere la probabilità di un risultato "buono" per il numero totale di risultati. Il numero totale di permutazioni è 20!=2,5 quintilioni. Come contare il numero di risultati "buoni"? Supponiamo che Kostya, Sasha e Lesha siano un superuomo. Allora noiAbbiamo solo diciotto soggetti. Il numero di permutazioni in questo caso è 18=6,5 quadrilioni. Con tutto questo, Kostya, Sasha e Lesha possono muoversi arbitrariamente tra loro nella loro tripla indivisibile, e questo è di più 3!=6 opzioni. Quindi abbiamo 18 costellazioni "buone" in totale!3! Non ci resta che trovare la probabilità desiderata: (18!3!) / 20! Che è circa 0,016. Se convertito in percentuale, risulta essere solo 1,6%.
Alloggio
Ora considereremo un' altra formula combinatoria molto importante e necessaria. L'alloggio è il nostro prossimo numero, che vi suggeriamo di considerare in questa sezione dell'articolo. Diventeremo più complicati. Assumiamo di voler considerare possibili permutazioni, solo non dall'intero insieme (n), ma da uno più piccolo (m). Cioè, consideriamo permutazioni di n elementi di m.
Le formule di base della combinatoria non dovrebbero essere solo memorizzate, ma comprese. Anche se diventano più complicati, poiché non abbiamo un parametro, ma due. Supponiamo che m \u003d 1, quindi A \u003d 1, m \u003d 2, quindi A \u003d n(n - 1). Se semplifichiamo ulteriormente la formula e passiamo alla notazione usando i fattoriali, otteniamo una formula abbastanza concisa: A \u003d n! / (n - m)!
Combinazione
Abbiamo considerato quasi tutte le formule di base della combinatoria con esempi. Passiamo ora alla fase finale di considerare il corso base di combinatoria - conoscere la combinazione. Ora sceglieremo m elementi dagli n che abbiamo, mentre li sceglieremo tutti in tutti i modi possibili. In che modo questo è diverso dall'alloggio? Noi nonconsidera l'ordine. Questo set non ordinato sarà una combinazione.
Introduci subito la notazione: C. Prendiamo piazzamenti di m palline su n. Smettiamo di prestare attenzione all'ordine e otteniamo combinazioni ripetute. Per ottenere il numero di combinazioni, dobbiamo dividere il numero di posizionamenti per m! (m fattoriale). Cioè, C \u003d A / m! Quindi, ci sono alcuni modi per scegliere tra n palline, approssimativamente uguali a quante scegliere quasi tutto. C'è un'espressione logica per questo: scegliere poco è come buttare via quasi tutto. È anche importante ricordare a questo punto che è possibile ottenere il numero massimo di combinazioni quando si tenta di selezionare metà degli elementi.
Come scegliere una formula per risolvere un problema?
Abbiamo esaminato in dettaglio le formule di base della combinatoria: posizionamento, permutazione e combinazione. Ora il nostro compito è facilitare la scelta della formula necessaria per risolvere il problema in combinatoria. Puoi usare il seguente schema piuttosto semplice:
- Chiediti: l'ordine degli elementi è preso in considerazione nel testo del problema?
- Se la risposta è no, usa la formula della combinazione (C=n! / (m!(n - m)!)).
- Se la risposta è no, allora devi rispondere a un' altra domanda: tutti gli elementi sono inclusi nella combinazione?
- Se la risposta è sì, usa la formula di permutazione (P=n!).
- Se la risposta è no, usa la formula di allocazione (A=n! / (n - m)!).
Esempio
Abbiamo considerato gli elementi della combinatoria, le formule e alcune altre questioni. Ora passiamo aconsiderando un problema reale. Immagina di avere un kiwi, un'arancia e una banana davanti a te.
Domanda uno: in quanti modi possono essere riorganizzati? Per fare ciò, utilizziamo la formula di permutazione: P=3!=6 vie.
Domanda due: in quanti modi si può scegliere un frutto? Questo è ovvio, abbiamo solo tre opzioni: scegli kiwi, arancia o banana, ma applichiamo la formula di combinazione: C \u003d 3! / (2!1!)=3.
Domanda tre: in quanti modi si possono scegliere due frutti? Quali opzioni abbiamo? kiwi e arancia; kiwi e banana; arancia e banana. Cioè, tre opzioni, ma è facile da controllare usando la formula di combinazione: C \u003d 3! / (1!2!)=3
Domanda quattro: in quanti modi si possono scegliere tre frutti? Come puoi vedere, c'è solo un modo per scegliere tre frutti: prendi un kiwi, un'arancia e una banana. C=3! / (0!3!)=1.
Domanda cinque: in quanti modi puoi scegliere almeno un frutto? Questa condizione implica che possiamo prendere uno, due o tutti e tre i frutti. Pertanto, aggiungiamo C1 + C2 + C3=3 + 3 + 1=7. Cioè, abbiamo sette modi per prendere almeno un frutto dalla tavola.
