Сочетания с повторениями | Комбинаторика | Теория вероятностей

Знакомиться со способами подсчета различных исходов мы начали со второй части Лекции 1 (смотрите ее тут: • Теория вероятностей. Л... ), в которой мы познакомились с перестановками и размещениями. Причем рассмотрели случаи различных элементов и с повторениями.
В третьей части Лекции 1 (вот ссылка на нее • Теория вероятностей. Л... ) мы познакомились с сочетаниями. А сочетания с повторениями отложили на потом.
Сегодня займемся сочетаниями с повторениями.
И это могло бы стать четвертой частью Лекции 1, но все же станет Лекцией 3.
На самом деле подсчитать последовательности из повторяющихся элементов, когда не важен порядок их расположения достаточно просто. Нужно эти последовательности закодировать. С двумя способами такой кодировки мы сегодня и познакомимся.
Изложение соответствует книжке Виленкина "Комбинаторика", которая может быть рекомендована в качестве литературы и для дополнительных самостоятельных упражнений.
Рассказ почему-то проходит в условиях "А и Б сидели не трубе. И пропало".
Читает Игорь Тиняков для канала Элементарная Математика
#комбинаторика #сочетания #сочетаниясповторениями

[@TheMorisBlack]

Зашёл подтянуть комбинаторику, оказался на теоретической информатике :)

[@Seraya_panelka]

Очень хорошее объяснение по сравнению с другими на ютубе. Спасибо!❤

[@elemath]

Пожалуйста!)

[@user-yl1ub2dr2g]

Смогла интуитивно понять формулы для размещений с повторениями и без, для сочетаний без повторений. Пару дней билась над тем, чтобы понять и вывести формулу для сочетаний с повторениями, но мало что получилось. К сожалению, не получится все прочувствовать самостоятельно в разумные сроки. К счастью, вы смогли мне помочь понять как можно интуитивно и на пальцах «прочувствовать» формулу сочетаний с повторениями. Большое спасибо за эту лекцию ❤

[@user-tc1or3ux4r]

Спасибо за лекцию! Всё очень понятно 👍👍👍

[@elemath]

Пожалуйста!)

[@user-rp4id3df7x]

Очень рад увидеть комбинаторику)

[@elemath]

большой перерыв до сочетаний с повторениями получился

[@user-ft2bb8xf8w]

Объяснение прекрасно!

[@user-ze8ls6kx6s]

Хотелось написать, что это замечательное видео Спасибо Вам за то, что понятно объясняете и мотивируете учиться и развиваться P.s благодаря ютубу я узнала и научилась многому, теперь в 9 классе получила красный аттестат Ютуб-мощь🙂❤️

[@elemath]

🙏🏻❗️

[@mautintv2244]

спасибо за лекции👍

[@elemath]

Пожалуйста!)

[@artemchernienko7069]

Спасибо за ролик :)

[@elemath]

Пожалуйста!)

[@iamzeus1250]

Огромное спасибо!

[@elemath]

Пожалуйста!)

[@user-sd3te8wy8p]

Возник вопрос по поводу второго варианта решения задачи с конфетами. Почему мы используем формулу сочетаний, у нас же в этом варианте решения теперь важна индексация элементов и при перестановке их местами получится уже другая комбинация? Последовательность 3; 4; 6; 7;...; 13 и последовательность 4; 3; 6; 7;...; 13 имеют разное отображение в конфетную последовательность, следовательно формулой для сочетаний пользоваться нельзя

[@user-cp7to2hy4x]

это задача перестановки. число позиций совпадает с числом конфет

[@armyant6187]

Я аж есть захотел. Пришлось бежать в магазин (НОЧЬЮ!) и покупать конфеты.

[@elemath]

❗️)))

[@warhamer9984]

Ответ 24:30 - С5/9... Четыре нуля разделителя и Пять оставшихся мест под единицы... Остальные пять мест уже зарезервированы под одну конфету каждой марки ..

[@elemath]

так и есть! в общем виде есть решение в комментариях, но, полагаю, Вы и сами его легко получите)

[@user-ew3lq4yl3s]

Спасибо за видео, хотелось бы посмотреть разборы вступительных работ в сильнейшие школы России в вашем исполнении, например Вступительные работы в ПФМЛ 239, там есть много интересных задач.Еще раз спасибо

[@elemath]

Пожалуйста!) Может когда будут и такие задачи.

[@armyant6187]

По поводу первой домашней задачи. Я так понял, что для этого надо немного изменить алгоритм. Теперь вместо барьера в виде нуля (как было раньше) надо делать барьер из непременного сочетания "10". И плюс к тому - исключить из первоначальных вариантов тот вариант, когда нуль появляется в самом конце строки. То есть, вместо (n+k-1) внизу "C" будет индекс (n+k-1-k-1) И тогда получается Сочетания из (n-2) по k.

[@elemath]

