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 }?

1 2 n

>

n k

Se , 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 come immagine lo stesso elemento di B). Quindi,

≤

n k

affinché esistano funzioni suriettive da A in B deve essere .

=

1) Se , allora le funzioni oltre che suriettive devono essere anche iniettive; infatti,

n k

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 allora il numero di funzioni suriettive da A in B è uguale al numero di

n k

funzioni iniettive da A in B, che è dato da n

!

< N

n k

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

n ,

k

⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞

n n n n n

⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟

= − + + + − + + −

' ' ' h ' n '

1 1

N D D D ... ( ) D ... ( ) D

⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟

− − −

− − −

n ,

k n ,

k n ,

k n ,

k n h ,

k ,

k

1 2 0

⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠

1 2 0

n n n n h

⎛ ⎞ ⎛ ⎞

n n

n n n

( )

∑ ∑ ∑

⎜ ⎟ ⎜ ⎟

= − = − − = −

k

h ' h h '

N ( 1 ) D ( 1 ) n h ( 1 ) C D

⎜ ⎟ ⎜ ⎟

− − −

− −

n ,

k n h ,

k n ,

n h n h ,

k

⎝ ⎠ ⎝ ⎠

n h

n h

= = =

h h h

0 0 0 ⎞

⎛

⎞

⎛

⎞

⎛

− − n

n

n

1 1

n n n

∑ ∑ ∑ ⎟

⎜

⎟

⎜

⎟

⎜ −

− = −

= −

= − h ' 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:

n ,

k ' A B

, da queste si tolgono le funzioni da in

si prendono tutte le funzioni da A in B, ossia D n ,

k ⎛ ⎞

n

⎜ ⎟ =

' '

B D nD

che però hanno condominio dato da escluso 1 elemento, che sono ;

⎜ ⎟ − −

− n ,

k n ,

k

1 1

⎝ ⎠

n 1

A B

in questo modo però si tolgono 2 volte anche quelle funzioni da in e che, escludono 2

⎛ ⎞

n

⎜ ⎟ '

B D

elementi di perciò bisogna aggiungere ; però, in questo modo si aggiungono

⎜ ⎟ −

− n ,

k

2

⎝ ⎠

n 2

A B B

2 volte le funzioni da in e che escludono 3 elementi di quindi bisogna aggiungere

⎛ ⎞

n

⎜ ⎟ '

D e così via.

⎜ ⎟ −

− n ,

k

3

⎝ ⎠

n 3 = N =n

3) Estendendo per la formula precedente, siccome ! allora si ha che:

n k n,n

⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞

n n n n n

⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟

= − + + + − + + −

' ' ' h ' n '

1 1

n

! D D D ... ( ) D ... ( ) D

⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟

− − −

− − −

1 2 0

n ,

n n ,

n n ,

n n h ,

n ,

n

⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠

1 2 0

n n n n h