Monomi di grado $m$ con $n$ variabili
Quanti sono i monomi di grado [tex]m[/tex] con [tex]n[/tex] variabili?
In altre parole, quante sono le espressioni del tipo [tex]{x_1}^{a_1}...{x_n}^{a_n}[/tex] con [tex]a_1+...+a_n=m[/tex]?
Vi propongo di calcolare questo numero come piu' vi piace. Io inaspettatamente sono riuscito a trovarlo solo con l'ausilio dell'analisi.
Ci dev'essere per forza pero' una dimostrazione puramente combinatoria.
In altre parole, quante sono le espressioni del tipo [tex]{x_1}^{a_1}...{x_n}^{a_n}[/tex] con [tex]a_1+...+a_n=m[/tex]?
Vi propongo di calcolare questo numero come piu' vi piace. Io inaspettatamente sono riuscito a trovarlo solo con l'ausilio dell'analisi.
Ci dev'essere per forza pero' una dimostrazione puramente combinatoria.
Risposte
Con l'ausilio dell'analisi? Se ti va mi piacerebbe tu illustrassi come hai fatto.
Io invece risolverei così: individuare un monomio simile equivale a costruire una sequenza di $m$ oggetti "*" e $n-1$ segnaposti "|", ad esempio
"**||*" corrisponde a $x_1^2x_3$.
Una simile sequenza è individuata una volta che siano stati collocati gli oggetti "*" , perché poi i posti restanti devono necessariamente contenere degli "|", quindi il numero totale di tali sequenze è il numero di modi in cui si possono piazzare $m$ oggetti indistinguibili in $n+m-1$ posti. Questo numero è $((n+m-1), (m))$.
Io invece risolverei così: individuare un monomio simile equivale a costruire una sequenza di $m$ oggetti "*" e $n-1$ segnaposti "|", ad esempio
"**||*" corrisponde a $x_1^2x_3$.
Una simile sequenza è individuata una volta che siano stati collocati gli oggetti "*" , perché poi i posti restanti devono necessariamente contenere degli "|", quindi il numero totale di tali sequenze è il numero di modi in cui si possono piazzare $m$ oggetti indistinguibili in $n+m-1$ posti. Questo numero è $((n+m-1), (m))$.
Oddio no, ti giuro che non ci avevo pensato! Grazie 
a questo punto mi scuso per la banalita' della domanda. Se vuoi metto la mia dimostrazione ma e' imbarazzante.
a questo punto mi scuso per la banalita' della domanda. Se vuoi metto la mia dimostrazione ma e' imbarazzante.
"Martino":
Oddio no, ti giuro che non ci avevo pensato! Grazie
Sì, vorrei vederla se non ti spiace... Sai della mia avversione per i ragionamenti combinatori, no?
P.S.: Ha a che fare con la formula multinomiale di Newton?
Ecco, gugo, ho imparato da te.
Ok, facciamola questa figuraccia.
Chiamiamo [tex]f_n(m)[/tex] il numero dei monomi di grado [tex]m[/tex] con [tex]n[/tex] variabili.
Consideriamo il seguente polinomio: [tex]P(x):={(1+x+x^2+...+x^m)}^n[/tex]. E' facile vedere che il coefficiente di [tex]P(x)[/tex] di grado [tex]m[/tex] e' proprio [tex]f_n(m)[/tex]. Infatti uno puo' pensare agli [tex]n[/tex] fattori come relativi a [tex]n[/tex] variabili distinte [tex]x_1,...,x_n[/tex], svolgere il prodotto e poi far collassare tutte le variabili in una sola imponendo che [tex]x_1=...=x_n=x[/tex]. In questo modo il coefficiente del termine di un dato grado minore o uguale di [tex]m[/tex] non fa altro che dire quanti sono i monomi di quel grado.
Ora, e' chiaro che:
Osservazione. Il coefficiente del termine di grado [tex]m[/tex] di un polinomio [tex]Q(x)[/tex] e' uguale alla derivata [tex]m[/tex]-esima di [tex]Q(x)[/tex] valutata in zero e divisa per [tex]m![/tex].
Osserviamo che [tex](1+x+x^2+...+x^m)(x-1) = x^{m+1}-1[/tex], da cui segue che [tex]P(x) = {\left(\frac{x^{m+1}-1}{x-1}\right)}^n[/tex]. Per l'osservazione [tex]f_n(m) = \frac{1}{m!} P^{(m)}(0)[/tex], dove la notazione [tex]g^{(k)}[/tex] indica la funzione derivata [tex]k[/tex]-esima della funzione [tex]g[/tex]. Scriviamo [tex]A(x)=(x^{m+1}-1)^n[/tex] e [tex]B(x)=(1/(x-1))^n[/tex], cosicche' [tex]P(x) = A(x) B(x) = {\left( x^{m+1}-1 \right)}^n {( x-1 )}^{-n}[/tex]. Osserviamo che tutte le derivate di [tex]A(x)[/tex] dalla prima alla [tex]m[/tex]-esima sono del tipo [tex]xf(x)[/tex] con [tex]f[/tex] definita in zero (in particolare si annullano se valutate in zero), e quindi per la regola di derivazione di un prodotto si ottiene che: [tex]P^{(m)}(0) = A(0) \cdot B^{(m)}(0) = (-1)^n B^{(m)}(0)[/tex]. Ricordiamo che [tex]B(x)=(x-1)^{-n}[/tex]. La derivata [tex]m[/tex]-esima di [tex]B(x)[/tex] e' chiaramente [tex]B^{(m)}(x) = (-n)(-n-1)...(-n-m+1)(x-1)^{-n-m}[/tex]. Ne segue che
[tex]f_n(m) = \frac{1}{m!} \cdot P^{(m)}(0) = \frac{1}{m!} \cdot (-1)^n \cdot B^{(m)}(0) =[/tex]
[tex]= \frac{1}{m!} \cdot (-1)^{-m} \cdot (-n) \cdot (-n-1) \cdot ... \cdot (-n-m+1) =[/tex]
[tex]= \frac{1}{m!} \cdot n \cdot (n+1) \cdot ... \cdot (n+m-1) = \binom{n+m-1}{m}[/tex].
Ora permettetemi un'osservazione: e' vero che l'analisi e' uno strumento potentissimo in generale per risolvere moltissimi problemi di svariate nature, ma non fa molto capire cosa esattamente sta succedendo. La dimostrazione di dissonance invece rende perfettamente l'idea del perche' il risultato e' quel particolare coefficiente binomiale.
Ok, facciamola questa figuraccia.
Chiamiamo [tex]f_n(m)[/tex] il numero dei monomi di grado [tex]m[/tex] con [tex]n[/tex] variabili.
Consideriamo il seguente polinomio: [tex]P(x):={(1+x+x^2+...+x^m)}^n[/tex]. E' facile vedere che il coefficiente di [tex]P(x)[/tex] di grado [tex]m[/tex] e' proprio [tex]f_n(m)[/tex]. Infatti uno puo' pensare agli [tex]n[/tex] fattori come relativi a [tex]n[/tex] variabili distinte [tex]x_1,...,x_n[/tex], svolgere il prodotto e poi far collassare tutte le variabili in una sola imponendo che [tex]x_1=...=x_n=x[/tex]. In questo modo il coefficiente del termine di un dato grado minore o uguale di [tex]m[/tex] non fa altro che dire quanti sono i monomi di quel grado.
Ora, e' chiaro che:
Osservazione. Il coefficiente del termine di grado [tex]m[/tex] di un polinomio [tex]Q(x)[/tex] e' uguale alla derivata [tex]m[/tex]-esima di [tex]Q(x)[/tex] valutata in zero e divisa per [tex]m![/tex].
Osserviamo che [tex](1+x+x^2+...+x^m)(x-1) = x^{m+1}-1[/tex], da cui segue che [tex]P(x) = {\left(\frac{x^{m+1}-1}{x-1}\right)}^n[/tex]. Per l'osservazione [tex]f_n(m) = \frac{1}{m!} P^{(m)}(0)[/tex], dove la notazione [tex]g^{(k)}[/tex] indica la funzione derivata [tex]k[/tex]-esima della funzione [tex]g[/tex]. Scriviamo [tex]A(x)=(x^{m+1}-1)^n[/tex] e [tex]B(x)=(1/(x-1))^n[/tex], cosicche' [tex]P(x) = A(x) B(x) = {\left( x^{m+1}-1 \right)}^n {( x-1 )}^{-n}[/tex]. Osserviamo che tutte le derivate di [tex]A(x)[/tex] dalla prima alla [tex]m[/tex]-esima sono del tipo [tex]xf(x)[/tex] con [tex]f[/tex] definita in zero (in particolare si annullano se valutate in zero), e quindi per la regola di derivazione di un prodotto si ottiene che: [tex]P^{(m)}(0) = A(0) \cdot B^{(m)}(0) = (-1)^n B^{(m)}(0)[/tex]. Ricordiamo che [tex]B(x)=(x-1)^{-n}[/tex]. La derivata [tex]m[/tex]-esima di [tex]B(x)[/tex] e' chiaramente [tex]B^{(m)}(x) = (-n)(-n-1)...(-n-m+1)(x-1)^{-n-m}[/tex]. Ne segue che
[tex]f_n(m) = \frac{1}{m!} \cdot P^{(m)}(0) = \frac{1}{m!} \cdot (-1)^n \cdot B^{(m)}(0) =[/tex]
[tex]= \frac{1}{m!} \cdot (-1)^{-m} \cdot (-n) \cdot (-n-1) \cdot ... \cdot (-n-m+1) =[/tex]
[tex]= \frac{1}{m!} \cdot n \cdot (n+1) \cdot ... \cdot (n+m-1) = \binom{n+m-1}{m}[/tex].
Ora permettetemi un'osservazione: e' vero che l'analisi e' uno strumento potentissimo in generale per risolvere moltissimi problemi di svariate nature, ma non fa molto capire cosa esattamente sta succedendo. La dimostrazione di dissonance invece rende perfettamente l'idea del perche' il risultato e' quel particolare coefficiente binomiale.
@Martino: Sono un cattivo maestro, lo so...
Ad ogni modo, il mio problema con la combinatoria è che confondo sempre combinazioni, disposizioni, etc... Quindi non riesco mai a fare questi conti che a chi è più allenato ed attento risultano molto facili.
Che dire, cercherò di imparare prima o poi.
Ad ogni modo, il mio problema con la combinatoria è che confondo sempre combinazioni, disposizioni, etc... Quindi non riesco mai a fare questi conti che a chi è più allenato ed attento risultano molto facili.
Che dire, cercherò di imparare prima o poi.
\[ \tag{1} M(n, d)=\sum_{j=0}^d M(n-1, j), \]Torno su questa vecchia discussione perché proprio ieri ho trovato un'altra maniera di calcolare lo stesso numero. Si tratta sempre di un metodo analitico, basato su una relazione di ricorrenza che permette di calcolare una funzione generatrice per il numero cercato.
Sia $M(n, d)$ la dimensione dello spazio vettoriale dei polinomi omogenei di $n$ variabili di grado $d$. (Che è uguale al numero di monomi di $n$ variabili di grado $d$, evidentemente). Un simile polinomio può essere scritto come
\[
\sum_{j=0}^d x_n^{d-j} P_j(x_1\ldots x_{n-1}),
\]
dove $P_j$ è un polinomio omogeneo di grado $j$ e di $n-1$ variabili. Questa osservazione porta alla relazione ricorsiva seguente:
\[\tag{1}
M(n, d)=\sum_{j=0}^d M(n-1, j),
\]
che è completata dalla ovvia condizione iniziale $M(1, d)=1$. A questo punto si introduce la funzione generatrice
\[
g_{n}(x)=\sum_{d=0}^\infty x^d M(n, d).\]
(La definizione ha senso perché la serie converge per $|x|<1$. E' una conseguenza della relazione ricorsiva che dà facilmente una stima grossolana di $M(n, j)$ al crescere di $j$. Ma lasciamo perdere questi dettagli analitici. )
La relazione ricorsiva (1) fornisce:
(Notazione: $[0\le j\le d<\infty]=1$ se la condizione in parentesi è verificata e $0$ altrimenti. Secondo Donald Knuth si chiama "parentesi di Iverson")
\[
g_n(x)=\sum_{d,j} x^d M(n-1, j)[0\le j \le d<\infty]=\sum_{j=0}^\infty M(n-1, j) \sum_{d=j}^\infty x^d=\frac{1}{1-x}\sum_{j=0}^\infty x^j M(n-1, j)=\frac{g_{n-1}(x)}{1-x}.\]
La condizione $M(1, d)=1$ fornisce la condizione iniziale per la successione $g_n(x)$:
\[
g_2(x)=\frac{1}{1-x}, \]
e in conclusione
\[
g_n(x)=\frac{1}{(1-x)^{n-1}}.\]
Non resta che sviluppare \((1-x)^{-n}\) in serie di Taylor ed eguagliare i coefficienti per trovare il risultato voluto.
Insomma, è tutto piuttosto complicato e sembra anche inutile, visto che c'è una interpretazione combinatoria in termini di sbarrette e stelline che invece è parecchio più immediata (Vedi i primi post). Ma il metodo è "industriale", e può servire in altre circostanze quando l'interpretazione combinatoria non c'è o non si vede. Per esempio, lo stesso numero $M(n, d)$ è uguale alla cardinalità di questo insieme:
\[
M(n, d)=\#\left\{l_1\ldots l_{n-1}\in \mathbb{Z}_{\ge 0}\ :\ 0\le l_1\le l_2\le \ldots \le l_{n-1}\le d.\right\}.\]
(E' il numero di punti a coordinate intere in un simplesso $n$-dimensionale di lato $d$). Questo si vede iterando la relazione ricorsiva (1):
\[
M(n, d)=\sum_{j_1\ldots j_{n-1}} [0\le j_1\le j_2\le \ldots \le j_{n-1}\le d] =\#\{0\le j_1\le j_2\le \ldots \le j_{n-1}\le d.\}.
\]
Se mi chiedessero direttamente di contare i punti interi nel simplesso, SENZA dirmi che il risultato è uguale al numero di monomi di $n$ variabili di grado $d$, io sicuramente non riuscirei a trovare una interpretazione combinatoria con le sbarrette e le stelline. Ma forse, pensandoci un po' su, riuscirei a trovare la relazione ricorsiva (1). E a quel punto, ricordandomi di questo metodo, chissà riuscirei a imbastire questo calcolo e arrivare alla soluzione.
Sia $M(n, d)$ la dimensione dello spazio vettoriale dei polinomi omogenei di $n$ variabili di grado $d$. (Che è uguale al numero di monomi di $n$ variabili di grado $d$, evidentemente). Un simile polinomio può essere scritto come
\[
\sum_{j=0}^d x_n^{d-j} P_j(x_1\ldots x_{n-1}),
\]
dove $P_j$ è un polinomio omogeneo di grado $j$ e di $n-1$ variabili. Questa osservazione porta alla relazione ricorsiva seguente:
\[\tag{1}
M(n, d)=\sum_{j=0}^d M(n-1, j),
\]
che è completata dalla ovvia condizione iniziale $M(1, d)=1$. A questo punto si introduce la funzione generatrice
\[
g_{n}(x)=\sum_{d=0}^\infty x^d M(n, d).\]
(La definizione ha senso perché la serie converge per $|x|<1$. E' una conseguenza della relazione ricorsiva che dà facilmente una stima grossolana di $M(n, j)$ al crescere di $j$. Ma lasciamo perdere questi dettagli analitici. )
La relazione ricorsiva (1) fornisce:
(Notazione: $[0\le j\le d<\infty]=1$ se la condizione in parentesi è verificata e $0$ altrimenti. Secondo Donald Knuth si chiama "parentesi di Iverson")
\[
g_n(x)=\sum_{d,j} x^d M(n-1, j)[0\le j \le d<\infty]=\sum_{j=0}^\infty M(n-1, j) \sum_{d=j}^\infty x^d=\frac{1}{1-x}\sum_{j=0}^\infty x^j M(n-1, j)=\frac{g_{n-1}(x)}{1-x}.\]
La condizione $M(1, d)=1$ fornisce la condizione iniziale per la successione $g_n(x)$:
\[
g_2(x)=\frac{1}{1-x}, \]
e in conclusione
\[
g_n(x)=\frac{1}{(1-x)^{n-1}}.\]
Non resta che sviluppare \((1-x)^{-n}\) in serie di Taylor ed eguagliare i coefficienti per trovare il risultato voluto.
Insomma, è tutto piuttosto complicato e sembra anche inutile, visto che c'è una interpretazione combinatoria in termini di sbarrette e stelline che invece è parecchio più immediata (Vedi i primi post). Ma il metodo è "industriale", e può servire in altre circostanze quando l'interpretazione combinatoria non c'è o non si vede. Per esempio, lo stesso numero $M(n, d)$ è uguale alla cardinalità di questo insieme:
\[
M(n, d)=\#\left\{l_1\ldots l_{n-1}\in \mathbb{Z}_{\ge 0}\ :\ 0\le l_1\le l_2\le \ldots \le l_{n-1}\le d.\right\}.\]
(E' il numero di punti a coordinate intere in un simplesso $n$-dimensionale di lato $d$). Questo si vede iterando la relazione ricorsiva (1):
\[
M(n, d)=\sum_{j_1\ldots j_{n-1}} [0\le j_1\le j_2\le \ldots \le j_{n-1}\le d] =\#\{0\le j_1\le j_2\le \ldots \le j_{n-1}\le d.\}.
\]
Se mi chiedessero direttamente di contare i punti interi nel simplesso, SENZA dirmi che il risultato è uguale al numero di monomi di $n$ variabili di grado $d$, io sicuramente non riuscirei a trovare una interpretazione combinatoria con le sbarrette e le stelline. Ma forse, pensandoci un po' su, riuscirei a trovare la relazione ricorsiva (1). E a quel punto, ricordandomi di questo metodo, chissà riuscirei a imbastire questo calcolo e arrivare alla soluzione.
Un altro modo utilizzando l'analisi:
$\frac{1}{1-x_{i}}=\sum_{k_{i}=0}^{\infty}x^{k_{i}}$ con \( \left| x_i\right| < 1\) ( serie assolutamente convergente )
\(\prod_{i=1}^{n}\frac{1}{1-x_{i}}=\prod_{i=1}^{n}\sum_{k_{i}=0}^{\infty}x^{k_{i}}=\left(1+x_{1}+x_{1}^{2}+x_{1}^{3}\ldots\right)\left(1+x_{2}+x_{2}^{2}+x_{3}^{2}+\ldots\right)\ldots\left(1+x_{n}+x_{n}^{2}+x_{n}^{3}+\ldots\right)=\sum_{m=0}^{\infty}\sum_{k1+\ldots k_{n}=m}x_{1}^{k1}\ldots x_{n}^{k_{n}}\)
Ponendo $x_{1}=x_{2}=\ldots=x_{n}=x$ e $a_{n,m}$ il numero di monomi di grado $m$
\(\left(1-x\right)^{-n}=\sum_{m=0}^{\infty}a_{n,m}x^{m}\)
Per la nota formula :
\(\left(1-x\right)^{-n}=\sum_{m=0}^{\infty}a_{n,m}x^{m}=\sum_{m=0}^{\infty}\binom{-n}{m}(-1)^{m}x^{m}\)
da cui
\(a_{n,m}=\binom{-n}{m}=\binom{m+n-1}{m}\)
$\frac{1}{1-x_{i}}=\sum_{k_{i}=0}^{\infty}x^{k_{i}}$ con \( \left| x_i\right| < 1\) ( serie assolutamente convergente )
\(\prod_{i=1}^{n}\frac{1}{1-x_{i}}=\prod_{i=1}^{n}\sum_{k_{i}=0}^{\infty}x^{k_{i}}=\left(1+x_{1}+x_{1}^{2}+x_{1}^{3}\ldots\right)\left(1+x_{2}+x_{2}^{2}+x_{3}^{2}+\ldots\right)\ldots\left(1+x_{n}+x_{n}^{2}+x_{n}^{3}+\ldots\right)=\sum_{m=0}^{\infty}\sum_{k1+\ldots k_{n}=m}x_{1}^{k1}\ldots x_{n}^{k_{n}}\)
Ponendo $x_{1}=x_{2}=\ldots=x_{n}=x$ e $a_{n,m}$ il numero di monomi di grado $m$
\(\left(1-x\right)^{-n}=\sum_{m=0}^{\infty}a_{n,m}x^{m}\)
Per la nota formula :
\(\left(1-x\right)^{-n}=\sum_{m=0}^{\infty}a_{n,m}x^{m}=\sum_{m=0}^{\infty}\binom{-n}{m}(-1)^{m}x^{m}\)
da cui
\(a_{n,m}=\binom{-n}{m}=\binom{m+n-1}{m}\)
"Martino":
Quanti sono i monomi di grado [tex]m[/tex] con [tex]n[/tex] variabili?
Mi pare che sia sottinteso che ciascun monomio deve non essere simile ad alcun altro.
Allora non è restrittivo assumere i monomi tutti "monici" (cioè con coefficiente 1).
Domanda a tutti quelli già intervenuti ((Martino, dissonance, gugo82 e totissimus):
Mettiamo che il grado m valga 4 e il numero n di variabili sia 2, diciamole x e y.
Secondo voi, $x^4$ e $y^4$ sono monomi di grado 4 con 2 variabili?
Dall'aver concluso che il numero di monomi [monici] di grado m con n variabili è $((n+m-1), (m))$ sembrerebbe di sì.
Nell'esempio $m=4$ e $n=2$ verrebbe $((2 + 4 - 1), (4)) = ((5), (4)) =5$. Cioè:
$x^4, y^4, x^3y, xy^3, x^2y^2$
Secondo me, invece, $x^5$ e $y^5$ sono in una sola variabile.
[Se no ... se mi fosse lecito il pensare ad altre variabili di grado zero, potrei dire che sono di un numero n di variabili grande a piacere.
]Mi pare, dunque, obbligatorio che in ciascun monomio compaiano tutte le n variabili e che quindi il grado di una di esse possa variare da 1 a $m – (n–1)$ inclusi (e non da 0 ad m inclusi).
Tornando all'esempio $m=4$ e $n=2$, per me i monomi [monici] di quarto grado nelle due variabili x ed y sono solo
$x^3y, x^2y^2, xy^3$;
tre in tutto (e non cinque).
Esaminando allora direttamente qualche caso con n ed m piccoli e ragionando poi per induzione mi pare che la risposta corretta al quesito sia $((m-1), (m - n)) = ((m-1), (n-1))$.
-----------
Grazie dissonance totissimus e Erasmus_First per gli interessanti interventi!
Erasmus_First sì a rigore è come dici tu, ma non è difficile dedurre la formula che vuoi da quella trovata sopra (invece il viceversa mi sembra meno ovvio). Quella che dici tu è la nostra applicata al caso di grado [tex]m-n[/tex] con [tex]n[/tex] variabili (facendo comparire le [tex]n[/tex] variabili una volta "di forza"), quindi viene [tex]\binom{n+(m-n)-1}{m-n} = \binom{m-1}{m-n}[/tex] come mi sembra che stai dicendo anche tu.
Erasmus_First sì a rigore è come dici tu, ma non è difficile dedurre la formula che vuoi da quella trovata sopra (invece il viceversa mi sembra meno ovvio). Quella che dici tu è la nostra applicata al caso di grado [tex]m-n[/tex] con [tex]n[/tex] variabili (facendo comparire le [tex]n[/tex] variabili una volta "di forza"), quindi viene [tex]\binom{n+(m-n)-1}{m-n} = \binom{m-1}{m-n}[/tex] come mi sembra che stai dicendo anche tu.
"Martino":Sì, proprio così.
[...] quindi viene [tex]\binom{n+(m-n)-1}{m-n} = \binom{m-1}{m-n}[/tex] come mi sembra che stai dicendo anche tu.
E ti ringrazio ... di questa precisazione che m'ha portato ad accorgermi d'ave scambiato $m$ con $n$ nello scrivere le formule finali.
[Le ho già corrette editando].
------
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo