Формула вариаций деталей m-угольника с n-сторонами

[kthxbye]

Продолжая вот эту тему, или, скорее, раскрывая подробности, как я к этому пришел.

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



Выделим стороны, которые там используются:



Если отбросить боковые позиции (1 и 5), для всех сторон у нас остается всего две вариации - 101(A) и 010(B). Сколько будет вариаций деталей, если мы будем использовать только A и B, меняя боковые позиции (1,5) на 0,1?

Но к такому вопросу я пришел не сразу. Я просто решил, что можно брать сразу всю сторону, не разбивая ее на центральную и боковые. При повороте код детали меняется, но она остается без изменений. Т.е. если мы берем 2 стороны (длинною в 5 квадратов), обозначаем их 1,2, то код детали например 1112 будет идентичен 1121, 1211, 2111. Строим таблицу и вычеркиваем дубликаты:

1111 1211 2111 2211
1112 1212 2112 2212
1121 1221 2121 2221
1122 1222 2122 2222

Т.е. если у 1112 по 3 "дубликата", то у 1212 всего 1. Таким образом у нас остались детали: 1) 1111,2222; 2) 1112,1122,1222; 3) 1212;

Строим аналогичную таблицу, но уже для трех сторон и замечаем следующие закономерности:

1) Площадь первой таблицы - 4х4, второй - 9х9, т.е. $2^4$ и $3^4$, где 4 - кол.-во сторон у детали (m), а 2 и 3 - кол.-во разных деталей (n);
2) Кол.-во деталей вида 1111 равно n;
3) Кол.-во деталей вида 1111 и 1212 (с дубликатами) равно $n^2$;
4) Кол.-во остальных деталей без дубликатов равно $\frac{n^m-n^2}{m}$;
5) Кол.-во деталей вида 1111 и 1212 (без дубликатов) равно $\frac{n(n+1)}{2}$;
6) Итого уникальных деталей $\frac{n^m-n^2}{m}+\frac{n(n+1)}{2}$;

Подставляем $m=4$, получаем ряд 1, 6, 24, 70, 165, 336, 616, 1044, 1665, 2530, 3696, 5226...

И все бы хорошо, но для $m=3$ не все значения целые. Значит для нечетных какая-то другая формула. Строим таблицу:

111 211
112 212
121 221
122 222

111 211 311
112 212 312
113 213 313
121 221 321
122 222 322
123 223 323
131 231 331
132 232 332
133 233 333

Находим, что:
1) Площадь таблицы $n^m$;
2) Деталей вида 111 - n;
3) Остальных без дубликатов - $\frac{n^m-n}{m}$;

Тут опять загвоздка - не все значения целые для составных нечетных. Временно оставив этот вопрос, я решил проверить формулу для $m=4$. Так как мы упростили сторону детали от 5, до 3 за счет выделения только двух центральных вариантов сторон - A и B, которым мы присвоили значения 0,1, сторона квадрата уменьшилась до 3 (1 центральная, 2 боковых). Т.е. деталь приняла вид:

БЦБ
ЦХЦ
БЦБ

Х - неизменный центр, центральные образуют крест. Далее я стал заполнять их единицами и нулями, мысленно удалял дубликаты, потом построил соответствующие модели:





Всего их получилось 70. Вспомним ряд 1, 6, 24, 70, 165, 336, 616, 1044, 1665, 2530, 3696, 5226...

Но центральных детали было всего две - A и B. А в ряду 70 стоит 4-м членом. Почему? Я решил сгуппировать детали по центральному основанию:





Выделилось всего 6 таких оснований:

Х0Х | Х1Х | Х1Х | Х1Х | Х1Х | Х1Х |
0Х0 | 0Х0 | 0Х1 | 0Х0 | 1Х1 | 1Х1 |
Х0Х | Х0Х | Х0Х | Х1Х | Х0Х | Х1Х |

Для каждого из них мы меняем боковые X на 0,1 и получаем: 1) 6 вариаций для детали с центральным основанием 0000; 2) 16 для 1000; 3) 10 для 1010; 4) 16 для 1100; 5) 16 для 1110; 6) 6 для 1111;

6+16+10+16+16+6=70. Почему именно 6, 10 и 16? Вариаций заполнения боковых у нас 16:

1) 0001, 0010, 0100, 1000;
2) 1010, 0101;
3) 1100, 1001, 0011, 0110;
4) 1110, 1101, 1011, 0111;
5) 0000, 1111;

Для моделей с центральным основанием 0000/1111 при повороте все вариации заполнения боковых п.1-4 равнозначны, т.е. суммарно 4 плюс еще 2 из п.5, получаем 6; с центральным основанием 1000, 1100, 1110 каждый вариант уникален, т.е. все 16; и, наконец, для 1010 равнозначны пары боковых:

1) 0010 и 1000, 0100 и 0001;
2) 0110 и 1001; 1100 и 0011;
3) 1110 и 1011; 0111 и 1101;

Т.е. 6 пар, удаляя дубликаты остается 10. А дальше начинается самое интересное:

1) 6х2 (12) 10х1 (10) 16х3 (48), 2+1+3=6, 12+10+48=70;
2) 6х3 (18) 10х3 (10) 16х18 (288), 3+3+18=24, 12+10+48=336;
3) 6х4 (24) 10х6 (10) 16х60 (960), 4+6+60=70, 12+10+48=1044;
4) 6х5 (30) 10х10 (10) 16х150 (2400), 5+10+150=165, 12+10+48=2530;

Вспомним ряд 1, 6, 24, 70, 165, 336, 616, 1044, 1665, 2530, 3696, 5226... и формулу: $\frac{n^m-n^2}{m}+\frac{n(n+1)}{2}$

Получив опытным путем п.1, я предположил, что возможна аналогия п.2 и далее. Это оказалось истиной. Но здесь я принял $\frac{n(n+1)}{2}$ из формулы, за 1,3,6,10 (которые мы умножаем на 10). На самом деле этот ряд получается здесь формулой $\frac{n(n-1)}{2}$;

Выше я рассматривал:
3) Кол.-во деталей вида 1111 и 1212 (с дубликатами) равно $n^2$;
5) Кол.-во деталей вида 1111 и 1212 (без дубликатов) равно $\frac{n(n+1)}{2}$;

Потому что это было удобно по таблице. Оказывается:
1) Кол.-во деталей вида 1212 (без дубликатов) равно $\frac{n(n-1)}{2}$;
2) Кол.-во их дубликатов также равно $\frac{n(n-1)}{2}$;

Отсюда $n^2$ из п.3 мы получаем благодаря $n+2\frac{n(n-1)}{2}$, а $\frac{n(n+1)}{2}$ из п.5 - $n+\frac{n(n-1)}{2}$;

Это квадрат. С шестиугольником интереснее. У него два различных делителя - 2,3. Результат конечной формулы зависит от количества различных делителей. Общий ее вид такой:

$\frac{n^m-n-ab}{m}+n+ac$, где $a=\frac{n(n-1)}{2}$, а b и c зависят от делителей. Для простых чисел они, видимо, равны нулю.

Рассмотрим на шестиугольнике. Мы можем разбить его на 3 части, каждая из которых должна быть одинаковой. В данном случае вариант один - 12. Итого имеем 121212. Ее дубликат - 212121. Если разбиваем на 2 части, то тут уже два варианта - 112 и 122. Соот.-но имеем 112112, у которой 2 дубликата - 121121, 211211, а также 122122 (дубликаты - 221221, 212212). Таким образом:

1) Кол.-во деталей вида 121212 (без дубликатов) равно $\frac{n(n-1)}{2}$;
2) Кол.-во их дубликатов также равно $\frac{n(n-1)}{2}$;
3) Кол.-во деталей вида 112 (без дубликатов) равно $2\frac{n(n-1)}{2}$;
4) Кол.-во их дубликатов равно $4\frac{n(n-1)}{2}$;

1+1+2+4=8=b, 1+2=3=c;

Возникли следующие вопросы:

1) Сколько существует вариантов отрезка, который потом будет дублироваться в зависимости от его длины? Например:

а) 2 - 12 (21);
б) 3 - 112(121,211), 122(221,212);
в) 4 - 1112(1121,1211,2111), 2221 (2212,2122,1222), 1122(1221, 2211, 2112);

Для 5 уже интереснее, там я начинаю сомневаться. Можно ли вывести какую-то формулу?
2) Можно ли какой-либо формулой выделять различные делители числа, а потом, умножая на формулу выше (если та существует), получать b и c?

[kthxbye]

Не актуально. Ну как, частично. Если кому интересно, решение такое. Общая формула, напомню:

kthxbye писал(а):

$\frac{n^m-n-ab}{m}+n+ac$, где $a=\frac{n(n-1)}{2}$, а b и c зависят от делителей.

Есть две последовательности (обе гуглятся в OEIS):
1) 1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630...$k_n$
2) 0, 0, 1, 2, 4, 6, 12, 18, 34, 58, 106, 186, 350, 630...$p_n$

Пара первых значений (при n=0,1) нас не интересует. Что там за формулы не понял - все на английском, плюс записаны текстом. Рассмотрим на примере: n=12, его делители - 2,3,4,6. Тогда $c$ можно найти двумя способами:
1) суммировать $k_2, k_3, k_4, k_6$: 1+2+3+9=15;
2) $p_{12}-k_{12}=15$;

Чтобы получить $b$, надо:
1) составить последовательность $j_n=k_n(n-1)$ (-1, 0, 1, 4, 9, 24, 45, 108, 210, 448, 891, 1860, 3685, 7560...$j_n$);
2) суммировать $j_2, k_3, k_4, k_6$: 1+4+9+45=59;
3) прибавить результат к $c$: 59+15=74;

Последовательность $g_n$ при которой $g_{12}-j_{12}=59$ в OEIS не нашел. Может быть и ее можно как-то вывести.

[kthxbye]

Решение выше справедливо только для $n=2$, потому что $a=\frac{n(n-1)}{2}=\frac{2(2-1)}{2}=1$. Оно вообще оказывается не нужно. Тогда общий вид:

$\frac{n^m-(b+n)}{m}+(c+n)$

В OEIS есть последовательности, образованные непонятной для меня формулой, например A027375, A027376, A027377 (наша $n=2,3,4$). Их можно использовать для нахождения $b=k_{a}+k_{b}+..+k_{z}$ и $c=h_{a}+h_{b}+..+h_{z}$, где $k_{m}$ - одна из указанных выше последовательностей (в зависимости от n), $h_{m}=\frac{k_{m}}{m}$, $a,b..z$ - делители (или множители) числа $m$ (кроме него самого и единицы).

Имея $b$ для $n=2$ проверил это так:

$\frac{n^m-\mod\frac{n^m}{m}}{m} = x; x-k_{m} = z; z\cdot m +\mod\frac{n^m}{m} = b+n;$

Хотелось бы понять, что за формула у последовательностей выше. И еще у вот этой - A052823, которая равна $h_{m}+c$ (при $n=2$, для других не нашел).

[kthxbye]

Спрашивал вот тут, но видимо шапка темы пугает, и до вопроса никто уже не доходит.

Не понимаю что за формулы у схожих последовательностей A027375, A027376, A027377 и у отличной от них A052823.

Буду очень признателен за даже поверхностное объяснение, не говоря уже о подробном.

[Lia]

Темы объединены. kthxbye, замечание за искусственный подъем темы созданием новой.

[arseniiv]

Ну вот, скажем, первая из них, первая предлагаемая формула:

http://oeis.org/A027375 писал(а):

a(n) = sum(d|n, mu(d)*2^(n/d)).

Это

$$a(n) = \sum_{d\mid n} 2^{n/d} \mu(d);$$

$d\mid n$ означает «$d$ делит $n$», и сумма по $d\mid n$ означает сумму по всем делителям $d$ числа $n$; $\mu$ — это, думается, функция Мёбиуса.

-- Вс апр 23, 2017 01:28:58 --

У последней указана формула для производящей функции (generating function).

-- Вс апр 23, 2017 01:33:04 --

Потом, там есть связь с A000031, а для той есть формула не только производящей функции.

[kthxbye]

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

$\frac{n^m-\sum\limits_{d_1|m}^{}(\sum\limits_{d|d_1}^{}n^{\frac{d_1}{d}}\mu(d))}{m}+\sum\limits_{d_1|m}^{}(\frac{1}{d_1}\cdot\sum\limits_{d|d_1}^{}n^{d}\mu(\frac{d_1}{d}))=\frac{1}{n}\cdot\sum\limits_{d|n}^{}m^{\frac{n}{d}}\varphi(d)$

Здесь $d$ - все делители (включая само число), $d_1$ - все, кроме самого числа. Формула вертикальная, то бишь выводилась для фиксированного $n$ и динамичного $m$. В горизонтальной везде $\varphi$, а тут еще и $\mu$.