Signorina, lei deve assolutamente ballare con me ;)

[enomis_costa88]

In un paese A ci sono n ragazze e n ragazzi e ogni ragazza conosce ogni ragazzo.
Sia a(n,r) il numero di modi nei quali r ragazze possono danzare con r ragazzi in modo tale che ciascuna ragazza conosca il suo compagno.

In un paese B ci sono n ragazze e 2n-1 ragazzi tali che la ragazza i conosca i ragazzi 1,2,...,2i-1 (e nessun altro).
Sia b(n,r) il numero di modi nei quali r ragazze del paese B possono danzare con r ragazzi di B in modo tale che ciascuna ragazza conosca il suo compagno.

Dimostrare che a(n,r)=b(n,r)

Buon lavoro e buon ballo a tutti!!

[chermit]

Come devono essere scelte le r ragazze fra le n del paese B? A caso? E gli r ragazzi anche loro a caso?

Nel paese A non importa come si scelgono le ragazze o i ragazzi: tanto tutti conoscono tutti quindi la probabilità che l' i-ma ragazza delle r scelte a caso conosca tutti gli r ragazzi scelti a caso e pari a 1: quindi se non sbaglio a(n,r)=r^2 per tutte le possibili combinazioni tra gli insiemi di r ragazze e r ragazzi.

Ciao Chermit

[enomis_costa88]

Come devono essere scelte le r ragazze fra le n del paese B? A caso? E gli r ragazzi anche loro a caso?

E' un conteggio chermit..quindi in tutti i modi possibili (ovviamente compatibili con le condizioni poste)

Ti faccio notare che sia a(n,r) che b(n,r) sono in funzione sia di r che di n.

In particolare $ a(n,r)\not=r^2 $

[NM]

Propongo questo metodo:

Si verifica prima che

$ a(n,r)=\binom{n}{r}^2r! $

fatto questo si può procedere a dimostrare il risultato per induzione su n usando questa relazione

$ b(n,r)=b(n-1,r)+(2n-r)b(n-1,r-1) $

che esprime il fatto che le combinazione relative ad r si possono contare come quelle che contengono la ragazza n_esima più quelle che non la considerano. Le prime combinazioni si calcolano facilmente, per le seconde si sceglie prima il posto per le r-1 ragazze e poi si posizione nei posti rimanenti (2n-r) l'n_esima.

Ci sono naturalmente un pò di punti (e di conti!) da sistemare (tipo il caso r=1 forse è bene farlo a mano per ogni n)...

[enomis_costa88]

si può procedere a dimostrare il risultato per induzione su n usando questa relazione

$ b(n,r)=b(n-1,r)+(2n-r)b(n-1,r-1) $

Si è la mia stessa idea!!

Ci sono naturalmente un pò di punti (e di conti!) da sistemare

Chi è che vuole formalizzarlo per bene o cercare altre strade?