Calcolo Combinatorio di Base

Messaggioda Marvin » 23/08/2005, 14:09

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
Avatar utente
Marvin
Average Member
Average Member
 
Messaggio: 42 di 521
Iscritto il: 28/07/2005, 11:30
Località: Milano

Messaggioda Rael » 23/08/2005, 16:26

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 ...
Rael
New Member
New Member
 
Messaggio: 55 di 87
Iscritto il: 08/10/2004, 21:23
Località: Italy

Messaggioda Marvin » 23/08/2005, 17:55

ok, mi ritrovo con il tuo ragionamento..davvero mi faceva impazzire...
Avatar utente
Marvin
Average Member
Average Member
 
Messaggio: 47 di 521
Iscritto il: 28/07/2005, 11:30
Località: Milano

Messaggioda Rael » 23/08/2005, 18:06

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
Rael
New Member
New Member
 
Messaggio: 59 di 87
Iscritto il: 08/10/2004, 21:23
Località: Italy

Messaggioda Marvin » 23/08/2005, 20:04

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...
Avatar utente
Marvin
Average Member
Average Member
 
Messaggio: 52 di 521
Iscritto il: 28/07/2005, 11:30
Località: Milano


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 16 ospiti