Блог пользователя GODF

Автор GODF, 4 года назад, По-английски

Hi. In this comment, there is a formula to count the number of graphs with i vertices having cycle length j. Which is  Can somebody explain the formula ?. I understand that first part. We choose j vertices from i vertices to form a cycle. Then we permute them. which is j!. But I could not figure out the rest.

Thank you for your time in advance.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's derived fairly straightforwardly from Cayley's formula. They even mention that in the thread. Basically, graphs which have exactly one cycle have trees branching out of the cycle; you can see the connection from there.