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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Поиск комбинаций
СообщениеДобавлено: 18 сен 2017, 22:04 
Не в сети
Начинающий
Зарегистрирован:
18 сен 2017, 21: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, 18:34 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 15:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
27 раз в 26 сообщениях
Очков репутации: 16

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 18:50 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Пусть [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, 19:04 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 15:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
27 раз в 26 сообщениях
Очков репутации: 16

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 19:33 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Почему так не любите рекуррентные формулы?
Уверяю вас, на практике решение комбинаторных задач через них наиболее просто и эффективно.
По алгоритму, подобному вычислению чисел Фибоначчи можно найти за [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, 19:36 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 15:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
27 раз в 26 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
Если воспользоваться рекуррентными соотношениями, которые предложил 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, 19:39 
Не в сети
Одарённый
Зарегистрирован:
12 ноя 2016, 15:04
Сообщений: 100
Cпасибо сказано: 25
Спасибо получено:
27 раз в 26 сообщениях
Очков репутации: 16

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск комбинаций
СообщениеДобавлено: 19 сен 2017, 20:53 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

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

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

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

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

monst92

4

283

22 фев 2019, 21:28

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

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

VolodinAS

5

481

25 июл 2016, 15:46

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

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

Flagellant

12

444

25 янв 2021, 15:27

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

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

evs

7

523

06 авг 2018, 19:02

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

в форуме Дискуссионные математические проблемы

analizator1337

6

261

23 июн 2022, 15:49

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

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

ivashenko

6

424

10 авг 2014, 13:37

Перебор k комбинаций из n шаров в b корзинах

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

aryaStark

9

222

24 мар 2022, 22:40

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

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

EuroMat

13

691

12 апр 2023, 22:18

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

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

Elijah96

14

137

09 янв 2024, 16:53

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

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

GeorgD

2

1089

29 июл 2016, 05:09


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



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

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


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

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

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

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