Задача по дискретной математике

[sali]

Помогите, пожалуйста, решить задачку по дискретной математике.
Найти коэффициент $x^k$ в разложении многочлена $(2x^3+x^2-x-2)^5$, k=5.
Вообще не знаю с какого бока к ней подступиться.

[/img]

[antbez]

Воспользуйтесь полиномиальной формулой

[Профессор Снэйп]

Или одним из математических пакетов, позволяющих производить вычисления с многочленами

Кстати, тут можно всё и ручками перемножить

[PAV]

PAV:

Тема переносится в карантин. Исправьте в своем сообщении формулы в соответствии с правилами форума (инструкция здесь). Когда будет готово, сообщите любому модератору, и тема будет возвращена обратно.

[PAV]

Возвращено

[VAL]

sali писал(а):

Помогите, пожалуйста, решить задачку по дискретной математике.
Найти коэффициент x^k в разложении многочлена $(2x^3+x^2-x-2)^5$, k=5.
Вообще не знаю с какого бока к ней подступиться.

Можно сначала решить в целых неотрицательных числах такую систему:
$ \left\{ \begin{array}{rcrcrcrcl} a&+&b&+&c&+&d&=&5\\ 3a&+&2b&+&c&&&=&5 \end{array} \right. $
А затем применить к каждому решению полиномиальную формулу, не забыв про коэффициенты перед степенями x.
Впрочем, я согласен, что это "стрельба из пушек по воробьям". В данном конкретном случае не сложно и "в лоб" посчитать.

[sali]

antbez
Большое спасибо, полиномиальная формула - это как раз то, что было нужно. Просто вообще не знала, с чего начинать.

Добавлено спустя 1 минуту 23 секунды:

VAL
Да, спасибо, к этой системе я в конечном счете и пришла.

Есть еще 2 задачки:
1) Сколько существует чисел, не превосходящих 1000, которые:
а) делятся одновременно на 6 и на 15;
б) делятся на 6 или на 15?

2) Сколько существует 9-значных чисел, сумма цифр которых четна?

[PAV]

1a. Выразите условие делимости одновременно на 6 и 15 в более простом виде, используя разложение на простые.

1б. Формула включений-исключений (в простейшем виде, для двух множеств).

2. В задаче нужно уточнить, считаются ли девятизначными числа с меньшим числом разрядов. В любом случае нужно задать начальные 8 разрядов произвольным допустимым образом, а затем приписать последний разряд так, чтобы сумма была четной.

[sali]

Я только начинаю изучать дискретную математику, причем самостоятельно, т.к. учусь на заочном. Поэтому мне сложно так сразу разобраться, нужно хотя бы знать тему, которую нужно читать, чтобы понять. С первым я прочитала формулу включений - исключений и поняла - спасибо. А насчет второй задачи пока понять не могу. Вы не могли бы дать ссылку на решебник, где были бы разобраны аналогичные примеры? Или хотя бы указать тему, которую мне надо прочитать, чирбы решить эту задачу? Спасибо.

[PAV]

Ссылки дать не могу. Задача вообще-то на формулу произведения комбинаторики: при последовательном выполнении некоторых действий количество способов перемножается. В данном случае "действиями" являются последовательные выборы цифр числа, одна за другой.

Можете для начала решить задачу попроще: сколько двузначных чисел, сумма цифр которых четна.

[VAL]

sali писал(а):

Я только начинаю изучать дискретную математику, причем самостоятельно, т.к. учусь на заочном. Поэтому мне сложно так сразу разобраться, нужно хотя бы знать тему, которую нужно читать, чтобы понять. С первым я прочитала формулу включений - исключений и поняла - спасибо. А насчет второй задачи пока понять не могу. Вы не могли бы дать ссылку на решебник, где были бы разобраны аналогичные примеры? Или хотя бы указать тему, которую мне надо прочитать, чирбы решить эту задачу? Спасибо.

А можно вместо книжки - совет?
При изучении комбинаторики (а именно этот раздел дискретной математики мы сейчас обсуждаем) очень многие студенты допускают принципиальную ошибку. Начитавшись (по диагонали) книжек или лекций, они приходят к выводу, что главное в комбинаторике это формулы. И "решают" задачи по принципу: "Применим формулу сочетаний. Ах, не то! Ну тогда размещений, сочетаний с повторениями, разбиений...". А задача, хоть и не сложная, но не вписывается ни в одну готовую формулу.

На самом деле, успех в решении комбинаторных задач основан на умении вести комбинаторные рассуждения. За редким исключением для решения учебных комбиторных задач (типа тех, что Вы привели) хватает не слишком сложных рассуждений и формулы для числа сочетаний (размещения и размещения с повторениями тоже часто встречаются по ходу решения, но формулы для их подсчета вполне могут применяться на уровне интуиции).

В свете вышеизложенного могу посоветовать древнюю, но, на мой взгляд, не устаревшую книжку Н.Я.Виленкина "Комбинаторика". Она не годится для освоения дискретной математики в полном объеме (там просто нет других разделов), но комбинаторика изложена по принципу разбора все более усложняющихся задач. Причем во главу угла ставятся именно комбинаторные рассуждения. Это если я ничего не забыл. Сам-то я ее лет 20 не открывал

[sali]

Большое спасибо за направление в обучении. Виленкина скачала, буду читать. Мне в моей будушей профессии очень пригодится знание комбинаторики.

[Архипов]

VAL в сообщении #149133 писал(а):

Начитавшись (по диагонали) книжек или лекций, они приходят к выводу, что главное в комбинаторике это формулы. И "решают" задачи по принципу: "Применим формулу сочетаний. Ах, не то! Ну тогда размещений, сочетаний с повторениями, разбиений...". А задача, хоть и не сложная, но не вписывается ни в одну готовую формулу.

Согласен с данным наблюдением. Хотя бы потому, что я сам так всегда поступаю. Сначала пытаюсь решить дедуктивным методом (применив формулу, если помню способ решения подобной задачи). Потом (в случае неудачи) решаю индуктивным методом, начиная с простого перебора вариантов или перебора движений симметрии. Обнаружив закономерность в ряде чисел, применяю ее в решении, обнаружив следующую закономерность....и т.д. В школьном учебнике по геометрии вскользь говорится о симметрии, из него запоминается только зеркальная симметрия. Хотя движения симметрии (перенос, поворот, подобие, отражение) здорово помогают в случаях, когда совершенно отсутствуют идеи решения.
Легче решать задачки, когда есть к ней ответ. По ретроспективному пути иногда можно просто догадаться - через какое арифметическое действие получилось такое число или символическое выражение. Когда же готового ответа нет - одолевают сомнения (а вдруг ошибся в способе решения или арифметическую ошибку допустил?).Арифметическую ошибку находим повторным вычислением или проверкой соответствия ответа условию задачи. Логическую ошибку можно обнаружить, если удастся решить задачу другими способами.

[Профессор Снэйп]

Архипов писал(а):

Хотя бы потому, что я сам так всегда поступаю...

Отсюда у Вас и все проблемы с пониманием условий.

Ох уж мне эти использователи формул! Из года в год сталкиваюсь с проблемой: вопрос о количестве бинарных отношений на $n$-элементном множестве --- архисложная задача для студентов первого курса. А всё оттого, что ленятся думать, начиная вместо этого вспоминать "формулы".