Да, так можно сделать! «1» у нас 𝑘 штук. Одну ставим в конце (исключаем нуль в конце строки, всё как Вы и написали!), остается 𝑘-1, из которых 𝑛-1 забираем на «10». Остается (𝑘-1)-(𝑛-1)=(𝑘-𝑛) штук «1» и (𝑛-1) штук «10», число комбинаций которых равно 𝑃(𝑘-𝑛,𝑛-1). Заметим, что условие в каждой «конфетной» последовательности была по крайней мере одна конфета каждого типа дает 𝑘>=𝑛. Кстати, при 𝑘=𝑛 получается одна комбинация!

[@user-ig4zo7xu4c]

Привет, Игорь. Пишу 29.04.23. Вот по поводу ясной погоды 1 и 2 или 21 и 22. Мне кажется, что это без разницы. Можно, конечно, и посчитать, но такое ощущение, что это тоже, как рассуждение, когда выгоднее сдавать экзамен первым или последним, если не знаешь 6 билетов их 31. Я там где-то писал, оставлял свой почтовый адрес.

[@elemath]

Здравствуйте, Александр! Укажите, пожалуйста, время по видео. Давно это было, я уж забыл чего там наговорил...

[@lenamak3050]

первая задача легко сначала берем и все пять конфет на первые пять мест ставим ,это сочетание 5 из 5 ,т.е. один способ.,а оставшиеся 5 мест это уж как угодно, т.е сочетание с повторениями 5 из 5, или сочетание из 9 по 5(ну или по 4). получается 1 умножить на C из 9 по 5

[@interbrigadistua3115]

Спасибо большое за урок! За ваши старания! Правда, понимаю, что пишу поздновато. Но можете подсказать, почему в перестановках с повторениями у нас происходит деление? У нас же по-идее должно быть: всего комбинаций ( n! ) минус перестановки элементов ( n1, n2 ... nk ), что именно я неправильно понял?

[@elemath]

Вот в этом видео объясняется kzbin.info/www/bejne/aZTQn2N-eriFfdU Где-то в середине.

[@interbrigadistua3115]

@@elemath Спасибо большое!

[@elemath]

Пожалуйста!)

[@armyant6187]

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

[@elemath]

Да, задача несколько сложнее. В общем виде можно сначала рассмотреть, когда есть нехватка (до длины выборки) одного типа (остальных типов достаточное количество, поэтому считать их умеем. Это как если бы мы при решении первой задачи зафиксировали 𝑛-1 «1», а потом посчитали бы оставшиеся «0» и «1»), потом двух и попробовать уловить закономерность.

[@user-vf7xz3kd9h]

Привет ты круто росказоваеш но мне интересно там одно видио скрыто в плейлисте ето неудачное видио?

[@elemath]

Привет! Сейчас новые видео появляются один раз в неделю, по субботам. К этому видео доступ будет открыт позднее. Тогда можно будет наверняка оценить, насколько оно неудачное))

[@user-vf7xz3kd9h]

Спосибо!!! вы всегда отвечаете на вопросы

[@elemath]

Пожалуйста!)

[@ivanwade4851]

Хотел бы у вас спросить, почему так происходит. На примере несложной задачи: стоят в вазе 5 роз и 6 тюльпанов. Число способов выбрать 3 розы - C из 5 по 3. Но если изменить вопрос задачи и спросить, сколько есть способов выбрать просто 3 цветка, то задача сводится к числу сочетаний с повторениями из 2 по 3. Почему же так происходит? Никак не могу осознать, что в 1-ом случае розы как бы уникальны, и выбор одной это не одинаковый случай с выбором другой. А во 2-ом все розы и тюльпаны не отличаются между собой и представляют собой просто 2 типа цветов. Помогите пожалуйста разобраться с этим. Заранее вам спасибо, вы прекрасный лектор в математике.

[@elemath]

Вы сами наделили задачи смыслом. 1 случай. Так как Вы пишете про розы, то тюльпаны тут вообще не при чем. Если розы неразличимы, то РРР - единственная тройка (аналог сочетаний с повторениями - выбрать три элемента из однотипных). А если различимы (одна подвядшая, одна свежая, одна искусственная и т.д.) и их 5, то число различных букетов из 3 штук будет (как Вы и написали) С₅³. Среди них будут букеты Р₁Р₂Р₅ и Р₂Р₃Р₅, например. Таким образом, Вы, предложив такой ответ к непоставленной задаче, сами решили, что розы различимы. 2 случай. Есть 11 цветков. Если все они различимы (как в случае 1 с розами), то 3 цветка из 11 можно выбрать С₁₁³ способами. И среди этих букетов будут и Р₁Т₅T₆, и Т₂Т₃Т₆, и другие (лишь порядок следования букв не имеет значения). Если цветки каждого типа неразличимы и типов цветов 2 (Р и Т), то способов уже 4 (ТТТ, РТТ, РРТ и РРР), но тогда количество цветов каждого типа ( и общее число) становится не важным, лишь бы оно было достаточно для осуществления выбора (для простоты задачи). Три розы и три тюльпана при Вашем предположении 5Р и 6Т найдутся, поэтому все 4 тройки, указанные выше, возможны. Поэтому надо чётко понимать (или формулировать) условие задачи, из которого должно следовать, различимы объекты или нет.

