Permutazioni tutte diverse (risposta ad Arouet) e frattali (sottoprodotto)
Radicale
Il problema era :
se ho una sequenza fissata S = s1, s2, ... sN di numeri naturali
estratti a caso da
un insieme di M numeri *senza* ripetizioni e con M > N, N ed M dati,
che probabilita'
ho di estrarre una sequenza x1, x2, ... xN fatta in modo tale che ogni
numero xj sia
diverso da sj ?
Per esempio 1,2,3 sia la fissata sequenza di 3 numeri (N = 3) estratti
da
M = {1,2,3,4,5} .
Allora 2,3,1 va bene, 2,9,4 va bene, 8,2,1 *non va* bene.
Allora intanto ipotizziamo che N = M.
Facciamo N = 5 per fissare le idee.
Ogni permutazione di S si puo' ottenere con uno scambio di posto tra
2 elementi della successione ! E' chiaro no ?
Allora le permutazioni che vanno bene sono tutte e sole quelle che
hanno *tutti* i posti scambiati.
:-)) Chiaro no ?
E gli scambi possibili sono :
il primo elemento si puo' scambiare col secondo, col terzo, col quarto
e col quinto. Totale 4. Il secondo elemneto col terzo, e non col primo
perche' gia' l'abbiamo contata facendo riferimeto al primo, poi col
quarto
e poi col quinto.
Quindi il primo elemento genera N - 1 scambi, il secondo N - 2 ...
Una permutazione valida deve prendere uno scambio da ognuno di
questi e quindi sono (N-1)(N-2) ... E percio (pensa un po) le
permutazioni.
buone sono (N-1) fattoriale.
... Tse' ! Te lo aspettavi fosse cosi' semplice ?
I conti tornano : con 3 elementi ce ne faccio 2, con 4 ne faccio 6.
Prova.
Se ora M > N secondo me basta considerare tutte le permutazioni di M
elementi (non di N, ma di M) che vanno bene rispetto ad una sequenza
di M elementi (artificiale) e fare (M-1) fattoriale. Capito perche' ?
Cerco di spiegartelo, ma non so se ne saro' capace.
Prendi la sequenza S fissata e scrivila
Prendi una sequenza con M elementi e schiaffala sotto la S,
in modo che il primo elemento di M stia sotto il primo di S.
Incolonnata insomma. Ovvio che quella M e' piu' lunga, esce fuori a
destra no ?
/Ogni/ permutazza di M con *tutti* i suoi posti scambiati e' fatta in
modo
tale, se vedi bene, che anche la parte a sinistra incolonnata sotto la
S
va bene. Per forza !
Lo vedi ?
Se pensi che sbaglio fammi sape'.
Per i frattali aspetto prima che mi confermate questo. Se e' sbagliato
e'
inutile che vado avanti.
Coso
o seguendo la luna, Radicale scrisse in
<f5e2d97f-b03a-4095...@t54g2000hsg.googlegroups.com>:
> Allora intanto ipotizziamo che N = M.
[...]
> Quindi il primo elemento genera N - 1 scambi, il secondo N - 2 ...
> Una permutazione valida deve prendere uno scambio da ognuno di
> questi e quindi sono (N-1)(N-2) ... E percio (pensa un po) le
> permutazioni.
> buone sono (N-1) fattoriale.
> ... Tse' ! Te lo aspettavi fosse cosi' semplice ?
> I conti tornano : con 3 elementi ce ne faccio 2, con 4 ne faccio 6.
> Prova.
Non per fare il guastafeste, ma... Con 4 a me ne vengono 9... :-)
Ciao ciao
Claudio
Nino
"Coso" <claudio.s...@gmail.com> ha scritto nel messaggio
news:48e78c4b$0$1084$4faf...@reader1.news.tin.it...
Certo!
2143
2341
2413
3142
3412
3421
4123
4312
4321
F.M.Arouet
> Se pensi che sbaglio fammi sape'.
Deve rileggere con calma il tuo ragionamento.
Ti rispiego il mio (che mi pare funzioni).
Prendiamo la sequenza di riferimento 1,2,3,4,5.
Prendo le permutazioni totali. Tolgo le permutazioni che hanno il
primo elemento = 1,
tolgo quelle con il secondo = 2.... tolgo quelle con il quinto = 5.
Poi aggiungo le permutazioni con primo elemeno =1 e secondo = 2 e
cosi' per tutte le coppie.
Poi tolgo quelle con primo elemento = 1, secondo =2, terzo =3 e cosi'
per tutte le terne.
Aggiungo le quaterne e tolgo la cinquina.
Con 3 elementi viene 2, con 4 elementi viene 9, con 5 non ho fatto i
conti.
Ciao.Fabio.
Radicale
Ti chiedo scusa :
ho sbagliato. Il tuo e' il metodo giusto.
F.M.Arouet
> ho sbagliato. Il tuo e' il metodo giusto.- Nascondi testo citato
>
> - Mostra testo citato -
Con N=M credo che la formula si possa scrivere cosi':
sommatoria con i che va da 0 a N di
(-1) elevato a i * (N-i)! *(N su i)
dove per N su i intendo N!/(N-i)!*i!
Ciao.Fabio.
Coso
dito o seguendo la luna, F.M.Arouet scrisse in
<da480f1b-7b09-479a...@d45g2000hsc.googlegroups.com>:
> Con N=M credo che la formula si possa scrivere cosi':
>
> sommatoria con i che va da 0 a N di
>
> (-1) elevato a i * (N-i)! *(N su i)
> dove per N su i intendo N!/(N-i)!*i!
E` corretta... infatti e` una delle possibili formule del derangement
[che e` esattamente il problema che state trattando, con N=M].
Ciao ciao
Claudio