2014 dxdy logo

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

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




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

 
 
 
 
Сообщение27.02.2006, 11:18 
Аватара пользователя
Вот наводящее соображение, из которого решение должно уже получиться довольно легко. Пусть имеется некоторое слово, которое имеет смысл. Подумайте, сколькими способами к нему в конец можно дописать одну букву, чтобы новое слово также имело смысл. Потребуется рассмотреть два случая в зависимости от того, как оканчивается заданное слово.

 
 
 
 Мумба-Юмба.
Сообщение27.02.2006, 11:27 
У меня другое соображение. По всем раскладам видно, что в этих словах каждые две буквы одинаковые. Пусть эти одинаковые буквы обозначим как а, в, с. Тогда в слове сочетания этих букв например ававававав, асасасасас, авсавсавса и т.д. Т.е. получается 10 ячеек, в каждой по две одинаковые буквы. Теперь надо применить какую-то формулу, которую я не могу вспомнить и нигде найти. Помогите, пожалуйста!

 
 
 
 Re: Мумба-Юмба.
Сообщение27.02.2006, 11:41 
Аватара пользователя
То, что Вы написали, я не понимаю. Что означает
ОЛЬГА1313 писал(а):
в этих словах каждые две буквы одинаковые


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

 
 
 
 
Сообщение27.02.2006, 12:20 
Пусть 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 
Аватара пользователя
Руст

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

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

 
 
 
 
Сообщение27.02.2006, 14:18 
Да, я неправильно посчитал начальное условие g(3)=12, а не 6.

 
 
 
 
Сообщение27.02.2006, 14:37 
Проще сразу указать, что слово из n букв расширяется до слова из n+1 букв двумя способомами независимо от окончания. Количество подходящих двухбуквенных 9 (любые слова из 3 буквенного алфабита).

 
 
 
 
Сообщение27.02.2006, 14:57 
Аватара пользователя
Руст писал(а):
Проще сразу указать, что слово из n букв расширяется до слова из n+1 букв двумя способомами независимо от окончания. Количество подходящих двухбуквенных 9 (любые слова из 3 буквенного алфабита).


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

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group