Пару вопросов по комбинаторкие

[Miktor]

Подскажите. Есть 2 задачи.

1. Сколько существует 8-разрядных десятичных чисел, в каждом из ко-
торых цифра 1 встречается ровно 5 раз? (Числа могут начинаться с нуля.)

2. Найти $a_{n}, если $a_{0} = 0, a_{1} = 1, a_{2} = 1$ и $a_{n+3} + 10a_{n+2} + 32a_{n+1} + 32a_{n} = 0.$

Если первую я представляю как решить, нужно сосчитать количество размещений 5-и едениц:
$A^5_8=\frac{8!}{3!}$
и это умножить на количество остальных чисел у которых единицы стоят на этих местах:
$9^3$ потому что единиц там не должно быть.
А вот как решить 2 задачу, пробовал выражать $a_{n} через данную формулу но там получаются слишком большие цифры, да и это же комбинаторика, а не математика.

[GAA]

К задаче № 2. Краткие теоретические сведения приведены в книге Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы (см. §7 «Уравнения в конечных разностях», гл.II «Интерполяция и численное интегрирование» в издании 1987) (poiskknig.ru). (В этой книге решение ищется аналогично тому, как это делается в случае линейного дифференциального уравнения с постоянными коэффициентами.)

[Zealint]

Решение первой задачи неправильное. Нужно $9^3$ умножать на число сочетаний, а не размещений. Так как единицы друг от друга никак не отличаются.

Решение второй задачи - это вывод явной формулы для последовательности, заданной рекуррентным соотношением. Как решать такие задачи написано здесь.

[arseniiv]

Miktor в сообщении #368024 писал(а):

А вот как решить 2 задачу, пробовал выражать $a_{n}$ через данную формулу но там получаются слишком большие цифры, да и это же комбинаторика, а не математика.

По секрету вам скажу: комбинаторика — это весьма нечёткое подмножество математики. А тут помогут производящие функции. Попробуйте с помощью уравнения и граничных условий найти выражение для функции (назовём её $A(z)$) $\sum_{k=0}^{\infty}{a_k z^k}$. Когда найдёте для неё выражение, попробуйте разложить её в ряд и тем самым выцепить $a_k$.

Zealint и GAA опередили.

[Zealint]

Когда решите, получите ответ типа такого

$$ a_n=-\frac{9}{4}\cdot(-4)^n+\frac78\cdot(-4)^n\cdot n+\frac94\cdot(-2)^n. $$

[Miktor]

У меня во 2 задаче получается в конце выражение:
$G(z)=\frac{z+11z^2}{1+10z+32z^2+32z^3}$
Как это разложить, я не знаю, точнее знаю, но не уверен что правильно до этого решил.

$$G(z)=z+z^2 - 10\sum_3^{\inf}{}a_{n-1}^z^{n}-32\sum_3^{\inf}{}a_{n-2}^z^{n}-32\sum_3^{\inf}{}a_{n-3}^z^{n}=z+z^2-10[G(z)-z]-32z^2G(z)-32z^3G(z)=\frac{z+11z^2}{1+10z+32z^2+32z^3}$$

И еще есть задача:Найти число целых положительных чисел, не превосходящих 1000 и
не делящихся ни на одно из чисел 6, 10 и 15.
с 10 это все понятно, таких чисел 99, 15 тоже не так плохо,хотя, конечно же можно посчитать вручную, и это будет 63: $1000=900+90=15*60+15+4$
Но во первых это не правильно, а с 6 так будет очень геморно подсчитать, где можно найти информацию о выводе правил деления, хотя с 6 и 15 и так понятно. больше интересует как это подсчитать по формуле.

[ewert]

Miktor в сообщении #368376 писал(а):

Найти число целых положительных чисел, не превосходящих 1000 ине делящихся ни на одно из чисел 6, 10 и 15.

Логически проще всего подсчитать количество чисел, делящихся хотя бы на одно из них, используя формулу включений-исключений.

