Como construir a recorrência que conta o número de sequências ordenadas que somam n usando apenas partes de tamanhos dados?

Resposta:

Para um conjunto de tamanhos S, \(a_0=1\) e para \(n\ge1\):
\(a_n=\displaystyle\sum_{\substack{s\in S\\ s\le n}} a_{n-s}.\)

Exemplo: Seja S = {1,3,4} e queira-se contar composições de \(n=5\).
Recorrência: \(a_n=a_{n-1}+a_{n-3}+a_{n-4},\; a_0=1.\)
Calculemos:
\(a_1=a_0=1\)
\(a_2=a_1=1\)
\(a_3=a_2+a_0=1+1=2\)
\(a_4=a_3+a_1+a_0=2+1+1=4\)
\(a_5=a_4+a_2+a_1=4+1+1=6\).
Assim, há 6 sequências ordenadas de soma 5 com partes em {1,3,4}.