комбинаторная задачка про спички

stat3032681

Есть n спичек. Сколько различных картинок можно из них составить?
Например, для трех спичек:
1) Все спички раздельно
2) Две спички соединены, одна отдельно
3) Три спички соединены в ряд
4) Три спички соединены в треугольник
Итого: 4 различные картинки.

antcatt77

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

stat3032681

спички можно соединять только концами... и считаем, что спички могут сжиматься и растягиваться, до любого размера...
задачу можно переформулировать на языке графов: сколько неизоморфных графов можно составить из n ребер?

kachokslava

органическую химию про изомеры поботайте ;)

stat3032681

почитал wikipedia про химию, очень похожие вещи, но насколько я понял, там все в основном перебором решается...
Мне бы хотелось знать, существует ли общее математическое решение для этой задачи?

iri3955

Ну, тогда еще 3 спички торчат из одной точки. И две спички соединены в кольцо, а третья либо отдельно, либо одной вершиной с ними, либо двумя. А если еще петли разрешить...

stat3032681

ну да, это подходит... но для простоты можно считать, что два ребра не могут соединяться двумя концами одновременно и петли запрещены...
в общем виде у меня сейчас только одна идея: занумеровать концы спичек и составить матрицу соединений, т.е. получаем матрицу 2n*2n, после этого можно определить классы эквивалентности для таких матриц, например, используя перестановки... количество классов эквивалентности = количество различных рисунков... но это больше алгоритмический подход...

roza200611

в общем виде у меня сейчас только одна идея: занумеровать концы спичек и составить матрицу соединений, т.е. получаем матрицу 2n*2n, после этого можно определить классы эквивалентности для таких матриц, например, используя перестановки... количество классов эквивалентности = количество различных рисунков... но это больше алгоритмический подход...
и незамедлительно выпить...

kachokslava

связный граф без циклов - дерево.
деревьев n^(n-2 если спички занумерованы.
для незанумерованных:
Counting the number of unlabeled free trees is a harder problem. No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. The first few values of t(n) are 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ... (sequence A000055 in OEIS). Otter (1948) proved the asymptotic estimate:
{t(n) \sim C \alpha^n n^{-5/2} \quad\text{as } n\to\infty,}
with C = 0.534949606… and α = 2.99557658565…. (Here, f∼g means that \lim_{n \to \infty} f/g = 1 .) This is a consequence of his asymptotic estimate for the number r(n) of unlabeled rooted trees with n vertices:
r(n) \sim D\alpha^n n^{-3/2} \quad\text{as } n\to\infty,
with D = 0.43992401257… and α the same as above (cf. Knuth (1997 Chap. 2.3.4.4 and Flajolet & Sedgewick (2009 Chap. VII.5).

iri3955

Автор имел ввиду без циклов длины 1 и 2.
Оставить комментарий
Имя или ник:
Комментарий: