Combinatoria
Ciao a tutti, sto ripassando combinatoria dopo anni senza mai vederla, ma c'è un quesito che non sto riuscendo a risolvere:
Dato l'insieme \(\displaystyle A \subset \mathbb{N} \) contenente soltanto numeri con esattamente sei cifre, determina il numero di elementi di \(\displaystyle A \) che hanno esattamente due cifre uguali.
Avevo pensato di ragionare come segue, ma è errato in quanto non solo non combaciante col risultato del testo.
Dato l'insieme \(\displaystyle A \subset \mathbb{N} \) contenente soltanto numeri con esattamente sei cifre, determina il numero di elementi di \(\displaystyle A \) che hanno esattamente due cifre uguali.
Avevo pensato di ragionare come segue, ma è errato in quanto non solo non combaciante col risultato del testo.
[*:155zfv5t] Scriviamo gli elementi di \(\displaystyle A \) nella forma \(\displaystyle a_1a_2a_3a_4a_5a_6 \), dove \( \exists ! i | a_i= a_j, i\neq j\) e $i,j\leq 6$.[/*:m:155zfv5t]
[*:155zfv5t] Supponiamo che sia $a_1=a_2$ fissati, senza preoccuparci di porli diversi da 0: il numero di elementi così costruiti sono le disposizioni $D_{9,4}$ (i nove numeri restanti disposti nelle quattro posizioni restanti), ovvero $D_{9,4}=9\cdot 8 \cdot 7 \cdot 6=3024$.[/*:m:155zfv5t]
[*:155zfv5t] Inoltre, questo ragionamento è replicabile per ognuna delle 10 cifre del sistema decimale, per cui il risultato andrà moltiplicato per 10.[/*:m:155zfv5t]
[*:155zfv5t] Questo ragionamento è però replicabile ovunque si trovino i valori per cui $a_i=a_j$, ovvero per ogni coppia non ordinata $(i,j)$ con $i,j\leq 6$ e $i \ne j$, ovvero tutte le possibili combinazioni di 6 elementi di cui 2 ripetuti (le posizioni dei valori uguali) e 4 ripetuti (le posizioni dei valori diversi), ovvero $C_{6;4,2}=\frac{6!}{4!2!}=15$. Avevo pensato anche a costruirmi una tabella 6x6 delle possibili coppie $(i,j)$, tenendomi solo la parte triangolare o superiore o inferiore ed eliminando anche la "diagonale principale" (i valori $i=j$), ottenendo sempre 15 possibilità.[/*:m:155zfv5t]
[*:155zfv5t] Al momento sembrerebbe quindi che l'insieme $A$ contenga $15\cdot 3024 \cdot 10=453600$ elementi.[/*:m:155zfv5t]
[*:155zfv5t] Vi devo però sottrarre tutte le combinazioni ottenute per cui $a_1=0$ o $a_1=a_2=0$, perché questi non rappresentano numeri naturali. Inizio con l'osservare che il caso $a_1=a_2=0$ è incluso in quello $a_1=0$, per cui mi basta studiare quest'ultimo. Distinguo i due casi dell'elemento $0a_2a_3a_4a_5a_6$:
[*:155zfv5t] ha lo 0 ripetuto: questo significa che $a_2a_3a_4a_5a_6$ saranno le disposizioni semplici dei numeri da 0 a 9 nelle 5 posizioni rimaste: $D_{10,5}=30240$;[/*:m:155zfv5t]
[*:155zfv5t] non ha 0 ripetuto: questo significa che $a_2a_3a_4a_5a_6$ sarà esattamente nella stessa forma sopraesposta, cambiando ovviamente il numero di cifre utilizzabili (9 e non più 10) e il numero di posizioni libere (3 e non più 4), quindi $D_{9,3}\cdot C_{5;3,2} \cdot 9=504\cdot 10 \cdot 9 = 45360$.[/*:m:155zfv5t][/list:u:155zfv5t][/*:m:155zfv5t]
[*:155zfv5t] Il risultato finale sarà quindi $453600-30240-45360=378000$[/*:m:155zfv5t][/list:u:155zfv5t]
Il testo riporta come soluzione $408240$, molto lontano dal mio risultato.
Non riesco però a trovare l'errore... Osservo però che $453600-45360$ (ovvero senza il caso "ha lo 0 ripetuto") mi porta al risultato corretto: potrebbe voler dire che sto mal interpretando quel che sto scrivendo?
Grazie a chi vorrà aiutarmi.
Risposte
Le due cifre ripetute possono trovarsi in $15$ posizioni diverse però $5$ volte una sarà nella prima posizione e non può essere zero mentre nella altre $10$ sì, quindi io tratterei i due casi separatamente.
Nel primo caso le cifre ripetute sono $9$, gli altri quattro posti possono essere occupati i $((9),(4))$ modi e permutati in $4!$ modi possibili, quindi in totale fa $136.080$
Nel secondo caso la prima posizione può essere occupata in nove modi diversi e le cifre ripetute generano nove casi; le restanti tre possono essere scelte in $((8),(3))$ modi diversi e permutate in $3!$ modi per un totale di $272.160$.
Totale complessivo $408.240$
Cordialmente, Alex
Nel primo caso le cifre ripetute sono $9$, gli altri quattro posti possono essere occupati i $((9),(4))$ modi e permutati in $4!$ modi possibili, quindi in totale fa $136.080$
Nel secondo caso la prima posizione può essere occupata in nove modi diversi e le cifre ripetute generano nove casi; le restanti tre possono essere scelte in $((8),(3))$ modi diversi e permutate in $3!$ modi per un totale di $272.160$.
Totale complessivo $408.240$
Cordialmente, Alex
Grazie axpgn, però al di là del risultato in sé mi piacerebbe capire cosa sto sbagliando. Ho modificato il post per correggere un errore di calcolo e per aggiungere un'osservazione finale.
Riesci a partire dal mio per capire dov'è l'errore tuo? Perché io a quest'ora non riesco a farne un'analisi "seria" 
... seriamente ...
Cordialmente, Alex
... seriamente ...Cordialmente, Alex
A occhio, secondo me, approcciare a "togliere" porta più facilmente ad errori quando le situazioni sono sostanzialmente diverse (perché "i vincoli" nei due casi ovvero con zero doppio o senza zero doppio sono diversi)
IMHO
IMHO
"axpgn":
A occhio, secondo me, approcciare a "togliere" porta più facilmente ad errori quando le situazioni sono sostanzialmente diverse (perché "i vincoli" nei due casi ovvero con zero doppio o senza zero doppio sono diversi)
IMHO
Probabilmente hai ragione, ma mi è venuto più naturale pensarla così.
Ora devo capire cosa ho sbagliato... Vista la coincidenza numerica che ho scritto in fondo al post, probabilmente sbaglio proprio a interpretare il significato di ciò che ho scritto.
Attenderò domani!
Hai trovato $453.600$ elementi.
Di questi, 45.360 cominciano per 9, 45.360 per 8, ..............,45.360 per 0.
In questi $45.360$ sono compresi sia quelli con lo $0$ singolo, sia quelli con lo $0$ ripetuto.
Per verifica:
a) numeri con lo $0$ singolo che cominciano per $0$---$8*7*6*9*10=30.240$
b) numeri con lo $0$ ripetuto che cominciano per $0$---$9*8*7*6*5=15.120$
e $30.240+15.120=45.360$
Di questi, 45.360 cominciano per 9, 45.360 per 8, ..............,45.360 per 0.
In questi $45.360$ sono compresi sia quelli con lo $0$ singolo, sia quelli con lo $0$ ripetuto.
Per verifica:
a) numeri con lo $0$ singolo che cominciano per $0$---$8*7*6*9*10=30.240$
b) numeri con lo $0$ ripetuto che cominciano per $0$---$9*8*7*6*5=15.120$
e $30.240+15.120=45.360$
Non ci crederai ma ieri sera il primo che mi è venuto in mente per chiarire sei stato tu
Ho letto il problema e ho provato a farlo a modo mio, poi ho provato a trovare l'errore nel tuo ragionamento ma non mi trovavo nel modo di ragionare e quindi non ce l'ho fatta, comunque ti riporto il mio procedimento nel caso ti sia utile per capire dove hai sbagliato (anche se sembra averci già pensato qualcun altro, ma ancora non hai risposto per dire se ti è chiaro).
Allora, divido 3 casi:
1) numeri senza $0$ come cifra: intanto scelgo le mie $5$ cifre che uso "\({9\choose 5}\)", poi scelgo quale cifra ripetere "$5$", poi faccio tutte le possibili permutazioni "$(6!)/2$".
2) numeri con uno $0$: scelgo le altre $4$ cifre "\({9\choose 4}\)", poi scelgo quale cifra ripetere "$4$", poi decido dove va lo $0$ "$5$" e poi faccio tutte le permutazioni possibili delle altre cifre "$(5!)/2$".
3) numeri con due $0$: scelgo al solito le $4$ cifre "\({9\choose 4}\)", poi scelgo come mettere i due $0$ "$5*4/2$" (all'inizio mi ero dimenticato "$/2$", ma è fondamentale), infine permuto le rimanenti in tutti i modi possibili "$4!$".
Mettendo insieme il tutto e ricordando che \({9\choose 4}={9\choose 5}\), si ha che il numero totale è \({9\choose 5}4!(5^2*3+5^2*2+5*2)=408240\).
Allora, divido 3 casi:
1) numeri senza $0$ come cifra: intanto scelgo le mie $5$ cifre che uso "\({9\choose 5}\)", poi scelgo quale cifra ripetere "$5$", poi faccio tutte le possibili permutazioni "$(6!)/2$".
2) numeri con uno $0$: scelgo le altre $4$ cifre "\({9\choose 4}\)", poi scelgo quale cifra ripetere "$4$", poi decido dove va lo $0$ "$5$" e poi faccio tutte le permutazioni possibili delle altre cifre "$(5!)/2$".
3) numeri con due $0$: scelgo al solito le $4$ cifre "\({9\choose 4}\)", poi scelgo come mettere i due $0$ "$5*4/2$" (all'inizio mi ero dimenticato "$/2$", ma è fondamentale), infine permuto le rimanenti in tutti i modi possibili "$4!$".
Mettendo insieme il tutto e ricordando che \({9\choose 4}={9\choose 5}\), si ha che il numero totale è \({9\choose 5}4!(5^2*3+5^2*2+5*2)=408240\).
"superpippone":
Hai trovato $453.600$ elementi.
Di questi, 45.360 cominciano per 9, 45.360 per 8, ..............,45.360 per 0.
In questi $45.360$ sono compresi sia quelli con lo $0$ singolo, sia quelli con lo $0$ ripetuto.
Per verifica:
a) numeri con lo $0$ singolo che cominciano per $0$---$8*7*6*9*10=30.240$
b) numeri con lo $0$ ripetuto che cominciano per $0$---$9*8*7*6*5=15.120$
e $30.240+15.120=45.360$
Concettualmente mi è chiaro questo, hai ragione ovviamente.
Solo non trovo perché il mio split è errato...
Se hai lo $0$ ripetuto non puoi fare $D_(10,5)$, perchè facendo così comprendi anche le disposizioni senza lo $0$. (es. 12345)
Devi fare $D_(9,4)=3.024$ e poi moltiplicare per $5$ perchè il secondo $0$ puoò occupare una qualsiasi delle 5 posizioni.
Se hai lo $0$ singolo devi fare $D_(8,3)$ prchè la nona cifra è quella ripetuta.
Devi fare $D_(9,4)=3.024$ e poi moltiplicare per $5$ perchè il secondo $0$ puoò occupare una qualsiasi delle 5 posizioni.
Se hai lo $0$ singolo devi fare $D_(8,3)$ prchè la nona cifra è quella ripetuta.
"superpippone":
Se hai lo $0$ ripetuto non puoi fare $D_(10,5)$, perchè facendo così comprendi anche le disposizioni senza lo $0$. (es. 12345)
Devi fare $D_(9,4)=3.024$ e poi moltiplicare per $5$ perchè il secondo $0$ puoò occupare una qualsiasi delle 5 posizioni.
Se hai lo $0$ singolo devi fare $D_(8,3)$ prchè la nona cifra è quella ripetuta.
Credo di capirla così, sì. Grazie!
È chiaro che la combinatoria devo rivederla da zero...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo