Задача о счастливых билетах — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метод производящей функции)
м (rollbackEdits.php mass rollback)
 
(не показано 16 промежуточных версий 3 участников)
Строка 15: Строка 15:
 
Действительно, однозначное число с суммой цифр <tex>k</tex> (для <tex>k=0,\ldots,9</tex>) можно представить одним способом. Для <tex>k>9</tex> — ноль способов. Заметим, что <tex>G^n(z)</tex> — производящая функция для чисел <tex>D_n^k</tex>, поскольку коэффициент при <tex>z^k</tex> получается перебором всех возможных комбинаций из <tex>n</tex> цифр, равных в сумме <tex>k</tex>. Ответом на задачу будет <tex>[z^{9n}]G^{2n}(z)</tex>. Перепишем производящую функцию в ином виде: <tex>
 
Действительно, однозначное число с суммой цифр <tex>k</tex> (для <tex>k=0,\ldots,9</tex>) можно представить одним способом. Для <tex>k>9</tex> — ноль способов. Заметим, что <tex>G^n(z)</tex> — производящая функция для чисел <tex>D_n^k</tex>, поскольку коэффициент при <tex>z^k</tex> получается перебором всех возможных комбинаций из <tex>n</tex> цифр, равных в сумме <tex>k</tex>. Ответом на задачу будет <tex>[z^{9n}]G^{2n}(z)</tex>. Перепишем производящую функцию в ином виде: <tex>
 
G(z) = 1+z+\ldots+z^9 = \dfrac{1-z^{10}}{1-z}
 
G(z) = 1+z+\ldots+z^9 = \dfrac{1-z^{10}}{1-z}
</tex> и получим, что <tex dpi="140">G^{2n}(z)=(1-z^{10})^{2n}(1-z)^{-2n}=\sum\limits_{k=0}^{2n}\binom{2n}{k}(-z^{10})^k\sum\limits_{j=0}^{\infty}\binom{-2n}{j}(-z)^j</tex>. Так как <tex dpi="140">\binom{-2n}{k}=(-1)^k\binom{2n+k-1}{k}</tex>, понятно, что <tex dpi="140">[z^{9n}]G^{2n}(z)=\sum\limits_{j=0}^{\lfloor{\frac{9n}{10}}\rfloor}(-1)^j\binom{2n}{j}\binom{11n-10j-1}{9n-10j}</tex>, что при <tex>n=3</tex> дает <tex dpi="140">\binom{6}{0}\binom{32}{27}-\binom{6}{1}\binom{22}{17}+\binom{6}{2}\binom{12}{7}=55252</tex>.
+
</tex> и получим, что <tex>G^{2n}(z)=(1-z^{10})^{2n}(1-z)^{-2n}=\displaystyle\sum\limits_{k=0}^{2n}\binom{2n}{k}(-z^{10})^k</tex><tex>\Big(\sum\limits_{j=0}^{\infty}\binom{-2n}{j}(-z)^j\Big)</tex>. Так как <tex>\dbinom{-2n}{k}=(-1)^k\dbinom{2n+k-1}{k}</tex>, понятно, что <tex>[z^{9n}]G^{2n}(z)=\displaystyle\sum\limits_{j=0}^{\lfloor{\frac{9n}{10}}\rfloor}(-1)^j\binom{2n}{j}\binom{11n-10j-1}{9n-10j}</tex>, что при <tex>n=3</tex> дает <tex>\dbinom{6}{0}\dbinom{32}{27}-\dbinom{6}{1}\dbinom{22}{17}+\dbinom{6}{2}\dbinom{12}{7}=55252</tex>.
  
 
== Решение с помощью [[Формула включения-исключения | формулы включения-исключения]]==
 
== Решение с помощью [[Формула включения-исключения | формулы включения-исключения]]==
Как мы заметили раньше, ответ на задачу равен количеству шестизначных билетов с суммой <tex>27</tex>. Рассмотрим расстановки целых неотрицательных чисел на шести позициях, дающих в сумме <tex>27</tex>; обозначим их множество <tex>A</tex>. Выделим шесть его подмножеств <tex>C_i, i = 1 \ldots 6</tex>, где <tex>i</tex>-е множество состоит из расстановок, у которых в <tex>i</tex>-й позиции стоит число, не меньшее <tex>10</tex>. Число счастливых билетов равно числу расстановок, не принадлежащих ни одному из множеств. Расстановке <tex>(a_1,a_2 \ldots a_n)</tex> из <tex>n</tex> чисел с суммой <tex>k</tex> сопоставим сочетание с повторениями <ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5#.D0.A1.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D1.8F_.D1.81_.D0.BF.D0.BE.D0.B2.D1.82.D0.BE.D1.80.D0.B5.D0.BD.D0.B8.D1.8F.D0.BC.D0.B8 Сочетание — Википедия]</ref> из <tex>n</tex> по <tex>k</tex>, в котором <tex>i</tex>-й элемент повторяется <tex>a_i</tex> раз. Так как это сопоставление взаимно-однозначно, количество расстановок равно количеству сочетаний с повторениями, т.е. <tex dpi="140">\binom{n+k-1}{n-1}</tex>. Число <tex>\left\vert{A}\right\vert</tex> всех расстановок неотрицательных целых чисел с суммой <tex>27</tex> в шесть позиций равно <tex dpi="140">\binom{32}{5}</tex>. Число расстановок <tex>\left\vert{C_i}\right\vert</tex> одинаково для всех <tex>i</tex> и равно <tex dpi="140">\binom{22}{5}</tex>. В самом деле, мы можем поставить в <tex>i</tex>-ю позицию число <tex>10</tex>, а оставшуюся сумму <tex>17</tex> произвольно распределить по шести позициям. Аналогично, число расстановок <tex>\left\vert{C_i \cap C_j}\right\vert</tex> одинаково для любой пары <tex>i, j, i \neq j</tex> и равно <tex dpi="140">\binom{12}{5}</tex>: мы выбираем две позиции и ставим в них <tex>10</tex> и произвольно распределяем оставшуюся сумму <tex>7</tex> по шести позициям. Таким образом, искомое количество расстановок равно <tex dpi="140">\left\vert{A}\right\vert - \binom{6}{1}\left\vert{C_i}\right\vert+\binom{6}{2}\left\vert{C_i \cap  C_j}\right\vert = \binom{32}{5}-6\binom{22}{5}+15\binom{12}{5} = 55252</tex>.
+
Как мы заметили раньше, ответ на задачу равен количеству шестизначных билетов с суммой <tex>27</tex>. Рассмотрим расстановки целых неотрицательных чисел на шести позициях, дающих в сумме <tex>27</tex>; обозначим их множество <tex>A</tex>. Выделим шесть его подмножеств <tex>C_i, i = 1 \ldots 6</tex>, где <tex>i</tex>-е множество состоит из расстановок, у которых в <tex>i</tex>-й позиции стоит число, не меньшее <tex>10</tex>. Число счастливых билетов равно числу расстановок, не принадлежащих ни одному из множеств. Расстановке <tex>(a_1,a_2 \ldots a_n)</tex> из <tex>n</tex> чисел с суммой <tex>k</tex> сопоставим сочетание с повторениями <ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5#.D0.A1.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D1.8F_.D1.81_.D0.BF.D0.BE.D0.B2.D1.82.D0.BE.D1.80.D0.B5.D0.BD.D0.B8.D1.8F.D0.BC.D0.B8 Сочетание — Википедия]</ref> из <tex>n</tex> по <tex>k</tex>, в котором <tex>i</tex>-й элемент повторяется <tex>a_i</tex> раз. Так как это сопоставление взаимно-однозначно, количество расстановок равно количеству сочетаний с повторениями, т.е. <tex>\dbinom{n+k-1}{n-1}</tex>. Число <tex>\left\vert{A}\right\vert</tex> всех расстановок неотрицательных целых чисел с суммой <tex>27</tex> в шесть позиций равно <tex>\dbinom{32}{5}</tex>. Число расстановок <tex>\left\vert{C_i}\right\vert</tex> одинаково для всех <tex>i</tex> и равно <tex>\dbinom{22}{5}</tex>. В самом деле, мы можем поставить в <tex>i</tex>-ю позицию число <tex>10</tex>, а оставшуюся сумму <tex>17</tex> произвольно распределить по шести позициям. Аналогично, число расстановок <tex>\left\vert{C_i \cap C_j}\right\vert</tex> одинаково для любой пары <tex>i, j, i \neq j</tex> и равно <tex>\dbinom{12}{5}</tex>: мы выбираем две позиции и ставим в них <tex>10</tex> и произвольно распределяем оставшуюся сумму <tex>7</tex> по шести позициям. Таким образом, искомое количество расстановок равно <tex>\left\vert{A}\right\vert - \dbinom{6}{1}\left\vert{C_i}\right\vert+\dbinom{6}{2}\left\vert{C_i \cap  C_j}\right\vert = \dbinom{32}{5}-6\dbinom{22}{5}+15\dbinom{12}{5} = 55252</tex>.
  
 
== Решение путем интегрирования ==
 
== Решение путем интегрирования ==
Рассмотрим многочлен Лорана (т.е. многочлен, в котором допускаются отрицательные степени) <tex>H(z)=G^3(z)G^3(1/z)</tex>. Заметим, что его свободный член равен <tex>\sum\limits_{i=0}^{27}[z^i]G^3(z)\cdot [z^{-i}]G^3(z^{-1})=\sum\limits_{i=0}^{27}(D_3^i)^2</tex>. Воспользуемся теоремой Коши <ref>[https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D0%B3%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%9A%D0%BE%D1%88%D0%B8 Интегральная формула Коши — Википедия]
+
Рассмотрим многочлен Лорана (т.е. многочлен, в котором допускаются отрицательные степени) <tex>H(z)=G^3(z)G^3(1/z)</tex>. Заметим, что его свободный член равен <tex>\displaystyle\sum\limits_{i=0}^{27}[z^i]G^3(z)\cdot [z^{-i}]G^3(z^{-1})=\sum\limits_{i=0}^{27}(D_3^i)^2</tex>. Воспользуемся теоремой Коши <ref>[https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D0%B3%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%9A%D0%BE%D1%88%D0%B8 Интегральная формула Коши — Википедия]
 
</ref> из комплексного анализа:
 
</ref> из комплексного анализа:
 
{{Теорема
 
{{Теорема
Строка 31: Строка 31:
 
Упростим многочлен <tex>H(z)</tex>:
 
Упростим многочлен <tex>H(z)</tex>:
 
: <tex>H(z)=\left( \dfrac{1-z^{10}}{1-z} \right) ^3\left(\dfrac{1-z^{-10}}{1-z^{-1}}\right)^3=\left(\dfrac{2-z^{10}-z^{-10}}{2-z-z^{-1}}\right)^3</tex> и применим замену <tex>z=e^{i\phi}</tex>:
 
: <tex>H(z)=\left( \dfrac{1-z^{10}}{1-z} \right) ^3\left(\dfrac{1-z^{-10}}{1-z^{-1}}\right)^3=\left(\dfrac{2-z^{10}-z^{-10}}{2-z-z^{-1}}\right)^3</tex> и применим замену <tex>z=e^{i\phi}</tex>:
: <tex>p_0=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}\left(\dfrac{2-e^{10i\phi}-e^{-10i\phi}}{2-e^{i\phi}-e^{-i\phi}}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}\left(\dfrac{2-2\cos(10\phi)}{2-2cos\phi}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int_{0}^{2\pi}\left(\dfrac{\sin^2(5\phi)}{\sin^2(\frac{\phi}{2})}\right)^3d\phi=\dfrac{1}{\pi}\displaystyle\int_0^{\pi}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi=\dfrac{1}{\pi}\displaystyle\int_{-\pi/2}^{\pi/2}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi</tex>
+
: <tex>p_0=\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}\left(\dfrac{2-e^{10i\phi}-e^{-10i\phi}}{2-e^{i\phi}-e^{-i\phi}}\right)^3d\phi</tex>
 +
: <tex>\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}\left(\dfrac{2-e^{10i\phi}-e^{-10i\phi}}{2-e^{i\phi}-e^{-i\phi}}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}\left(\dfrac{2-2\cos(10\phi)}{2-2cos\phi}\right)^3d\phi</tex>
 +
: <tex>\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}\left(\dfrac{2-2\cos(10\phi)}{2-2cos\phi}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int\limits_{0}^{2\pi}\left(\dfrac{\sin^2(5\phi)}{\sin^2(\frac{\phi}{2})}\right)^3d\phi</tex>
 +
: <tex>\dfrac{1}{2\pi}\displaystyle\int\limits_{0}^{2\pi}\left(\dfrac{\sin^2(5\phi)}{\sin^2(\frac{\phi}{2})}\right)^3d\phi=\dfrac{1}{\pi}\displaystyle\int\limits_0^{\pi}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi</tex>
 +
: <tex>\dfrac{1}{\pi}\displaystyle\int\limits_0^{\pi}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi=\dfrac{1}{\pi}\displaystyle\int\limits_{-\pi/2}^{\pi/2}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi</tex>
  
 
Рассмотрим функцию <tex>f(\phi)=\dfrac{\sin(10\phi)}{\sin\phi}</tex> на <tex>\left[-\dfrac{\pi}{2},\dfrac{\pi}{2}\right]</tex>. Вне отрезка <tex>\left[\dfrac{-\pi}{10},\dfrac{\pi}{10}\right]
 
Рассмотрим функцию <tex>f(\phi)=\dfrac{\sin(10\phi)}{\sin\phi}</tex> на <tex>\left[-\dfrac{\pi}{2},\dfrac{\pi}{2}\right]</tex>. Вне отрезка <tex>\left[\dfrac{-\pi}{10},\dfrac{\pi}{10}\right]
 
  f(\phi) \leqslant \dfrac{1}{\sin\frac{\pi}{10}}\approx 3</tex>, значит интеграл по этой части не больше <tex>3^6\pi \approx 2300</tex>, основная часть сосредоточена на <tex>\left[-\dfrac{\pi}{10},\dfrac{\pi}{10}\right]</tex>. Оценим интеграл по этому промежутку с помощью метода стационарной фазы.  <ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%81%D1%82%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B9_%D1%84%D0%B0%D0%B7%D1%8B Метод стационарной фазы — Википедия]</ref> Этот метод позволяет оценить значение интеграла
 
  f(\phi) \leqslant \dfrac{1}{\sin\frac{\pi}{10}}\approx 3</tex>, значит интеграл по этой части не больше <tex>3^6\pi \approx 2300</tex>, основная часть сосредоточена на <tex>\left[-\dfrac{\pi}{10},\dfrac{\pi}{10}\right]</tex>. Оценим интеграл по этому промежутку с помощью метода стационарной фазы.  <ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%81%D1%82%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B9_%D1%84%D0%B0%D0%B7%D1%8B Метод стационарной фазы — Википедия]</ref> Этот метод позволяет оценить значение интеграла
