элементарная комбинаторика, алфавит из трех букв, кол-во сло : Дискретная математика, комбинаторика, теория чисел fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 элементарная комбинаторика, алфавит из трех букв, кол-во сло
Сообщение27.02.2006, 11:06 


29/01/06
26
В алфавите племени Мумба-Юмба всего три буквы. Смысл имеют слова, в
записи которых среди любых трех подряд идущих букв ровно две – различные.
Сколько двадцатибуквенных слов в языке племени Мумба-Юмба имеют
смысл?

 Профиль  
                  
 
 
Сообщение27.02.2006, 11:18 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Вот наводящее соображение, из которого решение должно уже получиться довольно легко. Пусть имеется некоторое слово, которое имеет смысл. Подумайте, сколькими способами к нему в конец можно дописать одну букву, чтобы новое слово также имело смысл. Потребуется рассмотреть два случая в зависимости от того, как оканчивается заданное слово.

 Профиль  
                  
 
 Мумба-Юмба.
Сообщение27.02.2006, 11:27 


29/01/06
26
У меня другое соображение. По всем раскладам видно, что в этих словах каждые две буквы одинаковые. Пусть эти одинаковые буквы обозначим как а, в, с. Тогда в слове сочетания этих букв например ававававав, асасасасас, авсавсавса и т.д. Т.е. получается 10 ячеек, в каждой по две одинаковые буквы. Теперь надо применить какую-то формулу, которую я не могу вспомнить и нигде найти. Помогите, пожалуйста!

 Профиль  
                  
 
 Re: Мумба-Юмба.
Сообщение27.02.2006, 11:41 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
То, что Вы написали, я не понимаю. Что означает
ОЛЬГА1313 писал(а):
в этих словах каждые две буквы одинаковые


Рекомендую все-таки подумать над тем путем, который я наметил выше, из него получается очень простое и понятное решение.

 Профиль  
                  
 
 
Сообщение27.02.2006, 12:20 
Заслуженный участник


09/02/06
4401
Москва
Пусть f(n) количество слов c n буквами, окончивающихся на 2 одинаковые буквы, g(n) на 2 разные буквы. Тогда f(n+1)=g(n),g(n+1)=2f(n)+g(n),f(3)=6=g(3). Отсюда g(n)=2^n+2(-1)^n. Общее количество слов f(n)+g(n)=3*2^(n-1).

 Профиль  
                  
 
 
Сообщение27.02.2006, 12:29 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Руст

Ответ не такой, хотя рассуждение в целом правильное. У меня получается $9\cdot2^{n-2}$

Например, для n=3 на самом деле 18 слов, а у Вас получается 12

 Профиль  
                  
 
 
Сообщение27.02.2006, 14:18 
Заслуженный участник


09/02/06
4401
Москва
Да, я неправильно посчитал начальное условие g(3)=12, а не 6.

 Профиль  
                  
 
 
Сообщение27.02.2006, 14:37 
Заслуженный участник


09/02/06
4401
Москва
Проще сразу указать, что слово из n букв расширяется до слова из n+1 букв двумя способомами независимо от окончания. Количество подходящих двухбуквенных 9 (любые слова из 3 буквенного алфабита).

 Профиль  
                  
 
 
Сообщение27.02.2006, 14:57 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Руст писал(а):
Проще сразу указать, что слово из n букв расширяется до слова из n+1 букв двумя способомами независимо от окончания. Количество подходящих двухбуквенных 9 (любые слова из 3 буквенного алфабита).


Да, я ровно это решение и имел в виду.

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group