Punti fissi-Episodio II

[fields1]

Sia $S_n$, ancora una volta, l'insieme delle funzioni iniettive $f: {1,2,...,n}\rightarrow {1,2,...,n}$.

Sia inoltre $X$ l'insieme delle funzioni $f\in S_n$ tali che $f(x)!=x$ per ogni $x\in {1,2,...,n}$.

Qual e' la cardinalita' di $X$?

[TomSawyer1]

Fissando $1$ nella prima posizione, otteniamo $(n-1)! f \notin X$. Sia $m$ un intero tale che $1

Cita

Segnala

[fields1]

Che significa $(n-1)! f$? Immagino che sia una stenografia per dire $(n-1)!$ funzioni...

In ogni caso, la risposta non è corretta, e sinceramente non riesco a seguire il ragionamento che hai fatto...

[TomSawyer1]

Sì, intendevo quello. Comunque, forse ho capito male il problema.

Esempio per $n=3$. Le permutazioni sono 123, 132, 213, 231, 312, 321. In questo caso le permutazioni 231 e 312 non presentano nessun punto fisso, quindi la cardinalità di $X$ sarebbe 2. Non intendevi questo?

[fields1]

Sì, interpreti bene (del resto sono stato preciso nel formulare il problema).

Nel caso che citi ($n=3$), la tua formula c'azzecca e funziona anche nel caso $n=4$. Pero' fallisce subito nel caso $n=2$ e anche $n=5$.

[fields1]

Vediamo di dare un suggerimento.

La formula da dimostrare è

$|X|=n!(1/(2!)-1/(3!)+1/(4!)-....+(-1)^n/(n!))$

La bellezza di questa formula si puo' svelare con pochi ulteriori passaggi. Ricordando lo sviluppo in serie

$e^x=1+x/(1!)+x^2/(2!)+x^3/(3!)+.....$

ponendo $x=-1$, abbiamo

$1/e=1/(2!)-1/(3!)+1/(4!)-....$

Dunque otteniamo che, per $n\to oo$,

$|X|=(n!)/e$

Quanta bellezza!

[TomSawyer1]

Sia $A_j$ l'insieme delle funzioni che fissano $j$, per $1\le j \le n$. Allora, si ha che $|A_{i_1}|=(n-1)!, |A_{i_1} \bigcap A_{i_2}|=(n-2)!, \ldots, |A_{i_1}\bigcap \cdots \bigcap A_{i_(n-1)}|=(n-(n-1))!$, per $i_1\ne \ cdots \ne i_(n-1)$.
Quindi, applicando il principio di inclusione/esclusione (che risolve tutto in questo problema), $|X|=\sum_{i=0}^n(-1)^i((n),(i))(n-i)! =n! \sum_{i=0}(-1)^i/(i!)$.

Sarebbe interessante vedere anche la più elegante dimostrazione che si basa sullo sviluppo in serie di $e^x$. O la tua era una considerazione estetica a posteriori?

PS: è misteriosamente scomparso il primo topic sui punti fissi...

[fields1]

Ok, ottimo. Fa miracoli il principio di inclusione-esclusione, eh?

C'è un altro modo per risolvere il problema, ma anch'io l'ho risolto con il principio di inclusione-esclusione, che è la soluzione decisamente piu' semplice e più elegante dal punto di vista estetico. L'altro modo consiste nel contare direttamente le funzioni di X. Tale modo è più complicato (non troppo), però ingegnoso, ed e' dovuto nientemeno che ad Euler. Non postero' pero' il metodo, non ho tempo.

Lo sviluppo in serie di $e^x$ è servito solo a dimostrare la formula $|X|=(n!)/e$ per $n to oo$, a partire dalla formula esatta per $|X|$. Ho messo il risultato solo per la sua bellezza estetica e la meravigliosa connessione fra gruppi di permutazioni e il numero $e$.

ps: il primo topic sui punti fissi e' probabilmente caduto vittima dello spam, e hanno fatto tutto il possibile per salvarlo, lo hanno rianimato due volte, ma l'emoraggia era grave, le difese immunitarie deboli, ecc, e forse e' stata presa la decisione di sopprimere il poverino.

[fields1]

Il post di Piera mi ha suggerito il seguente facile, ma interessante, esercizio.

Abbiamo visto sopra che $|X|/|S_n|=1/e$, per $n\to oo$.

Sia ora $T_n$ l'insieme delle funzioni $f: {1,2,...,n}\rightarrow {1,2,...,n}$ e $Y_n$ l'insieme delle funzioni $f\in T_n$ tali che $f(x)!=x$ per ogni $x\in {1,2,...,n}$.

Dimostrare che, per $n\to oo$, anche $|Y_n|/|T_n|=1/e$