Pagina 1 di 1

Calcolo Combinatorio di Base

MessaggioInviato: 23/08/2005, 14:09
da Marvin
Uno di quei soliti quiz che mettono sul corriere mi ha messo in crisi:

viene chiesto quanti codici è possibile realizzare con i numeri da 1 a 9 e ogni codice è una stinga di 3 cifre..solo che non sono validi i numeri "inversi" (es. vale 123 ma non 321)
io ad occhio ho fatto 9^3 = 729
solo che questo conta tutte le combinazioni da 111 ... 999
non saprei come tradurre la seconda condizione..
è poi..è giusto usare le combinazioni?
mi sono accorto che questi quesiti mi mandano "in palla"..
qlc ha qualche suggerimento su come distinguere combinazioni/permutazioni & affini??

Marvin

MessaggioInviato: 23/08/2005, 16:26
da Rael
E' giusto usare le combinazioni.
per le PERMUTAZIONI è un altro tipo di problema, del tipo
"dati P elementi ed P posti, quante diverse configurazioni di elementi sui P posti si possono ottenere ??", gli elementi in genere sono tutti diversi tra loro, e conta l'ordire (es. 1234... è diverso da 1243...).

Ora per il problema, se 111, ..., 999 vanno eliminate, vanno eliminate tutte le palindrome (232, 121, 454, etc), quindi si deve sottrarre il numero di combinazioni palindrome al numero di combinazioni totale e dividere il risultato per 2 (delle rimanenti ognuna avrà un inversa)
ora il numero delle palindrome in questo caso è facile da calcolare (bel problema se invece le stringhe fossero state di lunghezza arbitraria (...ora ci penso e vedo se si può generalizzare)):
in questo caso le palindrome iniziano e finiscono con lo stesso numero, ed hanno un solo numero in mezzo
il primo e l'ultimo numero possono assumere tutti i valori da 1 a 9, e per ogni coppia agli estremi, ci sarà un numero in mezzo da 1 a 9, quindi 9 numeri in mezzo per ognuna delle 9 coppie agli estremi possibili, dunque 81
quindi il numero cercato dovrebbe essere (729-81)/2 = 324

ma come ho detto vediamo se si può generalizzare la cosa ...

MessaggioInviato: 23/08/2005, 17:55
da Marvin
ok, mi ritrovo con il tuo ragionamento..davvero mi faceva impazzire...

MessaggioInviato: 23/08/2005, 18:06
da Rael
Pare che sia riuscito a tirare fuori una relazione più generale per il numero delle combinazioni palindrome (ineffetti era semplice), per codici di "n" cifre e "k" simboli:

P(n) = k^((n+1)/2) se n è DISPARI
P(n) = k^(n/2) se n è PARI

ditemi se sparo cavolate :P

MessaggioInviato: 23/08/2005, 20:04
da Marvin
Ma sai che forse è un metodo che avevo usato tempo fa per fare un programma in Visual Basic che controllava le parole palindrome??
ah-ehm...