Il quesito è il seguente: data una sequenza di lettere, trovare il numero di permutazioni dove non compaiono lettere ripetute adiacenti.
Ad esempio per la sequenza AAB noi abbiamo:
AA'B -> non va bene
A'AB -> non va bene
ABA' -> va bene
A'BA -> va bene
BAA' -> non va bene
BA'A -> non va bene
(per evitare confusione ho distinto le due A chiamandole una A e una A', ma si tratta a tutti gli effetti della stessa lettera.)
In ogni modo in questo caso le permutazioni senza lettere ripetute consecutive sono due, cioè ABA' e A'BA.
Qui vi sono i risultati di altre sequenze, utile per testare:
aab: 2
aaa: 0
aabb: 8
abcdefa: 3600
abfdefa: 2640
aaabb: 12
Ora faccio una premessa, questo quesito online prevede la soluzione tramite un algoritmo in linguaggio Javascript, dunque è possibile che non ci sia nessuna formula elegante capace di trovare il numero desiderato e l'unico modo sensato in cui procedere sia la forza bruta (che io non amo), ma visto che ho provato a risolverlo matematicamente e ci sono andato molto vicino (di seguito posto la mia dimostrazione, manca solo un piccolo pezzo), ho pensato che valesse la pena chiedere a voi geni, anche solo per sapere se ho sbagliato qualcosa.
La mia soluzione parziale è questa:
Testo nascosto, fai click qui per vederlo
Data una sequenza di $\n$ lettere abbiamo $\ n! $ permutazioni, dunque ci basterà trovare il numero di combinazioni dove vi siano almeno due lettere adiacenti ripetuti per poter calcolare $\ n! - r $.
Se definiamo $\ k $ come il numero di lettere ripetute in una sequenza, allora il numero di permutazioni in cui troviamo la ripetizione nelle prime $\ k $ posizioni è $\ k! * (n-k)! $.
A questo punto a noi interessa sapere il numero di lettere adiacenti ovunque, e non solo nelle prime posizioni. Dunque moltiplichiamo tutto per il numero di posizioni possibili, cioè $\ (n - k + 1) $.
In conclusione il numero di permutazioni senza lettere adiacenti ripetute è:
$\ n! - k! * ( n - k + 1)! $
Consideriamo il caso abcdefa, il numero di lettere è 7, il numero di ripetizioni è 2, dunque abbiamo:
$\ 7! - 2!* (7 - 2 + 1 )! = 3600 $
E fin qui tutto bene.
Il problema si presenta quando le lettere ripetute sono più di una, ad esempio in aaabb. Un buon modo per procedere sarebbe di sottrarre prima le lettere ripetute in aaabc e poi quelle in abcdd (cioè quando contiamo le ripetizioni di A consideriamo le B come lettere qualsiasi, e viceversa) però in questo caso conteremmo le intersezioni due volte (anche il caso banale aaabb lo prendiamo in considerazione sia quando contiamo le a e quando contiamo le b).
Dunque definendo k le ripetizioni di a, e k' le ripetizioni di b, avrei:
$\ n!-k!(n-k+1)! -k'!(n-k'+1)+text{intersezione dei due insiemi} $.
Arrivato a questo punto non so proprio come procedere, spero che qualcuno possa darmi una delucidata.
Se definiamo $\ k $ come il numero di lettere ripetute in una sequenza, allora il numero di permutazioni in cui troviamo la ripetizione nelle prime $\ k $ posizioni è $\ k! * (n-k)! $.
A questo punto a noi interessa sapere il numero di lettere adiacenti ovunque, e non solo nelle prime posizioni. Dunque moltiplichiamo tutto per il numero di posizioni possibili, cioè $\ (n - k + 1) $.
In conclusione il numero di permutazioni senza lettere adiacenti ripetute è:
$\ n! - k! * ( n - k + 1)! $
Consideriamo il caso abcdefa, il numero di lettere è 7, il numero di ripetizioni è 2, dunque abbiamo:
$\ 7! - 2!* (7 - 2 + 1 )! = 3600 $
E fin qui tutto bene.
Il problema si presenta quando le lettere ripetute sono più di una, ad esempio in aaabb. Un buon modo per procedere sarebbe di sottrarre prima le lettere ripetute in aaabc e poi quelle in abcdd (cioè quando contiamo le ripetizioni di A consideriamo le B come lettere qualsiasi, e viceversa) però in questo caso conteremmo le intersezioni due volte (anche il caso banale aaabb lo prendiamo in considerazione sia quando contiamo le a e quando contiamo le b).
Dunque definendo k le ripetizioni di a, e k' le ripetizioni di b, avrei:
$\ n!-k!(n-k+1)! -k'!(n-k'+1)+text{intersezione dei due insiemi} $.
Arrivato a questo punto non so proprio come procedere, spero che qualcuno possa darmi una delucidata.
Grazie.