Esercizio combinatoria, conteggio funzioni.
Buongiorno,
non capisco il seguente passaggio di un esercizio.
Abbiamo \(\displaystyle X = \{1, 2, ..., 100\} \) e dobbiamo calcolare la cardinalità di \(\displaystyle B = \{f: X \to X \ \ |\ \ f^2(x) = 1 \ \ \forall x \in X\} \). Avevo cercato di risolverlo con le congruenze, ma la soluzione che propone è completamente diversa.
"Sia \(\displaystyle f \in B \) e sia \(\displaystyle Y = f^{-1}(1) \), allora \(\displaystyle Y \) è non vuoto perché \(\displaystyle 1 \in f(X) \). Inoltre \(\displaystyle f(Y) = \{1\} \) e \(\displaystyle 1 \notin f(X \setminus Y) \). Si verifica facilmente che la condizione \(\displaystyle f^2(X) = \{1\} \) è equivalente a \(\displaystyle \{1\} = f(Y) \subseteq Y \) e \(\displaystyle f(X \setminus Y) \subseteq Y \), allora per quanto detto sopra \(\displaystyle f(X \setminus Y) \subseteq Y \setminus \{1\} \)."
Non capisco l'ultima frase. Sto cercando un esempio di funzione che non sia banale per capire quello che l'esercizio dice che si verifica facilmente.
Ho provato a disegnare \(\displaystyle X = \{a, b, c, d, ...\} \) che tramite \(\displaystyle f(X) \) manda \(\displaystyle \{a, b, c\} \) in \(\displaystyle 1 \) e il resto in altri elementi. A questo punto \(\displaystyle f^{-1}(1)=\{a, b, c\} \subseteq X \). Ma se \(\displaystyle a = 1 \), \(\displaystyle f(X \setminus Y) = f(\{d, ...\}) \) perché dovrebbe essere contenuto in \(\displaystyle Y \setminus \{1\} = \{b, c\} \) ? Forse devo trovare un esempio o un'idea più specifica, ma sono difficoltà. Avrei bisogno di un'illuminazione.
non capisco il seguente passaggio di un esercizio.
Abbiamo \(\displaystyle X = \{1, 2, ..., 100\} \) e dobbiamo calcolare la cardinalità di \(\displaystyle B = \{f: X \to X \ \ |\ \ f^2(x) = 1 \ \ \forall x \in X\} \). Avevo cercato di risolverlo con le congruenze, ma la soluzione che propone è completamente diversa.
"Sia \(\displaystyle f \in B \) e sia \(\displaystyle Y = f^{-1}(1) \), allora \(\displaystyle Y \) è non vuoto perché \(\displaystyle 1 \in f(X) \). Inoltre \(\displaystyle f(Y) = \{1\} \) e \(\displaystyle 1 \notin f(X \setminus Y) \). Si verifica facilmente che la condizione \(\displaystyle f^2(X) = \{1\} \) è equivalente a \(\displaystyle \{1\} = f(Y) \subseteq Y \) e \(\displaystyle f(X \setminus Y) \subseteq Y \), allora per quanto detto sopra \(\displaystyle f(X \setminus Y) \subseteq Y \setminus \{1\} \)."
Non capisco l'ultima frase. Sto cercando un esempio di funzione che non sia banale per capire quello che l'esercizio dice che si verifica facilmente.
Ho provato a disegnare \(\displaystyle X = \{a, b, c, d, ...\} \) che tramite \(\displaystyle f(X) \) manda \(\displaystyle \{a, b, c\} \) in \(\displaystyle 1 \) e il resto in altri elementi. A questo punto \(\displaystyle f^{-1}(1)=\{a, b, c\} \subseteq X \). Ma se \(\displaystyle a = 1 \), \(\displaystyle f(X \setminus Y) = f(\{d, ...\}) \) perché dovrebbe essere contenuto in \(\displaystyle Y \setminus \{1\} = \{b, c\} \) ? Forse devo trovare un esempio o un'idea più specifica, ma sono difficoltà. Avrei bisogno di un'illuminazione.
Risposte
"complesso":Perché per ipotesi $f(f(x))=1$ per ogni $x in X$. Quindi per esempio hai $f(f(d))=1$ e quindi $f(d)$ appartiene alla controimmagine di $1$, cioè $f(d) in Y$. D'altra parte $f(d) ne 1$ perché se fosse $f(d)=1$ allora avresti $d in Y$ che è falso perché $Y={a,b,c}$.
A questo punto \(\displaystyle f^{-1}(1)=\{a, b, c\} \subseteq X \). Ma se \(\displaystyle a = 1 \), \(\displaystyle f(X \setminus Y) = f(\{d, ...\}) \) perché dovrebbe essere contenuto in \(\displaystyle Y \setminus \{1\} = \{b, c\} \) ?
Grazie Martino per la solerte risposta! Finalmente ho capito e dovrei essere riuscito a trovare un esempio sensato:
\( \displaystyle {\begin{matrix}f\colon &X&\longrightarrow &X&\\&x&\longmapsto &1,& \text{se } x \text{ dispari}\\&x&\longmapsto &3,& \text{se } x \text{ pari}\end{matrix}} \).
Buona serata
\( \displaystyle {\begin{matrix}f\colon &X&\longrightarrow &X&\\&x&\longmapsto &1,& \text{se } x \text{ dispari}\\&x&\longmapsto &3,& \text{se } x \text{ pari}\end{matrix}} \).
Buona serata
Sì ottimo. Sei riuscito poi a calcolare la cardinalità di $B$?
"Martino":
Sì ottimo. Sei riuscito poi a calcolare la cardinalità di $ B $?
Sì, grazie. Una volta sbloccato il meccanismo sono riuscito a ricavare il resto.
$|Y| = k+1$, con $0 \leq k \leq 99$
$|X \setminus Y| = 100 - (k + 1) = 99 - k$
Contando quindi le applicazioni da $X \setminus Y$ a $Y \setminus \{ 1 \}$ si trova che per ogni applicazione ci sono $|Y \setminus \{1\}|^{|X \setminus Y|}=k^{99-k}$ scelte. I possibili sottoinsiemi $Y$ sono \(\displaystyle {99 \choose k} \), e quindi \(\displaystyle |B| = \sum_{k=0}^{99} {99 \choose k} k^{99-k} \).
Divertente. Si potrebbe calcolare anche quante funzioni ci sono in
$B = \{f: X \to X \ \ |\ \ f^3(x) = 1 \ \ \forall x \in X\}$
Con lo stesso sistema. E così via anche per altri esponenti.
Solo che in questo caso bisogna dividere l'insieme $X setminus {1}$ in tre pezzi, il pezzo dell'antiimmagine di ${1}$, quello degli elementi che ci mettono esattamente due applicazioni di $f$ ad arrivare a $1$ (non prima) e quello degli elementi che ci mettono esattamente tre applicazioni (non prima).
Ovviamente questi insiemi potrebbero essere vuoti, ma non il primo.
$B = \{f: X \to X \ \ |\ \ f^3(x) = 1 \ \ \forall x \in X\}$
Con lo stesso sistema. E così via anche per altri esponenti.
Solo che in questo caso bisogna dividere l'insieme $X setminus {1}$ in tre pezzi, il pezzo dell'antiimmagine di ${1}$, quello degli elementi che ci mettono esattamente due applicazioni di $f$ ad arrivare a $1$ (non prima) e quello degli elementi che ci mettono esattamente tre applicazioni (non prima).
Ovviamente questi insiemi potrebbero essere vuoti, ma non il primo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo