Funzioni suriettive: Quante esistono da A a B? Analisi delle possibilità quando n è uguale a k.

Funzioni suriettive

Ci poniamo la seguente domanda: quante sono le funzioni suriettive dall’insieme A = {1, 2, …, k}

all’insieme B = {a₁, a₂, …, a_n}?

Se n > k, evidentemente non esistono funzioni suriettive da A in B, perché ogni elemento di A può avere come immagine un solo elemento di B, quindi al più possono essere saturati k elementi di B (al più, perché elementi diversi di A potrebbero avere come immagine lo stesso elemento di B). Quindi, affinché esistano funzioni suriettive da A in B deve essere n ≤ k.

1) Se n = k, allora le funzioni oltre che suriettive devono essere anche iniettive; infatti, siccome ogni elemento di A ha una sola immagine in B, allora, per poter esaurire gli elementi di B, ogni elemento di A deve avere immagine diversa in B.

Dunque, se n = k, allora il numero di funzioni suriettive da A in B è uguale al numero di funzioni iniettive da A in B, che è dato da n!

n < N

2) Se n < k, il numero delle funzioni suriettive da A a B è:

N = D_n,k − D_n,k−1 + D_n,k−2 + … + ( )D_n,k−h + … − ( )D_n,k−0

1 1

N = ∑ ( − 1 )^h D_n,k−h = ∑ ( − 1 )^h ( ) D_n−h,k = ∑ ( − 1 )^h C_n,h D_n−h,k

h = 0 h = 0 h = 0

n

⎛ ⎞

⎛ ⎞

⎛ ⎞

n

n

∑ ∑ ∑ ⎟

⎜

⎟

⎜

⎟

⎜ − − n

n

n

1 1

n n n

= − = −

= − h   k   h   k

1 1 1 (n − h)

(n − h) ( )

D ( )

N ( ) ⎟

⎜

⎟

⎜

⎟

⎜ −

−

n,k n−h,k ⎠

⎝

⎠

⎝

⎠

⎝ h

h

n h

= = =

0 0 0

h h h

Il numero N delle funzioni suriettive da A a B si ottiene in questo modo:

si prendono tutte le funzioni da A in B, ossia D_n,k, da queste si tolgono le funzioni da A in B,

n,k ' A B

<strong>funzioni suriettive</strong>

n   k ⎛ ⎞

n

⎜ ⎟ =

' '