Nell’articolo precedente abbiamo contato le partizioni di un intero $n$ in $k$ parti dove le parti erano strettamente positive oppure non-negative. Questa volta consideriamo una classe più generale di restrizioni sulle $k$ parti. Cominciamo con un esempio.
Problema. In quanti modi possiamo scegliere $a+b+c=10$ con $0 \le a \le 8$ e $0 \le b, c \le 6$?
Soluzione. Il problema è parecchio più complicato di quelli che abbiamo affrontato nella puntata precedente. La soluzione è nel rappresentare le varie possibilità per i tre numeri come dei polinomi. Ad esempio:
$$a \to 1+x+x^2+\cdots+x^8\\
b \to 1+x+x^2+\cdots+x^6\\
c \to 1+x+x^2+\cdots+x^6$$
Ovvero se $m$ è una possibilità per il numero, aggiungiamo il termine $x^m$. Poiché $x^a x^b x^c = x^{a+b+c}$, la somma $a+b+c$ corrisponde al prodotto dei polinomi che rappresentano $a,b$ e $c$. Quindi la soluzione del problema è il coefficiente di $x^{10}$ nel polinomio
$$p(x)=(1+x+x^2+\cdots+x^8) (1+x+x^2+\cdots+x^6)^2$$
Infatti quando moltiplichiamo $x^a$, $x^b$ e $x^c$ otteniamo $x^{a+b+c}$. Ora, $p(x)$ ha tre termini: il primo ha per esponenti tutti i possibili $a$ (cioè ad $a=0$ corrisponde $x^0=1$, ad $a=1$ corrisponde $x^1=x$, e così via fino all’ultimo possibile $a$, cioè 8, che corrisponde a $x^8$.) Il secondo termine corrisponde a tutti i possibili $b$, che varia tra 0 e 6. Il terzo a tutti i possibili $c$, che anch’esso varia tra 0 e 6.
Quando moltiplichiamo questi tre polinomi per ottenere il polinomio finale, prendiamo un $x^a$ dal primo termine, un $x^b$ dal secondo e un $x^c$ dal terzo, e li moltiplichiamo insieme per ottenere un $x^{a+b+c}$. A noi interessa $x^{10}$ perché $a+b+c=10$, e ci interessa il coefficiente di $x^{10}$ perché è il numero di volte che prendendo un $x^a$ dal primo termine, un $x^b$ dal secondo e un $x^c$ dal terzo, otteniamo $a+b+c=10$.
Per ottenere il coefficiente di $x^{10}$ bisogna massaggiare il polinomio. Abbiamo:
\begin{equation*}
\begin{split}
p(x) & =\left(1+x+x^2+\cdots+x^8 \right) \left(1+x+x^2+\cdots+x^6 \right)^2 = \\
&= \left( \frac{1-x^9}{1-x} \right) \left( \frac{1-x^7}{1-x} \right)^2= \\
&= \left( 1-x^9 \right) \left( 1-x^7 \right)^2 \frac{1}{(1-x)^3} = \\
&= \left( 1-x^9 \right) \left( 1-2x^7+x^{14} \right) \frac{1}{(1-x)^3}= \\
&= \left( 1-2x^7-x^9 + S(x) \right)\frac{1}{(1-x)^3}
\end{split}
\end{equation*}
dove $S(x)$ è un polinomio schifoso di grado maggiore di 10 (non ci interessa neanche calcolarlo, la $S$ sta per schifo). Per trattare il denominatore utilizziamo un’espansione in serie:
$$\frac{1}{\left( 1-x \right) ^{q}}= \sum_{k=0}^{\infty} {k+q-1 \choose q-1} x^k=1+q x+{q+1 \choose q-1} x^2+{q+2 \choose q-1} x^3+\cdots$$
Quindi $\frac{1}{(1-x)^3}=\sum_{k=0}^{\infty} {k+2 \choose 2}x^k$. Nell’altro polinomio abbiamo 1, $x^7$, $x^9$. Per portare l’esponente a $10$, dobbiamo moltiplicarli rispettivamente per $x^{10}$, $x^3$, $x$. Nel polinomio infinito, il coefficiente di $x^{10}$ è ${10+2 \choose 2}$, il coefficiente di $x^3$ è ${3+2 \choose 2}$ e il coefficiente di $x$ è ${1+2 \choose 2}$. Quindi il nostro numero è: $$ 1 \times {10+2 \choose 2} -2 \times {3+2 \choose 2}-1 \times {1+2 \choose 2}= 1 \times 66 – 2 \times 10 – 1 \times 3 = 43$$
ovvero la soluzione che cercavamo.
Questo metodo può essere utilizzato per problemi ancora più brutti. Ad esempio:
Problema. In quanti modi possiamo scegliere $a+b+c+d+e=25$ con $3 \le a \le 12$, $0 \le b, c, d \le 15$, $e = 4, 5, 9$?
Soluzione. Il problema è simile a quello prima. Poiché ci sono cinque lettere il polinomio che cerchiamo avrà cinque termini. Il primo (corrispondente ai valori di $a$) conterrà le potenza da $x^3$ a $x^{12}$. Il secondo, il terzo e il quarto (corrispondenti a $b$, $c$ e $d$) tutti quelli tra $x^0=1$ e $x^{15}$. Il quinto (che corrisponde a $e$) ha solo $x^4$, $x^5$ e $x^9$, perché $e$ può assumere solo questi valori. Il polinomio sarà quindi:
$$p(x)= (x^3+x^4+x^5+\cdots+x^{12}) (1+x+x^2+\cdots+x^{15} ) ^3 (x^4+x^5+x^9)$$
Ci interessa il coefficiente di $x^{25}$. Rimbocchiamoci le maniche e massaggiamo:
\begin{equation*}
\begin{split}
p(x) &= (x^3+x^4+x^5+\cdots+x^{12}) (1+x+x^2+\cdots+x^{15} ) ^3 (x^4+x^5+x^9)=\\
&= x^3 \frac{1-x^{10}}{1-x} \left( \frac{1-x^{16}}{1-x} \right)^3 (x^4+x^5+x^9)=\\
&=(x^3-x^{13}) (1-3x^{16}+3x^{32}-x^{48}) (x^4+x^5+x^9) \frac{1}{(1-x)^4}= \\
&=(x^3-3x^{19}-x^{13}+S(x)) (x^4+x^5+x^9) \frac{1}{(1-x)^4}=\\
&=(x^7+x^8+x^{12}-x^{17}-x^{18}-x^{22}-3x^{23}-3x^{24}+S(x)) \frac{1}{(1-x)^4}
\end{split}
\end{equation*}
dove il polinomio schifoso $S(x)$ ha grado maggiore di $25$, e quindi non ci interessa. Ora, questa volta $\frac{1}{(1-x)^4}=\sum_{k=0}^{\infty} {k+3 \choose 3}x^k$.
Nell’altro polinomio abbiamo $x^7$, $x^8$, $x^{12}$, $x^{17}$, $x^{18}$, $x^{22}$, $x^{23}$, $x^{24}$. Per portarli a 25, dobbiamo moltiplicarli rispettivamente per $x^{18}$, $x^{17}$, $x^{13}$, $x^8$, $x^7$, $x^3$, $x^2$, $x$. Nel polinomio infinito, il coefficiente di $x^{18}$ è ${18+3 \choose 3}$, il coefficiente di $x^{17}$ è ${17+3 \choose 3}$, e così via. Il nostro numero è pertanto:
\begin{multline*}
1 \times {18+3 \choose 3} + 1 \times {17+3 \choose 3}+ 1 \times {13+3 \choose 3}- 1 \times {8+3 \choose 3}+\\- 1 \times {7+3 \choose 3}- 1 \times {3+3 \choose 3}- 3 \times {2+3 \choose 3}- 3 \times {1+3 \choose 3}=\\
= 1330+1140+560-165-120-20-30-12=2683
\end{multline*}
che è la nostra soluzione.
Con lo stesso metodo possiamo risolvere problemi più pratici:
Problema. In quanti modi posso ottenere $1$ euro con tre monete da $20$ centesimi, cinque da $10$, e cinque da $5$?
Soluzione Per prima cosa passiamo l’unità di misura in centesimi, così evitiamo le frazioni. In termini aritmetici, se $a$ è il numero di monete da $20$ che usiamo, $b$ il numero di monete da $10$ che usiamo e $c$ il numero di monete da $5$ che usiamo, dev’essere:
$$ 20 a + 10 b + 5 c = 100 $$
Con: $0 \le a \le 3$, $0 \le b \le 5$, $0 \le c \le 5$. È molto simile ad un problema di partizioni, se non fosse per i coefficienti davanti. Per semplificarci il lavoro possiamo anche dividere tutto per $5$:
$$ 4 a + 2 b + c = 20 $$
Ma ciò non cambia la sostanza del lavoro. Usiamo sempre il metodo dei polinomi, ma questa volta, quando moltiplichiamo per, ad esempio, $a$, questo vale per quattro (è come se invece di a vere $a=0, 1, 2, 3$ avessimo $a=0, 4, 8, 12$).
Il polinomio quindi, in questo caso è:
\begin{equation*}
\begin{split}
&(1+x^4+x^8+x^{12}) (1+x^2+x^4+x^6+x^8+x^{10}) (1+x+x^2+x^3+x^4+x^5)=\\
&= \frac{1-x^{16}}{1-x^4} \frac{1-x^{12}}{1-x^2} \frac{1-x^6}{1-x}=\\
&=(1-x^{16}) (1-x^6-x^{12}+x^{18}) \frac{1}{(1-x)^3 (1+x)^2 (1+x^2)}=\\
&=(1-x^6-x^{12}-x^{16}+x^{18}+S(x)) \frac{1}{(1-x)^3 (1+x)^2 (1+x^2)}
\end{split}
\end{equation*}
Non è semplice calcolare l’enorme e orribile frazione: non possiamo semplicemente trovare la serie di ogni frazione e moltiplicarle insieme, perché è un complicato problema di partizione esso stesso (provate).
Per cui scomponiamo l’orribile frazione in frazioni parziali:
$\frac{1}{(1-x)^3 (1+x)^2 (1+x^2)}=\frac{Ax+B}{1+x^2}+\frac{C}{1+x}+\frac{D}{(1+x)^2}+\frac{E}{1-x}+\frac{F}{(1-x)^2}+\frac{G}{(1-x)^3}$
Facendo il minimo comune multiplo e risolvendo il sistema di equazioni in $A, B, C, D, E, F, G$ per ottenere un’identità, troviamo $$A=\frac{1}{8} \; \; B=\frac{1}{8} \; \; C=\frac{5}{32} \; \; D=\frac{1}{16} \; \; E=\frac{9}{32} \; \; F=\frac{1}{4} \; \; G=\frac{1}{8}$$
Ora ci serve conoscere le varie serie infinite per tutti le frazioni. Conosciamo già quelle per $\frac{1}{1+x}$, $\frac{1}{1-x}$, $\frac{1}{(1-x)^2}$ e $\frac{1}{(1-x)^3}$. La serie di $\frac{1}{(1+x)^2}$ si ottiene semplicemente sostituendo $-x$ ad $x$ nella serie di $\frac{1}{(1-x)^2}$, mentre per la serie di $\frac{1}{1+x^2}$ prima sostituiamo $t=x^2$ per ottenere la nuova frazione $\frac{1}{1+t}$, che sappiamo calcolare perché basta sostituire $-t$ nella serie nota di $\frac{1}{1-t}$. Quindi:
\begin{equation*}
\begin{split}
&\frac{1}{(1-x)^3 (1+x)^2 (1+x^2)}=\\
&=\frac{x+1}{8(1+x^2)}+\frac{5}{32(1+x)}+\frac{1}{16(1+x)^2}+\frac{9}{32(1-x)}+\frac{1}{4(1-x)^2}+\frac{1}{8(1-x)^3}=\\
&=\frac{x+1}{8} \sum_{k=0}^{\infty} (-1)^k x^{2k} + \frac{5}{32} \sum_{k=0}^{\infty} (-1)^k x^k + \frac{1}{16} \sum_{k=0}^{\infty} (-1)^k (k+1) x^k +\\
&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+ \frac{9}{32} \sum_{k=0}^{\infty} x^k + \frac{1}{4} \sum_{k=0}^{\infty} (k+1) x^k + \frac{1}{8} \sum_{k=0}^{\infty} \frac{(k+2)(k+1)}{2} x^k=\\
&=\frac{x+1}{8} \sum_{k=0}^{\infty} (-1)^k x^{2k} + \frac{1}{32} \sum_{k=0}^{\infty} x^k \left[ 5 (-1)^k + 2 (-1)^k (k+1) + 9 + 8(k+1) + \right. \\
&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left. + 2 (k+2)(k+1) \right]= \\
&=\frac{x+1}{8} \sum_{k=0}^{\infty} (-1)^k x^{2k} + \frac{1}{32} \sum_{k=0}^{\infty} x^k \left[9+5 (-1)^k + 2(k+1)((-1)^k + k+6)\right]=\\
\end{split}
\end{equation*}
(separando nelle parti di esponente pari e dispari)
\begin{equation*}
\begin{split}
&= \frac{1}{16}\sum_{k=0}^{\infty} x^{2k} \left[ 2(-1)^k + 7 + (2k+1)(2k+7) \right]+\\ &\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+ \frac{1}{8}\sum_{k=0}^{\infty} x^{2k+1} \left[ (-1)^k + 1 + 2(k+1)(k+3) \right]\\
\end{split}
\end{equation*}
dove $\sum_{k=0}^{\infty}$ è la somma immediatamente precedente. È sufficiente per quello che cerchiamo:
$$ p(x)= (1-x^6-x^{12}-x^{16}+x^{18}+S(x)) \sum_{k=0}^{\infty} (\cdots) $$
Nel polinomio finito abbiamo $1$, $x^6$, $x^{12}$, $x^{16}$ e $x^{18}$, e ci serve $x^{20}$: dobbiamo accoppiarli, rispettivamente, con $x^{20}$, $x^{14}$, $x^8$, $x^4$ e $x^2$ del polinomio infinito. Questi sono tutti pari, e li otteniamo dalla somma infinita pari rispettivamente per $k=10$, $k=7$, $k=4$, $k=2$ e $k=1$, e quindi valgono: $36, 20, 9, 4, 2$. Il numero che cerchiamo è quindi:
$$ 36-20-9-4+2=5$$
che è il numero corretto. Ciò si può verificare enumerando tutte le possibili combinazioni.