Tavoli rotondi e distinzione di sessi

[Gatto]

Premetto che non so la soluzione , è un problema che ho trovato e che mi ha dato qualche problema...

"Ad una festa in maschera ci sono $ 2n $ persone, $ n $ maschi e $ n $ femmine. In quanti modi si possono sedere in un tavolo rotondo, se l'unica distinzione è tra maschi e femmine?"

[Alex90]

Ci provo...

le persone si possono disporre in $ 2n! $ modi, considerando poi le persone uguali e le rotazioni diventano:

$ \displaystyle \frac{2n!}{2n\cdot n! \cdot n!} = \frac{(2n-1)!}{n!^2} $

[Gatto]

Ci provo...

le persone si possono disporre in $ 2n! $ modi, considerando poi le persone uguali e le rotazioni diventano:

$ \displaystyle \frac{2n!}{2n\cdot n! \cdot n!} = \frac{(2n-1)!}{n!^2} $

Uno dei primi pensieri fatti anch'io... però $ n = 2: $

$ \displaystyle \frac{3!}{2!2!} = \frac{3}{2} $ che non è intero

[SkZ]

a sto punto ci si puo' aiutare empiricamente
n=1 si ha 1 modo
n=2 si hanno 2 modi
n=3 si hanno 4 modi
n=4 si hanno 10 modi

edit: dimenticato un caso per n=4, contato doppio un altro, ergo era giusto

[piever]

Uhm, ho paura che il risultato non si scriva in maniera molto decorosa..

Per adesso direi che il risultato è:

$ \displaystyle \frac{1}{2n}\sum_{d|n} {2d\choose d} \cdot\phi\left(\frac{n}{d}\right) $

che, stando alla tabella di skz, funziona per n=1,2,3,4... (cosa di cui sono genuinamente sorpreso...)

La mia dimostrazione è ai limiti dell'indecenza però... Qualcuno ne ha di più decorose prima che mi avventuro a postarla?

l'unica distinzione è tra maschi e femmine

Giusto per curiosità, è opera tua questa bizzarra formulazione del problema?

[SkZ]

non sono sicuro (non ho controllato) ma mi pare che (escludendo il caso n=1) ci sia una soluzione semplice.
Cmq, perche' quella formula? ovvero come la giustifichi?

[Gatto]

l'unica distinzione è tra maschi e femmine

Giusto per curiosità, è opera tua questa bizzarra formulazione del problema?

No, è un problema che ho trovato in giro... cmq sono curioso del perchè della formula (e della dimostrazione )

[piever]

Uhm, ecco un modo non troppo sottile per dimostrare quella formula:

Ogni disposizione possibile di maschi e femmine ha un ordine (vale a dire il numero minimo k tale che shiftando tutto di k posti da una parte ottengo la stessa configuarazione di maschi e femmine). Di conseguenza la configurazione si ottiene prendendo il primo "blocco" di k tizi seduti e ripetendoglielo accanto fino a riempire la tavola, quindi tra queste k persone, metà sono maschi e metà sono femmine, per cui k=2m per qualche m (m è il numero di maschi). Ora, visto che k|2n, allora m|n, quindi in sostanza l'idea è contare tutte le configurazioni che hanno ordine 2m con m divisore di n, e dividere ciascuna quantità per l'ordine (perché a noi interessano a meno di rotazioni).

Chiamiamo f(m) le configurazioni di ordine 2m (per ora _non_ le conto a meno di rotazioni): è chiaro che, per ogni m, $ \displaystyle\sum_{d|m}f(d)={2m\choose m} $ da cui $ \displaystyle f(m)=\sum_{d|m}{2d\choose d}\cdot \mu \left(\frac{m}{d}\right) $

Ora la quantità che a noi interessa è dunque:

$ \displaystyle\sum_{m|n} \frac{f(m)}{2m}=\sum_{m|n}\frac{1}{2m}\sum_{d|m}{2d\choose d}\cdot \mu \left(\frac{m}{d}\right)=\sum_{d|n}{2d\choose d}\sum_{d|m|n}\frac{1}{2m}\cdot \mu \left(\frac{m}{d}\right)= $

$ \displaystyle =\frac{1}{2n}\sum_{d|n}{2d\choose d}\sum_{\delta |\nu }\frac{\nu}{\delta }\cdot \mu(\delta )= \frac{1}{2n}\sum_{d|n}{2d\choose d}\cdot\phi (\nu )=\frac{1}{2n}\sum_{d|n}{2d\choose d}\cdot\phi \left(\frac{n}{d}\right) $

Dove $ \displaystyle\nu =\frac{n}{d} $ e $ \displaystyle\delta =\frac{m}{d} $

Ora, se la sommatoria finale possa essere scritta in maniera più decorosa mi è ignoto...

P.S. Skz, qual è la soluzione facile?

[SkZ]

avevo poco tempo e una soluzione simil giusta, ergo in scioltezza, la parte $ $f(n)=\frac{(2n)!}{n!n!} $ e' sicuramente giusta, basta solo trovare il valore di $ ~k $ tale che $ $\frac{f(n)}{k} $ sia la soluzione
dai i tentativi a mano hai
$ $n=1\Rightarrow f(n)=2\Rightarrow k=2 $
$ $n=2\Rightarrow f(n)=6\Rightarrow k=3 $
$ $n=3\Rightarrow f(n)=20\Rightarrow k=5 $
$ $n=4\Rightarrow f(n)=70\Rightarrow k=7 $
allora le cose sono 2:
1) k e' l'n-esimo primo: assurdo e cmq si vede che per $ ~n=5 $ non vale ($ ~11\not|252 $)
2) $ ~k=2n-1 $ e escludo $ ~n=1 $ come caso anomalo: ha piu' senso e piu' facile da trovare una giustificazione

ergo $ $\frac{(2n)!}{(2n-1)n!n!} $

Cmq non e' giusto!! appena accorto che mi ero doimenticato un caso nel n=4, quello in cui sono alternati.
a volte il caso e' molto bastardo

la frase sopra e' sbagliata.
avevo contato 2 volte un caso, ergo i conti tornano di nuovo

[gismondo]

Credo si possa generalizzare in questo modo:
Dati $ $2n $ oppure $ $2n+1 $ individui di cui $ $k $ maschi il numero di modi in cui si possono disporre attorno a un tavolo rotondo è:

$ \frac{1}{2n-1} {2n\choose k} $
oppure $ \frac{1}{2n+1} {2n+1\choose k} $

[Tibor Gallai]

Falliscono già per n=6.

[Gatto]

Tibor per n = 5 e n = 6 quanto dovrebbe venire?

[piever]

Falliscono già per n=6.

Uhm, a quali ti riferisci?

E sopratutto, qual è, secondo te, la soluzione al problema originale di Gatto?

@ gismondo: uhm, mi sembra ottimista generalizzare a quel modo...

@ Gatto: a me risulta che per n=5 sono 26 e per n=6 sono 80... Mah...

EDIT: Ok Tibor, ora ho riguadagnato fiducia in me stesso

Tra l'altro, sai se il risultato finale si può scrivere decentemente??

[Tibor Gallai]

Ah, io concordo con la soluzione di piever!
Dicevo che le varie altre soluzioni e/o generalizzazioni falliscono per n=6.
Almeno, così mi pare.

[SkZ]

la mia sol "empirica" dice 28 per n=5 e 84 per n=6

una sovrastima del 7.7 e 5%. Beh, non posso lamentarmi.
E' abbastanza esatta!

ma li avete contati tutti a mano? per n=6
per n=7 sarebbero 246. Chi controlla?