Conteggio di funzioni
Allora mi sto dedicando infruttuosamente da un po' di tempo a questo problema di conteggio:
Presi due insiemi $N$ $X$ quante sono le funzioni arricchite, cioè tutte quelle funzioni di cui l'insieme composto dalla retroimmagine di un elemento $x$ possiede un ordine per ogni elemento $x$$inX$, con $X$ non distinguibile ed $|N|=n$ e $|X|=x$?
Un esempio è il seguente: $f,gN\toX$ se $N={1,2,3,4}$ e $X={1,2}$ tali che
$f(1)=g(1)=1, f(2)=g(2)=1, f(3)=g(3)=1, f(4)=g(4)=2$
e
$f^-1(1)={1<2<3}$
$g^-1(1)={1<3<2}$
Allora $f!=g$
Allora io ho pensato che il mio problema fisicamente potrebbe essere rappresentato come: "in quanti modi posso mettere n palline in x scatole ed in ogni scatola avere un ordine diverso?"
Così ho pensato: se conto solo il numero delle funzioni suriettive e indico tale numero con $S_(n,x) $ per $n$ palline e $x$ scatole ho che:
$S_(i,i)=1$
$S_(i,j)=0 text{se} j>i$
$S_(i,1)=i!$ perché avrò una funzione diversa per ogni ordine che definisco, cioè per ogni disposizione delle $i$ palline.
$S_(n,2)=(n-1)/2 *n!$ posso farvi vedere il conto
allora: prendo un sottoinsieme di $n-1$ elementi, e guardo quanto sono le "n-1 disposizioni" poi ci sommo i sottoinsiemi di $n-2$ elementi e guardo quante sono le "n-2 disposizioni" per le "2 disposizioni",... e ripeto questa cosa fino ad parte intera di $n/2$.
In formule:
$\sum_{i=1}^\(n/2)\ ((n),(n-i)) * (n-i)!i!$
Se non ho sbagliato a scrivere si vede facilmente che il risultato è quello scritto lassù!
Ora mi trovo in difficoltà... perché ho provato a fare lo stesso conteggio per $x=3$ ma non sono arrivato a nulla...
Secondo me si necessita dell'utilizzo dei diagrammi di Ferrers, ma non vado da nessuna parte!
Le funzioni normali sono semplicemente
$\sum_{i=1}^x\ S_(n,i)$
Ma non so come trovare una ricorrenza per le $S_(n,x)$
Presi due insiemi $N$ $X$ quante sono le funzioni arricchite, cioè tutte quelle funzioni di cui l'insieme composto dalla retroimmagine di un elemento $x$ possiede un ordine per ogni elemento $x$$inX$, con $X$ non distinguibile ed $|N|=n$ e $|X|=x$?
Un esempio è il seguente: $f,gN\toX$ se $N={1,2,3,4}$ e $X={1,2}$ tali che
$f(1)=g(1)=1, f(2)=g(2)=1, f(3)=g(3)=1, f(4)=g(4)=2$
e
$f^-1(1)={1<2<3}$
$g^-1(1)={1<3<2}$
Allora $f!=g$
Allora io ho pensato che il mio problema fisicamente potrebbe essere rappresentato come: "in quanti modi posso mettere n palline in x scatole ed in ogni scatola avere un ordine diverso?"
Così ho pensato: se conto solo il numero delle funzioni suriettive e indico tale numero con $S_(n,x) $ per $n$ palline e $x$ scatole ho che:
$S_(i,i)=1$
$S_(i,j)=0 text{se} j>i$
$S_(i,1)=i!$ perché avrò una funzione diversa per ogni ordine che definisco, cioè per ogni disposizione delle $i$ palline.
$S_(n,2)=(n-1)/2 *n!$ posso farvi vedere il conto
allora: prendo un sottoinsieme di $n-1$ elementi, e guardo quanto sono le "n-1 disposizioni" poi ci sommo i sottoinsiemi di $n-2$ elementi e guardo quante sono le "n-2 disposizioni" per le "2 disposizioni",... e ripeto questa cosa fino ad parte intera di $n/2$.
In formule:
$\sum_{i=1}^\(n/2)\ ((n),(n-i)) * (n-i)!i!$
Se non ho sbagliato a scrivere si vede facilmente che il risultato è quello scritto lassù!
Ora mi trovo in difficoltà... perché ho provato a fare lo stesso conteggio per $x=3$ ma non sono arrivato a nulla...
Secondo me si necessita dell'utilizzo dei diagrammi di Ferrers, ma non vado da nessuna parte!
Le funzioni normali sono semplicemente
$\sum_{i=1}^x\ S_(n,i)$
Ma non so come trovare una ricorrenza per le $S_(n,x)$
Risposte
Mmmm, sembra che questo problema abbia generato una sorta di effetto Non Polinomiale sugli utenti!!!
Vediamo se è veramente così!
Vi offro al vaglio una possibile soluzione:
Allora se la prendo larga:
ho provato ad utilizzare il coefficiente multinomiale:
$((,,n,),(K_1,K_2,...,K_x))=(n!)/(K_1!K_2!...K_x!)$
Che mi dice in quanti modi posso stipare $n$ palline in $x$ scatole ognuna di cardinalità $k_i$.
Chiaramente non è questo il numero di scatole che mi serve, ma sarà esattamente il doppio, poiché ogni ripartizione considera anche la speculare, ma le mie scatole sono indistinguibili.
Esempio: voglio mettere 5 oggetti $A,B,C,D,E$ in 3 scatole, in modo tale da rispettare tutte le Hp del problema tranne il fatto che sono arricchite: allora le mie possibilità saranno:
$A-B-CDE,A-C-BDE,A-D-CBE,A-E-BCD,B-C-ADE,B-D-ACE,B-E-ACD,$
$C-D-ABE,C-E-ABD,D-E-ABC$
e questo solo per la partizione $1-1-3$
Poi ci sono le rimanenti:
$A-BC-DE,A-BD-CE,A-BE-CD,B-AC-DE,B-AD-CE,B-AE-CD,C-AB-DE,$
$C-AD-BE,C-AE-BD,D-AB-CE,D-AC-BE,D-AE-BC,E-AB-CD,E-AC-BD,$
$E-AD-BC$
Queste sono invece per la partizione $1-2-2$
Ora se faccio il conto il coefficiente multinomiale per le prime vale
$((5),(3))=20$ ma le partizioni che ho scritto sono $10$
Riperto per le seconde e mi torna
$((5,),(2,2))=30$ ma quelle che ho scritto sono $15$;
Dunque dall'esempio dovrebbe risultare chiaro perché ne escluda metà!
Quindi provato che il numero di partizioni delle scatole possibili è il coeff. multinomiale diviso due soffermiamoci ad analizzare un caso particolare del mio problema:
Il caso in cui ho le scatole di cardinalità $K_1,K_2,...,K_x$
Dunque per ogni scatola avrò la cardinalità $K_i$
Allora il conteggio finale sarà:
$(((,,n,),(K_1,K_2,...,K_x))*(K_1!K_2!...K_x!)/2)=(n!)/2$
Ma allora mi basterà considerare i numeri di partizioni di $n$ in $x$ parti che indico con $P_{n,x}$.
E dunque in base a quanto osservato sin ora si vede che:
Il numero di funzioni arricchite suriettive da un insieme $N$ di cardinalità $n$ ad insieme $X$ di cardinalità $x$ è
$((n!)/2)P_{n,x}$.
Vediamo se è veramente così!
Vi offro al vaglio una possibile soluzione:
Allora se la prendo larga:
ho provato ad utilizzare il coefficiente multinomiale:
$((,,n,),(K_1,K_2,...,K_x))=(n!)/(K_1!K_2!...K_x!)$
Che mi dice in quanti modi posso stipare $n$ palline in $x$ scatole ognuna di cardinalità $k_i$.
Chiaramente non è questo il numero di scatole che mi serve, ma sarà esattamente il doppio, poiché ogni ripartizione considera anche la speculare, ma le mie scatole sono indistinguibili.
Esempio: voglio mettere 5 oggetti $A,B,C,D,E$ in 3 scatole, in modo tale da rispettare tutte le Hp del problema tranne il fatto che sono arricchite: allora le mie possibilità saranno:
$A-B-CDE,A-C-BDE,A-D-CBE,A-E-BCD,B-C-ADE,B-D-ACE,B-E-ACD,$
$C-D-ABE,C-E-ABD,D-E-ABC$
e questo solo per la partizione $1-1-3$
Poi ci sono le rimanenti:
$A-BC-DE,A-BD-CE,A-BE-CD,B-AC-DE,B-AD-CE,B-AE-CD,C-AB-DE,$
$C-AD-BE,C-AE-BD,D-AB-CE,D-AC-BE,D-AE-BC,E-AB-CD,E-AC-BD,$
$E-AD-BC$
Queste sono invece per la partizione $1-2-2$
Ora se faccio il conto il coefficiente multinomiale per le prime vale
$((5),(3))=20$ ma le partizioni che ho scritto sono $10$
Riperto per le seconde e mi torna
$((5,),(2,2))=30$ ma quelle che ho scritto sono $15$;
Dunque dall'esempio dovrebbe risultare chiaro perché ne escluda metà!
Quindi provato che il numero di partizioni delle scatole possibili è il coeff. multinomiale diviso due soffermiamoci ad analizzare un caso particolare del mio problema:
Il caso in cui ho le scatole di cardinalità $K_1,K_2,...,K_x$
Dunque per ogni scatola avrò la cardinalità $K_i$
Allora il conteggio finale sarà:
$(((,,n,),(K_1,K_2,...,K_x))*(K_1!K_2!...K_x!)/2)=(n!)/2$
Ma allora mi basterà considerare i numeri di partizioni di $n$ in $x$ parti che indico con $P_{n,x}$.
E dunque in base a quanto osservato sin ora si vede che:
Il numero di funzioni arricchite suriettive da un insieme $N$ di cardinalità $n$ ad insieme $X$ di cardinalità $x$ è
$((n!)/2)P_{n,x}$.
Non è corretta nemmeno questa infatti se si prova con $n=6$ e con la partizione $2-2-2$ non torna 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo