Cardinalità dell'insieme delle funzioni suriettive
Salve a tutti!
Non riesco a far vedere che
\[|\mathcal{S}_{n}^{k}|=\sum_{j=0}^{n}(-1)^{j}\binom{n}{j}(n-j)^k\]
dove \(\mathcal{S}_{n}^{k}\) è l'insieme delle funzioni suriettive da \(K=\{1,2,...,k\}\) a valori in \(N=\{1,2,...,n\}\).
Il ragionamento che ho fatto arriva ad una conclusione sbagliata.
Non riesco a capire dov'è che sbaglio.
Dunque, per prima cosa definisco gli insiemi \(A_j\) costituiti dalle funzioni \(f:K\longmapsto N\) la cui immagine ha \(j\) elementi.
Secondo questa definizione dovrei avere che \(\mathcal{S}_{n}^{k}=A_n\).
Ogni funzione di dominio \(K\) dovrei poterla identificare univocamente con una \(k\)-lista.
Se una funzione ha \(x\) elementi nella sua immagine, la sua k-lista associata presenterà \(x\) simboli distinti.
Un insieme \(A_j\) avrà come elementi tutte e solo le \(k\)-liste che è possibile costruire con \(j\) simboli distinti.
I \(j\) simboli da utilizzare nella \(k\)-lista li devo scegliere tra quelli presenti nell'insieme \(N\), dunque ho \(\binom{n}{j}\) possibili scelte.
Secondo questo ragionamento, dovrei poter scrivere
\[\begin{align}
|A_j|&=\binom{n}{j}j^k-\sum_{i=0}^{j-1}|A_i| \\
&=\binom{n}{j}j^k-\left| \, \bigcup_{i=0}^{j-1}A_i \, \right | \\
&=\binom{n}{j}j^k-\sum_{i=0}^{j-1} \binom{n}{i}i^k \qquad \forall j \in \mathbb{N}
\end{align} \]
da cui
\[|\mathcal{S}_{n}^{k}|=n^k-\sum_{i=0}^{n-1}\binom{n}{i}i^k\]
Ringrazio anticipatamente chiunque voglia darmi una mano.
Non riesco a far vedere che
\[|\mathcal{S}_{n}^{k}|=\sum_{j=0}^{n}(-1)^{j}\binom{n}{j}(n-j)^k\]
dove \(\mathcal{S}_{n}^{k}\) è l'insieme delle funzioni suriettive da \(K=\{1,2,...,k\}\) a valori in \(N=\{1,2,...,n\}\).
Il ragionamento che ho fatto arriva ad una conclusione sbagliata.
Non riesco a capire dov'è che sbaglio.
Dunque, per prima cosa definisco gli insiemi \(A_j\) costituiti dalle funzioni \(f:K\longmapsto N\) la cui immagine ha \(j\) elementi.
Secondo questa definizione dovrei avere che \(\mathcal{S}_{n}^{k}=A_n\).
Ogni funzione di dominio \(K\) dovrei poterla identificare univocamente con una \(k\)-lista.
Se una funzione ha \(x\) elementi nella sua immagine, la sua k-lista associata presenterà \(x\) simboli distinti.
Un insieme \(A_j\) avrà come elementi tutte e solo le \(k\)-liste che è possibile costruire con \(j\) simboli distinti.
I \(j\) simboli da utilizzare nella \(k\)-lista li devo scegliere tra quelli presenti nell'insieme \(N\), dunque ho \(\binom{n}{j}\) possibili scelte.
Secondo questo ragionamento, dovrei poter scrivere
\[\begin{align}
|A_j|&=\binom{n}{j}j^k-\sum_{i=0}^{j-1}|A_i| \\
&=\binom{n}{j}j^k-\left| \, \bigcup_{i=0}^{j-1}A_i \, \right | \\
&=\binom{n}{j}j^k-\sum_{i=0}^{j-1} \binom{n}{i}i^k \qquad \forall j \in \mathbb{N}
\end{align} \]
da cui
\[|\mathcal{S}_{n}^{k}|=n^k-\sum_{i=0}^{n-1}\binom{n}{i}i^k\]
Ringrazio anticipatamente chiunque voglia darmi una mano.
Risposte
Considera una generica funzione $f : K to N$.
Definisci, per ogni i da 1 a n,
$ n_i = "cardinalità" { x in K " tale che " f(x)=i}$, praticamente è il numero di volte che il punto del codominio i è immagine secondo la funzione f.
Gli $n_i$ sono interi non negativi tali che $sum_{i=1}^n =k$. Chiama $S$ l'insieme di tutte le nuple $(n_1,...,n_n)$ possibili.
Data una particolare nupla ( ovvero definito quante volte ciascun elemento del codominio è immagine, eventualmente nessuna, in tal caso $n_i=0$) il numero di funzioni possibli sono:
$(k!)/(n_1! *...*n_n!)$.
Vale che $ sum_{(n_1,...,n_n) in S } (k!)/(n_1! *...*n_n!)= n^k$.
Una funzione è suriettiva quando $n_i >= 1$ per ogni i, chiama $S_1$l'insieme contenti tali nuple ed $ S_0$ l'insieme delle nuple che contengono almeno uno 0.
Quello che devi calcolare è:
$ sum_{(n_1,...,n_n) in S_1} (k!)/(n_1! *...*n_n!) = n^k - sum_{(n_1,...,n_n) in S_0} (k!)/(n_1! *...*n_n!)$
Se ti fai un pò di conti vedi che quella somma è uguale alla somma che presenti come soluzione ( provaci, ma non è semplicissimo).
Ciao
Definisci, per ogni i da 1 a n,
$ n_i = "cardinalità" { x in K " tale che " f(x)=i}$, praticamente è il numero di volte che il punto del codominio i è immagine secondo la funzione f.
Gli $n_i$ sono interi non negativi tali che $sum_{i=1}^n =k$. Chiama $S$ l'insieme di tutte le nuple $(n_1,...,n_n)$ possibili.
Data una particolare nupla ( ovvero definito quante volte ciascun elemento del codominio è immagine, eventualmente nessuna, in tal caso $n_i=0$) il numero di funzioni possibli sono:
$(k!)/(n_1! *...*n_n!)$.
Vale che $ sum_{(n_1,...,n_n) in S } (k!)/(n_1! *...*n_n!)= n^k$.
Una funzione è suriettiva quando $n_i >= 1$ per ogni i, chiama $S_1$l'insieme contenti tali nuple ed $ S_0$ l'insieme delle nuple che contengono almeno uno 0.
Quello che devi calcolare è:
$ sum_{(n_1,...,n_n) in S_1} (k!)/(n_1! *...*n_n!) = n^k - sum_{(n_1,...,n_n) in S_0} (k!)/(n_1! *...*n_n!)$
Se ti fai un pò di conti vedi che quella somma è uguale alla somma che presenti come soluzione ( provaci, ma non è semplicissimo).
Ciao
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo