Prova combinatoria per coefficiente binomiale composito / annidato

Question

In questo momento sto lavorando a un problema per cui ci viene chiesto di fornire una prova combinatoria per il seguente dove $n \geq 4$: $${{n \choose 2} \choose 2} = 3{n \choose 4} + 3{n \choose 3}$$

LHS: numero di sottoinsiemi di dimensione 2 da $n$e quindi contiamo tutti i modi per creare sottoinsiemi di 2 da quei sottoinsiemi.

RHS: Numero di sottoinsiemi da cui possiamo ricavare la dimensione 4 $n$ moltiplicato per 3 aggiunto al numero di sottoinsiemi che possiamo ricavare dalla dimensione 4 $n$ moltiplicato per 3. Inizialmente ho provato a metterlo in relazione usando tre diversi gruppi con $n$elementi, ma sospetto che la mia logica fosse difettosa in quanto avrei potuto contare due volte sull'RHS. Qualsiasi aiuto sarebbe molto apprezzato.

Answer 1

Entrambi i lati contano il numero di coppie di bordi nel grafico completo $K_n$. Il LHS è chiaro. Per l'RHS, considera se i bordi condividono un vertice comune (il secondo termine) o meno (il primo termine).

Answer 2

Se scegli $4$ elementi distinti di un set, ci sono $3$ in diversi modi puoi organizzarli in due sottoinsiemi di $2$ elementi ciascuno: puoi accoppiare il primo elemento con uno qualsiasi degli altri tre elementi, lasciando che i due elementi rimanenti si accoppino tra loro.

Se scegli $3$ elementi distinti di un insieme, ci sono anche $3$ in diversi modi puoi disporli (con duplicazione) in due sottoinsiemi di $2$ elementi ciascuno: puoi scegliere ciascuno dei $3$ elementi come l'elemento da duplicare e accoppiare un "gemello" con ciascuno degli altri due elementi.

Non ci sono altri modi per selezionare gli elementi da un set che consente di esaurire gli elementi selezionati e disporli in sottoinsiemi distinti di $2$ elementi ciascuno, quindi questo esaurisce i modi per selezionare due sottoinsiemi di $2$ elementi ciascuno.

Answer 3

A sinistra abbiamo il conteggio totale di due diversi modi di scegliere 2 elementi su n. Poiché questi due modi sono diversi, non possono sovrapporsi completamente.

Se non ci sono sovrapposizioni, è come scegliere 4 elementi, quindi per uno degli elementi ci sono altre 3 opzioni per accoppiarli, dando $3{n\choose 4}$.

Se c'è una sovrapposizione, allora ci sono 3 modi per scegliere la sovrapposizione, dando $3{n\choose 3}$.