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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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




Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Поиск комбинаций
СообщениеДобавлено: 18 сен 2017, 23:04 
Не в сети
Начинающий
Зарегистрирован:
18 сен 2017, 22:55
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Доброго времени суток. Застрял с задачей. Есть набор символов ( a[math]_{1}[/math], a[math]_{2}[/math], a[math]_{3}[/math], a[math]_{4}[/math], a[math]_{5}[/math], a[math]_{6}[/math], a[math]_{7}[/math] ), которые могут принимать 3 значения, для общности рассуждения скажем d, b, c. Нужно найти все комбинации, которые могут принять данные символы с учетом того, что ни в одной из комбинаций d и с не могут стоять рядом.

Буду рад любой помощи и подсказкам.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 19:34 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 16:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
25 раз в 24 сообщениях
Очков репутации: 15

Добавить очки репутацииУменьшить очки репутации
Мне очень стыдно, но, признаться, Вы меня загрузили. Я не могу найти приемлемого комбинаторного решения этой задачи. Поэтому все, что я могу Вам предложить, это подойти к большой доске и нарисовать дерево возможных комбинаций наподобие того, что прикреплено в файле. У Вас будет всего два дерева. Одно начинается с буквы b, другое - с с. Третье дерево получится из второго заменой c на d и наоборот. Возможности бумаги не позволяют рисовать такие большие деревья. Для доски это будет возможно. Но вот если бы у Вас было не 7 символов, а, скажем, 70, то я на данный момент пас. Могучие и великие участники форума, буду благодарен Вам лично за решение этой бросающей всем нам вызов задачи! Я готов признаться, что плохо знаю комбинаторику, но хочу знать, как решается эта задача.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 19:37 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 16:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
25 раз в 24 сообщениях
Очков репутации: 15

Добавить очки репутацииУменьшить очки репутации
Не могу прикрепить файл. Как файл здесь прикреплять?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 19:50 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3190
Cпасибо сказано: 55
Спасибо получено:
697 раз в 630 сообщениях
Очков репутации: 201

Добавить очки репутацииУменьшить очки репутации
Пусть [math]x_{k,b}, \, x_{k,c}, \, x_{k,d}[/math] - количество наборов с данным свойством из [math]k[/math] символов и с последним символом b, c, d соответственно.
Тогда справедливо
[math]x_{k+1,d}=x_{k,b}+x_{k,d}[/math]
[math]x_{k+1,c}=x_{k,b}+x_{k,c}[/math]
[math]x_{k+1,b}=x_{k,b}+x_{k,c}+x_{k,d}[/math]
[math]x_{1,b}=x_{1,c}=x_{1,d}=1[/math]

Можно еще чуть упростить, если заметить, что в силу симметрии [math]x_{k,c}= x_{k,d}[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
Kirill1986
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 20:04 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 16:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
25 раз в 24 сообщениях
Очков репутации: 15

Добавить очки репутацииУменьшить очки репутации
swan, т. е. Вы предлагаете рекуррентными соотношениями довести задачу до ответа? Но, позволю спросить, если [math]k[/math] очень большое, то никаких других рецептов, дающих ответ в явной форме нет, что ли? Интересно самому стало.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 20:07 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 16:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
25 раз в 24 сообщениях
Очков репутации: 15

Добавить очки репутацииУменьшить очки репутации
Файл:Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 20:33 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3190
Cпасибо сказано: 55
Спасибо получено:
697 раз в 630 сообщениях
Очков репутации: 201

Добавить очки репутацииУменьшить очки репутации
Почему так не любите рекуррентные формулы?
Уверяю вас, на практике решение комбинаторных задач через них наиболее просто и эффективно.
По алгоритму, подобному вычислению чисел Фибоначчи можно найти за [math]\log k[/math] шагов.
То есть быстрее, чем, скажем, вычислить [math]\sin k[/math].

По поводу конкретно данной задачи. Я стал выписывать значения [math]x_{k,b}[/math] и [math]x_{k,c}[/math].
И что-то смутно знакомое бросилось в глаза. Залез в OEIS и точно. Наши [math]x_{k,b}[/math] и [math]x_{k,c}[/math] есть ни что иное как числитель и знаменатель подходящей дроби к [math]\sqrt 2[/math].
Соответственно можете ознакомиться с цепными дробями и прочитать про методы их вычисления.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
Kirill1986
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 20:36 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 16:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
25 раз в 24 сообщениях
Очков репутации: 15

Добавить очки репутацииУменьшить очки репутации
Если воспользоваться рекуррентными соотношениями, которые предложил swan, то для данной конкретной задачи у меня получилось:
[math]x_{7,b}=239[/math],
[math]x_{7,c}=169[/math],
[math]x_{7,d}=169[/math].
Общее число способов: [math]x_{7}= x_{7,b}+x_{7,c}+x_{7,d}=577[/math].

swan, большое спасибо! Но в общем случае задача какая-то мутноватая...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 20:39 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 16:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
25 раз в 24 сообщениях
Очков репутации: 15

Добавить очки репутацииУменьшить очки репутации
Беру свои слова про мутноватую задачу обратно! Просто я подзабыл теорию чисел...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 21:53 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3272
Cпасибо сказано: 229
Спасибо получено:
207 раз в 196 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
Я посчитал за 2 минуты в уме, но наверное неправильно, получилось 2*80+113= 273.

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

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

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

slavyanin

3

443

26 май 2013, 20:01

Количество комбинаций

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

bleike

2

388

27 сен 2012, 22:24

Вероятность симметничных комбинаций

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

ivashenko

6

191

10 авг 2014, 14:37

Количество комбинаций в таблице

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

Oleg1989

1

215

20 янв 2014, 15:24

Просчет количества комбинаций

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

VolodinAS

5

121

25 июл 2016, 16:46

Как рассчитать количество вариантов комбинаций?

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

GeorgD

2

405

29 июл 2016, 06:09

Определить количество комбинаций диапазона до слова

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

beats

5

223

03 май 2015, 14:02

Рассчитать количество всех возможных комбинаций

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

masterxq

1

244

29 ноя 2015, 21:48

Количество комбинаций сумм из заданных чисел

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

Volodislavir

0

152

30 окт 2015, 04:17

Подсчет вероятности, связь с количеством комбинаций

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

lanc3r

8

254

04 дек 2015, 18:17


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



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

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


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

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

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

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