10 giubbotti in 3 giorni

[Admin]

Il signor Rossi indossa almeno un giubbotto al giorno.
In 3 giorni ha indossato un totale di 10 giubbotti diversi.
In quanti modi ha potuto indossare i 10 giubbotti?

Saluti
Admin

[Quelo]

Se non consideriamo il tipo di giubbotto, ma solo la quantità, le combinazioni possibili sono 36

Per esempio: il primo giorno indossa 1 giubbotto, il secondo 1 giubbotto e il terzo gli altri 8 (1,1,8)
Oppure il primo giorno indossa 1 giubbotto, il secondo 2 giubbotti e il terzo gli altri 7 (1,2,7)
e così via

Codice: Seleziona tutto

1,1,8 - 1,8,1 - 8,1,1 = 3 combinazioni
1,2,7 - 1,7,2 - 2,1,7 - 2,7,1 - 7,1,2 - 7,2,1 = 6 combinazioni
1,3,6 - ... = 6 combinazioni
1,4,5 - ... = 6 combinazioni
2,3,5 - ... = 6 combinazioni
2,2,6 - ... = 3 combinazioni
3,3,4 - ... = 3 combinazioni
4,4,2 - ... = 3 combinazioni

36 combinazioni, 3 giorni per ogni combinazione, ci vogliono 108 giorni

Poiché i giubbotti sono diversi, dobbiamo tenere conto di quali giubbotti indossa ogni giorno.
Se i miei calcoli sono esatti, le combianzioni possibili sono 55980 pari a 167940 giorni che sono circa 460 anni

Prendiamo una combinazione tipo (1,1,8)
Il primo giorno indossa uno dei 10 giubbotti, il secondo uno dei 9 rimanenti, il terzo giorni gli altri 8
$\displaystyle C=\binom{10}{1}\binom{9}{1}=\frac{10!}{1!9!}\frac{9!}{1!8!}=\frac{10!}{1!1!8!}=90$

con (1,2,7) avremo
$\displaystyle C=\binom{10}{1}\binom{9}{2}=\frac{10!}{1!9!}\frac{9!}{2!7!}=\frac{10!}{1!2!7!}=360$

con (2,3,5) avremo
$\displaystyle C=\binom{10}{2}\binom{8}{3}=\frac{10!}{2!8!}\frac{8!}{3!5!}==\frac{10!}{2!3!5!}=2520$

più in generale con (a,b,c)
$\displaystyle C=\binom{a+b+c}{a}\binom{b+c}{b}=\frac{(a+b+c)!}{a!b!c!}$

Moltiplicando per le combinazioni viste sopra, otteniamo il nostro risultato

$\displaystyle C=3\left(\frac{10!}{1!1!8!}+\frac{10!}{2!2!6!}+\frac{10!}{3!3!4!}+\frac{10!}{4!4!2!}\right)+6\left(\frac{10!}{1!2!7!}+\frac{10!}{1!3!6!}+\frac{10!}{1!4!5!}+\frac{10!}{2!3!5!}\right)=55980$

Se conta anche l'ordine in cui i giubbotti vengono indossati, le cose si complicano un po'

++++++++++++++

Mi correggo, se consideriamo anche l'ordine in cui i giubbotti vengono indossati, dobbiamo moltiplicare ogni combinazione per tutte le possibilità, che sono $a!b!c!$
per esempio nella (1,1,8), il terzo giorno ho 8! sequenze in cui indossare 8 giubbotti

Sempre se non ho sbagliato i calcoli, le combinazioni totali sono 36 x 10! = 130.636.800 (circa 400 milioni di giorni / 1 milione di anni)

[Admin]

Tutto corretto Sergio.
Apprezzo la tua soluzione "enumerativa composta".
In prima battuta lo avevo approcciato anch'io così, ma poi mi son perso in mille rivoli .
Ho usato quindi un approccio più sbrigativo, in seconda battuta.
Infine, ho provato a risolverlo per via "analitica" (cosa che mi ha sempre interessato ma che non ho mai compreso fino in fondo).

Attendiamo altri contributi, vari ed eventuali .

Admin

[franco]

Concordo sul risultato, ma io l'avevo pensata più semplice:
Ho 10! modi diversi per mettere in fila i 10 giubbotti.
Ho 36 modi diversi per suddividerli in 3 insiemi consecutivi non vuoti
Totale 36*10!=130636800 possibilità.

[Admin]

Concordo sul risultato, ma io l'avevo pensata più semplice:
Ho 10! modi diversi per mettere in fila i 10 giubbotti.
Ho 36 modi diversi per suddividerli in 3 insiemi consecutivi non vuoti
Totale 36*10!=130636800 possibilità.

Si Franco, in effetti avevo preso spunto da un esercizio in cui si parlava di persone e di stanze.
Pertanto l'ordine in cui si indossano i giubbotti in uno stesso giorno è da ritenersi ininfluente.

[valerio80]

Buongiorno,
scusate per l'intromissione, vi leggo spesso ma non contribuisco in quanto le mie capacità sono nettamente inferiori alle vostre.
In questo caso mi permetto però di fare una osservazione.
Nel problema c'è una particolarità che a mio avviso non è stata analizzata.
La frase "In 3 giorni ha indossato un totale di 10 giubbotti diversi." non vuol dire a mio avviso che un singolo giubbotto lo posso indossare un solo giorno, il giubbotto 1 lo posso indossare anche tutti e 3 i giorni, quindi la somma dei giubbotti indossati nei 3 giorni deve essere un numero compreso tra 10 e 30 (nel caso in cui i 10 giubbotti li ho usati sia nel giorno 1 che nel 2 che nel 3).
Cosa ne pensate?

[franco]

Buongiorno,
scusate per l'intromissione, vi leggo spesso ma non contribuisco in quanto le mie capacità sono nettamente inferiori alle vostre.
In questo caso mi permetto però di fare una osservazione.
Nel problema c'è una particolarità che a mio avviso non è stata analizzata.
La frase "In 3 giorni ha indossato un totale di 10 giubbotti diversi." non vuol dire a mio avviso che un singolo giubbotto lo posso indossare un solo giorno, il giubbotto 1 lo posso indossare anche tutti e 3 i giorni, quindi la somma dei giubbotti indossati nei 3 giorni deve essere un numero compreso tra 10 e 30 (nel caso in cui i 10 giubbotti li ho usati sia nel giorno 1 che nel 2 che nel 3).
Cosa ne pensate?

Ciao Valerio,
In verità ci avevo pensato anche io però, viste le risposte precedenti, avevo data per buona l'interpretazione dell'uso una volta sola.
Mi sembra valga assolutamente la pena di esplorare anche l'opzione di "utilizzo plurimo", tanto siamo qui per divertirci

[Quelo]

Ciao Valerio,
il bello di questo forum è che chiunque può partecipare, nessuno viene giudicato e tutti i contributi sono utili.
La tua riflessione è interessante, io non ci avevo pensato.

[franco]

