Lezione 8

Scrittura in base arbitraria dei naturali.

Definizione 8.1   Sia $b\in\mathbb{N}$. Diremo che $n\in \mathbb{N}$ è rappresentabile in base $b$ se esistono numeri $\varepsilon _0,\varepsilon _1,\dots,\varepsilon _k\in I_b=\{0,1,\dots,b-1\}$ tali che $n=\varepsilon _0 +\varepsilon _1b+\varepsilon _2 b^2+\dots \varepsilon _k b^k$.

Osservazione 8.2   Si osservi che nessun numero è rappresentabile in base 0 (dato che $I_0=\varnothing$) e che l'unico numero rappresentabile in base $1$ è lo 0. In questo caso infatti la condizione (2) implica che ogni $\varepsilon _i=0$.

Osservazione 8.3   La rappresentabilità in base $b$ può essere espressa anche nel seguente modo: esiste una successione $\{\varepsilon _i\}_{i\in\mathbb{N}}$ di interi tali che:

1. $\{\varepsilon _i\}$ è definitivamente nulla (i.e. esiste $i_0\in\mathbb{N}$ tale che $\varepsilon _i=0$ per ogni $i>i_0$);
2. $\varepsilon _i\in I_b$ (ovvero $0\le\varepsilon _i<b$) per ogni $i\in\mathbb{N}$;
3. $n=\sum_{i=0}^\infty \varepsilon _i b^i$.

Questo perché la condizione (1) implica che la somma in (3) ha un numero finito di addendi non nulli.

Teorema 8.4 (rappresentazione dei naturali in base arbitraria)   Sia $b\in\mathbb{N}$, $b\ge 2$. Allora ogni $n\in \mathbb{N}$ è rappresentabile in modo unico in base $b$. Ossia esiste una successione $\{\varepsilon _i\}_{i\in\mathbb{N}}$ come nell'osservazione precedente e se $\{\varepsilon '_i\}_{i\in\mathbb{N}}$ è un'altra tale successione, allora $\varepsilon _i=\varepsilon _i'$ per ogni $i\in\mathbb{N}$.

Dimostrazione.  Dimostriamo l'esistenza per induzione su $n$. Se $n=0$ basta prendere $\varepsilon _i=0$ per ogni $i\in\mathbb{N}$. Supponiamo ora $n>0$ e che la tesi sia vera per ogni $k<n$. Siano $q,r$ tali che $n=bq+r$ con $0\le r<b$. Dato che $b\ge 2$ si ha che $0\le q<bq\le bq+r=n$ e quindi per ipotesi di induzione esiste una successione definitivamente nulla $\{\delta_i\}$, costituita di interi tali che $0\le\delta_i<b$ per ogni $i$ e tale che $q=\sum\limits_{i=0}^\infty \delta_i b^i$. Ma allora

$$n=bq+r=b\sum\limits_{i=0}^\infty \delta_i b^i+r=\sum\limits_{i=0}... ...\sum_{i=1}^\infty\delta_{i-1}b^i+r=\sum\limits_{i=0}^\infty \varepsilon _i b^i$$

dove si è posto $\varepsilon _0=r$ e $\varepsilon _i=\delta_{i-1}$ per ogni $i>0$. La successione $\{\varepsilon _i\}$ è definitivamente nulla, dato che lo è $\{\delta_i\}$ ed inoltre $0\le\varepsilon _i=\delta_{i-1}<b$ per ogni $i>0$ e $0\le\varepsilon _0=r<b$.

Dimostriamo ora l'unicità. Procediamo per induzione su $n$. Se $n=0=\sum_i\varepsilon _ib^i$ allora ogni addendo della somma essendo non negativo, deve essere nullo e quindi $\varepsilon _i=0$ per ogni $i$.

Supponiamo ora $n>0$ e che l'espressione in base $b$ sia unica per tutti i numeri $k<n$. Sia $n$ tale che $n=\sum\limits_{i=0}^\infty \varepsilon _i b^i=\sum\limits_{i=0}^\infty \varepsilon '_i b^i$. Allora possiamo scrivere

$$n=b\sum\limits_{i=1}^\infty \varepsilon _i b^{i-1}+\varepsilon _0=b\sum\limits_{i=1}^\infty \varepsilon '_i b^{i-1}+\varepsilon '_0$$

ma per l'unicità della divisione euclidea si ha che $\varepsilon _0=\varepsilon '_0$ e $q=\sum\limits_{i=1}^\infty \varepsilon _i b^{i-1}=\sum\limits_{i=1}^\infty \varepsilon '_i b^{i-1}$. Come prima $q<n$ e quindi per ipotesi di induzione si ha anche che $\varepsilon _i=\varepsilon '_i$ per ogni $i\ge1$.     $\square$

Osservazione 8.5   Anche in questo caso la dimostrazione del teorema di rappresentazione in base assegnata dei naturali, permette di scrivere un algoritmo ricorsivo per il calcolo della stringa degli $\varepsilon _i$

$$\hbox{\vrule \vbox{\hrule\kern5pt\hbox{\kern5pt \begin{minipage}{... ...lla stringa che hai ottenuto} }$\end{minipage}\kern5pt}\kern5pt\hrule }\vrule}$$

algoritmo che può essere tradotto in un programma ricorsivo per la definizione di una funzione B_RAPP che calcoli la rappresentazione di un numero in base fissata.

$$\hbox{\vrule\vbox{\hrule\kern5pt\hbox{\kern5pt \begin{minipage}{.... ...APP(q,b)] END IF }\end{verbatim}\end{minipage}\kern5pt}\kern5pt\hrule }\vrule}$$

Il coefficiente binomiale

Definizione 8.6   Siano $n$, $k\in\mathbb{N}$ con $k \le n$ si pone

$${n \choose k}= \frac {n!}{(n-k)! k !}$$

Osservazione 8.7   È immediato verificare che ${n \choose k}={n \choose n-k}$.

Esercizio 8.1   Provare che

$${n+1 \choose k} = {n \choose k}+{n \choose k-1}.$$

Soluzione

$k$-sottinsiemi

Definizione 8.8   Sia $X$ un insieme e $k\in\mathbb{N}$, un sottinsieme $A\subseteq X$ sarà detto un $k$-sottinsieme se $\left\vert A\right\vert =k$. Denoteremo con ${X \choose k}$ l'insieme dei $k$-sottinsiemi di $X$. I $k$-sottinsiemi sono anche chiamati $k$-combinazioni semplici.

Proposizione 8.9   Se $X$ è finito e $k\le \left\vert X\right\vert$, allora

$$\left\vert{X \choose k}\right\vert={\left\vert X\right\vert \choose k}.$$

Dimostrazione.  Procediamo per induzione su $\left\vert X\right\vert$. Se $\left\vert X\right\vert=0$ allora $k=0$ e $X=\varnothing$. Ma allora

$$\left\vert{\varnothing \choose 0}\right\vert=\left\vert\{\varnothing \}\right\vert=1={0 \choose 0}={\left\vert\varnothing \right\vert \choose 0}.$$

Supponiamo ora che $\left\vert X\right\vert>0$. Se $k=\left\vert X\right\vert$, allora ${X \choose k}=\{X\}$ e quindi $\left\vert{X \choose k}\right\vert=1$. D'altra parte anche ${\left\vert X\right\vert \choose k}=1$. ANche il caso $k=0$ è facile. Supponiamo allora $0<k<\left\vert X\right\vert$. Fissiamo $x_0\in X$ un elemento e poniamo

$$\begin{array}{rcl} {\cal A}_1 & = &\{A\subset X\mid \left\vert A\... ...\{A\subset X\mid \left\vert A\right\vert=k\text{ e } x_0\not\in A\} \end{array}$$

chiaramente si ha

$${X \choose k}={\cal A}_1\cup{\cal A}_2,\qquad {\cal A}_1\cap{\cal A}_2=\varnothing$$

da cui $\left\vert{X \choose k}\right\vert=\left\vert{\cal A}_1\right\vert+\left\vert{\cal A}_2\right\vert$ )cfr esercizio4.2). Posto $X'=X-\{x_0\}$ si ha che

$${\cal A}_2={X' \choose k}.$$ (7)

inoltre la funzione $F:{X' \choose k-1}\to {\cal A}_1$ definita da $F(A)=A\cup\{x_0\}$ è una bigezione e quindi, dato che $\left\vert X'\right\vert=\left\vert X\right\vert-1$, per ipotesi di induzione si ha

$$\left\vert{\cal A}_1\right\vert =*\left\vert{X' \choose k-1}\right\vert={\left\vert X'\right\vert \choose k-1}$$

$$\left\vert{\cal A}_2\right\vert =*\left\vert{X' \choose k}\right\vert={\left\vert X'\right\vert \choose k}$$

Ma allora, usando il risultato dell'esercizio 8.1

$$\left\vert{X \choose k}\right\vert={\left\vert X'\right\vert \cho... ...}= {\left\vert X'\right\vert+1 \choose k}={\left\vert X\right\vert \choose k}.$$

    $\square$

Esercizio 8.2   Provare che

$${n \choose 0}+{n \choose 1}+\dots+{n \choose n-1}+{n \choose n}=2^n$$

Soluzione

Perché non gioco al Superenalotto!

Una sestina al Superenalotto, è un sottinsieme di $6$ elementi dell'insieme dei numeri naturali da $1$ a $90$, quindi, per la proposizione 8.9 il numero di sestine possibili è dato da:

$${90 \choose 6}=622614630$$

Pertanto, la probabilità di vincere giocando una sestina è pari a $1/622614630=0.000000161 \%$. Se quindi il gioco fosse equo, la puntata su una giocata dovrebbe essere pagata $622614630$ volte la posta. Dato che la puntata su una sestina costa $0.50$ Euro, mi aspetterei, in caso di successo, un premio di $0.50 \cdot 622614630 = 311307315$ Euro.

Un montepremi così alto non si è ancora visto!