[generico] permutazioni

[PGI-Bis]

Ok, il mio calcolo combinatorio è eufemisticamente arrugginito. Mi servirebbe una conferma.

Devo computare le permutazioni di un insieme. Per un insieme di N elementi mi servono tutte le permutazioni di ordine W con 0 < W < N.

Per controllare la correttezza di quello che ho scritto mi sono detto "ok, vediamo se il totale degli insiemi creati corrisponde al numero totale di permutazioni possibili su un insieme di N elementi".

Bene, ovviamente non ho trovato quale sia questo totale - capita quando non si sa bene quello che si cerca.

Di mio sarei arrivato alla conclusione che il numero totale di permutazioni semplici per un insieme di N elementi è la sommatoria di

w! * ( (n!) / (k! * (n - k)! ) )

per w da 0 a N

Vale a dire il numero di permutazioni di un insieme di N elementi è pari alla somma del numero di permutazioni semplici di ogni elemento dell'insieme delle parti di N.

Torna a qualcuno questo conto?

[BrutPitt]

La mia ruggine fa concorrenza alla tua... ma mi sembra di ricordare che:

se n e' il numero di elementi disponibili
e w e' il numero di elementi da permutare

con appunto 0<=w<=n ... allora:

P(n, w) = n!/(n-w)!

da cui, nel caso di n=w, si ha appunto che P(n)=n!

Ora... nella tua formula e' subentrato un k, (l'orario?), ma se quel k voleva essere w... semplificando, giungeresti alla stessa formula.

P.S.
Spero di non aver detto io castronerie... visto che mi son appena alzato e il caffe' e' ancora sul fuoco.

[banryu79]

Formulario? qui

[PGI-Bis]

W è un alieno che atterra da queste parti dopo le due di notte. Sì è k non w.

k! * ( (n!) / (k! * (n - k)! ) )

per k da 0 a n.

[Oceans11]

Scusate l'intrusione, ma le permutazioni di N oggetti sono i modi in cui si possono ordinare questi N oggetti, quindi se si pensa all'ordine come posizioni successive a partire dalla posizione 1 fino alla posizione N:

l'oggetto 1 si può mettere in N posizioni diverse,
l'oggetto 2 si può mettere in N-1 posizioni diverse (tutte tranne quella occupata dall'oggetto 1)
l'oggetto 3 si può mettere in N-2 posizioni diverse (tutte tranne quelle occupate dall'oggetto 1 e 2)
l'oggetto N si può mettere solo in 1 posizione (le altre sono tutte occupate)

quindi alla fine si ha:

P(N) = N * (N-1) * (N-2) * ... * 1 = N!


Se invece si vuole ogni insieme *ordinato* di k elementi (distinti) presi da un insieme che ne contiene n, allora si parla di disposizioni (semplici) di n elementi di classe k:

D(n,k) = n * (n-1) * (n-2) * (n-3) * (n-k+1) = n! / (n-k)!

[PGI-Bis]

Quello è pacifico. A me interessa però il numero totale di combinazioni in questo senso: se ho l'insieme { 1, 2, 3 } allora mi servono gli insiemi:

{ 1 2 3 }
{ 1 3 2 }
{ 2 1 3 }
{ 2 3 1 }
{ 3 1 2 }
{ 3 2 1 }
{ 2 3 }
{ 3 2 }
{ 1 3 }
{ 3 1 }
{ 3 }
{ 1 2 }
{ 2 1 }
{ 2 }
{ 1 }
{ }

Cioè non mi servono solo le permutazioni di N oggetti ma anche quelle di n - 1, n - 2, n - 3 ... fino a zero. Che poi non mi serve neanche averle, mi interessa solo sapere quante sono per verificare che, ad esempio, per un insieme di 3 elementi ne esistano effettivamente 16, per 4 elementi 65, per 5 elementi 326 eccetera.

[banryu79]

In base al tuo esempio e alla tua spiegazione io ho questi risultati:
Con N = 0, ho un caso speciale per cui la formula non vale.
Con N = 1, ottengo 2
Con N = 2, ottengo 5
Con N = 3, ottengo 16
Con N = 4, ottengo 61
Con N = 5, ottengo 286

La formula che ho usato è questa:

N!  +  Sum[k=1 -> N-1]((N-k)! * N)  +  1

dove Sum[k=1 -> N-1] è la sommatoria con k che va da 1 a N-1 di ((N-k)! * N).

Sbaglio di brutto?

[PGI-Bis]

Se sapessi dirti che sbagli non avrei fatto la domanda .

Il mio "ragionamento" è questo. Posto che per un insieme di n elementi esistono n! permutazioni di ordine n il numero totale delle combinazioni che cerco dovrebbe essere la somma delle permutazioni di ordine variabile da zero a n che posso ottenere dal mio insieme. Permutazioni diverse, cioè o contengono elementi diversi o contengono gli stessi elementi ma in ordine diverso.

Ora per un insieme di N elementi esistono 2^N sottoinsiemi (il noto insieme delle parti). Da qui passo a dire - senza alcuna giustificazione a me nota - che se per ognuno di quei sottoinsiemi computo il numero di permutazioni semplici e faccio la somma ottengo il valore che cerco. Credo abbia a che fare col fatto che gli elementi dell'insieme delle parti differiscono tra loro per almeno un elemento e le partizioni semplici di insiemi disgiunti sono reciprocamente disgiunte. Ma al momento non mi viene una dimostrazione.

