Collana n-colorata

[Simo_the_wolf]

Quanti modi ci sono di fare una collana con 2n perle di n colori in modo che ci siano 2 perle colorate per ogni colore e che le 2 perle di un determinato colore non siano adiacenti?

[enomis_costa88]

Dopo avere tentato per un po' (ed essendomi incasinato tantissimo) di cercarla in forma polinomiale (emm è quasi impossibile quando si parla di permutazioni..però almeno la sommatoria avrei sperato di riuscire a toglierla) mi limito a postare questo modesto lavoro (e potenzialmente erroneo) .

Step 1: Considerazioni sulla collana non ancora chiusa.

prima di chiuderla ho $ \frac{(2n)!}{2^n} $ anagrammi con ripetizione

Data una configurazione di perle, ad essa posso associare una 2n-upla {1,2...,2n} in base alla posizione delle perle, permutare la 2n-upla cambiando posizione alle perle.
sia j il numero di configurazioni di perle diverse che posso ottenere permutando ciclicamente (con un ciclo di lunghezza 2n) per 1,2,...,2n volte la 2n-upla associata alla configurazione di perle.

Queste j configurazioni saranno equivalenti una volta chiusa la collana.

Step 2:$ j \in $ {2n;n}
Perchè si riproduca la stessa configurazione prima di 2n permutazioni come sopra descritte della 2n-upla associata deve ripetersi una stessa configurazione di perle più volte lungo la collana.
Infatti è ovvio che se j<2n allora una perla di un colore ha preso il posto di un'altra perla dello stesso colore e viceversa; se così non accadesse j=2k; ciò può accadere solamente ogni n (posso avere max 2 perle per colore) mosse quindi l'altro valore (che si verifica facilmente come accettabile) è 2n.

Step 3: quando j=2n e quando j=n?

J = n se e solo se ogni perla di un colore ha sostituito l'altra perla dello stesso colore dopo n sciftamenti.
Ciò è possibile solamente per n! anagrammi delle perle perchè si deve seguire la seguente struttura:
creo 2n uple con n perle di n colori $ \not = $ ; pongo ciascuna perla dello stesso colore a n posti di distanza ovvero dopo avere permutato come voglio la prima n-upla le posizioni della seconda sono fisse.

Per i restanti $ \frac{(2n)!}{2^n} -n! $ valori ho j=2n.

Step 4: Le possibili collane n-colorate ove ci sono 2 perle per ogni colore sono:

$ \frac{\frac{(2n)!}{2^n} -n!}{2n} + \frac{n!}{n} $ =$ [\frac{(2n)!}{2^n} +n!]\frac{1}{2n} $

Lemma 1: se posso anagrammare una i-upla in m modi e j=i sempre allora gli anagrammi una volta chiusa la collana ovvero a meno di permutazioni cicliche (di ciclo i) della i-upla di numeri associata sono: $ \frac{m}{i} $
vero perchè ad ogni anagramma ne equivalgono (a meno di permutazioni cicliche con ciclo lungo i) altri i.

noto che j= numero di perle (sempre) in tutti quei casi in qui una perla non ha compagna.. e quando ho fissato una coppia.

Lemma 2: se ho due perle adiacenti e indistinguibili posso considerarle come una sola perla (se non ne ho altre uguali alle 2 stesse non ho poi tante altre condizioni da porre).

Step 5: Se ho k coppie fissate allora potrò anagrammare la collana aperta in questo modo: ponendo una coppia (che posso scegliere in almeno k modi diversi) agli estremi della collana e ponendo le altre k-1 come k-1 perle per il lemma 2; alle permutazioni trovate in questo modo devo poi aggiungere quelle in cui ho posto k coppie di perle come k perle.
Quando chiudo la collana: le collane trovate nel secondo metodo vanno divise per 2n-k per trovare le collane chiuse corrispondenti; questo per il lemma 1. Invece le collane trovate con il primo metodo non vanno neppure contate perchè applicando una permutazione ciclica in cui il ciclo è 2n-k+1 (ovvero sciftando le perle) ottengo sicuramente una collana già contata;

