8 oggetti 6scatole

[danielf]

in quanti modi si possono sistemare otto oggetti distinti in sei scatole diverse sapendo che in ogni scatola deve esserci almeno un oggetto?

[Giulius]

Messi i primi 6 oggetti in ciascuna scatola (8!/2! possibilità) dobbiamo scegliere come mettere i rimanenti 2. Ci sono due casi incompatibili:
1. Tutti e due nella stessa scatola (6 possibilità)
2. Ciascuno dei due in una scatola diversa (6*5 possibilità).
Abbiamo però contato più di una volta alcuni casi:
nell'1 con il modo di contare applicato ho contato 3 volte ogni caso (perchè l'ordine con cui gli oggetti vengono messi nella scatola è irrilevante in questo problema);
nel 2 con il modo di contare applicato ho contato 4 volte ogni caso (per lo stesso motivo).
In definitiva le possibilità sono:

$ N=\displaystyle \frac {\frac{8!}{2!}6}{3}+\frac{\frac{8!}{2!}6*5}{4}=191520 $

[Claudio.]

Messi i primi 6 oggetti in ciascuna scatola (8!/2! possibilità) dobbiamo scegliere come mettere i rimanenti 2. Ci sono due casi incompatibili:
1. Tutti e due nella stessa scatola (6 possibilità)
2. Ciascuno dei due in una scatola diversa (6*5 possibilità).
Abbiamo però contato più di una volta alcuni casi:
nell'1 con il modo di contare applicato ho contato 3 volte ogni caso (perchè l'ordine con cui gli oggetti vengono messi nella scatola è irrilevante in questo problema);
nel 2 con il modo di contare applicato ho contato 4 volte ogni caso (per lo stesso motivo).
In definitiva le possibilità sono:

$ N=\displaystyle \frac {\frac{8!}{2!}6}{3}+\frac{\frac{8!}{2!}6*5}{4} $

Non ho capito perchè dividi per 3 e per 4, le due statuette insieme posono essere messe in 6 scatole diverse, quindi moltiplicando per 6 non conti anche l'ordine....e per l'altro la stessa cosa.

[Giulius]

Dal testo mi pare di capire che le scatole sono tutte distinte così come gli oggetti.
Chiamo A,B,C,D,E,F le scatole e 1,2,3,4,5,6,7,8 gli oggetti.
Nel primo caso (3 oggetti in una stessa scatola e 1 nelle altre 5 scatole) contavo come distinti ad esempio i casi:
* delle 8!/2! scelte per i primi oggetti scelgo A1B2C3D4E5F6 e poi aggiungo la coppia 7,8 nella scatola F -> A1B2C3D4E5F678
** delle 8!/2! scelte per i primi oggetti scelgo A1B2C3D4E5F7 e poi aggiungo la coppia 6,8 nella scatola F -> A1B2C3D4E5F768
*** delle 8!/2! scelte per i primi oggetti scelgo A1B2C3D4E5F8 e poi aggiungo la coppia 6,7 nella scatola F -> A1B2C3D4E5F867
Ma non mi importa l'ordine con il quale inserisco gli oggetti nella scatola quindi questi tre casi sono equivalenti.
Nel secondo caso (2 oggetti in 2 scatole e un solo oggetto nelle restanti 4) contavo come distinti ad esempio i casi:
* delle 8!/2! scelte per i primi oggetti scelgo A1B2C3D4E5F6 e poi aggiungo la coppia 7,8 nella scatola A e nella B -> A17B28C3D4E5F678
** delle 8!/2! scelte per i primi oggetti scelgo A7B2C3D4E5F6 e poi aggiungo la coppia 1,8 nella scatola A e nella B -> A17B28C3D4E5F678
*** delle 8!/2! scelte per i primi oggetti scelgo A1B8C3D4E5F6 e poi aggiungo la coppia 2,7 nella scatola B e nella A -> A17B28C3D4E5F678
**** delle 8!/2! scelte per i primi oggetti scelgo A7B8C3D4E5F6 e poi aggiungo la coppia 1,2 nella scatola A e nella B -> A17B28C3D4E5F678
Ma anche questi 4 casi sono tutti uguali per lo stesso motivo.
Mi scuso perchè sono terribilmente contorto a spiegare in effetti =) (posto che sia giusto come l'ho risolto...)

[iademarco]

Un modo leggermente diverso
distinguiamo subito i 2 casi:
1)3 oggetti che vanno in una stessa scatola
2)2 scatole che hanno 2 oggetti

1)Scegliamo le 5 scatole con 1 oggetto, scegliamo i 5 oggetti fra 8 da mettervi e moltiplichiamo per le possibili permutazioni:
$ \displaystyle{6 \choose 5}\cdot{8 \choose 5}\cdot{5!} $

2)Scegliamo le 4 scatole con 1 oggetto, scegliamo i 4 oggetti fra 8 da mettervi e moltiplichiamo per le possibili permutazioni di questi 4 e moltiplichiamo per i modi in cui possiamo posizionare i restanti 4 in 2 scatole:
$ \displaystyle{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6} $

In totale: $ \displaystyle{6 \choose 5}\cdot{8 \choose 5}\cdot{5!}+{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6}=40320+151200=191520 $

[danielf]

2)Scegliamo le 4 scatole con 1 oggetto, scegliamo i 4 oggetti fra 8 da mettervi e moltiplichiamo per le possibili permutazioni di questi 4 e moltiplichiamo per i modi in cui possiamo posizionare i restanti 4 in 2 scatole:
$ \displaystyle{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6} $

In totale: $ \displaystyle{6 \choose 5}\cdot{8 \choose 5}\cdot{5!}+{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6}=40320+151200=191520 $

non ho solo capito perchè moltiplichi per 6

[dario2994]

E se fossero 50 scatole e 100 oggetti...

[Giulius]

Alur...la differenza con il caso precedente è che non posso più fare la distinzione nei due casi come facevo prima (a meno di non essere masochista e avere tanta voglia di contare). Noto che il problema è analogo a contare le funzioni suriettive da un insieme di 100 oggetti in uno di 50 oggetti. Quindi sapendo che:
le funzioni f:A->B suriettive sono $ \displaystyle n=\sum_{i=0}^{|B|-1}(-1)^i\binom{|B|}{i}(|B|-i)^|^A^| $
Nel nostro caso |B|=50 e |A|=100
(infatti se pongo |B|=6 e |A|=8 la formula restituisce esattamente
$ 6^8-6*5^8+15*4^8-20*3^8+15*2^8-6=191520 $)

[dario2994]

Ovviamente è giusto... ma che ne dici di dimostrare quella formuletta ;)

[Giulius]

Ovviamente è giusto... ma che ne dici di dimostrare quella formuletta

ne dico che...non ne ho voglia =P.
Ora sto uscendo quindi vado un po' di fretta: l'idea è considerare le funzioni f:A -> B (|B|<=|A|) ma tali che f(A) sia strettamente un sottinsieme di B. Togliendo dal numero totale di funzioni |B|^|A| il numero di queste funzioni si ha il numero di funzioni suriettive.
Si classificano quindi le funzioni in insiemi C_i in cui l'i-esimo insieme è costituito da tutte e sole le funzioni f che non raggiungono l'i-esimo elemento di B (quindi 0<i<|B|+1). Si deve quindi contare la cardinalità dell'unione di questi insiemi tramite il principio IE. La cardinalità di ogni I_i è data da (|B|-1)^|A|, la cardinalità dell'intersezione a due a due degli I_i è (|B|-2)^|A| e quella dell'intersezioni a i a i (|B|-i)^|A|. Applicando IE e svolgendo i conti dovrebbe saltare fuori proprio quella formula....the details of the proof are left to the reader

[dario2994]

Perfetto :)
Giusto per completezza (anche se devo ammettere che è abbastanza chiara anche la sua proto-dimostrazione) ecco un link in Italiano in cui è presente la dimostrazione:
http://www.silsismi.unimi.it/SILSISMI/I ... toria1.pdf

[iademarco]

In totale: $ \displaystyle{6 \choose 5}\cdot{8 \choose 5}\cdot{5!}+{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6}=40320+151200=191520 $

non ho solo capito perchè moltiplichi per 6

moltiplico per i modi in cui possiamo posizionare i restanti 4 oggetti in 2 scatole, mettendone 2 in ogni scatola