Комбинаторная задача

[Klein]

Picetto писал(а):

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

Я в Питоне насчитал 26922

from itertools import combinations, product

def valid_arrangement(arrangement):
    """ Проверить, является ли расположение допустимым (нет соседних одинаковых бусин). """
    return all(arrangement[i] != arrangement[i + 1] for i in range(len(arrangement) - 1))

def count_circular_jewelry(bead_types=7, total_beads=17):
    half_length = (total_beads - 1) // 2  # Длина одной половины, исключая среднюю бусину
    total_count = 0

    # Итерация для 2 и 3 типов бусин
    for num_types in [2, 3]:
        for beads in combinations(range(bead_types), num_types):
            # Итерация по всем возможным расположениям для первой половины
            for arrangement in product(beads, repeat=half_length):
                if valid_arrangement(arrangement):
                    # Для каждого допустимого расположения, итерация по возможным средним бусинам
                    for middle_bead in beads:
                        if middle_bead != arrangement[-1]:  # Проверка условия смежности с средней бусиной
                            full_arrangement = arrangement + (middle_bead,) + arrangement[::-1]
                            if valid_arrangement(full_arrangement):  # Проверить полное кольцевое расположение
                                total_count += 1

    return total_count

# Подсчет количества различных дизайнов бус
count_circular_jewelry()

[svv]

Посчитал на компьютере в лоб (сгенерировал ожерелья и из них пересчитал подходящие под условия). У меня получился тот же ответ $26712$, что и в книге. Как уже несколько раз объяснили, у тех, кто насчитал $26922$, ошибка в том, что ожерелья, в которых использованы два цвета, считаются несколько раз. Задавая три разрешённых цвета, вы не отсеиваете ожерелья, где реально использовано только два цвета.

Klein
В число ожерелий из трёх возможных цветов $1,2,3$ Ваша программа включает и такие (от центральной бусины к краю):
121212121
212121212
131313131
313131313
232323232
323232323
Мало того, что каждое из них считается и при num_types=2, так и при num_types=3 каждое из них посчитается пять раз. Например, 121212121 посчитается при таких наборах из трёх возможных цветов: $(1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,2,7)$. Поскольку двухцветных ожерелий $7\cdot 6=42$, для коррекции вашего ответа надо из $26922$ вычесть $5\cdot 42=210$, получится верный ответ $26712$.

-- Чт янв 04, 2024 06:13:47 --

Picetto в сообщении #1624801 писал(а):

когда мы считаем для трех ВИДОВ, мы считаем для трех разных видов тоесть в самой бусе там три разных бусин и их перестановки, учитывая условие первую бусину при размещении мы можем выбрать из трех разных Видов бусин, а потом остается только 2

Пусть у нас три разрешённых цвета: $1,2,3$. Выбираем для первой (центральной) бусины цвет $1$. Дальше для каждой следующей бусины есть два варианта. Всего $256$ вариантов. Но, внимание, среди них есть и такой:
121212121
Образно говоря, Ваша формула $3\cdot 2^8$ «не следит», чтобы были использованы все три цвета. И несмотря на заклинания, в списке «трёхцветных» ожерелий двухцветные встречаются тоже, потому что три — это просто количество разрешённых цветов.

[Vadim32]

#include <stdio.h>
#include <set>
using namespace std;
typedef int COLOR;
static const int MAX_N=9;

COLOR busins[9];
int number_of_ok=0;

void try_next(int n, set<COLOR> color_set, COLOR last_color)
{  
   if(n==MAX_N)
   {  number_of_ok++;
      return;
   }
   else
   {  
      for(int next_color=0; next_color<7; next_color++)
      {  if(next_color!=last_color)
         {  if(color_set.size()<3)
            {  set<COLOR> next_color_set=color_set;
               next_color_set.insert(next_color);
               try_next(n+1, next_color_set, next_color);
            }
            else
            {  if(color_set.find(next_color)!=color_set.end())
               {  try_next(n+1, color_set, next_color);
               }
            }
         }
      }
   }
}

int main(int argc, char* argv[])
{
   for(int color=0; color<7; color++)
   {  set<COLOR> color_set;
      color_set.insert(color);
      try_next(1, color_set, color);
   }
   printf("result=%d\n", number_of_ok);
   return 0;
}

получилось
result=26712

[Klein]

svv

Увидел ошибку. Исправил и насчитал 26712 в этот раз.

from itertools import combinations, product

def valid_arrangement(arrangement):
    """ Проверить является ли расположение допустимым (нет соседних одинаковых бусин). """
    return all(arrangement[i] != arrangement[i + 1] for i in range(len(arrangement) - 1))

def count_circular_jewelry(bead_types=7, total_beads=17):
    half_length = (total_beads - 1) // 2  # Длина одной половины, исключая среднюю бусину
    total_count = sum(
        valid_arrangement(arrangement + (middle_bead,) + arrangement[::-1])
        for n in [2, 3] for beads in combinations(range(bead_types), n)
        for arrangement in product(beads, repeat=half_length)
        for middle_bead in beads if middle_bead != arrangement[-1]
    )
    # Корректировка учета двойного подсчета
    return total_count - 5 * len(list(combinations(range(bead_types), 2))) * 2

# Подсчитать количество различных бус
count_circular_jewelry()

[sergey zhukov]

А, ну понятно. $3\times 2^8$ - это получено по принципу "у следующей бусины два варианта по отношению к предыдущей". Тогда, конечно, здесь уже все комбинации учтены, включая и двухцветные. Причем эти же двухцветные бусы будут повторно получены и в других "трехцветных" группах из тех 35 и поэтому подсчитаны по нескольку раз каждая. В общем, все, как уже svv объяснил.

[Yadryara]

Yadryara в сообщении #1624807 писал(а):

надо идти от простого к сложному. Попробуйте расписать для ожерелья из 7, а затем и из 9 бусин.

А я всё-таки решил пойти именно так, аналитически, без компьютерного перебора. И вывел формулу

$$ k = 2\cdot21 + 6\cdot{35}\cdot(2^ {\frac{l-3}2} -1)$$

Где $l\geqslant3$ — нечётная длина ожерелья. В частном случае, для $l=17$ , как раз и даёт $k=26712$