Un po' di fretta ma ho pensato alla "variante" proposta da Valerio.
Provo a immaginare che il signor Rossi abbia un armadio con 10 appendini che sostengono i 10 giubbotti e ulteriori 10 appendini vuoti.
Ogni giorno prende a caso 10 appendini e indossa tutto quello che ci trova.
L'unica combinazione non ammessa è quella "tutti i 10 appendini vuoti".
Le combinazioni possibili ogni giorno (consideando ininfluente l'ordine con cui i giubbotti sono indossati) sono quindi $20!/(10!*10!)-1=184.755$
In 3 giorni, le possibili combinazioni sono $(20!/(10!*10!)-1)^3=6.306.502.924.168.875$

[Admin]

Vi posto le mie considerazioni sul problema.
Comincio col precisare l'enunciato, per restringere al solo caso che avevo inteso inizialmente:

Il signor Rossi indossa almeno un giubbotto al giorno.
Ogni mattina, sceglie quanti e quali giubbotti indosserà durante il giorno.
In $3$ giorni ha indossato un totale di $10$ giubbotti, tutti diversi.
In quanti modi ha potuto scegliere i giubbotti ogni giorno?

Consideriamo i $10$ giubbotti come un insieme di $10$ elementi.
Si tratta di contare le partizioni dell'insieme in $3$ sottinsiemi non vuoti, e moltiplicarlo per le permutazioni dei $3$ sottinsiemi (dato che i $3$ giorni sono distinti).

Ora il numero di partizioni di un insieme di $n$ elementi, in $k$ sottinsiemi non vuoti ci è dato dai numeri di Stirling di seconda specie, ossia:

$S(n,k)=\left\{\begin{matrix} n \\ k \end{matrix}\right\}=\displaystyle\frac{1}{k!}\sum\limits_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$

Nel caso i $k$ sottinsiemi abbiano un ordine specifico si parla di versione ordinata di $S(n,k)$, ossia:

$S_o(n,k)=k!\cdot\left\{\begin{matrix} n \\ k \end{matrix}\right\}=\displaystyle\sum\limits_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$

E' questo il nostro caso; quindi il valore cercato è:

$S_o(10,3) = \displaystyle\sum\limits_{j=0}^{3}(-1)^{3-j}\binom{3}{j}j^{10}= 3 -3\cdot 2^{10} + 3^{10} = 55980$

Questo era il modo sbrigativo.

Supponendo però di non conoscere la formula dei numeri di Stirling di seconda specie, vediamo come possiamo calcolarne il valore, utilizzando le Funzioni Generatrici.
Dobbiamo calcolare $3! \cdot \left\{\begin{matrix} 10 \\ 3 \end{matrix}\right\}$.
Consideriamo la successione della versione ordinata dei numeri di Stirling di seconda specie $\{S_o(0,k),S_o(1,k),S_o(2,k), \cdots, S_o(n,k) \}$ con $0 \le k \le n$.
Consideriamo la sua funzione generatrice esponenziale (egfs), ossia:
$\displaystyle F_{S_o(n,k)}(x) = S_o(0,k)+ S_o(1,k)\cdot x + S_o(2,k)\cdot \frac{x^2}{2!} + S_o(3,k)\cdot \frac{x^3}{3!} + \cdots = \cdot\sum_{n=0}^{\infty}k!\cdot S(n,k)\cdot \frac{x^n}{n!} = k!\cdot\sum_{n=0}^{\infty}S(n,k)\cdot \frac{x^n}{n!} $
Come conseguenza della regola del prodotto (si veda B.Sagan - Combinatorics, The Art of Counting - par. 4.4: scaricabile qui) si ricava:

$\displaystyle F_{S_o(n,k)}(x) = \underbrace{F_{\overline{E}}(x)\cdot F_{\overline{E}}(x) \cdots F_{\overline{E}}(x)}_{\text{k volte}} = F_{\overline{E}}(x)^k$

dove $F_{E}(x)$ è la funzione generatrice esponenziale di base, relativa alla successione $\{1,1, \cdots, 1,1 \}$ e vale

$\displaystyle F_{E}(x) = 1+ x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots = \cdot\sum_{n=0}^{\infty}\frac{x^n}{n!} = e^x $

mentre $F_{\overline{E}}(x)$ è la variante di $F_{E}(x)$ , relativa alla successione $\{0,1, \cdots, 1,1 \}$ e vale

$\displaystyle F_{\overline{E}}(x) = 0 + x + \frac{x^2}{2!}+ \frac{x^3}{3!} + \cdots = \cdot\sum_{n=1}^{\infty}\frac{x^n}{n!} = e^x -1$

Quindi si ottiene

$\displaystyle F_{S_o(n,k)}(x) = F_{\overline{E}}(x)^k = (e^x - 1)^k$

Questa è la funzione generatrice esponeziale relativa ailla versione ordinata dei numeri di Stirling.
Nel nostro caso, $n=10$ e $k=3$, quindi si ha:

$\displaystyle F_{S_o(n,3)}(x) = F_{\overline{E}}(x)^3 = (e^x - 1)^3$

Dobbiamo trovare ora il coefficiente del termine $\displaystyle\frac{x^{10}}{10!}$ della serie.
Per farlo, svolgiamo il cubo di binomio:

$\displaystyle (e^{x}-1)^{3}=e^{3x}-3e^{2x}+3e^{x}-1$

Adesso utilizziamo le espansioni in serie dei singoli termini e sommiamo i coefficienti relativi ad ogni esponente.
Il coefficiente relativo al termine $\displaystyle\frac{x^{10}}{10!}$ risulta quindi essere

$\displaystyle S_o(10,3) = (3^{10}- 3\cdot (2^{10}) +3) = 55980$

Saluti
Admin