Coefficiente binomiale

Definizione combinatoria

Vediamo la definizione combinatoria del coefficient binomiale. Consideriamo la potenza $n$ -esima del binomio $(x + y)$ :

(x + y)^{n} = (x + y) \dots (x + y) n volte

Per la proprietà distributiva, si puù scrivere come:

(x + y)^{n} = \sum z_{1} z_{2} \dots z_{n}

la somma è su tutte le stringhe di lunghezza $n$ , con $z_{i} \in {x, y}$ . Se in una stringa $z \in {x, y}^{n}$ vi sono $h$ occorrenze della variabile $x$ , e quindi $n - h$ della variabile $y$ , supponendo che commutino, possiamo scrivere $z = x^{h} y^{n - h}$ . Possiamo quindi raggruppare nella somma precedente tutte le stringhe con un dato numero di occorrenze fissate, il loro numero sarà proprio come definiremo il coefficiente binomiale, per ora $C (n, h)$ :

(x + y)^{n} = h = 0 \sum n c (n, h) x^{h} y^{n - h}

Identità

Da questa definizione “implicita”, è subito chiara l’identità:

(h n) = (n - h n)

in quanto c’è simmetria per scambio $x, y$ , ovvero posso definire una biiezione banale che scambia i caratteri. Oppure, basta osservare che il polinomio a sinistra è simmetrico per scambio $x, y$ .

Ogni stringa $z_{1} \dots z_{n}$ defnisce una bipartizione sull’insieme $[n]$ , nella seguente maniera:

i \in I ⟺ z_{i} = x

è evidente che l’insieme complementare $J := [n] ∖ I$ , sono le posizioni dei caratteri $y$ , ovvero:

i \in J ⟺ z_{i} = y

quindi abbiamo partizionato $[n] = I \cup J$ . E’ anche ovvio che $∣ I ∣ = h$ , il numero di caratteri $x$ e $∣ J ∣ = n - h$ .

Possiamo quindi scrivere la sommatoria iniziale come:

(x + y)^{n} = bipart. I, J di [n] \sum x^{∣ I ∣} y^{∣ J ∣} = h = 0 \sum n ∣ I ∣ = h \sum x^{h} y^{n - h}

quindi il coefficiente binomiale sta contando il numero sottoinsiemi di $h$ elementi di un insieme di $n$ elementi, che con la notazione introdotta per i grafi:

(h n) = (h [ n ])

Possiamo trovare un’altra identità con questa nuova caratterizzazione: Supponiamo di voler scegliere una tribù di $h$ persone con un capo, a partire da una popolazione di $n$ individui.Ora sappiamo che il numerò di tribù possibili è $(h n)$ . Supponiamo che ogni tribù debba avere un capo, esistono due modi per sceglierlo:

democratico la tribù sceglie uno dei suoi membri per diventare capo.

h (h n)

dittatoriale il capo scegli i suoi $h - 1$ memebri della tribù:

n (h - 1 n - 1)

I due risultati devono coincidere, quindi:

h (h n) = n (h - 1 n - 1)

Viene chiamata absorption/extraction identity, portando $h$ dall’altro lato è evidente perchè. 3. E’ possibile generalizzare la precedente identità, supponiamo ora che la tribù sia guidata da un’oligarchia. Ho sempre i due approcci:

democratico ogni tribù scegli i suoi $m \leq h$ leader:

(h n) (m k)

oligarchica Gli oligarchi scelgono i loro $k - m$ sudditi:

(m n) (k - m n - m)

I due risultati devono coincidere, quindi:

(h n) (m k) = (m n) (h - m n - m)

Questa identità viene chiamata cancellation identity.

Otteniamo un’altra identità, bipartizionando l’insieme $(h [ n ])$ : fissiamo un elemento $i \in [n]$ , induce la bipartizione $S_{i} \cup S_{c}$

S_{i} := {I \subseteq [n] : i \in I} S_{c} := {I \subseteq [n] : i \in / I}

essendo disgiunti, la cardinalità dell’unione è la somma delle cardinalità:

(h n) = (h n - 1) + (h - 1 n - 1)

h = 0 \sum n (h n)^{2} = (n 2 n)

Abbiamo un gruppo di $n$ uomini ed $n$ donne, in totale $2 n$ persone. Vogliamo invitarle ad una festa, ma c’è spazio solo per $n$ persone in totale $; ($ . E’ chiaro che avrò $(n 2 n)$ modi possibili per riempire la festa, ovvero di scegliere il sottoinsieme di $n$ invitati $A \subset [2 n]$ . Partizioniamo gli invitati $A = U_{A} \cup D_{A}$ . Contiamo i sottoinsiemi che contengono $i$ donne, (e quindi $n - i$ uomini):

(i n) (n - i n) = (i n)^{2}

Mi basta sommare per $i = 0, n$ ed ottengo la tesi!.

Formula di Vandermonde. Fisso un sottoinsieme di $[n]$ di $m$ elementi. Partiziono i sottoinsiemi in base quanti elementi fissati contengono.

(h n) = k = 0 \sum m (k m) (h - k n - k)

Recursive sum

(h n) = k = r - 1 \sum n - 1 (r - 1 k)

Proof Induction on $n$ , use the first identity. $□$

i = 0 \sum n i (i n) = n 2^{n - 1}

Proof Double counting dei sottoinsiemi puntati di $[n]$ : Conto quanti sottoinsiemi puntati di $i$ elementi ci sono, sommo fino ad $n$ . Prima fisso l’elemento, ho $n$ scelte, completo aggiungendo tutti i sottoinsiemi dei rimanenti $n - 1$ elementi, che sono $2^{n - 1}$ . $□$

Definizione algebrica

Da qui possiamo definire algebricamente il coefficiente binomiale alla maniera solita: Per il primo elemnto $a_{1}$ abbiamo $n$ scelte, per $a_{2}$ $n - 1$ , e così via fino ad avere $n - h + 1$ scelte per l’emento $a_{h}$ . Ma per un insieme l’ordine non conta, quindi dividiamo per tutte le permutazioni di un insieme di $h$ elementi, otteniamo la solita formula:

(h n) = \frac{n !}{h ! ( n - h !)}

che rispetta tutte le proprietà dimostrate precedentemente.

Upper bound

Un upperbound immediato si verifica maggiorando $n^{\underline{k}}$ con $n^{k}$

(k n) \leq \frac{n ^{k}}{k !} \leq (\frac{e n}{k})^{k} \leq n^{k}

dove si è usato il lower bound per il fattoriale:

e^{x} = k = 0 \sum \infty \frac{x ^{k}}{k !} \geq \frac{k ^{k}}{k !}

per $x$ positivi, dunque:

(\frac{k}{e})^{k} \leq k!

Lorenzo Gregoris

Explorer

Coefficiente binomiale

Coefficiente binomiale

Definizione combinatoria

Identità

Definizione algebrica

Upper bound

Graph View

Table of Contents

Backlinks

Lorenzo Gregoris

Explorer

Coefficiente binomiale

Coefficiente binomiale §

Definizione combinatoria §

Identità §

Definizione algebrica §

Upper bound §

Graph View

Table of Contents

Backlinks

Coefficiente binomiale

Definizione combinatoria

Identità

Definizione algebrica

Upper bound