Combinatoria: Contare monomi con qualche proprieta'

[Pappappero1]

Vorrei proporre un problema a cui sto pensando da qualche giorno.

Fissiamo due numeri naturali $n$ e $D$. E' cosa nota che il numero di monomi in $n$ indeterminate di grado esattamente $D$ e'
\[
\binom{D+n-1}{D}.
\]
La dimostrazione di questo fatto e' facile. Si puo' vedere ad esempio questo.

Richiediamo ora che i monomi che vogliamo contare abbiano qualche proprieta'. Spieghero' il caso che mi interessa maggiormente, ma forse esiste qualche generalizzazione che include anche questo caso e che si presta a un approccio interessante.

Fissiamo $n$,$D$ e $d$ (moralmente $d \ge D/n$, ma non e' strettamente necessario). Vogliamo contare il numero di monomi di grado $D$ in $n$ indeterminate in cui ogni indeterminata compare in grado al piu' $d$.

Ho una soluzione parziale "impresentabile" (nel senso che e' una pioggia di sommatorie una dentro l'altra), ma mi piacerebbe sapere se esiste una formula chiusa piu' o meno carina per questo numero (o magari una ricorsione). Qualche idea?

[Pappappero1]

Credo di aver risolto il problema in un modo molto carino.

Se qualcuno avesse una formula chiusa piu' concisa di quella che propongo, ancora meglio.

Il numero che ottengo e' il seguente
\[
\binom{D+n-1}{D} - n\binom{D-(d+1) + n-1}{D-(d+1)} + \binom{n}{2}\binom{D-2(d+1)+n-1}{D-2(d+1)}.
\]

Aggiungo in spoiler la dimostrazione. Ho l'impressione che ci sia una dimostrazione piu' immediata (la formula sembra un inizio di un principio di inclusione-esclusione).

Indico con $S^k$ lo spazio vettoriale dei polinomi omogenei di grado $k$ in $n$ indeterminate. E' noto che \(\dim S^k = \binom {k+n-1}{k}.\)

Indico con $\partial_j$ la derivata nella variabile $x_j$; \(\partial_j ^m\) indichera' la derivata $m$-esima nella variabile $x_j$.

Consideriamo la mappa lineare:
\[
F: S^D \to S^{D-(d+1)} \times ... \times S^{D-(d+1)} \\
f \mapsto (\partial_1^{d+1} f , ... , \partial_n^{d+1} f )
\]
Il nucleo di questa mappa e' generato dai monomi che ci interessano. Dunque, il nostro obiettivo e' calcolare la dimensione del nucleo. Vogliamo usare la formula $\dim \ker F = \dim S^D - \dim Im F$, percio' ci serve la dimensione dell'immagine di $F$.

L'immagine di $F$ e' lo spazio lineare dell'$n$-uple di polinomi in grado $D-(d+1)$ che sono derivate $d+1$-esime di uno stesso polinomio di grado $D$.

Per $d=0$, e' noto che una $n$-upla di polinomi $(g_1 , ... , g_n)$ tutti di grado $D-1$ e' il gradiete di un polinomio $G$ di grado $D$ se e solo se, per ogni $i,j$ si ha $\partial_i g_j = \partial_j g_i$: questo e' conseguenza del fatto che su uno spazio semplicemente connesso le forme differenziali chiuse sono tutte e sole le forme differenziali esatte; in particolare, la forma $g_1 dx_1 + ... + g_n dx_n$ e' esatta se e solo se e' chiusa. Questo risultato si estende a derivate di ordine qualsiasi (almeno nel caso di derivate non miste, cioe' della forma $\partial_j^d$ - non sono sicuro nel caso generale).

In particolare, per $d$ qualsiasi si ha che $(g_1 , ... , g_n) \in Im F$ se e solo se, per ogni $i,j$, $\partial_i^{d+1} g_j = \partial_j^{d+1} g_i$. Questo definisce un sistema lineare negli \( n \binom{D-(d+1) + n-1}{D - (d+1)}\) coefficienti della $g_i$. Si hanno \(\binom{n}{2}\) equazioni polinomiali, ciascuna delle quali definisce equazioni tra i coefficienti delle \(\partial_i^{d+1}{g_j}\) che sono \(\binom{D-2(d+1) + n-1}{D - 2(d+1)}\). Tutte queste equazioni sono linearmente indipendenti e percio' si ottiene
\[
\dim Im F = n \binom{D-(d+1) + n-1}{D - (d+1)} - \binom{n}{2} \binom{D-2(d+1) + n-1}{D - 2(d+1)} .
\]
Questo conclude la dimostrazione.

Qualunque approccio piu' rapido e' benvenuto.


Edit: Ho fatto un errore. Non e' vero che le equazioni che si ottengono sono linearmente indipendenti, anche se in molti casi sembra che sia vero. In effetti per certi valori la formula che ho proposto non e' corretta. Commenti sull'approccio o idee per migliorarlo sono comunque benvenuti.

Edit2: Dopo una marea di conti sembrerebbe che le equazioni sono sempre indipendenti tranne nel caso in cui $d = 0$, e in quel caso la risposta e' banalmente $0$ (a meno che anche $D$ non sia $0$, ma allora siamo a parlare del nulla). A questo pero' la ragione ovvia per cui pensavo che ci fosse indipendenza non e' piu' valida e non so piu' concludere.

Edit3: No! Il caso $(D,n,d) = (7,3,1)$ (e anche altri casi quando $d=1$) ha equazioni dipendenti (in particolare $3$ relazioni). In effetti in questo caso la mia formula restituisce $3$, mentre il valore corretto e' ovviamente $0$.

[Pappappero1]

Ho chiesto su mathoverflow...qui.

L'articolo linkato nella seconda risposta da' diverse interpretazioni combinatorie del numero che ci interessa; fondamentalmente spiega che non c'e' una formula "bella", ma fornisce numerose identita' che possono essere utili nei calcoli.

Anche se non c'e' stata una grande partecipazione, ringrazio chi ci ha pensato.