[@ivanwade4851]

Спасибо Вам, как всегда выручаете :)

[@elemath]

Пожалуйста!)

[@ivanwade4851]

@@elemath вы очень интересное Д/З предлагаете в конце этого ролика. С первой задачей быстро разобрался, даже в общем виде, но со второй не могу никак придумать идею для решения, хоть даже и изучил комментарий другого человека. Не могли ли вы, пожалуйста, дать бы какую-то наводку на решение такой задачи? Задумка ограничения количеств конфет классная идея. Но сложная.. P.s. извините, что в последнее время часто вас что-то спрашиваю. Зато делаю актив вам, хех

[@elemath]

попробуйте сначала разобрать такой случай: А=1, остальные Б,В,Г,Д каждое больше 10.

[@user-ib3ev5pl2t]

А как посчитать количество подмножеств множества, где разрешены повторения. К примеру, 12234, подсчитать количество всевозможных подмножеств

[@elemath]

Если множество состоит из n элементов, то у него 2^n подмножеств. Не имеет значения, в каком порядке в них идут элементы. В Вашем примере элементов 5. Два из них равны, но это разные двойки: 2₁ и 2₂. Можно по аналогии спросить, сколько подмножеств у множества из 5 апельсинов. {А₁} и {А₂} - разные подмножества. Если вопрос поставить иначе, например, сколько разных чисел можно составить из цифр {1, 2, 2, 3, 4} при условии, что меньшая предшествует большей, то 12₁3 и 12₂3 будут одинаковыми числами, поэтому такую комбинацию надо учесть один раз. Аналога пустого множества тут не будет, но будет аналог всего множества 12234; однозначных чисел будет 4: 1, 2, 3 и 4; двузначных будет 7: 12, 13, 14, 22, 23, 24 и 34. из 10 выбросили три числа, которые с другой двойкой дают повтор: 12, 23 и 24. Из 10 трехзначных также надо выкинуть те, в которые двойка входит один раз (их также три 123,124 и 234), также и с четырехзначными (1234). Остается лишь обобщить результат.

[@user-ib3ev5pl2t]

@@elemath спасибо. Я имел в виду, сколько подмножеств с повторениями именно из этого подмножества с повторения можно получить, т.е 1, 21, но при этом из-за дубля надо что-то отнять я не могу понять что

[@user-ib3ev5pl2t]

​@@elemath хм а что если то же самое, как и 2^n, только тут будет у одного 2 варианта быть или не быть, а у двойки 3 варианта - нету, есть одна и есть два. А как через сочетания это выразить

[@elemath]

@user-ib3ev5pl2t различаются ли у Вас 21 и 12? Если нет, то это аналог подмножеств и это условие "меньшая цифра предшествует большей". Если да, то условие не нужно, тогда можно спросить, сколько различных чисел можно составить из цифр {1, 2, 2, 3, 4}. В первом случае таких чисел 2⁵-1-2³. Первое здесь число подмножеств множества из 5 элементов, 1 убирает пустое множество, 2³ - число подмножеств множества из трех элементов {1, 3, 4}, к которым можно присоединить двойку и будет повтор. Например, к 13 присоединяем 2. Будет 132, но это число уже учтено числом 123. Поэтому вычитаем число этих повторов.

[@elemath]

2⁵ =(1+1)⁵ и если раскрыть, то и будут сочетания, но можно и сразу пользоваться числом всех подмножеств.

[@user-rp1yn9dq7g]

думал что, хоть что-то знаю в комбинаторике😢

[@manzukrecordsexclusive578]

да ахуенное объяснение кста, в 8 кл выручило

[@artwelf]

Решение первой задачи: у нас есть 10 единиц, между которыми мы должны расставить 4 нуля так, чтобы нули не стояли рядом друг с другом. Другими словами, между десятью единицами у нас есть 9 промежутков, в которые можно вставить нули, и из этих промежутков мы должны выбрать четыре. Способов выбрать 4 промежутка из девяти - это число сочетаний из 4 по 9.

[@elemath]

так и есть!

[@elemath]

забыл добавить, что только из 9 по 4)

[@artwelf]

@@elemath Да, я всегда путаю это. Поэтому предпочитаю говорить "количество способов выбрать 4 предмета из девяти" ))

[@muzjazz3722]

Баунти не заслуживают такого обращения с собой! это дискриминация! это самые вкусные конфеты! а то белочки какие-то там блин

[@elemath]

о, да!