Rudimenti di calcolo combinatorio. Qualcuno mi puo' spiegare

[sigma]

Sto approcciando il calcolo combinatorio e vorrei capire esattamente (cioe’ non le formulette ma l’origine del significato) cosa vuol dire quanto segue.

Si dice PERMUTAZIONE di n elementi ogni applicazione BIUNIVOCA di $I_n$ in se’.

Siccome non voglio imparare quella frase a memoria ma vorrei capirne il significato proverei a fare un esempio:

Partiamo da zero: prendiamo un insieme A=(a, b)

Una applicazione in se’ sara’ $f: A -> A $ e sara’ un sottoinsime del prodotto cartesiano AxA={(a, b), (b, a), (b, b), (a, a)}

Giusto fin qua’? Ora, dato quanto scritto sopra cos’e’ una applicazione biunivoca di $I_n$ in se’?


Mi scuso se il post e’ confuso o totalmente sballato. La ragione e’che sono nella nebbia totale…

[sigma]

A costo di dire delle cretinate vado avanti:

Una funzione da A in A (cioe’ un sottoinsieme di AxA) dovra’ essere INIETTIVA e SURIETTIVA per essere una permutazione

I sottoinsiemi

(a, b), (b,a)

E

(a, a), (b, b)

Mi pare che rispettino queste proprieta’.

Quindi i due insiemi saranno 2 permutazioni di A.

Deliro?

[Nidhogg]

$I_n$ indica l'applicazione identica $I$ su un insieme $X$ di $n$ elementi.

[irenze]

No, credo che In qui stia per l'insieme {1,...,n}.

Infatti è $X_n={1,2,...,n}$.

Ciao!

[sigma]

$I_n$ e' l'insieme ${1,..., n}$

Proviamo a fare l'esempio con l'insieme $I_3 = {1, 2, 3}$ Mi scriveresti una permutazione qualsiasi di tali elementi spiegandomi perche' e' un'applicazione biunivoca di $I_3$ in se'?

PS
Intuitivamente ho capito che 123 o 321 sono delle permutazioni ma non ho capito come si scrivano come "applicazioni biunivoche di $I_3$" in se'.

[Camillo]

Ti posso dire che le permutazioni di n elementi distinti sono le disposizioni semplici degli n elementi presi ad n ad n( li devi prendere sempre tutti , quello che differenzia una permutazione dall'altra è l'ordine con cui gli elementi sono disposti) .

Dati n elementi distinti , si chiama disposizione semplice degli n elementi , presi a k a k , un gruppo ordinato di k degli n elementi dati.

Le permutazioni di n elementi sono : n ! .

Nel caso dell'esempio da te indicato di tre elementi : 1,2,3 si ha n=3 e quindi le permutazioni sono : 3 ! = 6 e sono :

123
132
213
231
312
321

Camillo

[irenze]

Ma qual è il problema? La rappresentazione?

[irenze]

Una permutazione si scrive mettendo le immagini ordinate:
ad esempio 321 è l'applicazione
1->3
2->2
3->1

Oppure si può scrivere come ciclo:
ad esempio (321) vuol dire
3->2
2->1
1->3

[sigma]

Grazie Camillo e Irenze per le vostre risposte. la verita' e' che il problema e la spiegazione che cerco e' un'altra (o almeno penso).

Come accennato il concetto di permutazione (123, 231, etc..) mi e' chiaro, cosi' come mi e' chiaro calcolarne il numero [n!]. Cio' che invece non mi e' chiaro e mettere insieme il concetto (intuitivo) con la definizione riportata all'inizio.

Andiamo per gradi: innanzitutto dice che una permutazione e' una APPLICAZIONE di $I_n$ in se', cioe' (dico io - e per favore correggetemi se sbaglio) un SOTTOINSIEME del prodotto cartesiano $I_nxI_n$

Prendiamo $I_2 = {1,2}$

$I_2xI_2={(1,1),(1,2),(2,1),(2,2)}$

Mi puoi indicare un sottoinsieme di $I_2xI_2$ che costituisce un'applicazione biunivoca (e quindi una permutazione)?

[irenze]

Tutte e sole le permutazioni sono
{(1,1),(2,2)}
e
{(1,2),(2,1)}.

(Devi avere che tutte le cifre compaiono una - e solo una - volta nella prima componente e una - e una sola - nella seconda.
In termini di definizione analitica, P sottoinsieme di InxIn è una permutazione di In se ed solo se per ogni a in In esiste unico b in In tale che (a,b) appartiene a P.
Ma continuo a non capire qual è il tuo problema...)