Rudimenti di calcolo combinatorio. Qualcuno mi puo' spiegare
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…
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…
Risposte
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?
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?
$I_n$ indica l'applicazione identica $I$ su un insieme $X$ di $n$ elementi.
No, credo che In qui stia per l'insieme {1,...,n}.
Infatti è $X_n={1,2,...,n}$.
Ciao!
Infatti è $X_n={1,2,...,n}$.
Ciao!
$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'.
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'.
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
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
Ma qual è il problema? La rappresentazione?
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
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
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)?
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)?
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...)
{(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...)
Ciao Irenze, grazie per la pazienza.
Il mio problema e' collegare i sottoinsiemi dati dalla definizione di permutazione:
{(1,1),(2,2)}
e
{(1,2),(2,1)}
con l'idea intuitiva delle "sequenze" 12 e 21.
Ad esempio {(1,1),(2,2)} corrisponde a 12 o 21? E perche'? Da cosa lo "vedi"?
Il concetto pare ovvio per tutti ma io non sembro in grado di arrivarci...
Il mio problema e' collegare i sottoinsiemi dati dalla definizione di permutazione:
{(1,1),(2,2)}
e
{(1,2),(2,1)}
con l'idea intuitiva delle "sequenze" 12 e 21.
Ad esempio {(1,1),(2,2)} corrisponde a 12 o 21? E perche'? Da cosa lo "vedi"?
Il concetto pare ovvio per tutti ma io non sembro in grado di arrivarci...
Corrisponde a 12.
Te l'ho scritto sopra il significato delle rappresentazioni!
Se scrivi una permutazione di {1,...,n} nella rappresentazione che stai dando tu, stai semplicemente scrivendo l'elenco ordinato delle immagini degli elementi di {1,...,n} (il primo numero è l'immagine di 1, il secondo l'immagine di 2 e così via).
Te l'ho scritto sopra il significato delle rappresentazioni!
Se scrivi una permutazione di {1,...,n} nella rappresentazione che stai dando tu, stai semplicemente scrivendo l'elenco ordinato delle immagini degli elementi di {1,...,n} (il primo numero è l'immagine di 1, il secondo l'immagine di 2 e così via).
Finalmente ci sono! Grazie a tutti! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo