[Combinatoria elementare] Alcune proprietà dei multiindici
\( \newcommand{\sgn}[1]{\operatorname{sgn}{#1}} \)\( \newcommand{\Im}[1]{\operatorname{Im}{#1}} \)Ciao. Sia \( [j] = \{1,\dots,j\} \), e siano \( f\colon[h]\to[n] \) e \( g\colon[k]\to[n] \) due funzioni qualsiasi. Con \( f\vee g \) denoto la funzione \( [h + k]\to[n] \) che mappa
\[
f\vee g(x) =
\begin{cases}
f(x) & \text{se $ 1\leqq x\leqq h $}\\
g(x - h) & \text{se $ 1+h\leqq x\leqq k + h $}
\end{cases}
\]
Sia \( \mathscr I_n^k \) l'insieme delle funzioni \( [k]\to[n] \) strettamente crescenti, per due interi \( k\leqq n \).
Devo provare un po' di cose.
1. Siano \( I\in\mathscr I_n^h \) e \( J\in\mathscr I_n^k \) tali che \( \Im I\cap\Im J = \emptyset \). Allora esiste un'unica permutazione \( \sigma\in S_{h + k} \) (= il gruppo simmetrico) tale che \( (I\vee J)\circ\sigma\in\mathscr I_n^{h + k} \).
2. Definito il segno di \( I\vee J \) come \( \sgn(I\vee J) := \sgn\sigma \), dove \( \sigma \) è la permutazione della quale si sono verificate esistenza e unicità su, è
\[
\sgn(I\vee J) = (-1)^{hk}(J\vee I)
\]
3. Data \( I\in\mathscr I_{h + k}^h \), esiste ed è unica \( cI\in\mathscr I_{h + k}^k \) tale che \( I\vee cI\colon[h + k]\to[h + k]\) sia una permutazione. Inoltre \( c\colon\mathscr I_{h + k}^h\to\mathscr I_{h + k}^k \) che mappa \( I\mapsto cI \) è biiettiva.
La 2. e la 3. non ho idea di come approcciarle. A occhio sono cose ovvie, ma ho dei problemi proprio a formalizzare i ragionamenti.
Poi ci sarebbe altro, ma voglio vedere se fatto intanto questo dopo riesco a fare da solo.
\[
f\vee g(x) =
\begin{cases}
f(x) & \text{se $ 1\leqq x\leqq h $}\\
g(x - h) & \text{se $ 1+h\leqq x\leqq k + h $}
\end{cases}
\]
Sia \( \mathscr I_n^k \) l'insieme delle funzioni \( [k]\to[n] \) strettamente crescenti, per due interi \( k\leqq n \).
Devo provare un po' di cose.
1. Siano \( I\in\mathscr I_n^h \) e \( J\in\mathscr I_n^k \) tali che \( \Im I\cap\Im J = \emptyset \). Allora esiste un'unica permutazione \( \sigma\in S_{h + k} \) (= il gruppo simmetrico) tale che \( (I\vee J)\circ\sigma\in\mathscr I_n^{h + k} \).
2. Definito il segno di \( I\vee J \) come \( \sgn(I\vee J) := \sgn\sigma \), dove \( \sigma \) è la permutazione della quale si sono verificate esistenza e unicità su, è
\[
\sgn(I\vee J) = (-1)^{hk}(J\vee I)
\]
3. Data \( I\in\mathscr I_{h + k}^h \), esiste ed è unica \( cI\in\mathscr I_{h + k}^k \) tale che \( I\vee cI\colon[h + k]\to[h + k]\) sia una permutazione. Inoltre \( c\colon\mathscr I_{h + k}^h\to\mathscr I_{h + k}^k \) che mappa \( I\mapsto cI \) è biiettiva.
La 2. e la 3. non ho idea di come approcciarle. A occhio sono cose ovvie, ma ho dei problemi proprio a formalizzare i ragionamenti.
Poi ci sarebbe altro, ma voglio vedere se fatto intanto questo dopo riesco a fare da solo.
Risposte
Io avrei approcciato il problema come segue, ma considera che sono anni che non vedo questo genere di cose.
1. Sia \(f \colon |h| \to |n|\) una qualsiasi funzione iniettiva. La sua immagine sarà quindi formata da \(h\) elementi disgiunti e posso costruire una permutazione \(\overline{f} \colon |h| \to |h| = \tau_f \circ f\) dove \(\tau_f\) è la funzione che manda ogni elemento dell'immagine di \(f\) in \(|h|\) preservandone l'ordine. Avremo che \(f \in \mathscr I^h_n\) se e solo se \(\overline{f} = 1_{S_h}\).
Consideriamo ora \(I \vee J\). È una funzione iniettiva per cui abbiamo una permutazione \(\overline{I \vee J}\) che non sarà necessariamente l'identità. Tuttavia esisterà un'unica permutazione \(\sigma^{-1} = \overline{I \vee J}\) per cui
\[ 1_{S_{h+k}} = \overline{I \vee J} \circ \sigma = \bigl( \tau \circ (I \vee J) \bigr) \circ \sigma = \tau \circ \bigl( (I \vee J) \circ \sigma \bigr) = \overline{(I \vee J) \circ \sigma} \]
Abbiamo quindi che \((I \vee J) \circ \sigma \in \mathscr I^{h+k}_n \) per la discussione precedente.
2. Siccome \(\mathrm{sgn}(\sigma^{-1}) = \mathrm{sgn}(\sigma),\) abbiamo che
\[ \mathrm{sgn}(I \vee J) = \mathrm{sgn}(\sigma) = \mathrm{sgn}(\overline{I \vee J}) \]
Inoltre \(J \vee I = (I \vee J) \circ \phi \) dove \(\phi\) è la permutazione che sposta gli ultimi \(h\) elementi ai primi \(h\) e i primi \(k\) negli ultimi \(k\). Abbiamo inoltre che
\[ \mathrm{sgn}(J \vee I) = \mathrm{sgn}(\overline{J \vee I}) = \mathrm{sgn}(\overline{I \vee J})\,\mathrm{sgn}(\phi) = (-1)^{hk}\mathrm{sgn}(I \vee J) \]
1. Sia \(f \colon |h| \to |n|\) una qualsiasi funzione iniettiva. La sua immagine sarà quindi formata da \(h\) elementi disgiunti e posso costruire una permutazione \(\overline{f} \colon |h| \to |h| = \tau_f \circ f\) dove \(\tau_f\) è la funzione che manda ogni elemento dell'immagine di \(f\) in \(|h|\) preservandone l'ordine. Avremo che \(f \in \mathscr I^h_n\) se e solo se \(\overline{f} = 1_{S_h}\).
Consideriamo ora \(I \vee J\). È una funzione iniettiva per cui abbiamo una permutazione \(\overline{I \vee J}\) che non sarà necessariamente l'identità. Tuttavia esisterà un'unica permutazione \(\sigma^{-1} = \overline{I \vee J}\) per cui
\[ 1_{S_{h+k}} = \overline{I \vee J} \circ \sigma = \bigl( \tau \circ (I \vee J) \bigr) \circ \sigma = \tau \circ \bigl( (I \vee J) \circ \sigma \bigr) = \overline{(I \vee J) \circ \sigma} \]
Abbiamo quindi che \((I \vee J) \circ \sigma \in \mathscr I^{h+k}_n \) per la discussione precedente.
2. Siccome \(\mathrm{sgn}(\sigma^{-1}) = \mathrm{sgn}(\sigma),\) abbiamo che
\[ \mathrm{sgn}(I \vee J) = \mathrm{sgn}(\sigma) = \mathrm{sgn}(\overline{I \vee J}) \]
Inoltre \(J \vee I = (I \vee J) \circ \phi \) dove \(\phi\) è la permutazione che sposta gli ultimi \(h\) elementi ai primi \(h\) e i primi \(k\) negli ultimi \(k\). Abbiamo inoltre che
\[ \mathrm{sgn}(J \vee I) = \mathrm{sgn}(\overline{J \vee I}) = \mathrm{sgn}(\overline{I \vee J})\,\mathrm{sgn}(\phi) = (-1)^{hk}\mathrm{sgn}(I \vee J) \]
Grazie mille per la risposta! Me la leggo non appena ritorno su questi argomenti.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo