Vicini litigiosi

[decs]

Ci sono 16 case; in quanti modi posso sistemare 4 vicini in modo che ogni vicino è distante dall'altro di almeno due case? Due sistemazioni che occupano le stesse case (ma variano i vicini che occupano quelle case) sono da considerarsi uguali.

[Stef2008]

Sia $C_{l,n}$ il numero di modi di sistemare $l$ persone in $n$ case in modo che essi abbiano una distabza di almeno $2$ fra loro.
Chiaramente $C_{1,n}=n$.
Osserviamo che $C_{l,n}=C_{l,n-1}+C_{l-1,n-3}$, infatti nel mettere $l$ persone in $n$ case con quelle condizioni, abbiamo i casi in cui l'ultima è vuota che sono $C_{l,n-1}$, i casi in cui l'ultima è piena allora devo mettere altri $ l-1$, ma la casa $ n-1 $ e $ n-2 $ per le condizioni devono essere vuote... ne deriva la ricorsione.
$C_{2,n}=C_{2,n-1}+\max(0,n-3)$. Da cui facilmente
$C_{2,n}=1+2+...+(n-3)$ (esso è zero se tale quantità dovesse essere negativa).
$C_{3,n}=C_{3,n-1}+\binom{n-5}{2}$ con la convenzione che il binomiale è zero se il numero sotto è maggiore di quello di sopra (convenzione da applicare a tutti i binomiali anche nel resto della soluzione).
Quindi per n maggiori o uguali a 7:
$C_{3,n}=\sum_{i=7}^{n}\binom{i-5}{2}=\binom{2}{2}+...+\binom{n-5}{2}=\binom{n-4}{3}$
Se n minore di 7 allora $C_{3,n}=0$
Qui abbiamo usato una nota identità tra binomiali (se non la conosci te la linko: https://en.m.wikipedia.org/wiki/Hockey-stick_identity)
In modo analogo
$C_{4,n}=C_{4,n-1}+C_{3,n-3}=C_{4,n-1}+ \binom{n-7}{3}$

Per n maggiori uguali a 10:
$C_{4,n}=\sum_{i=10}^{n}\binom{i-7}{3}= \binom{3}{3}+...+\binom{n-7}{3}=\binom{n-6}{4}$, qui si usa la stessa identità di prima...
Quindi $C_{4,16}=\binom{10}{4}=210$. Che è ciò che cercavamo.
In generale $C_{l,n}=\binom{n-2(l-1)}{l}$, si può dimostrare per induzione su $ l$

Fammi sapere se ci sono cose poco chiare o errori

[decs]

Fammi sapere se ci sono cose poco chiare o errori

Tutto chiaro, ma ho ancora un dubbio; il problema si può ricondurre a quanti numeri [math]a, b, c, d, e tali che sia [math]a, e ≥ 0 e [math]b, c, d ≥ 2 sono tali che la loro somma sia 12, ossia quanti numeri [math]a, β, γ, δ, e tutti [math]≥ 0 sono tali che la loro somma sia 6. La risposta è [math]\frac{10!}{6! · 4!}, ossia effettivamente [math]120. Ma questi non dovrebbero essere i modi in cui si contano più volte anche sistemazioni uguali? Se le contassimo una sola volta, la risposta dovrebbe essere 22, che è visivamente sbagliata, eppure non riesco a capire il perché non si debba fare

[Stef2008]

Tutto chiaro, ma ho ancora un dubbio; il problema si può ricondurre a quanti numeri [math]a, b, c, d, e tali che sia [math]a, e ≥ 0 e [math]b, c, d ≥ 2 sono tali che la loro somma sia 12.

Ciao, se mi dici come hai dedotto ciò, magari posso aiutarti.
Edit: ho capito come lo hai ricavato... poi ti spiego

[Stef2008]

Ok, ecco la spiegazione (in grassetto la parte che credo ti interessi di più):
Ordiniamo le case da sinistra verso destra. Chiaramente due configurazioni sono uguali se e solo se le case occupate sono le stesse (eventualmente anche da persone diverse). Siano $a,e$ il numero di case consecutive lasciate vuote da sinistra e da destra rispettivamente. Siano $b,c,d$ le distanze tra la casa 1 e 2, 2 e 3, 3 e 4. Chiaramente per le condizioni del testo $b,c,d \geq 2$ e $a,e \geq 0$, $a+b+c+d+e=12$. Ora una configurazione è determinata in modo biunivoco da $ a,b,c,d,e$. Infatti se qualcuno di questi numeri fosse diverso le case occupate sarebbero diverse... in particolare ad esempio una permutazione che non è un identità di una soluzione, porta a una soluzione diversa... quindi non c'è motivo di dividere il risultato per qualcosa. Quindi basta contare queste cinquine... e si arriva alla soluzione $\binom{10}{4}$.

[decs]

Ah certo, mi era sfuggito il fatto che permutando si arrivava a soluzioni diverse... grazie mille!

[Stef2008]

Prego!

[Thoma(sinθ)]

Quindi basta contare queste cinquine... e si arriva alla soluzione $\binom{10}{4}$.

Perdonate l'ignoranza, come si contano le cinquine in questione in maniera veloce? Ovvero, come arriviamo al coefficiente binomiale 10 su 4?

[Stef2008]

Quindi basta contare queste cinquine... e si arriva alla soluzione $\binom{10}{4}$.

Perdonate l'ignoranza, come si contano le cinquine in questione in maniera veloce? Ovvero, come arriviamo al coefficiente binomiale 10 su 4?

Questo link spiega la formula: https://people.dm.unipi.it/lombardo/Tea ... izioni.pdf
Se le hai ci sono anche nelle schede del Gobbino.
Comunque ci si riconduce alle combinazioni con ripetizioni...
Prova a vedere, se hai dubbi fammi sapere

[Thoma(sinθ)]

Comunque ci si riconduce alle combinazioni con ripetizioni...
Prova a vedere, se hai dubbi fammi sapere

Oggi un mio professore mi ha illustrato proprio la via delle combinazioni con ripetizione. Grazie mille per la disponibilità e per i collegamenti :)

[Thoma(sinθ)]

Se le hai ci sono anche nelle schede del Gobbino.

https://umi.dm.unibo.it/prodotto/schede-olimpiche/
queste sono le schede di cui parli?

[Stef2008]

Prego, sì sono quelle le schede del Gobbino.