§ 2. Задача о числе наборов цифр с заданной суммой компонент

Если искомое количество обозначить через _m^s , то

_m^s = 0 при s > 9m и при s < 0,

_m⁰ = 1, _m¹ = m, _m² = ,

₁ⁱ = 1 (0  i  9), ₁ⁱ = 0 (i  10),

_m+1^s = _m^s + _m^s–1 + _m^s–2 + _m^s–3 + _m^s–4 + _m^s–5 + _m^s–6 + _m^s–7 + _m^s–8 + _m^s–9.

Последняя формула, справедливая при любом m  N, следует из того, что в любом наборе (a₁ ; a₂ ;… ; a_m+1) с суммой компонент s на первом месте стоит одна из цифр 0  a₁  9, а сумма компонент “хвоста” (a₂ ;… ; a_m+1) равна s – a₁ . Таким образом, .

Пусть (m-набор не может иметь сумму компонент, большую 9m). Ясно, что

g₁(x) = 1x⁰ + 1x¹ + … + 1x⁹ = 1 + x¹ + … + x⁹,

g₂(x) = 1x⁰ + 2x¹ + 3x² + 4x³ + 5x⁴ + 6x⁵ + 7x⁶ + 8x⁷ + 9x⁸ + 10x⁹ +

+ 9x¹⁰ + 8x¹¹ + 7x¹² + 6x¹³ + 5x¹⁴ + 4x¹⁵ + 3x¹⁶ + 2x¹⁷ + 1x¹⁸.

При вычислении g₂(x) учитывалось, что пары (a; b) с суммой s при 0  s  9 исчерпываются следующими: (0; s), (1; s–1), … , (s–1; 1), (s; 0) и их количество s + 1, а при 10  s  18 таковыми будут пары (s–9; 9), (s–10; 8), … , (8; s–10), (9; s–9) и их число |(s–9)–9| + 1 = |s–18| + 1 = 19–s.

Лемма (о связи g_m(x) и g₁(x)). g_m(x) = g₁(x)^m .

Доказательство. Индукция по m. База для m = 1 верна.

Пусть доказано, что g_m(x) = g₁(x)^m для m = 1, … , k  N. Докажем, что g_k+1(x) = g₁(x)^k+1 . По предположению индукции

g_k(x) = g₁(x)^k = g₀ + g₁x + … + g_9kx^9k .

Тогда g₁(x)^k+1 = (1 + x + x² + … + x⁹)(g₀ + g₁x + … + g_9kx^9k) =

= 1g₀ + (1g₁+1g₀)x + … + (1g_9k–1+1g_9k)x^9k+8 + 1g_9kx^9(k+1).

Здесь при xⁱ стоит сумма 1g_i + 1g_i–1 + … + 1g_i–9 в соответствии с формулой умножения многочленов, которая удобнее записывается для рядов в следующем виде: .

По смыслу g_i – это по предположению индукции количество k-наборов с суммой компонент i : g_i = _kⁱ. Как вычислить число _k+1^j всех (k+1)-на­боров с суммой компонент j ? Ответ даёт рекуррентная формула из начала параграфа:

_k+1^j = _k^j + _k^j–1 + _k^j–2 + _k^j–3 + _k^j–4 + _k^j–5 + _k^j–6 + _k^j–7 + _k^j–8 + _k^j–9,

совпадающая с приведённым выше правилом вычисления коэффициентов многочлена g₁^k+1. Значит, _k+1^j равно j-му коэффициенту многочлена g₁^k+1.

Лемма доказана.

Итак, нужно вычислить (1 + x + x² + … + x⁹)^m = =

= (1 – x¹⁰)^m(1 – x)^–m = =

Здесь использована формула (1 – y)^–k = , а также соглашение = 0 при p < 0, при q < 0, при q > p.

Итак, , т.е. _mⁱ – коэффициент при xⁱ в полученном разложении. Итак,

_m^s = .

В частности, ₆²⁷ = =

= =

= 7293132 – 18192122 + 9101112 = 201376 – 158004 + 11880 = 55252.