Principio combinatorio / inclusione-esclusione
Ho questo problema:
Un panificio vende $4$ varietà di ciambelle ma ce ne sono solo $6$ cioccolato e $7$ smaltato.
Quanti modi possiamo acquistare $12$ ciambelle se la selezione deve includere almeno $3$ ciambelle glassate (l'ordine è irrilevante)?
Nel mio tentativo, ho prima sottratto il $3$ smaltato dobbiamo includere le stelle e le barre utilizzate per trovare il numero di modi assumendo quantità illimitate di tutto: $12-3 = 9$ macchie da riempire, con $4$ varietà $= {12\choose9} = 220$ modi.
Da qui stavo pensando che possiamo sottrarre il numero di modi che includono più degli importi che abbiamo, ad esempio, i modi che hanno $7$, $8$, o $9$ ciambelle al cioccolato e modi che hanno $5$, $6$, $7$, $8$, o $9$ ciambelle glassate.
Tuttavia, non sono sicuro che questo sia il modo migliore per affrontare questo problema? Non capisco davvero dove sarebbe coinvolto il principio di inclusione-esclusione.
Risposte
La domanda implica che ce ne siano almeno $12$ ciambelle di ciascuna delle altre varietà disponibili.
Se scegliamo tre ciambelle glassate per cominciare, allora dobbiamo selezionare altre nove ciambelle dalle sei cioccolato, quattro glassate e un numero illimitato (per i nostri scopi) delle altre due varietà disponibili. Il numero di modi in cui possiamo farlo è il numero di soluzioni dell'equazione$$a + b + c + g = 9 \tag{1}$$ negli interi non negativi soggetti alle restrizioni che $c \leq 6$ e $g \leq 4$.
Una particolare soluzione dell'equazione 1 corrisponde al posizionamento di $4 - 1 = 3$segni di addizione in una fila di nove. Per esempio,$$1 1 1 + 1 1 1 1 + 1 1 +$$ corrisponde alla soluzione $a = 3$, $b = 4$, $c = 2$, $g = 0$. Il numero di tali soluzioni è$$\binom{9 + 4 - 1}{4 - 1} = \binom{12}{3}$$ poiché dobbiamo selezionare quale $4 - 1 = 3$ del $9 + 4 - 1 = 12$ posizioni richieste per $9$ quelli e $4 - 1 = 3$ i segni di addizione saranno riempiti con segni di addizione, come hai trovato.
Da questi dobbiamo sottrarre il numero di soluzioni in cui $c > 6$ o $g > 4$. Si noti che queste restrizioni non possono essere violate contemporaneamente da allora$7 + 5 = 12 > 9$.
Supponiamo che la restrizione $c \leq 6$è violato. Quindi almeno sette ciambelle al cioccolato devono essere inserite nella scatola. Permettere$c' = c - 7$. Poi$c'$è un numero intero non negativo. Sostituzione$c' + 7$ per $c$ nell'equazione 1 si ottiene \begin{align*} a + b + c' + 7 + g & = 9\\ a + b + c' + g & = 2 \tag{2} \end{align*} L'equazione 2 è un'equazione negli interi non negativi con $$\binom{2 + 4 - 1}{4 - 1} = \binom{5}{3}$$ soluzioni.
Supponiamo che la restrizione $g \leq 4$è violato. Quindi almeno cinque ciambelle glassate aggiuntive devono essere inserite nella scatola. Permettere$g' = g - 5$. Poi$g'$è un numero intero non negativo. Sostituzione$g' + 5$ per $g$ nell'equazione 1 si ottiene \begin{align*} a + b + c + g' + 5 & = 9\\ a + b + c + g' & = 4 \tag{3} \end{align*} L'equazione 3 è un'equazione negli interi non negativi con $$\binom{4 + 4 - 1}{4 - 1} = \binom{7}{3}$$ soluzioni.
Quindi, il numero di modi per selezionare $12$ ciambelle, di cui almeno tre glassate, delle quattro varietà date le restrizioni che sono disponibili solo sei ciambelle al cioccolato e sette glassate è $$\binom{12}{3} - \binom{5}{3} - \binom{7}{3}$$