Найти количество 2n-значных чисел, из цифр 1,2,3,4; в которых “1” встречается столько же раз сколько и “2”, а “3”, столько же как “4”.

задан 9 Май 20:56

Опечатка в написании термина: должно быть реКуРРентные.

(10 Май 0:43) falcao
10|600 символов нужно символов осталось
0

Ответом будет квадрат числа сочетаний: $%(C_{2n}^n)^2$%. Доказывается это так.

Рассмотрим подмножество $%A$%, состоящее из всех $%i$% от 1 до $%2n$%, для которых на $%i$%-м месте стоит цифра 1 или 3. Ясно, что $%|A|=n$%. Аналогично, $%B$% означает множество номеров нахождения цифр 1 или 4. Здесь также $%|B|=n$%. Это два $%n$%-элементных подмножества в $%\{1,2,...,2n\}$%. Их знание полностью задаёт число: на месте номеров из пересечения $%A\cap B$% пишем 1, на места из $%A\setminus B$% пишем 3, на места из $%B\setminus A$% пишем 4, на оставшиеся места пишем 2. Если цифра 1 была $%k$% раз, то 3 и 4 встретятся по $%n-k$% раз, и 2 появится $%2n-k-2(n-k)=k$% раз, то есть столько же, сколько цифра 1. Это значит, что пара подмножеств $%(A,B)$% может быть выбрана любой со свойством $%|A|=|B|=n$%. Отсюда следует ответ.

ссылка

отвечен 9 Май 22:03

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

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

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

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

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

отмечен:

×1,093
×4

задан
9 Май 20:56

показан
63 раза

обновлен
10 Май 0:43

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

по почте:

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

по RSS:

Ответы

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

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