OliForum Matematico

Sia $ A = \{1,2, \ldots, n\} $. Determinare quante sono le funzioni $ f : A \rightarrow A $ tali che $ |f(A)| = n -1 $

astenersi esperti

f(x)=|x-2|
è accettabile come funzione?
p.s. se si ha n-1 elementi

exodd ha scritto:f(x)=|x-2|
è accettabile come funzione?
p.s. se si ha n-1 elementi

Sì è accettabile. Una funzione è una qualsiasi legge che lega degli elementi di un inisieme di partenza(dominio) a degli elementi di un insieme di arrivo (codominio) [in questo caso i due insiemi coincidono]. E, con insiemi discreti possiamo definirla come più ci pare veramente. Per esempio se abbiamo un insieme $ A = \{1,2,3,4\} $ possiamo definire la nostra funzione così:

$ f(x) = \begin{cases} 2 & \mbox{ se } x = 3 \\ 1 & \mbox{ se } x = 4 \\ 3 & \mbox{ se } x = 2 \\ 4 & \mbox{ se } x = 1 \\ \end{cases} $

è ovvio che $ f(x) $, con $ ~x $ fissato, assume un solo valore per la definizione stessa di funzione.

è preso dal test iniziale del senior di pisa 2006

exodd ha scritto:è preso dal test iniziale del senior di pisa 2006

e allora??
i problemi si fanno, non si cercano in giro.
e poi, non credo che sia un'invenzione originale dell'estensore del test del senior (che poi è cmq gobbino) .... è piuttosto una domanda a cui si trova di fronte chiunque inizi a fare un po' di conteggi con le funzioni.

A proposito ... una volta che un non esperto lo fa, chiederei: e se ci mettiamo n-2? e n-3? e... ?

Dimostriamo innanzitutto che le funzioni $ f $ sono "quasi" bigettive, ovvero che a parte 2 elementi di $ A $ che hanno la stessa funzione, per il resto i valori sono tutti differenti:
1) se non ci fosse neanche una coppia di elementi con lo stesso valore della funzione, allora $ f $ sarebbe bigettiva, dunque $ |f(A)|=n $
2) supponiamo che ci siano due "ripetizioni": allora scartiamo due elementi, e prendiamo gli altri $ n-2 $; anche se hanno tutti un valore della funzione diversa, la cardinalità è al massimo $ n-2 $.

A questo punto conviene calcolare il numero di funzioni bigettive, che sono $ n! $, e considerare che da ognuna di esse si possono ottenere funzioni del tipo richiesto associando un elemento dell'insieme di partenza a un altro elemento dell'insieme d'arrivo, in coppia con un altro elemento di partenza. Le possibilità di scelta dell'elemento da "cambiare" sono $ n $, per ognuna di esse abbiamo $ n-1 $ possibili elementi d'arrivo. Ora supponiamo che in una funzione avevamo:
$ f(x)=a $
$ f(y)=b $
Supponiamo di aver cambiato $ f(x) $ in $ b $, sichhé $ a $ non è più un valore della funzione. Abbiamo:
$ f(x)=f(y)=b $
$ y\not\in f(A) $

Alla stessa situazione possiamo arrivare anche da un'altra funzione bigettiva, quella in cui $ x $ e $ y $ si scambiano:
$ f(x)=b $
$ f(y)=a $

In questo caso cambiamo $ f(y) $ in b. Morale della favola? Dobbiamo dividere tutto per due. Il risultato è
$ |\{f:A\rightarrow A \mbox{ tali che }|f(A)|=n-1\} |=n!\left( \begin{array}{c} n \\ 2 \end{array} \right) $

Se c'è qualcosa che non va, siete pregati di chiamare il numero verde (ancora non disponibile) o di aggiungere un post. Grazie in anticipo.

2 cose tipografiche:
1)"un altro" è senza apostrofo
2) $ y=f(niente) $ è abbastanza discutibile ... ti consiglierei di provare con una cosa del tipo $ y $ non appartiene all'immagine di $ f $ o se proprio vuoi essere simbolico $ y\not\in f(A) $.

Poi, tu giustamente dici che se due funzioni bigettive f,g sono tali che $ f(x)=g(y)=a $ e $ f(y)=g(x)=b $, allora con il tuo procedimento danno luogo alla stessa funzione "quasi bigettiva". Ok, ma, fissata ad esempio $ f $, quante sono le funzioni bigettive $ g $ tali che $ f(x)=g(y)=a $ e $ f(y)=g(x)=b $? Sono solo 2? E poi, anche se due funzioni fossero tali che $ f(x)=g(x)=a $ e $ f(y)=g(y)=b $, darebbero la stessa funzione "quasi bigettiva" che danno quelle di prima ... insomma, mi sa che ne hai contate un po' troppe, di funzioni, o meglio, ne hai contata qualcuna troppe volte.

Concordo perfettamente sugli errori tipografici, che provvederò a correggere. Ma due funzioni bigettive $ f $ e $ g $ diverse tra loro portano ad uno stesso risultato solo se sono uguali tranne che per due elementi x e y scambiati tra di loro, no? Per esempio, se n=5, le funzioni f e g:
f(1)=3; f(2)=5; f(3)=2; f(4)=4; f(5)=1
g(1)=3; g(2)=5; g(3)=2; f(4)=1; f(5)=4

portano (anche, ma non solo) alle seguenti funzioni f' e g':
f'(1)=3; f'(2)=5; f'(3)=2; f'(4)=4; f(5)=4
g'(1)=3; g'(2)=5; g'(3)=2; g'(4)=4; g'(5)=4

che sono uguali tra loro

ops, sì scusa, è tutto giusto ... stavo pensando a |f(A)|=k ...

btw: c'è un altro modo per contare queste funzioni, scegliendo la coppia di valori che dovranno avere la stessa immagine, scegliendo poi quale elemento non includere nell'immagine e infine scegliendo come assegnare i rimanenti.

ed ora, |f(A)|=k ...