Partizioni da 3 elementi
Partizioni da 3 elementi
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?
Bonus: E con 4?
The only goal of science is the honor of the human spirit.
Re: Partizioni da 3 elementi
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.
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.
Re: Partizioni da 3 elementi
Si è corretto! Riguardo il bonus, non è esattamente uguale..
The only goal of science is the honor of the human spirit.
Re: Partizioni da 3 elementi
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}$
?
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}$
?
Re: Partizioni da 3 elementi
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 ha scritto: 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$
$ 210^2+211^2+212^2+213^2+214^2+215^2+216^2+217^2+218^2+219^2+220^2=\\
=221^2+222^2+223^2+224^2+225^2+226^2+227^2+228^2+229^2+230^2\\
210=2*3*5*7 $
Re: Partizioni da 3 elementi
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...
Re: Partizioni da 3 elementi
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?
The only goal of science is the honor of the human spirit.
Re: Partizioni da 3 elementi
In realtà secondo i miei calcoli verrebbejordan ha scritto: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?
$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
Re: Partizioni da 3 elementi
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)$.
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)$.
The only goal of science is the honor of the human spirit.
Re: Partizioni da 3 elementi
Sarebbe dunque non troppo azzardato affermare che
$f(n,k)=\sum_{i=1}^{k} (-1)^{k-i} \binom{k}{i} \cdot i^n$
?
$f(n,k)=\sum_{i=1}^{k} (-1)^{k-i} \binom{k}{i} \cdot i^n$
?
Re: Partizioni da 3 elementi
Si, va bene. Qualcuno che risolve il corollario?
The only goal of science is the honor of the human spirit.
Re: Partizioni da 3 elementi
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.
$$
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.
$ 210^2+211^2+212^2+213^2+214^2+215^2+216^2+217^2+218^2+219^2+220^2=\\
=221^2+222^2+223^2+224^2+225^2+226^2+227^2+228^2+229^2+230^2\\
210=2*3*5*7 $