A.2.5 Комбинаторика: сочетания с повторениями

#dudvstud #математиканапальцах #войтивайти
Телеграм: t.me/dudvstud
Плейлисты, литература, помощь проекту и прочее: dudvstud.wixsite.com/website
Моделируем сочетания с повторениями и подсчитываем их количество.

[@anzarsh]

Последние 2 урока конечно уже нужно включать голову или я не выспался сегодня) Спасибо!

[@windachae4778]

Спасибо огромное за уроки, подготовился к кр по дискретной математике благодаря вам!) У Вас классная подача, всё спокойно, чётко и структурировано + повторение перед началом занятия, ещё раз спасибо

[@dudvstud9081]

Спасибо!

[@user-pj8un5yx9z]

Хорошо бы разобрать на конкретных примерах, как и перестановки с повторениями .

[@anzarsh]

Кстати, на канале уже больше 10т. просмотров, поздравляю!

[@dudvstud9081]

Спасибо! :)

[@user-uy9lp2jp7q]

Большое спасибо)

[@user-lc1ph5jg5k]

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

[@dudvstud9081]

Мне нравится эта идея. Со следующего раздела (теория вероятности) начнем эту схему.

[@user-kw4hl4gd4x]

Добрый день. Подскажите пожалуйста, где на практике данная формула применяется?

[@dudvstud9081]

Добрый! Любая задача на состав, при ограниченном объеме: в школьной сборной 5 детей (мальчики и девочки), сколько есть вариантоа гендерного состава команды? Сколько можно сварить трехсолодовых сортов пива, если есть семь разных солодов? (Не точно, что такое пиво бывает в реальности :) )

[@user-pp8gi2pm4m]

Спасибо за уроки ! Не подскажете, когда будут уроки по другим темам ?

[@dudvstud9081]

Через пару недель будем повторять функции, экспоненты, логарифмы. Потом будет первая часть теории вероятностей. Потом повторение геометрии (кратко). Затем тригонометрия. Это все примерно до средины января. После этого окончательно погрузимся в высшую математику: линейная алгебра, производные и интегралы, операторы поля, дифференциальные уравнения, аналитическая геометрия, вторая часть теории вероятностей и статистика. По срокам тут сложно оценить.

[@user-pp8gi2pm4m]

@@dudvstud9081 Спасибо :)

[@dudvstud9081]

Еще будут темы "полиномы" и "спектральные преобразования".

[@artempoddieniezhnyi6031]

Добрый день Слава, всегда путаюсь в обозначениях типа С из n по k - это обозначние числа С из множества n подмножества к? также была запись в формуле бинома Ньютона С из n по i , но i это была степень. В общем если структурировать что обозначают записи типа С из n по k ?

[@dudvstud9081]

C из n по k (n внизу, k вверху) - это количество вариантов выбрать k элементов (подмножество) из множества n. C из 4 по 2 - это количество вариантов как застегнуть наручники на человеке, используя любые его 2 конечности :)

[@angryworm80]

К аналогичной формуле сочетания с повторениями можно еще придти используя формулу перестановок с повторениями для модели из «0» и «1». Всего у нас n-1+k мест и среди них два типа объектов. Соответственно, как и сказано, каждый код однозначно определяет способ выбора k объектов из n с повторениями. Но чтоб найти количество таких кодов надо найти число перестановок из n-1+k с повторениями. Получаем в числителе (n-1+k)! А в знаменателе факториалы для количества неразличимых элементов каждого типа (n-1)!k! ... а дальше уже можно с помощью нехитрых преобразований показать эквивалентность этой формулы с формулой сочетания из n-1+k по k. Просто я не очень понял момент, почему когда ищем все варианты кода, то применяем сочетания 🤷🏻‍♂️ Мне стало понятно только когда я вычислил через перестановки с повторениями.

[@dudvstud9081]

Спасибо за комментарий. Да, так тоже правильно :)

[@angryworm80]

@@dudvstud9081 :)

[@ursusrursus6935]

Тоже не понял почему все варианты такого кода это сочетания.

[@ursusrursus6935]

А вот теперь понял. С 3го раза. В общем нужно пронумеровать все позиции в этом коде. И получается вы выбираете k неповторяющихся номеров, среди общего числа (n-1+k), в которые поставить единицы.

[@user-zq6pu4fd8o]

Почему мы можем использовать именно формулу сочетаний без повторений? Я не вижу связи, в сочетаниях без повторений "к"-факториал вариантов наборов исключается из размещений без повторений и это понятно как, мне не понятно, то что если n-1 нулей это размер набора в сочетаниях без повторений и этот факториал вариантов наборов исключается из размещений без повторений, то как это связано с количеством вариантов учитываемых в сочетаниях с повторениями? На ответ не рассчитываю, но буду рад если это случится, интуитивно я что-то понимаю но не могу объяснить себе.

[@dudvstud9081]

Спасибо за комментарий. Я стараюсь отвечать на все комментарии, по крайней мере, когда успеваю :) Мы ситуацию с повторениями свели к более простой, без повторений. Для этого мы были вынуждены построить модель: систему, которая функционирует аналогичным с исследуемым объектом образом образом , но может быть описана более простыми формулами. В нашем случае моделируемый объект это набор с повторяющимися "мячиками", а модель - это набор с разделителями, который сводится к цепочке из 0 и 1 и может описываться Ну а сам процесс построения этой модели и составляем, в общем-то, суть урока... (Ах это прекрасное время, когда уроки были по 8 минут и я еще не умел писать ровно... :)))

