|
Найти количество прямоугольников размера $%1 \times n $%,состоящего из $%n$% клеток,некоторые из которых закрашены в черный цвет. Решение имеется,вопрос именно по нему. Каждая клетка может быть закрашенной или незакрашенной,т.е. цвет клеткиможет быть выбран 2-мя способами независимо от "раскраски" остальной части прямоугольника. Таким образом, по правилу произведения общее кол-во прямоугольников равно $%2^n$%. Я не пойму почему $%2$%(количество способов закраски внутренних клеток) возводится в степень$%n$%(это как я понимаю число всех клеток внутри прямоугольника и длина его стороны)- и с правилом произведения у меня ассоциаций не получается. Объясните пожалуйста каким способом легче всего понять этот ответ и как конкретно здесь действует правило произведения. задан 20 Окт '13 9:47 
Dragon65 |
|
Я так понимаю, Ваш вопрос связан с уяснением того факта, почему правило произведения в данном случае даёт верный ответ, то есть подсчитывает именно число всевозможных закрасок. Объяснение можно дать такое. Прежде всего, вместо закрасок прямоугольника можно рассматривать строки из нулей и единиц: 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 
falcao т.е. получается количество таких прямоугольников будет равно количеству способов переставить внутри клетки, которые могут изменяться 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
|
|
Рассмотрим двоичное число некоторой длины. Пусть в нем 0 - белая клетка, а 1 - черная. Тогда рассмотрим все двоичные числа от 0 до числа состоящего из n единиц (числа длиной меньшей n будем дополнять незначащими нулями). Тогда легко убедится, что так мы переберем все раскраски, а их количество будет очевидно: $$ 2^n $$ Например для двух у нас получаются числа: 00 01 10 11 отвечен 20 Окт '13 11:17 
algogol Или можно построить все такие числа так: пусть мы ставим на i-ую позицию 0 или 1. Тогда с i-ой позиции у нас есть два перехода на i + 1-ую. Либо поставить туда 1, либо поставить туда 0(рекурсия). Тогда получается двоичное дерево, а количество листьев в нем(т.е. искомых чисел) в нем будет как-раз 2^n
(20 Окт '13 11:25)
algogol
|