Комбинаторика, подсчет комбинаций Опции

[Alenka123]

Помогите поссчитать ,пожалуйста.Вроде несложно,но перебором что-то не получается все учесть.

Квадрат разделен на 9 равных квадратиков.
Он состоит соответственно из 4 белых,3 синих и 2 красных цветов.

Сколько существует симметричных таких квадратов относительно оси,проходящей через середину одной из сторон.

Сообщение отредактировано: Alenka123 - 15.12.2007 1:50

[Michael_Rybak]

Эта задача - точно по математике? Тебе нужно формулами посчитать, или программу написать? (потому что если ты про перебор - то это уже не математика, а информатика)

[Alenka123]

Мне нужно просто поссчитать.Там типа число сочетаний и все такое. По формуле С из n по k и т.д.

[Michael_Rybak]

Ок, давай решать.

Шаги такие:

1. Легко видеть, что квадратов, симметричных относительно обеих осей одновременно - нет (почему?). Поэтому посчитаем количество квадратов, симметричных относительно вертикальной оси, и умножим это число на 2 (т.к. "горизонтальных", очевидно, столько же).

Таким образом, нас интересуют квадраты вида:

Код

a d a
b e b
c f c

Под разными переменными могут стоять одинаковые цвета, но разные цвета не могут стоять под одинаковыми переменными.

2. Сразу понятно, что e = синий (почему?)

Таким образом, переменным a, b, c, d, f нужно поставить в соответствие цвета (белый, синий, красный) так, чтобы в наборе (a, a, b, b, c, c, d, f) белый встретился 4 раза, а синий и красный - по два.

Отсюда сразу заключаем, что d = f (почему?).

3. Перепишем условие с учетом того, что d = f:

Переменным a, b, c, d нужно поставить в соответствие цвета (белый, синий, красный) так, чтобы в наборе (a, a, b, b, c, c, d, d) белый встретился 4 раза, а синий и красный - по два.

"Сократим" это условие на 2 (в наборе каждая переменная встречается дважды):

Переменным a, b, c, d нужно поставить в соответствие цвета (белый, синий, красный) так, чтобы в наборе (a, b, c, d) белый встретился 2 раза, а синий и красный - по одному.

Дальше сможешь?

Не забудь умножить на 2 в конце.

[Alenka123]

Спасибо большое за ответ.Сейчас все прочитаю,разберусь и отвечу...

Добавлено через 8 мин.
Michael_Rybak

А дальше просто считаем по формуле С из 4 по 2 и умножить на С из 2 по 1?

[Michael_Rybak]

Да, молодец.

[Alenka123]

Спасибо

[Alenka123]

Michael_Rybak
Я тут опять начала разбираться и получилось,что не обязательно е-синий.Можно привести примеры,когда е-не синий.Другое дело,что из d,е,f обязательно будет кто-то синий.А как тогда решать?Может просто потом умножить результат еще на 3,так как типа того,что мы сначала решили,что допустим е-синий,а потом предполагаем относительно d,потом относительно f?
И еще,существует квадрат ,симметричный относительно обоих осей(соже легко приводится пример)



Добавлено через 6 мин.

Michael_Rybak
Я тут опять начала разбираться и получилось,что не обязательно е-синий.Можно привести примеры,когда е-не синий.Другое дело,что из d,е,f обязательно будет кто-то синий.А как тогда решать?Может просто потом умножить результат еще на 3,так как типа того,что мы сначала решили,что допустим е-синий,а потом предполагаем относительно d,потом относительно f?
И еще,существует квадрат ,симметричный относительно обоих осей(соже легко приводится пример)

Да,а еще ,если не трудно,не подскажите,как таким образом подсчитать квадраты,симметричные относительно какой-либо диагонали?

[Michael_Rybak]

Оу, вот это я неплохо затупил, прости, Аленка

Ты права, нужно еще умножить на три.

Квадратов, симметричных относительно обеих осей - всего 2. Если опять не туплю. Какой ужас. Спишем на позднее время.

Так вот, когда умножили на три, нужно еще вычесть вот эти два квадрат, симметричные относительно обеих осей, т.к. каждый из них посчитали дважды - в горизонтальных и в вертикальных.

Относительно диагонали точно так же - обозначаем одинаковыми буквами одинаковые квадратики, и считаем:

a b c
b d e
c e f

Выбираем, где из a, d, f будет синий, и дальше - идентичное решение. Только что квадратов, симметричных относительно главной диагонали не 2, а 0.

[Alenka123]

Так относительно обоих диагоналей тоже есть 2 квадрата.

[Michael_Rybak]

Блин. Действительно. Ну теперь спишем на ранее время

[Alenka123]

Вроде симметрию рассмотрели правильно.Только все равно у меня где-то ошибка,потому что вообще мне надо рассмотреть сколько всего таких различных квадратов.То есть надо еще рассматривать повороты на 0,90,180,270 градусов.И потом сумму всех этих фиксирующих множеств делить на 8(4 поворота и 4 симметрии) и должно получиться целое число,а получается не целое.
Только вот не найду,где ошибка.
Получается,что в поворотах.Но понятно,что при повороте на 90 и 270 градусов раскраска не сохраняется.
На 180 получается 12.
На 0 получается С из 9 по 4 * С из 5 по 2.
При обеих симметриях получается по 72-2одинаковых,то есть 140.

[Michael_Rybak]

Подожди, тебе нужно посчитать, сколько таких разных квадратов, которые друг в друга не переходят при повороте и симметричном отражении?

[Alenka123]

Нужно соссичтать,сколько различных квадратов,окрашенных в 4 белых,3 синих и 2 красных цвета,если окраска считается одинаково при подходящем повороте и подхожящей симметрии.
И считаем по лемме Бернсайда,то есть сумма всех фиксирующих множеств делится на 8(4 поворота и 4 симметрии)

Добавлено через 10 мин.
Ошибка вроде в том,что когда мы умножаем на 3(когда сначала считаем,что е-синий и т.д) мы несколько раз считаем тот случай,когда все 3 синих на одной оси.Но вот я не понимаю,сколько тогда надо вычесть квадратов.

[Michael_Rybak]

А, так 2 отнимать не нужно, ты ведь четыре симметрии рассматриваешь отдельно, и за каждую симметрию добавлять нужно по 36.

Добавлено через 2 мин.

Ошибка вроде в том,что когда мы умножаем на 3(когда сначала считаем,что е-синий и т.д) мы несколько раз считаем тот случай,когда все 3 синих на одной оси.Но вот я не понимаю,сколько тогда надо вычесть квадратов.

Точно.

Вычесть нужно 2 * количество квадратов, у которых d = e = f = синий. Т.е. 2 * C из 3 по 2.

Добавлено через 49 сек.
(потому, что каждый из этих квадратов посчитан трижды).

[Alenka123]

Да,спасибо,не надо 2 отнимать ,все получилось.


Добавлено через 1 мин.
Без Вас бы не решила.

[Michael_Rybak]

Хехе, я бы без тебя - тоже