Руководитель проекта
Прошу прощения за прошлую тему. C правилами ознакомился.

Подскажите как решить задачу?
Есть 3 красных шара 3 синих и 3 черных.
Сколькими способами можно расставить в ряд шары, так что бы ни какие 2 шара одного цвета не стояли рядом?

Подскажите хоть в каком направлении "рыть"

Дык непросто. Видимо. Сходу мысли не приходят.

to venja

Я сам голову ломал неделю так чего-то и не получается. Вот решил спросить. Видимо точно не просто.

А нельзя так:6*4*4?

6*4*4
Это как понимать? В смысле пояснить

Можно, конечно, дерево построить... Но это уж конечно крайний случай. Пока ничего лучше в голову не пришло.

to A_nn
Это уж действительно крайний вариант

"6*4*4"
Да, это не правильно.

А можно мне сказать? Я вот забил на мудрые формулы и по-простому построил дерево. Привожу текст программы для Excel:
Нажмите для просмотра прикрепленного файла
Программа нашла 174 варианта размещения. В отсутствии "двойников" я убедился кондово - затянул найденные расстановки в Access и построил по этому полю индекс без повторений. Проблема в другом: как доказать, что я ни чего не пропустил? Программа не может являться доказательством. Может быть кто-нибудь предложит вариант, отсутствующий среди найденных?

to Ботаник

я тоже на delphi прогу написал, просто перебрал все варианты получилось 174 как и у тебя. А вот как быть с мудрыми формулами???

Программа, которую ты накарябал, и есть твоё

решение этой задачи.

Вот если преподаватель не примет его, тогда и будем думать

Если эта комбинаторная задача задана математиком, а не преподавателем информатики, то скорее всего он будет требовать аналитическое решение, а не программу.

Рассуждения Liona подтолкнули меня довести это направление до конца, т.е. сделать в лоб
Разбиваем ряд из 9 шаров на последовательные тройки.
Занумеруем шары разными цифрами для удобства

Дальше рассматриваем случаи
1.случай, когда в каждой тройке все шары разного цвета
123 123 123
321 213 213
и т.д.
3!*4*4=96 способов

2. случай, когда во всех тройках есть 2 шара одинакового цвета
121 313 232
212 323 131
и т.д.
3!=6 способов

3. случай, когда на первом месте стоит тройка шаров с разными цветами,
при этом в двух оставшихся тройках будет по 2 шара одинакового цвета
идентичен случаю 4

4. случай, когда на последнем месте стоит тройка, в которой все шары разного цвета,
при этом в двух оставшихся тройках будет по 2 шара одинакового цвета
121 323 123
212 313 123
313 212 123
131 232 123
4*3!=24 способов

5. случай, когда тройка шаров с разными цветами стоит посередине,
при этом в двух оставшихся тройках будет по 2 шара одинакового цвета
232 123 131
313 123 212
323 123 121
232 123 131

4*3!=24 способов, когда тройка, в которой все шары разного цвета, посредине

Считаем: 96+6+24+24+24=174, что собственно и нужно
Если у нас ответы совпали, то, скорее всего, я ничего не упустил (хотя всё может быть)
И не придется рисовать никаких деревьев

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

Да, я потом поняла, что ограничилась только 1-ым случаем...

to Black Ghost

Задача комбинаторная не информатика.

Спасибо за предоставленный способ.

И Lion спасибо за мысль

Наверно другого решения нет.

Снова очень извиняюсь...

2 sadek:
Вы, уважаемый, чему так радуетесь? Советую сличить решение, данное Black Ghost, с тем, что выдала ваша программа на delphi. Вас ждёт сюрприз. Наверное другое решение всё-таки существует

2 Black Ghost:
Во втором случае у вас шесть вариантов расклада. Могу предложить больше. Например так:
1) КЧК СКС ЧСЧ
2) КЧК ЧСЧ СКС
3) СКС КЧК ЧСЧ
4) СКС ЧСЧ КЧК
5) СЧС КСК ЧКЧ
6) СЧС ЧКЧ КСК
7) КСК ЧКЧ СЧС
и это, увы, не всё…

Да... надо подумать еще
К-1 Ч-2 С-3
121 232 313 меняем всевозможными способами 1, 2, 3 местами 3! -способами
121 313 232 - здесь всё - то же самое 3! способами
я об этом что-то не подумал
2*3!=12
Надо выписать их все... и убедиться, так ли это...

Опытным путем, следуя совету "Ботаник", выяснено
1 способ - 96 вариантов
2 способ - 12 вариантов !!!
3 способ - 24 варианта
4 способ - 18 вариантов !!!
5 способ - 24 варианта
способы согласно предложенных Black Ghost

1) чем этот способ будет отличаться от простроения дерева? Точно такое же нестрогое решение "на пальцах".
2) если во втором варианте раскладов стало больше, то из каких вариантов отнимать, чтобы сумма не изменилась? Или не отнимать? Ведь не факт, что 174 - верное число.

Процесс решения мы заменили подгонкой под готовый (возможно неверный) ответ, найденный экспериментальным путём.

вот и получается во втором способе прибавили 6, а в четветром отняли 6

Да, что-то не получается нормального метода... Единственное, что облегчает задачу, так это фиксирование первых двух шаров (что приводит к уменьшению в 6 раз). Но не избавляет от примитивного перебора...
Надо думать...

Вот это точно