combinazioni con ripetizioni consentite

Vedi contare con le biezioni

In quanti modi posso scegliere $k$ elementi da $n$, senza ordine e con possibili ripetizioni?

Definiamo un insieme $A$ in cui ogni elemento è un modo di scegliere $k$ elementi da $n$ senza ordine e con possibili ripetizioni.

Qual’è l’insieme con cui possiamo mettere $A$ in biezione?

Esempio: Scelgiamo $k$ elementi da $\Omega =\{a,b,c,d\}$ con possibili ripetizioni.

Usiamo l’algoritmo sticks and stars.

$$\{a,b,a,d,a\}\mapsto \ast \ast \ast \mid \ast \mid \mid \ast \mid \mapsto \{a,a,a,b,d\}$$

L’insieme di partenza e di arrivo è lo stesso (non considerando l’ordinamento), perché la funzione è una biezione. Questa funzione è effettivamente una funzione di codifica invertibile.

Ogni elemento di $B$ è il numero $k$ di stars + il numero $n-1$ di sticks.

Determiniamo $|B|$. Ogni stringa di lunghezza $k+n-1$ (cioè la codifica di ogni elemento di $B$ in $k$ stars e $n-1$ sticks) è univocamente determinata dalla posizione delle stars, che sono $k$. Quindi ogni stringa è costruita scegliendo $k$ posizioni in cui mettere una star da $k+n-1$ locazioni disponibili (combinazioni senza ripetizioni).

Quindi la formula generale è:

$$\left(\genfrac{}{}{0ex}{}{k+n-1}{k}\right)=\frac{(k+n-1)!}{k!\cdot (n-1)!}$$

Esempi

Quante parole di lunghezza 7 ci sono con esattamente 3 A?

1. Scegliamo dove posizionare le 3 A (combinazione senza ripetizione): $\left(\genfrac{}{}{0ex}{}{7}{3}\right)$
2. Scegliamo come mettere i caratteri rimanenti (disposizioni con ripetizioni consentite): $26^4$
3. Totale = $\left(\genfrac{}{}{0ex}{}{7}{3}\right)\cdot 26^4=35\cdot 26^4$

---

Quante funzioni ci sono $f:\{1,2,\dots ,n\}\mapsto \{1,2,\dots ,k\}$ e strettamente crescenti?

• Numero di funzioni (permutazioni): $k^n$

Per avere funzioni strettamente crescenti assumiamo $k\ge n$.

Una funzione strettamente crescente è codificata univocamente (quindi anche in maniera invertibile) dal suo codominio e il suo dominio (che in questo caso è sempre lo stesso per le varie funzioni).

• Per ottenere tutti i codominii, quindi tutte le funzioni strettamente crescenti, bisogna scegliere $n$ elementi da $k$. Quindi $\left(\genfrac{}{}{0ex}{}{k}{n}\right)$.

todo funzioni crescenti in generale