: <tex>\displaystyle\int_{-\pi/10}^{\pi/10}f^td\phi=\displaystyle\int_{-\pi/10}^{\pi/10}e^{t\ln{f}}d\phi</tex>. При <tex>t \rightarrow \infty</tex> значение интеграла определяется поведением его фазы, т.е. <tex>\ln{f}</tex>, в окрестности стационарной точки <tex>0</tex> (точки, где <tex>(\ln{f})'=0</tex>, или, что то же самое, <tex>f'=0</tex>). Вблизи <tex>0</tex> <tex>f(\phi) \approx 10 \left(1 - \dfrac{33}{2}\phi^2\right)</tex>, а <tex>\ln{f}(\phi) \approx \ln 10 - \dfrac{33}{2}\phi^2</tex>. При больших <tex>t </tex> получим
+
: <tex>\displaystyle\int\limits_{-\pi/10}^{\pi/10}f^td\phi=\displaystyle\int\limits_{-\pi/10}^{\pi/10}e^{t\ln{f}}d\phi</tex>. При <tex>t \rightarrow \infty</tex> значение интеграла определяется поведением его фазы, т.е. <tex>\ln{f}</tex>, в окрестности стационарной точки <tex>0</tex> (точки, где <tex>(\ln{f})'=0</tex>, или, что то же самое, <tex>f'=0</tex>). Вблизи <tex>0</tex> <tex>f(\phi) \approx 10 \left(1 - \dfrac{33}{2}\phi^2\right)</tex>, а <tex>\ln{f}(\phi) \approx \ln 10 - \dfrac{33}{2}\phi^2</tex>. При больших <tex>t </tex> получим
: <tex>{\displaystyle\int_{-\pi/10}^{\pi/10}\exp(t(\ln 10 - \frac{33}{2}\phi^2))d\phi=10^t \int_{-\pi/10}^{\pi/10}\exp(-\frac{33}{2}\phi^2)d\phi=\sqrt{\dfrac{\pi}{66t}} \cdot \mathrm{erf}\left(\sqrt{\dfrac{33t}{2}\phi}\right)\bigg\rvert_{-\pi/10}^{\pi/10}}</tex>, где <tex>\mathrm{erf}(z)</tex> {{---}} функция ошибок <ref>[http://mathworld.wolfram.com/Erf.html Erf -- from Wolfram MathWorld]</ref>. Заметим, что при <tex>z > 2 </tex> <tex>\mathrm{erf}(z) \approx 1</tex>, поэтому интеграл примерно равен <tex>10^t \sqrt{\dfrac{2\pi}{33t}}</tex>.
+
: <tex>{\displaystyle\int\limits_{-\pi/10}^{\pi/10}\exp(t(\ln 10 - \frac{33}{2}\phi^2))d\phi=10^t \int\limits_{-\pi/10}^{\pi/10}\exp(-\frac{33}{2}\phi^2)d\phi=\sqrt{\dfrac{\pi}{66t}} \cdot \mathrm{erf}\left(\sqrt{\dfrac{33t}{2}\phi}\right)\bigg\rvert_{-\pi/10}^{\pi/10}}</tex>, где <tex>\mathrm{erf}(z)</tex> {{---}} функция ошибок <ref>[http://mathworld.wolfram.com/Erf.html Erf -- from Wolfram MathWorld]</ref>. Заметим, что при <tex>z > 2 </tex> <tex>\mathrm{erf}(z) \approx 1</tex>, поэтому интеграл примерно равен <tex>10^t \sqrt{\dfrac{2\pi}{33t}}</tex>.
 
Полагая <tex>t=6</tex> и вспоминая выражение для <tex>p_0</tex>, получаем приближенное равенство:
 
Полагая <tex>t=6</tex> и вспоминая выражение для <tex>p_0</tex>, получаем приближенное равенство:
 
: <tex>p_0 \approx \dfrac{10^6}{3\sqrt{11\pi}} \approx 56700</tex>
 
: <tex>p_0 \approx \dfrac{10^6}{3\sqrt{11\pi}} \approx 56700</tex>
 
Этот результат с хорошей точностью (отклонение составляет не более <tex>3\%</tex>) приближает искомое значение.
 
Этот результат с хорошей точностью (отклонение составляет не более <tex>3\%</tex>) приближает искомое значение.
 +
 
== Способ с конечной суммой ==  
 
== Способ с конечной суммой ==  
Рассмотрим функцию <tex>g(\phi)=H(e^{i\phi})=\left(\dfrac{\sin{5\phi}}{\sin{\frac{\pi}{2}}}\right)^6</tex>. Как доказано выше, <tex>L_6=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}g(\phi)d\phi</tex>. Для интеграла можно выписать приближенную формулу и получить <tex>L_6 \approx \dfrac{1}{N}\sum\limits_{k=0}^{N-1}g(\dfrac{2\pi k}{N})</tex>. Интересно, что при достаточно большом <tex>N</tex> это равенство становится точным.
+
Рассмотрим функцию <tex>g(\phi)=H(e^{i\phi})=\left(\dfrac{\sin{5\phi}}{\sin{\frac{\pi}{2}}}\right)^6</tex>. Как доказано выше, <tex>L_6=\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}g(\phi)d\phi</tex>. Для интеграла можно выписать приближенную формулу и получить <tex>L_6 \approx \displaystyle\dfrac{1}{N}\sum\limits_{k=0}^{N-1}g\Big(\dfrac{2\pi k}{N}\Big)</tex>. Интересно, что при достаточно большом <tex>N</tex> это равенство становится точным.
 
{{Утверждение
 
{{Утверждение
 
|statement=При <tex>N \geqslant 28</tex> и любом <tex>\phi_0</tex> <tex>L_6 = \dfrac{1}{N}\sum\limits_{k=0}^{N-1}g(\phi_k)</tex>, где <tex>\phi_k=\phi_0+\dfrac{2\pi k}{N}, k > 0</tex>.
 
|statement=При <tex>N \geqslant 28</tex> и любом <tex>\phi_0</tex> <tex>L_6 = \dfrac{1}{N}\sum\limits_{k=0}^{N-1}g(\phi_k)</tex>, где <tex>\phi_k=\phi_0+\dfrac{2\pi k}{N}, k > 0</tex>.

Текущая версия на 19:15, 4 сентября 2022

Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, [math]024321[/math]. Известно, что количество счастливых билетов из шести цифр равно [math]55252[/math].

Задача:
Для натурального [math]n[/math] найти количество [math]2n[/math]-значных счастливых билетов [math]L_n[/math].

Общие идеи

Обозначим количество [math]n[/math]-значных чисел с суммой [math]k[/math] как [math]D_n^k[/math] (число может содержать ведущие нули). [math]2n[/math]-значный счастливый билет состоит из двух частей: левой ([math]n[/math] цифр) и правой (тоже [math]n[/math] цифр), причём в обеих частях сумма цифр одинакова. Зафиксируем [math]x[/math][math]n[/math]-значное число с суммой [math]k[/math] в левой части (всего таких чисел [math]D_n^k[/math], значит это можно сделать [math]D_n^k[/math] способами). Для него будет существовать [math]D_n^k[/math] возможных вариантов числа в правой части, следовательно количество счастливых билетов с суммой [math]k[/math] в одной из частей равно [math](D_n^k)^2[/math]. Значит общее число билетов равно [math]L_n = \sum\limits_{k=0}^{9n} (D_{n}^{k})^2[/math]. Верхний индекс суммирования равен [math]9n[/math], так как максимальная сумма цифр в одной части билета равна [math]9n[/math]. Также можно сопоставить счастливому билету [math]a_1a_2\ldots a_n b_1b_2 \ldots b_n[/math] [math]2n[/math]-значное число с суммой [math]9n[/math]: [math]a_1a_2\ldots a_n (9-b_1)(9-b_2) \ldots (9-b_n)[/math], причем это соответствие взаимно-однозначно, значит множества счастливых билетов и [math]2n[/math]-значных чисел с суммой [math]9n[/math] равномощны, поэтому [math]L_n=D_{2n}^{9n}[/math].

Метод динамического программирования

Научимся вычислять [math]D_n^k[/math]. Положим [math]D_0^k=\begin{cases}1,&k=0\\0,&k\gt 0\end{cases}[/math]. При [math]n\gt 0[/math] количество [math]n[/math]-значных чисел с суммой цифр [math]k[/math] можно выразить через количество [math](n-1)[/math]-значных чисел, добавляя к ним [math]n[/math]-ю цифру, которая может быть равна [math]0, 1, \ldots, 9[/math]: [math]D_n^k=\sum\limits_{j=0}^{9}D_{n-1}^{k-j}[/math]. Ответ — в [math]D_{2n}^{9n}[/math], алгоритм будет работать за [math]O(n^2)[/math].

Метод производящей функции

Выпишем производящую функцию [math]G(z)[/math], коэффициент при [math]z^k[/math] у которой будет равен [math]D_1^k[/math]: [math] G(z) = 1+z+z^2+z^3+z^4+z^5+z^6+z^7+z^8+z^9.[/math] Действительно, однозначное число с суммой цифр [math]k[/math] (для [math]k=0,\ldots,9[/math]) можно представить одним способом. Для [math]k\gt 9[/math] — ноль способов. Заметим, что [math]G^n(z)[/math] — производящая функция для чисел [math]D_n^k[/math], поскольку коэффициент при [math]z^k[/math] получается перебором всех возможных комбинаций из [math]n[/math] цифр, равных в сумме [math]k[/math]. Ответом на задачу будет [math][z^{9n}]G^{2n}(z)[/math]. Перепишем производящую функцию в ином виде: [math] G(z) = 1+z+\ldots+z^9 = \dfrac{1-z^{10}}{1-z} [/math] и получим, что [math]G^{2n}(z)=(1-z^{10})^{2n}(1-z)^{-2n}=\displaystyle\sum\limits_{k=0}^{2n}\binom{2n}{k}(-z^{10})^k[/math][math]\Big(\sum\limits_{j=0}^{\infty}\binom{-2n}{j}(-z)^j\Big)[/math]. Так как [math]\dbinom{-2n}{k}=(-1)^k\dbinom{2n+k-1}{k}[/math], понятно, что [math][z^{9n}]G^{2n}(z)=\displaystyle\sum\limits_{j=0}^{\lfloor{\frac{9n}{10}}\rfloor}(-1)^j\binom{2n}{j}\binom{11n-10j-1}{9n-10j}[/math], что при [math]n=3[/math] дает [math]\dbinom{6}{0}\dbinom{32}{27}-\dbinom{6}{1}\dbinom{22}{17}+\dbinom{6}{2}\dbinom{12}{7}=55252[/math].

Решение с помощью формулы включения-исключения

Как мы заметили раньше, ответ на задачу равен количеству шестизначных билетов с суммой [math]27[/math]. Рассмотрим расстановки целых неотрицательных чисел на шести позициях, дающих в сумме [math]27[/math]; обозначим их множество [math]A[/math]. Выделим шесть его подмножеств [math]C_i, i = 1 \ldots 6[/math], где [math]i[/math]-е множество состоит из расстановок, у которых в [math]i[/math]-й позиции стоит число, не меньшее [math]10[/math]. Число счастливых билетов равно числу расстановок, не принадлежащих ни одному из множеств. Расстановке [math](a_1,a_2 \ldots a_n)[/math] из [math]n[/math] чисел с суммой [math]k[/math] сопоставим сочетание с повторениями [1] из [math]n[/math] по [math]k[/math], в котором [math]i[/math]-й элемент повторяется [math]a_i[/math] раз. Так как это сопоставление взаимно-однозначно, количество расстановок равно количеству сочетаний с повторениями, т.е. [math]\dbinom{n+k-1}{n-1}[/math]. Число [math]\left\vert{A}\right\vert[/math] всех расстановок неотрицательных целых чисел с суммой [math]27[/math] в шесть позиций равно [math]\dbinom{32}{5}[/math]. Число расстановок [math]\left\vert{C_i}\right\vert[/math] одинаково для всех [math]i[/math] и равно [math]\dbinom{22}{5}[/math]. В самом деле, мы можем поставить в [math]i[/math]-ю позицию число [math]10[/math], а оставшуюся сумму [math]17[/math] произвольно распределить по шести позициям. Аналогично, число расстановок [math]\left\vert{C_i \cap C_j}\right\vert[/math] одинаково для любой пары [math]i, j, i \neq j[/math] и равно [math]\dbinom{12}{5}[/math]: мы выбираем две позиции и ставим в них [math]10[/math] и произвольно распределяем оставшуюся сумму [math]7[/math] по шести позициям. Таким образом, искомое количество расстановок равно [math]\left\vert{A}\right\vert - \dbinom{6}{1}\left\vert{C_i}\right\vert+\dbinom{6}{2}\left\vert{C_i \cap C_j}\right\vert = \dbinom{32}{5}-6\dbinom{22}{5}+15\dbinom{12}{5} = 55252[/math].

Решение путем интегрирования

Рассмотрим многочлен Лорана (т.е. многочлен, в котором допускаются отрицательные степени) [math]H(z)=G^3(z)G^3(1/z)[/math]. Заметим, что его свободный член равен [math]\displaystyle\sum\limits_{i=0}^{27}[z^i]G^3(z)\cdot [z^{-i}]G^3(z^{-1})=\sum\limits_{i=0}^{27}(D_3^i)^2[/math]. Воспользуемся теоремой Коши [2] из комплексного анализа:

Теорема (Коши):
Для любого многочлена Лорана [math]p(z)[/math] его свободный член [math]p_0[/math] равен
[math]p_0=\dfrac{1}{2\pi i}{\displaystyle \int} \dfrac{p(z)}{z} dz[/math], где интегрирование происходит по любой окружности, ориентированной против часовой стрелки и содержащей внутри себя начало координат.

Упростим многочлен [math]H(z)[/math]:

[math]H(z)=\left( \dfrac{1-z^{10}}{1-z} \right) ^3\left(\dfrac{1-z^{-10}}{1-z^{-1}}\right)^3=\left(\dfrac{2-z^{10}-z^{-10}}{2-z-z^{-1}}\right)^3[/math] и применим замену [math]z=e^{i\phi}[/math]:
[math]p_0=\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}\left(\dfrac{2-e^{10i\phi}-e^{-10i\phi}}{2-e^{i\phi}-e^{-i\phi}}\right)^3d\phi[/math]
[math]\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}\left(\dfrac{2-e^{10i\phi}-e^{-10i\phi}}{2-e^{i\phi}-e^{-i\phi}}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}\left(\dfrac{2-2\cos(10\phi)}{2-2cos\phi}\right)^3d\phi[/math]
[math]\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}\left(\dfrac{2-2\cos(10\phi)}{2-2cos\phi}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int\limits_{0}^{2\pi}\left(\dfrac{\sin^2(5\phi)}{\sin^2(\frac{\phi}{2})}\right)^3d\phi[/math]
[math]\dfrac{1}{2\pi}\displaystyle\int\limits_{0}^{2\pi}\left(\dfrac{\sin^2(5\phi)}{\sin^2(\frac{\phi}{2})}\right)^3d\phi=\dfrac{1}{\pi}\displaystyle\int\limits_0^{\pi}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi[/math]
[math]\dfrac{1}{\pi}\displaystyle\int\limits_0^{\pi}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi=\dfrac{1}{\pi}\displaystyle\int\limits_{-\pi/2}^{\pi/2}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi[/math]

Рассмотрим функцию [math]f(\phi)=\dfrac{\sin(10\phi)}{\sin\phi}[/math] на [math]\left[-\dfrac{\pi}{2},\dfrac{\pi}{2}\right][/math]. Вне отрезка [math]\left[\dfrac{-\pi}{10},\dfrac{\pi}{10}\right] f(\phi) \leqslant \dfrac{1}{\sin\frac{\pi}{10}}\approx 3[/math], значит интеграл по этой части не больше [math]3^6\pi \approx 2300[/math], основная часть сосредоточена на [math]\left[-\dfrac{\pi}{10},\dfrac{\pi}{10}\right][/math]. Оценим интеграл по этому промежутку с помощью метода стационарной фазы. [3] Этот метод позволяет оценить значение интеграла

[math]\displaystyle\int\limits_{-\pi/10}^{\pi/10}f^td\phi=\displaystyle\int\limits_{-\pi/10}^{\pi/10}e^{t\ln{f}}d\phi[/math]. При [math]t \rightarrow \infty[/math] значение интеграла определяется поведением его фазы, т.е. [math]\ln{f}[/math], в окрестности стационарной точки [math]0[/math] (точки, где [math](\ln{f})'=0[/math], или, что то же самое, [math]f'=0[/math]). Вблизи [math]0[/math] [math]f(\phi) \approx 10 \left(1 - \dfrac{33}{2}\phi^2\right)[/math], а [math]\ln{f}(\phi) \approx \ln 10 - \dfrac{33}{2}\phi^2[/math]. При больших [math]t [/math] получим
[math]{\displaystyle\int\limits_{-\pi/10}^{\pi/10}\exp(t(\ln 10 - \frac{33}{2}\phi^2))d\phi=10^t \int\limits_{-\pi/10}^{\pi/10}\exp(-\frac{33}{2}\phi^2)d\phi=\sqrt{\dfrac{\pi}{66t}} \cdot \mathrm{erf}\left(\sqrt{\dfrac{33t}{2}\phi}\right)\bigg\rvert_{-\pi/10}^{\pi/10}}[/math], где [math]\mathrm{erf}(z)[/math] — функция ошибок [4]. Заметим, что при [math]z \gt 2 [/math] [math]\mathrm{erf}(z) \approx 1[/math], поэтому интеграл примерно равен [math]10^t \sqrt{\dfrac{2\pi}{33t}}[/math].

Полагая [math]t=6[/math] и вспоминая выражение для [math]p_0[/math], получаем приближенное равенство:

[math]p_0 \approx \dfrac{10^6}{3\sqrt{11\pi}} \approx 56700[/math]

Этот результат с хорошей точностью (отклонение составляет не более [math]3\%[/math]) приближает искомое значение.

Способ с конечной суммой

Рассмотрим функцию [math]g(\phi)=H(e^{i\phi})=\left(\dfrac{\sin{5\phi}}{\sin{\frac{\pi}{2}}}\right)^6[/math]. Как доказано выше, [math]L_6=\dfrac{1}{2\pi}\displaystyle\int\limits_0^{2\pi}g(\phi)d\phi[/math]. Для интеграла можно выписать приближенную формулу и получить [math]L_6 \approx \displaystyle\dfrac{1}{N}\sum\limits_{k=0}^{N-1}g\Big(\dfrac{2\pi k}{N}\Big)[/math]. Интересно, что при достаточно большом [math]N[/math] это равенство становится точным.

Утверждение:
При [math]N \geqslant 28[/math] и любом [math]\phi_0[/math] [math]L_6 = \dfrac{1}{N}\sum\limits_{k=0}^{N-1}g(\phi_k)[/math], где [math]\phi_k=\phi_0+\dfrac{2\pi k}{N}, k \gt 0[/math].
[math]\triangleright[/math]

По определению, [math]g(\phi)=\sum\limits_{j=-27}^{27}a_je^{ij\phi}[/math], где [math]a_j[/math] — коэффициенты многочлена [math]H(z)[/math]. Обозначим [math]r(\phi)=\sum\limits_{j=1}^{27}a_j(e^{ij\phi}+e^{-ij\phi}), g(\phi)=a_0+r(\phi)[/math]. Докажем, что [math]\sum\limits_{k=0}^{N-1}g(\phi_k)=0[/math]. Раскроем [math]g(\phi_k)[/math]:

[math]{\displaystyle\sum\limits_{k=0}^{N-1}\sum\limits_{j=1}^{27}a_j\left(\exp\left(ij\left(\phi_0+\dfrac{2\pi k}{N}\right)\right) + \exp\left(-ij\left(\phi_0+\dfrac{2\pi k}{N}\right)\right)\right)= e^{ij\phi_0}\sum\limits_{j=1}^{27}a_j\sum\limits_{k=0}^{N-1}\left(\exp\left(ij\dfrac{2\pi k}{N}\right) + \exp\left(-ij\dfrac{2\pi k}{N}\right)\right)}[/math].

Рассмотрим внутреннюю сумму:

[math]{\displaystyle\sum\limits_{k=0}^{N-1}\left(\exp\left(\dfrac{2ijk\pi}{N}\right)+\exp\left(-\dfrac{2ijk\pi}{N}\right)\right)=\sum\limits_{k=0}^{N-1}\exp\left(\dfrac{2ijk\pi}{N}\right)+\sum\limits_{k=0}^{N-1}\exp\left(-\dfrac{2ijk\pi}{N}\right)}[/math]. Получили две геометрические прогрессии со знаменателями, не равными [math]1[/math]: [math]N\gt j \implies \exp\left(\dfrac{2ij\pi}{N}\right)\neq 1, \exp\left(-\dfrac{2ij\pi}{N}\right)\neq 1[/math]. Значит искомая сумма равна
[math]\dfrac{1-\exp\left(2ij\pi\right)}{1-\exp\left(\dfrac{2ij\pi}{N}\right)}+\dfrac{1-\exp\left(-2ij\pi\right)}{1-\exp\left(-\dfrac{2ij\pi}{N}\right)}=0[/math], так как [math]e^{2\pi i}=1[/math].

Таким образом, [math]\dfrac{1}{N}\sum\limits_{k=0}^{N-1}g\left(\phi_k\right)=\dfrac{1}{N}\sum\limits_{k=0}^{N-1}\left(a_0+g\left(\phi_k\right)\right)=a_0[/math],

а свободный член [math]H\left(z\right)[/math] равен [math]L_6[/math], как известно из предыдущего раздела.
[math]\triangleleft[/math]

См. также

Примечания

Источники информации

  • Ландо С. К., Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144с. ISBN 978-5-94057-042-4