Ammesso e non concesso che sia così allora il problema diventa capire la cardinalità degli elementi dell'insieme delle parti di un insieme di N elementi. E' chiaro che la cardinalità minima è zero e la massima è N.

E' pure noto che un insieme di N elementi ha N! / (K! * (N - K)! sottoinsiemi di K elementi. Poichè ognuno di questi sottoinsiemi di K elementi ha K! permutazioni arrivo alla formula:

sommatoria { K! * ( N! / (K! * (N - K)!) }

per ogni K da 0 a N.

Ma è un modo di ragionare che ha talmente tanti buchi da poterci scolare la pasta. Onde evitare di perdere delle ore a cercare la dimostrazione di quella formula volevo appunto sapere se è già nota a qualcuno o se non risulti affatto.

[yorkeiser]

A occhio, la formula potrebbe essere:
Sommatoria su k in [0;n] di n!/(n-k)!
che su 3 elementi darebbe
1+3+6+6 = 16 permutazioni

[rеpne scasb]

■

[banryu79]

Originariamente inviato da yorkeiser

Premetto che ho letto proprio al volo; la sommatoria proposta non mi pare corretta:
nel caso di 3 elementi, avresti 1+18+3 = 22 combinazioni.

Veramente per N = 3 ne calcolo 16 io.
Forse non molto chiaro come ho scritto la formula

Un passo alla volta:

N! + Sum[k=1 -> N-1]((N-k)! * N) + 1

3! = 6.

N! + Sum[k=1 -> N-1]((N-k)! * N) + 1

from 1 to N-1(2)...
con k ==1 : (3-1)! * 3 = 6.
con k ==2 : (3-2)! * 3 = 3.

N! + Sum[k=1 -> N-1]((N-k)! * N) + 1

1.

Totale: 6 + 6 + 3 + 1 = 16 per N = 3, il che è corretto.

[yorkeiser]

Originariamente inviato da banryu79

Veramente per N = 3 ne calcolo 16 io.
Forse non molto chiaro come ho scritto la formula

Un passo alla volta:

3! = 6.


from 1 to N-1(2)...
con k ==1 : (3-1)! * 3 = 6.
con k ==2 : (3-2)! * 3 = 3.


1.

Totale: 6 + 6 + 3 + 1 = 16 per N = 3, il che è corretto.

Chiedo venia banryu, infatti avevo editato Oltre ad aver sballato il calcolo (2! = 6, ma dove ?) m'ero perso quell'N! prima della sommatoria.
EDIT Mi pare che comunque abbiamo scritto cose diverse, io qualcosa al denominatore, tu al denominatore... uhm.. mumble mumble

[banryu79]

Originariamente inviato da yorkeiser

Chiedo venia banryu, infatti avevo editato Oltre ad aver sballato il calcolo (2! = 6, ma dove ?) m'ero perso quell'N! prima della sommatoria.
Sostanzialmente abbiamo scritto la stessa cosa, magari quella che ho postato io è un attimino più concisa ma comunque dovrebbero coincidere

Chiedo venia pure io, ho incasinato la formula perchè sono refrattario al pensiero matematico e stavo pensando in termini a me più familiari.

[yorkeiser]

Per N=4, ottengo
1+4+12+24+24 = 65 elementi, quindi effettivamente una differenza con la formula di banryu comunque c'è. Se avessi ancora qualche voglia matematica a quest'ora, mi metterei a smanettare con i fattoriali per vedere in cosa differiscono

[banryu79]

PGI, alla fine facci sapere come hai risolto

@EDIT: ho ricontrollato manina fino a N = 5.
- la formula che ho proposto è errata di brutto.
- La sommatoria proposta da Oceans11 e yorkeiser mi da i risultati attesi.

[PGI-Bis]

Il problema è che ho l'algoritmo ma non ho la sua giustificazione formale. Adesso sto studiando l'equazione proposta da repne.

[wingman87]

La formula del primo post a me sembra corretta. Ho anche ricontrollato le slide di calcolo e a meno di aver fatto errori nel ragionamento dovrebbe funzionare.

[wingman87]

Originariamente inviato da PGI-Bis

Il problema è che ho l'algoritmo ma non ho la sua giustificazione formale. Adesso sto studiando l'equazione proposta da repne.

Bisogna partire dalle combinazioni semplici che sono definite come:
"Diciamo combinazione semplice di n oggetti k a k ogni sottoinsieme di N contenente k oggetti. Ovvero ogni scelta di k oggetti di N"
C(n,k)=n!/[k!*(n-k)!]
Che è anche la formula del coefficiente del binomio di Newton

Poi si usano le permutazioni:
"Diciamo permutazione di n oggetti ogni possibile allineamento degli oggetti"
P(n)=D(n,n)=n!
Dove D indica le disposizioni semplici.

Quindi se N è la cardinalità del tuo insieme fai:
la sommatoria per k che va da 0 a N di (le combinazioni k a k di N oggetti * il numero di permutazioni di un insieme di k elementi)