Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Комбинаторная задачка
СообщениеДобавлено: 02 апр 2013, 13:15 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2013, 13:02
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Дорогие все!
Столкнулся с задачей: как найти количество случаев, когда среди 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) и легко превысит единицу при росте М.
Что-то тут явно не так но вот что именно?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторная задачка
СообщениеДобавлено: 03 апр 2013, 00:52 
Не в сети
Мастер
Зарегистрирован:
09 окт 2012, 21:02
Сообщений: 212
Cпасибо сказано: 43
Спасибо получено:
20 раз в 16 сообщениях
Очков репутации: 22

Добавить очки репутацииУменьшить очки репутации
Хочу уточнить условие. Задано M позиций, на которых могут находиться нули или единицы. Из них ровно N заняты единицами [math](N \leq M)[/math], остальные - нулями. Нужно определить, в скольких случаях из этих N единиц не менее L идут подряд [math](L \leq N)[/math].
Всё верно?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторная задачка
СообщениеДобавлено: 03 апр 2013, 08:33 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2013, 13:02
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Да, так.
Но я уже и сам понял ошибку. Если производить такую циклическую подстановку описанными способами то возникает очень много дублирующихся результатов.
Типа если группу из трех единиц 111 переставлять по отношению к другой групее из двух единиц 11 то будет всего один результат: 11111 а не три.
(111 - 11) (1 - 111 - 1)(11 - 111). А как вычислить строго уникальные сочетания я не понимаю.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторная задачка
СообщениеДобавлено: 03 апр 2013, 09:17 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2013, 13:02
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
PS Кстати, если кто мне поможет то я тоже могу помочь в благодарность.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторная задачка
СообщениеДобавлено: 03 апр 2013, 14:59 
Не в сети
Мастер
Зарегистрирован:
09 окт 2012, 21:02
Сообщений: 212
Cпасибо сказано: 43
Спасибо получено:
20 раз в 16 сообщениях
Очков репутации: 22

Добавить очки репутацииУменьшить очки репутации
Начнём с того, что определимся с общими параметрами:

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, соответственно нужно поиграться с тем, как эти последовательности (сколькими способами) могут быть расположены в строке и как при этом можно расположить оставшиеся единицы.

Пока, к сожалению, большим помочь не могу. Но, может, Вы что-то придумаете.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Free Dreamer "Спасибо" сказали:
mad_math
 Заголовок сообщения: Re: Комбинаторная задачка
СообщениеДобавлено: 03 апр 2013, 16:00 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2013, 13:02
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Во-первых спасибо.
Во-вторых могу Вам скажем денег на телефон положить.
В-третьих как бы это красивое решение выцепить...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторная задачка
СообщениеДобавлено: 03 апр 2013, 17:49 
Не в сети
Мастер
Зарегистрирован:
09 окт 2012, 21:02
Сообщений: 212
Cпасибо сказано: 43
Спасибо получено:
20 раз в 16 сообщениях
Очков репутации: 22

Добавить очки репутацииУменьшить очки репутации
Во-первых, всегда пожалуйста.
Во-вторых, интересно, в каком контексте задача всплыла: это учебное задание какое-то, по работе всплыло (если да, то очень интересно в связи с чем) или ещё что-то?
В-третьих, я ещё подумаю над решением - если что-то стоящее надумается, напишу.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторная задачка
СообщениеДобавлено: 10 апр 2013, 13:09 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2013, 13:02
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Это типа баловство на беттинге. Осмысление такой штуки как мартингейл.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 8 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Комбинаторная задача

в форуме Теория вероятностей

sergebsl

28

274

15 окт 2023, 14:44

Комбинаторная формула

в форуме Дискретная математика, Теория множеств и Логика

Claudia

14

853

13 сен 2018, 21:04

Комбинаторная задача

в форуме Теория вероятностей

Romaru

7

448

05 авг 2019, 17:45

Непонятная комбинаторная задача

в форуме Комбинаторика и Теория вероятностей

Jazzman

17

1260

15 июн 2014, 00:02

Комбинаторная задача про футболистов

в форуме Комбинаторика и Теория вероятностей

Jazzman

2

1712

16 июн 2014, 17:12

Комбинаторная задача на перестановки

в форуме Комбинаторика и Теория вероятностей

Jazzman

5

824

16 июн 2014, 17:25

Комбинаторная задача на сочетания

в форуме Дискретная математика, Теория множеств и Логика

Romaru

1

232

10 авг 2019, 22:27

Любопытная комбинаторная задача из ЕГЭ-2013

в форуме Комбинаторика и Теория вероятностей

searcher

5

712

25 апр 2020, 20:56

Комбинаторная задача, для меня оказалась сложной

в форуме Комбинаторика и Теория вероятностей

Math137

10

676

12 янв 2022, 15:53

Комбинаторная задача с выборкой шаров из урны

в форуме Теория вероятностей

diofant

5

488

28 июн 2019, 17:45


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved