Trovare il numero di permutazioni dove non compaiono gli stessi elementi adiacenti

[crissstian96]

Salve, innanzitutto mi scuso nel caso la categoria non dovesse essere corretta, ero indeciso se postarla qua o in "Statistica e probabilità", ma dal momento che si tratta di un quiz che ho trovato online e che per quanto si parli permutazioni non è detto che abbia qualcosa a che fare con la statistica, alla fine ho deciso di postare qua.
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:

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.

Grazie.

[Pachisi]

Ho trovato qualcosa, ma non è in forma chiusa. Magari qualcuno riesce a trovare un'interpretazione combinatorica.

Lettere uguali le considero uguali.
Faccio vedere il caso con 3 lettere, $A,B,C$. Non mi sembra troppo difficile generalizzare, ma diventa tedioso.
Supponiamo di avere la stringa $\underset{x_1}{\underbrace{A...A}}\underset{x_2}{\underbrace{B...B}}\underset{x_3}{\underbrace{C...C}}$. Osserviamo che ogni stringa che funziona è delle forma: $-\underset{i_1}{\underbrace{B...B}}-\underset{j_1}{\underbrace{C...C}}-...-\underset{i_n}{\underbrace{B...B}}-\underset{j_m}{\underbrace{C...C}}-$ dove: i) C'è una $A$ tra ogni due $B$ e ogni due $C$, ii) ogni $-$ rappresenta una posizione dove possiamo mettere al massimo una $A$, iii) $i_1+i_2+...+i_n=x_2$ con $0 \le i_k \le x_2$ per ogni $k$ e $n \in {1,2,...,x_2}$, $j_1+j_2+...+j_m=x_3$ con $0 \le j_k \le x_3$ per ogni $k$ e $m \in {1,2,...,x_3}$. Ora, il numero di stringhe che funzionano è uguale al modo di posizionare al massimo una $A$, tra le rimanenti, in ogni $-$. Calcolo il numero di $A$ usate: visto che c'è una $A$ tra ogni due $B$ e tra ogni due $C$, il numero di $A$ usate è $(i_1-1)+(i_2-1)+...+(i_n-1)+(j_1-1)+(j_2-1)+...+(j_m-1)=x_2+x_3-n-m$. Quindi, il numero di $A$ rimanenti è $x_1-x_2-x_3+n+m$. Queste possiamo posizionarle nelle rimanenti $n+m+1$ posizioni (il numero di segni $-$). Visto che possiamo mettere al massimo una $A$ in ogni $-$, abbiamo $((n+m+1),(x_1-x_2-x_3+n+m))=((n+m+1),(x_2+x_3+1-x_1))$ opzioni. Quindi, in totale abbiamo $\sum_{1\le n \le x_2, 1\le m \le x_3} ((n+m+1),(x_2+x_3+1-x_1))$ stringhe dove per ogni $n$ e $m$, l'ordine in cui appaiono gli $i_k$ e $j_k$ importa.
Mi dispiace, ma è abbastanza brute force. Spero che almeno il ragionamento sia chiaro.

[consec]

Ciao, stavo pensando un po' a questo problema, ti dispiacerebbe dirmi quante sono le permutazioni di AAAAABCDFFFF (cinque A, quattro F, tre lettere qualsiasi) tali che non compaiono lettere uguali adiacenti (considerando anche le permutazioni delle lettere ripetute, quindi assumendole distinguibile, come negli esempi che hai già postato)? Purtroppo non saprei dove trovare l'algoritmo necessario su internet per procurarmi gli esempi da solo

[vict85]

Al di là del fatto che permutazioni, in algebra, ha il significato di biiezione e quindi esclude il caso di ripetizioni, non capisco perché pensiate che sia più facile cercare il numero di stringhe con ripetizioni. Insomma una parola senza ripetizioni è semplicemente una parola in cui la \(\displaystyle (n+1) \)-esima lettera è diversa dalla \(\displaystyle n \)-esima lettera. Quindi se l'alfabeto è formato da \(\displaystyle m \) lettere e le parole sono di lunghezza \(\displaystyle s \) allora puoi scegliere la prima lettera tra \(\displaystyle m \) lettere diverse e le successive tra \(\displaystyle (m-1) \) lettere (tutte le lettere meno quella scelta precedentemente). Insomma il valori che cerchi è \(\displaystyle m(m-1)^{s-1} \) parole.

[Pachisi]

@vict85:
Mi sembra che il problema che tu stia risolvendo sia leggermente diverso. Tu supponi di non avere restrizioni sul numero di ogni lettera (quindi puoi sceglierne $m-1$ ogni volta), mentre il problema era di determinare il numero di permutazioni buone data una stringa di lettere.

[superpippone]

E' da un po' di giorni che penso a questo quesito.
Ritengo che la strada di cercare una formula generale non sia percorribile.
Troppe le variabili.
Fino alla sequenza AABBCC, riesco a trovare una soluzione.
Ma oltre non ci arrivo.
Penso che una sequenza AAAAABBBBCCCDDEFGH sia da delirio.....

Ritengo invece che con un programmino impostato in maniera diversa, la faccenda non sia troppo complicata.
A saper programmare, ovvio....

@Pachisi: con la tua formula quante ti risultano le stringhe diverse per AABBCC? Io ne ho trovate 240.

[Pachisi]

A me viene 30, ma considero le due A, le due B, le due C uguali tra di loro. Distinte, viene 240.

[superpippone]

Behh, anche a me viene 30.
Ma siccome lui "distingue" le lettere uguali $30*2!*2!*2! = 240$
Però oltre non vado....