Mentre studiacchiavo un po' di combinatoria, ho trovato un classico esercizio: Dati due insiemi A e B, rispettivamente di cardinalità n e k, con n>=k, trova il numero di tutte le possibili funzioni suriettive dall'insieme A a quello B.
Il punto è che sapevo già dell'esistenza di un teorema (quello di Bell), ma ho deciso di provare prima da me, senza neanche guardarlo, e sono arrivato ad una formula diversa. Apprezzerei se qualcuno le desse un'occhiata.... per dirmi dove sta l'errore!
(per chi si è preoccupato per la mia salute mentale guardando il titolo del topic: era uno scherzo)
lo riscrivo qui (trascrizione del flusso psicologico)
- 1) mmmh stè funzioni suriettive sono più complicate di iniettive o biiettive.. devo trovare un'altra strada.. mmmmmmh... (...) TOH! Perchè non provare con un ragionamento inverso? inizierò soddisfando la condizione di suriettività, vale a dire trovare, per ogni elemento di B, un elemento diverso di A che gli faccia da contrimmagine (tanto alla fin fine questa situazione dovrà verificarsi per forza, viste le definizioni di "funzione" e "suriettività"). Ciò significa che, per ogni elemento del codominio, devo scegliere una contrimmagine (ovviamente diversa) del dominio.
BEH .. in quanti modi posso farlo? Semplice: disposizioni di n elementi in classi di k. Ovvero il numero di possibili funzioni iniettive dal codominio al dominio della funzione iniziale (suona strano usare delle iniettive da 'B' ad 'A' per trovare le suriettive da 'A' a 'B', ma è così. In latex (azz peccato che non posso fare anche un disegnino):
$ \frac{n!}{(n-k)!} $
2) Beh, ora che la condizione necessaria e sufficiente per la suriettività è soddisfatta, mi tocca passare alla definizione di funzione: ad OGNI elemento del dominio devo associare ...(etc) Dunque mi tocca arrangiare quelli rimanenti, che sono precisamente $ n-k $. Beh, ognuno di loro è completamente libero di andare in uno qualsiasi dei k elementi di B, eh dunque i modi possibili con cui posso farlo sono $ k^{(n-k)} $
3) PASSO FINALE: per ogni modo con cui ho associato posso abbinare ogni modo con cui ho associato [gli n-k rimanenti], dunque la formula finale moltiplica le due iniziali:
$ Suriezioni(n,k) = \frac{n!}{(n-k)!} k^{(n-k)} $
Per favore leggete, pensate, votate, insultate etc: l'importante è POSTARE! Ho bisogno di sapere dove sbaglio!!
EDIT: Azzzz ho trovato l'errore: sto contando un sacco di doppioni in questo modo. Adesso il problema che mi sto ponendo è: QUANTI doppioni di ogni funzione? Così basta dividere .. mmmmmmmh AIUTATEMI