Найти количество прямоугольников размера $%1 \times n $%,состоящего из $%n$% клеток,некоторые из которых закрашены в черный цвет. Решение имеется,вопрос именно по нему.

Каждая клетка может быть закрашенной или незакрашенной,т.е. цвет клеткиможет быть выбран 2-мя способами независимо от "раскраски" остальной части прямоугольника. Таким образом, по правилу произведения общее кол-во прямоугольников равно $%2^n$%.

Я не пойму почему $%2$%(количество способов закраски внутренних клеток) возводится в степень$%n$%(это как я понимаю число всех клеток внутри прямоугольника и длина его стороны)- и с правилом произведения у меня ассоциаций не получается.

Объясните пожалуйста каким способом легче всего понять этот ответ и как конкретно здесь действует правило произведения.

задан 20 Окт '13 9:47

10|600 символов нужно символов осталось
1

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

Прежде всего, вместо закрасок прямоугольника можно рассматривать строки из нулей и единиц: 0 означает, что клетка не закрашена, а 1 -- закрашена. Тогда надо понять, почему количество строк длиной $%n$% будет равно $%2^n$%.

Начнём со случая $%n=1$%. Составим полный список всех закрасок. Ясно, что их две: 0 и 1. Теперь, если нам надо составить полный список всех закрасок для $%n=2$%, то они получаются так: к каждой прежней закраске мы приписываем справа либо 0, либо 1. И тогда 0 даёт два случая 00, 01, а 1 даёт 10, 11. Получается "каталог" из $%4=2^2$% строк:

00

01

10

11

Далее создаём каталог всех двоичных строк длиной 3, приписывая к каждой из предыдущих строк справа либо 0, либо 1. Получается (по строкам)

000, 001

010, 011

100, 101

110, 111

То есть общее количество вариантов стало вдвое больше: теперь оно равно $%2^2\cdot2=2^3$% (для строк длиной 3). Понятно, что оно всегда удваивается на следующем шаге, откуда и следует общая формула $%2^n$% для числа вариантов.

ссылка

отвечен 20 Окт '13 11:35

т.е. получается количество таких прямоугольников будет равно количеству способов переставить внутри клетки, которые могут изменяться 2-мя способами,так?$% A_{n}^{k} $%

(20 Окт '13 19:03) Dragon65

Нет, мы не переставляем клетки, а для каждой из них устанавливаем одно из двух состояний. То же самое было бы в случае наличия $%n$% переключателей, каждый из которых включает или выключает отдельную лампочку. Выражение $%A_n^k$%, когда $%n$% предметов размещают без повторений на $%k$% местах, к рассматриваемой ситуации не имеет отношения. Тем более, что $%k$% тут ничему не равно. Наш случай в классификации относится к размещениям с повторениями из $%2$% по $%n$%, когда два вида предметов (0 или 1) размещаются по $%n$% местам.

(20 Окт '13 19:23) falcao

это ясно. получается длина прямоугольника, которая равна $%n$% тут не играет большой роли, $%2^n$% это количество прямоугольников, составленных из $%n$% разноцветных клеток и не обязательно у них одна сторона будет $%n$%, но и для таких прямоугольников это верно, так?

(20 Окт '13 20:55) Dragon65

Если Вы имеете в виду, что для прямоугольника размером $%m\times n$% ответом на аналогичный вопрос будет $%2^{mn}$% (так как $%mn$% -- количество клеток), то это совершенно верно. То есть фигура может иметь какую угодно форму, но влияет не она, а лишь общее число клеток.

(20 Окт '13 21:09) falcao

Спасибо $%:)$%

(21 Окт '13 15:33) Dragon65

А, ещё один последний в этой теме вопрос: например есть 8 клеточная ячейка(вписывать можно только 0 и 1) количество способов вписываний с повторениями будет $%2^8=256$%- и вот мне интересно, то, каким образом до этого "догадались", исходя из рассуждений которые привели Вы в своем ответе(они как бы базовые)и отсюда $%N=2^i$% где $%i$% количество "мест" и N-количество расстановок?

(21 Окт '13 15:37) Dragon65

@Dragon65: размещения с повторениями -- это самая простая конструкция в комбинаторике. Догадаться, не зная теории, можно в процессе анализа случаев, когда мест одно, два, три и так далее. А из правила произведения это следует напрямую, так как на каждом этапе у нас два случая, а самих этапов, скажем, $%n$%. Тогда перемножается $%n$% двоек (строго по правилу!) и получается $%2\cdot2\cdot\ldots\cdot2=2^n$%. Это частный случай ситуации $%m_1m_2\ldots m_n$% при $%m_1=\cdots=m_n=2$%.

(21 Окт '13 15:50) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
0

Рассмотрим двоичное число некоторой длины. Пусть в нем 0 - белая клетка, а 1 - черная. Тогда рассмотрим все двоичные числа от 0 до числа состоящего из n единиц (числа длиной меньшей n будем дополнять незначащими нулями). Тогда легко убедится, что так мы переберем все раскраски, а их количество будет очевидно: $$ 2^n $$

Например для двух у нас получаются числа: 00 01 10 11

ссылка

отвечен 20 Окт '13 11:17

изменен 20 Окт '13 11:18

Или можно построить все такие числа так: пусть мы ставим на i-ую позицию 0 или 1. Тогда с i-ой позиции у нас есть два перехода на i + 1-ую. Либо поставить туда 1, либо поставить туда 0(рекурсия). Тогда получается двоичное дерево, а количество листьев в нем(т.е. искомых чисел) в нем будет как-раз 2^n

(20 Окт '13 11:25) algogol
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×790

задан
20 Окт '13 9:47

показан
708 раз

обновлен
21 Окт '13 15:50

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

по почте:

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

по RSS:

Ответы

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

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