Le configurazioni che hanno una coppia data sono (considerando la coppia come un'unico elemento perchè le perle della stessa sono indistinguibili e adiacenti) $ \displaystile \frac{\frac{(2n-1)!}{2^{n-1}}}{2n-1} $
essendo una collana e quinidi a meno di permutazione ciclica di lunghezza 2n-1 (con j=2n-1 sempre) posso porre la scritta di prima = $ \displaystile \frac{(2n-2)!}{2^{n-1}} $
le coppie possibili (sottinteso dello stesso colore) sono n quindi le collane irregolari saranno < di: $ \displaystile n \frac{(2n-2)!}{2^{n-1}} $

Step 6: è palese che ho contato delle configurazioni più volte..per sapere il numero esatto devo usare il principio inclusione-esclusione ovvero..

collane con fissata una:
singola coppie-coppia di coppie+terna di coppie-quaterna di coppie....+- n-upla di coppie.

inoltre fissate una certa i-upla di coppie sicuramente adiacentio per il lemma 2 posso considerare tutte le coppie appartenenti alla i-upla come i elementi invece che 2i (analogamente a prima);
per qualsiasi i-upla di coppie avrò $ {n \choose i} $ modi per sceglierla.
Nel calcolare ciò che segue devo inoltre tenere conto che parlo di configurazioni a meno di permutazioni cicliche con lunghezza del ciclo= numero di perle presenti e con sempre j= numero di perle presenti tenendo in considerazione l lemmi 1 e 2.

ottengo quindi che le configurazioni inaccettabili perchè contengono almeno una coppia sono:

$ \displaystile \sum^{n}_{k=1} (-1)^{k-1} {n \choose k} \frac{(2n-k-1)!}{2^{n-k}} $

Step 7: le regolari saranno quindi:

$ \displaystile{ [\frac{(2n)!}{2^n} +n!]\frac{1}{2n} + \sum^{n}_{k=1} (-1)^{k} {n \choose k} \frac{(2n-k-1)!}{2^{n-k}}} $

Buona giornata Simone

[Marco]

Step 3: quando j=2n e quando j=n?

J = n se e solo se ogni perla di un colore ha sostituito l'altra perla dello stesso colore dopo n sciftamenti [ NdM].

So far so good.

Ciò è possibile solamente per n! anagrammi delle perle perchè si deve seguire la seguente struttura:
creo 2n uple con n perle di n colori $ \not = $ ; pongo ciascuna perla dello stesso colore a n posti di distanza ovvero dopo avere permutato come voglio la prima n-upla le posizioni della seconda sono fisse.

E qui non ci siamo più. Controesempio: n=2. La collana con j = n è una sola (che è anche l'unica possibile): 1212. Però 2121 è identico a 1212.

@Simo: Il testo così com'è non è chiaro. Puoi precisare meglio che cosa vuol dire "modi diversi di fare una collana"?

E poi, ad occhio, non sembra esserci una soluzione facile (modulo granchi del sottoscritto: ormai mi conoscete...) Ci garantisci che la soluzione abbordabile ci sia?

[enomis_costa88]

E qui non ci siamo più. Controesempio: n=2. La collana con j = n è una sola (che è anche l'unica possibile): 1212. Però 2121 è identico a 1212.

Mi scuso per delle imprecisioni formali che saranno certamente contenute lassu..

Pongo a mia disculpa il fatto che è la prima volta che provo ad usare in modo così "imponente" la teoria delle permutazioni in un problema e sicuramente mi sarò in più punti espresso male.

In questo caso mi pare corretto perchè esistono 2! anagrammi (stò parlando di anagrammi diversi non ancora di collane) con j=n=2.
2121 e 1212.
Posso immaginare il conteggio che ho effettuato sopra come il conteggio del numero possibile di collane aperte; più avanti avevo contato le possibili collane totali tenendo conto che devo dividere per n gli anagrammi con j=n e per 2n gli anagrammi con j=2n per ottenere le possibili configurazioni accettabili.
Le configurazioni accettabili con n=j sono n!/n=1 se n=2.

Inoltre se voglio sapere quante sono le accettabili con 2 perle sostituisco nel risultato dello step7.
(24/4 + 2) /4 - 2 +1=1 come dici tu.

Insomma l'idea è più o meno questa:
calcolo le possibili collane APERTE con j=n;
calcolo le possibili collane aperte con j=2n;
chiudo le collane e calcolo quante sono quelle chiuse tenendo conto che ove j=2n avrò 2n collane equivalenti tra loro e ove j=n avrò solamente n collane equivalenti tra loro.
Dopodichè calcolo le collane che non vanno bene (usando il principio di inclusione esclusione..è come se dovessi contare gli elementi di un'insieme sapendo la cardinalità dei suoi sottoinsiemi e le intersezioni tra i vari sottoinsiemi) e faccio una sottrazione per ottenere il risultato finale.

Buona Serata

[ma_go]

uhm...
io posto l'idea che avevo provato a sviluppare (non troppo approfonditamente, devo ammetterlo), e la scrivo in bianco, nel caso qualcuno preferisse non leggere...

intanto, mi pare che questa soluzione dovrebbe contemplare il caso di collane distinte a meno di rotazioni, ma non di simmetrie... per capirci ABCABC è diverso da CBACBA...

ora, prendiamo una collana lunga n+3, con i colori numerati, e proviamo a rimuovere le due perle di uno stesso colore... abbiamo tre possibilità:
- otteniamo una collana n+2 "valida";
- otteniamo una collana n+1 "valida" più due perle vicine di uno stesso colore;
- otteniamo una collana n "valida" più due coppie di perle vicine di due stessi colori.
adesso, viceversa, da ciascuna di queste possibilità ricaviamo:
- da una collana n+2 "valida" otteniamo n(2n-1) collane n+3 "valide";
- da una collana n+1 "valida" più una coppia di perle vicine di uno stesso colore otteniamo (2n)² collane n+3 "valide";
- da una collana n valida più due coppie di perle di due stessi colori otteniamo (2n)² collane n+3 "valide".
a questo punto, dovrebbe essere possibile scrivere la ricorsione (che è praticamente già scritta), però mi sovviene qualche dubbio (che magari potrei provare a fugare, se non fosse mezzanotte e se praticamente non ci vedessi fuori dalla sonno), riguardo ad eventuali altri fattori n o n-1 o n-2 o cose simili, per via delle scelte troppo arbitrarie dei colori...
però ragionevolmente la ricorrenza dovrebbe venire:
c_{n+3} = 2n(n+1)c_{n+2} + 4n²c_{n+1} + 4n²c_{n},
con c_0 = 1 (per convenzione), c_1 = 0, c_2 = 1,
e la corrispondente serie generatrice dovrebbe soddisfare la relazione
s-1-x² = 2x²D(xs') - x²s' + 4x³D(xs') + 4x²²D(xs').

desidero porre l'accento sui condizionali

[enomis_costa88]

intanto, mi pare che questa soluzione dovrebbe contemplare il caso di collane distinte a meno di rotazioni, ma non di simmetrie... per capirci ABCABC è diverso da CBACBA...

Anche io l'avevo pensato così sennò diventa troppo difficile (almeno con la mia idea j potrebbe assumere valori fino a 4n mi pare).
Piuttosto mi piacerebbe sapere ovviamente se ho sbagliato qualcosa nella soluzione (e nel caso come aggiustarla).

PS ho verificato il mio risultato sui casi piccoli (n=1,2,3 anzi per n=3 ho verificato solamente i casi in cui j=n e i casi irregolari..e tutto torna però potrebbero sempre esserci delle imprecisioni che si vedono solo su casi più grandi )

[enomis_costa88]

@ma_go: Penso ci sia qualche problema con la ricorsione.

c_3 è definito come c_3=2*0*1*1+4*0^2*0 +4*0^2*1.
eppure mi parrebbe proprio essere 5.

infatti:
abcabc; cbacba; bcbaca; cbcaba; cacbab

che è poi il risultato che si ottiene con il mio metodo
(720/8 +6)/6 -3*24/4+3*6/2-1*2 = 5

PS è sottinteso che però messi a posto questi dettagli risolvere il problema attraverso una ricorsione è più elegante (e "compatto") che non con una sommatoria

[ma_go]

uhm.. sì, mi hanno segnalato l'errore, provvederò a sistemare la questione, se possibile...