[arseniiv]

(О формулах)

Не $\inf$, а $\infty$.

[Zealint]

Производящая функция, кажется, найдена правильно. Ну теперь раскладывайте её в ряд.

[ewert]

Zealint в сообщении #368048 писал(а):

Решение второй задачи - это вывод явной формулы для последовательности, заданной рекуррентным соотношением. Как решать такие задачи написано здесь.

Не очень понятно, зачем нужно возиться для разностных уравнений с производящими функциями (разве что из спортивного интереса). Вместо того, чтобы сходу написать характеристическое уравнение $q^3+10q^2+32q+32=0$, найти его корни $q_1=q_2=-4$ и $q_3=-2$ (это в любом варианте решения придётся делать), записать общее решение по стандартному правилу в виде $a_n=A\cdot q_1^n+B\cdot q_1^n\cdot n+C\cdot q_3^n$, быстренько подогнать произвольные постоянные $A,B,C$ под начальные данные и получить ответ.

[Zealint]

В данном случае, конечно, можно сделать и так, когда соотношение линейное и с постоянными коэффициентами. Только сначала нужно доказать, что то, что вы говорите правильно. Лично я вывожу такие вещи через производящие функции, поэтому мое решение "с нуля" будет именно таким. Если кого-то научили через харуравнение (и доказали, что это правильно) то ради бога.

[ewert]

(Оффтоп)

Zealint в сообщении #368513 писал(а):

Только сначала нужно доказать, что то, что вы говорите правильно.

Я лично никогда и никому этого не доказывал (просто как-то не доводилось). Но зато мне постоянно приходится на этот факт ссылаться (со словами: "ну вы, мол, это уже проходили; а если не проходили -- то примите просто по аналогии, ей-богу, это правда). Если все корни простые -- то доказательство вполне тривиально. Если есть кратные -- то идея та же, что и при доказательстве аналогичного утверждения для дифуров. А поскольку линейные разностные уравнения с постоянными коэффициентами достаточно принципиальны -- то и утверждение мне представляется важным.

[Miktor]

ewert в сообщении #368435 писал(а):

Zealint в сообщении #368048 писал(а):

Решение второй задачи - это вывод явной формулы для последовательности, заданной рекуррентным соотношением. Как решать такие задачи написано здесь.

Не очень понятно, зачем нужно возиться для разностных уравнений с производящими функциями (разве что из спортивного интереса). Вместо того, чтобы сходу написать характеристическое уравнение $q^3+10q^2+32q+32=0$, найти его корни $q_1=q_2=-4$ и $q_3=-2$ (это в любом варианте решения придётся делать), записать общее решение по стандартному правилу в виде $a_n=A\cdot q_1^n+B\cdot q_1^n\cdot n+C\cdot q_3^n$, быстренько подогнать произвольные постоянные $A,B,C$ под начальные данные и получить ответ.

А как искать характеристическое уравнение и подгонять постоянные, постоянные через известные нам $a_0,a_1,a_2$?

[ewert]

Miktor в сообщении #369027 писал(а):

А как искать характеристическое уравнение

Характеристическое уравнение искать не надо -- надо его просто выписать, взяв в качестве коэффициентов при степенях $q$ ровно коэффициенты того разностного уравнения. Но можно (если нечаянно это вдруг забылось) и найти, подставив в разностное уравнение геометрическую прогрессию $a_n\equiv q^n$ и попросту сократив полученное на младшую степень.

Miktor в сообщении #369027 писал(а):

и подгонять постоянные

Это вообще какой-то праздный вопрос. У Вас есть три требования -- на значения нулевого, первого и второго членов последовательности. Ну так и наложите эти требования на уже имеющуюся линейную комбинацию с неизвестными произвольными постоянными $A,B,C$. Получите систему уравнений для тех постоянных. Уж где-где, но уж в этом-то месте -- теории точно никакой не нужно.