1
1

Сколькими способами можно вычеркнуть $%23$% буквы из последовательности $%ABABA...BA$% (всего $%27$% букв) так, чтобы остались $%4$% буквы $%ABBA$%, идущие именно в таком порядке?

задан 2 дня назад

Я решил вычислительно, но ответ слишком уж красивый вид имеет -- значит, должно быть короткое комбинаторное решение.

(2 дня назад) falcao

@falcao : Ответ $$ 2^{10} \times 13! $$ да?

(2 дня назад) Rams

@Rams: нет, конечно -- там число существенно меньше.

(2 дня назад) falcao

@falcao, спасибо большое. Тогда я что-то не учитывал. Использовал рекуррентную формулу.

(2 дня назад) Rams
10|600 символов нужно символов осталось
2

Вот решение, не требующее вычисления длинных сумм и прочего.

Пусть дано слово $%(AB)^nA$%. В данном условии $%n=13$%. Нас интересует, сколькими способами можно в этом слове оставить $%\ldots A\ldots B\ldots B\ldots A\ldots\,$%. Рассмотрим два случая.

1) Первые две буквы $%AB$% идут подряд. Выделим три вхождения буквы $%A$%, из которых первое и последнее -- это первая и последняя буквы остающегося в результате $%ABBA$%, а вторая $%A$% предшествует последней $%B$% из $%ABBA$%. Такая тройка букв $%A$% может быть любой, так как первая буква $%B$% однозначно восстанавливается (она идёт сразу за первой $%A$%), а вторая $%B$% идёт вслед за выделенной второй буквой тройки. Получается $%C_{n+1}^3$% способов выбора.

2) Первые две буквы $%AB$% не идут подряд. Тогда перед $%B$% находится какое-то другое $%A$%, отличное от первого вхождения. Выделим его. Также выделим первое и последнее вхождение $%A$% в будущем $%ABBA$%, и ещё одно $%A$%, предшествующее второй из букв $%B$%. Нами выделена четвёрка букв $%A$%, которая может быть любой. По ней однозначно восстанавливается то $%ABBA$%, которое останется. Первая и последняя буквы $%A$% заданы, а вхождения $%B$% следует за второй и третьей выделенной буквой $%A$%. Этим определяется такое $%ABBA$%, где за первым $%A$% не идёт непосредственно $%B$%. Число способов выделить четвёрку равно $%C_{n+1}^4$%.

Итого $%C_{n+1}^3+C_{n+1}^4=C_{n+2}^4$% по свойству треугольника Паскаля. При $%n=13$% это даёт $%1365$% способов.

Я решал поначалу другим способом, рассматривая число вхождений вида $%(AB)^kA$% при $%2\le k\le n$%. Оно равно $%n+1-k$%, и если буквы $%A$%, оставляемые нами, крайние в этом вхождении, то пару букв $%B$% можно выбрать $%C_k^2$% способами. Это даёт сумму $%\sum\limits_{k=2}^n(n+1-k)C_k^2$%. Такие выражения стандартным способом суммируются, и когда получился подозрительно хороший ответ, я нашёл способ получить его чисто комбинаторно, без подсчёта сумм.

ссылка

отвечен 2 дня назад

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,849

задан
2 дня назад

показан
44 раза

обновлен
2 дня назад

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru