Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 8 ] |
|
Автор | Сообщение | |
---|---|---|
Ilia |
|
|
Столкнулся с задачей: как найти количество случаев, когда среди N единиц размещенных всевозможными способами на M местах не менее L единиц идут подряд? Остальные позиции можно заполнять нулями. M>L Придумал вот что: рассмотрим M этих самых мест. Группа из L единиц подряд может стоять на каждом из них, и с обоих краев тоже. Стало быть всего (M-L+1) способами. Остальное мето можно заполнить нулями и единцами как угодно, стало быть 2^(M-L) способов. Всего, стало быть (M-L+1)*2^(M-L). Написал скриптушечку на VBA, проверил, все ок. Но тут решил проверить а какую долю среди всех 2^M комбинаций из нулей и единиц составляют эти самые у которых не менее L подряд единиц. Разделив одно на другое видим что эта доля равна (M-L+1)*2^(-L) и легко превысит единицу при росте М. Что-то тут явно не так но вот что именно? |
||
Вернуться к началу | ||
Free Dreamer |
|
|
Хочу уточнить условие. Задано M позиций, на которых могут находиться нули или единицы. Из них ровно N заняты единицами [math](N \leq M)[/math], остальные - нулями. Нужно определить, в скольких случаях из этих N единиц не менее L идут подряд [math](L \leq N)[/math].
Всё верно? |
||
Вернуться к началу | ||
Ilia |
|
|
Да, так.
Но я уже и сам понял ошибку. Если производить такую циклическую подстановку описанными способами то возникает очень много дублирующихся результатов. Типа если группу из трех единиц 111 переставлять по отношению к другой групее из двух единиц 11 то будет всего один результат: 11111 а не три. (111 - 11) (1 - 111 - 1)(11 - 111). А как вычислить строго уникальные сочетания я не понимаю. |
||
Вернуться к началу | ||
Ilia |
|
|
PS Кстати, если кто мне поможет то я тоже могу помочь в благодарность.
|
||
Вернуться к началу | ||
Free Dreamer |
|
|
Начнём с того, что определимся с общими параметрами:
1) всего способов составить строку длины M из нулей и единиц можно [math]2^M[/math] способами 2) составить строку, в которой будет ровно N единиц можно столькими способами, сколькими можно зафиксировать позиции для единиц в этой строке (позиции у нас такие: 1, 2, ..., M; какие-то N из них занимают единицы, остальные нули), т.е. [math]C_{M}^{N}[/math] Например, сколькими способами можно составить строку длины 4 c 2-мя единицами? 1100 1010 1001 0110 0101 0011 т.е. [math]C_{4}^{2}=6[/math]-ью способами 3) Постановка задачи "не меньше L" сводится к задаче "ровно k" при [math]L \leq k \leq N[/math]. Если точнее, то я предлагаю посчитать общее число способов расставить единицы так, что длина самой длинной их последовательности равна L - обозначим это число через [math]N_k[/math] - а потом просуммировать: [math]N = \sum _{k = L}^{N} N_k[/math] Значит, задача фактически состоит в том, чтобы найти число [math]N_L[/math] при условиях [math]M \in \mathbb{N}[/math] [math]1 \leq N \leq M[/math] [math]1 \leq L \leq N[/math] Мне кажется, есть какое-то красивое решение, но додуматься до него пока не могу, так что остаётся перебор вариантов. Надо разбить общее число способов расставить нужным образом единицы на какие-то части: например, часть способов, в которой слева от максимальной последовательности единиц стоят только нули; то же самое, но справа; часть способов, когда с каждой стороны от максимальной последовательности есть хотя бы одна единица. Нужно учесть, что при N, близком к M, и при L, близком к N, могут возникнуть трудности. Заодно учесть, что максимальная последовательность может быть не единственной: например, при M = 10, N = 6, L = 2, можем иметь 3 таких последовательности: 0-1-1-0-0-1-1-0-1-1, соответственно нужно поиграться с тем, как эти последовательности (сколькими способами) могут быть расположены в строке и как при этом можно расположить оставшиеся единицы. Пока, к сожалению, большим помочь не могу. Но, может, Вы что-то придумаете. |
||
Вернуться к началу | ||
За это сообщение пользователю Free Dreamer "Спасибо" сказали: mad_math |
||
Ilia |
|
|
Во-первых спасибо.
Во-вторых могу Вам скажем денег на телефон положить. В-третьих как бы это красивое решение выцепить... |
||
Вернуться к началу | ||
Free Dreamer |
|
|
Во-первых, всегда пожалуйста.
Во-вторых, интересно, в каком контексте задача всплыла: это учебное задание какое-то, по работе всплыло (если да, то очень интересно в связи с чем) или ещё что-то? В-третьих, я ещё подумаю над решением - если что-то стоящее надумается, напишу. |
||
Вернуться к началу | ||
Ilia |
|
|
Это типа баловство на беттинге. Осмысление такой штуки как мартингейл.
|
||
Вернуться к началу | ||
[ Сообщений: 8 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Комбинаторная задача
в форуме Теория вероятностей |
28 |
274 |
15 окт 2023, 14:44 |
|
Комбинаторная формула | 14 |
853 |
13 сен 2018, 21:04 |
|
Комбинаторная задача
в форуме Теория вероятностей |
7 |
448 |
05 авг 2019, 17:45 |
|
Непонятная комбинаторная задача
в форуме Комбинаторика и Теория вероятностей |
17 |
1260 |
15 июн 2014, 00:02 |
|
Комбинаторная задача про футболистов
в форуме Комбинаторика и Теория вероятностей |
2 |
1712 |
16 июн 2014, 17:12 |
|
Комбинаторная задача на перестановки
в форуме Комбинаторика и Теория вероятностей |
5 |
824 |
16 июн 2014, 17:25 |
|
Комбинаторная задача на сочетания | 1 |
232 |
10 авг 2019, 22:27 |
|
Любопытная комбинаторная задача из ЕГЭ-2013
в форуме Комбинаторика и Теория вероятностей |
5 |
712 |
25 апр 2020, 20:56 |
|
Комбинаторная задача, для меня оказалась сложной
в форуме Комбинаторика и Теория вероятностей |
10 |
676 |
12 янв 2022, 15:53 |
|
Комбинаторная задача с выборкой шаров из урны
в форуме Теория вероятностей |
5 |
488 |
28 июн 2019, 17:45 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |