Partizioni da 3 elementi

[jordan]

Dato l'insieme $S=\{1,\ldots,n\}$ con $n$ intero maggiore di $2$, in quanti modi è possibile partizionarlo in tre sottoinsiemi $A,B,C$ non vuoti?

Bonus: E con 4?

[Delfad0r]

Se non ci fosse la restrizione che i tre sottoinsiemi non fossero vuoti, avremmo $3^n$ diversi modi (ciascun elemento potrebbe finire in $A$, $B$ oppure $C$).
Dobbiamo però sottrarre a questi i casi in cui almeno uno fra $A, B, C$ è vuoto. Grazie al principio di inclusione-esclusione, otteniamo che il numero da sottrarre è $\binom{3}{2} 2^n - \binom{3}{1}$; infatti, possiamo scegliere $\binom{3}{2}$ coppie in $\{A,B,C\}$, e per ciascuna di queste esistono $2^n$ modi di ripartire gli $n$ elementi; possiamo invece scegliere $\binom{3}{1}$ elementi singoli in $\{A,B,C\}$, e per ciascuno di questi c'è un solo modo di ripartire gli $n$ elementi.
Dunque il numero di modi di ripartire gli $n$ elementi in tre sottoinsiemi $A, B, C$ non vuoti è
$3^n-3 \cdot 2^n+3$.

Se il metodo è giusto (cosa di cui non sono troppo sicuro), allora il bonus si fa quasi uguale.

[jordan]

Si è corretto! Riguardo il bonus, non è esattamente uguale..

[Delfad0r]

Sono contento che sia corretto (ho usato un metodo simile in un quesito del TF)!

Per quanto riguarda il bonus, mi stai dicendo che non è
$4^n-\binom{4}{3} \cdot 3^n+ \binom{4}{2} \cdot 2^n - \binom{4}{1}$
?

[Loara]

Dunque il numero di modi di ripartire gli $n$ elementi in tre sottoinsiemi $A, B, C$ non vuoti è
$3^n-3 \cdot 2^n+3$

Se però poniamo $n=3$, non vi è un solo modo di "partizionare" il'insieme ($\{1\}\{2\}\{3\}$), mentre dalla tua formula si evince che $3^3-3\cdot 2^3+3=27-24+3=6$ otteniamo anche tutte le possibili permutazioni di tali sottoinsiemi . O forse sono io che ho capito male .

[Delfad0r]

Boh, io avevo capito che $({1},{2},{3})$ e $({1},{3},{2})$ fossero da considerarsi partizioni distinte. Poi non so, è jordan l'autore del problema...

[jordan]

Il risultato cambierebbe soltanto di una costante $3!$, quindi non c'è problema in entrambe le interpretazioni. Riguardo il secondo post di Delfad0r, se metti $n=5$ il risultato viene $6\cdot 4!$ (modulo conti), giusto? Dov'è il problema?

[Delfad0r]

Il risultato cambierebbe soltanto di una costante $3!$, quindi non c'è problema in entrambe le interpretazioni. Riguardo il secondo post di Delfad0r, se metti $n=5$ il risultato viene $6\cdot 4!$ (modulo conti), giusto? Dov'è il problema?

In realtà secondo i miei calcoli verrebbe
$4^5-4 \cdot 3^5+6 \cdot 2^5-4=1024-972+192-4=240=10 \cdot 4!=\binom{5}{2} \cdot 4!$
che ha senso, perchè posso scegliere in $\binom{5}{2}$ i 2 elementi da mettere insieme, e una volta fatto questo ho $4!$ modi di distribuire i 4 (+1 che però sta insieme all'altro) elementi. Non capisco dove stia l'errore

[jordan]

Niente, apposto cosi: la tua ricorsione è giusta. Anche se a prima vista non sembra, è collegato a questo: l'errore che ho fatto in quella dimostrazione (che mi è stato fatto notare da Gottinger ieri notte) è che se, per esempio, si devono partizionare 4 oggetti in 2 sottoinsiemi, non necessariamente 3 elementi fanno parte dello stesso sottoinsieme (il che è ovvio, detto cosi, ma scrivendo la ricorsione sbagliata..).

Un corollario della tua formula: Definiamo $f(n,k)$ il numero di modi di partizionare gli interi $\{1,\ldots,n\}$ in $k$ sottoinsiemi. Allora esiste un $k$ sufficientemente grande tale che $2^k$ divide $f(n,2k)$.

[Delfad0r]

Sarebbe dunque non troppo azzardato affermare che
$f(n,k)=\sum_{i=1}^{k} (-1)^{k-i} \binom{k}{i} \cdot i^n$
?

[jordan]

Si, va bene. Qualcuno che risolve il corollario?

[Loara]

E' facile dedurre che:
$$
f(n, k)=k!S(n, k)
$$
con $S(n, k)$ i numeri di Stirling di seconda specie, ovvero il numero di partizioni di $n$ elementi in $k$ insiemi non ordinati. Il corollario diventa allora equivalente a dimostrare:
$$
2^k\, | (2k)!
$$
Ragioniamo per induzione: l'affermazione è vera per $k=1$, supponendo che sia vera per $k$, dimostriamo che è vera anche per $k+1$, ovvero
$$
2^{k+1}\, |[2(k+1)]!\rightarrow 2\cdot 2^k\, |(2k)!(2k+1)(2k+2)
$$
poichè $2k+2$ è pari, allora $2\, |(2k+1)(2k+2)$, e da ciò segue la tesi.