[@user-zq6pu4fd8o]

@@dudvstud9081 я благодарен вам за ваш труд. Действительно вас приятно слушать.

[@dudvstud9081]

@@user-zq6pu4fd8o спасибо :)

[@user-et7yb4fq8c]

Объясните почему в сочетаниях с повторениями в числителе количество элементов это сумма п + к - 1???

[@dudvstud9081]

На 6:34 мы сформировали код из 0 и 1, который моделирует сочетания с повторениями и дальше считаем сколькими способами его можно сформировать. Там же и приходим к п + к - 1.

[@user-dh9iw2zu7d]

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

[@dudvstud9081]

Есть такое замечательное свойство сочетаний: сочетания из n по k эквивалентно сочетания из n по n-k. Что в нашем случае делает эквивалентными распределения 0 или 1.

[@jeckydreemurr9631]

А может кто-нибудь объяснить, почему уже второе занятие говорится, что выбранный элемент возвращается во множество и может быть выбран сколько угодно раз, а во всех примерах, что я находила, задачи типа "есть 2 красные лампочки и четыре синие, сколько можно составить цепей". Мы же не можем составить цепь из шести синих лампочек, если их всего четыре. У меня какая-то несостыковка😅

[@dudvstud9081]

Потому что уже второе занятие мы говорим про размещения перестановки и сочетания с повторениями. А Вы приводите пример задачи без повторений. Это раньше было, позапрошлые уроки.

[@danjilov3965]

Круто! Прям отлично объяснили на примере двоичного кода. Даже в какой-то момент будто Виленкина читал, только там с палками, менее интуитивно понятно) Есть небольшой вопрос: как посчитать сочетания с повторениями + с ограничениями на каждую группу Например: a a b b c c c c И нам нужно например посчитать количество выбора из 2 элементов, порядок теперь не важен: a a b b c c a b a c b c Но как теперь быть если нужно выбрать 3 элемента? а может учавствовать лишь дважды, и b лишь дважды. Наверное можно сказать ещё что «данную группу можем вернуть в исходную последовательность лишь m раз». В общем есть ли какая-то формула на данный случай? Мне самому кажется, что универсальной формулы нет, максимум что формула для отдельной группы. Таким образом применяем формулу для каждой группы и дальше ещё что-то делаем

[@danjilov3965]

Нашёл одну выкладку m.mathnet.ru/links/27ba49e3b34e42e72ac3725be1d8c921/pdm409.pdf Но я сейчас не в силах её осилить. Уровень пока не позволяет

[@dudvstud9081]

Готовой формулы на такой случай мне не известно. Надо комбинировать формулы. Вот Ваш пример с парами: есть 3 варианта выбрать первый элемент и 3 - второй. Это размещения с повторениями 3^2. Но пары одинаковых элементов будут повторяться. Поэтому 3^2 - 3 = 6. Для троек рассуждаем аналогично: Есть 3 способа выбрать первый элемент, 3 - второй и 3 - третий. Но не будет троек с а и с b. Получается: 3^3 - 2 = 25. Из них, с учетом повторений надо выбросить повтроения типа аса, асс, сса и типа abc, acb bac, bca, cab, cba. Один элемент без повторений ссс. Его уставляем как есть :) Осталось 6 повторений с тремя элементами и 25 - 1 - 6 = 18 повторений с парами одинаковых элементов. Такие последовательности повторяются по 3 штуки (аса, асс, сса). Итого, собираем конечный результат: 1 (ссс) + 1 (abc) + 18 (aac) / 3 = 8

[@lanya823]

Элегантное решение! Что-то не помню, чтоб я такое проходила или очень хорошо забыла. В любом случае красота решения порадовала) Рассуждения про моделирования выбивают из колеи и мешают воспринимать собственно матиматику. И я не уверенна, что это уместно называть моделированием. Ибо моделирование это когда для реального объекта или процеса создается абстракция, которая его описывает (желательно в хорошей степени). А у нас изначально была абстрактная задача. Я бы проще сказала, что одну задачу сводим к другой. Видим, что между вариантами из этих 2 задач есть взаимнооднозначное соответствие, т.е. кол-во вариантов в обоих задачах равно, и потому решение второй задачи будет решением и первой.

[@dudvstud9081]

Спасибо за отзыв!

[@user-ne3xu7bx7v]

Получается последняя формула будет равна= (n-1+k)!/ (n-1)!k! ? 😂я подставила вместо n --> n-1+k .

[@dudvstud9081]

Да, вроде бы так

[@berluse-2464]

Без примеров очень сложно вникнуть

[@nicholasspezza9449]

Жесть, конечно, никакого объяснения в принципе нет. Просто формулы рисует.

[@dudvstud9081]

Какую формулу я "нарисовал" без объяснения? Дайте таймкода

[@dudvstud9081]

Я крайне положительно отношусь к критике, если она обоснованная. Но такое замечание мне сложно воспринять всерьез, потому что все 8 минут были посвящены объяснению одной формуле. Давайте тайм-код, что Вам показалось нарисованным без объяснения. Попробую еще раз объяснить.