Ile jest multigrafów o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ k}\) krawędziach? (bez pętli).
Prosiłbym o wytłumaczenie rozwiązania.
Ile jest multigrafów?
-
pajkul
- Użytkownik
- Posty: 31
- Rejestracja: 25 kwie 2012, o 10:16
- Płeć: Mężczyzna
- Lokalizacja: PL
- Podziękował: 4 razy
Ile jest multigrafów?
Podana odpowiedź to
\(\displaystyle{ {k+ {n \choose 2} - 1 \choose {n \choose 2} - 1 }}\)
Gdzie \(\displaystyle{ k}\) to suma liczby wystąpień krawędzi \(\displaystyle{ x_{i}}\) po indeksie \(\displaystyle{ i}\), gdzie \(\displaystyle{ i}\)to liczba całkowita od \(\displaystyle{ 1}\) do \(\displaystyle{ {n \choose 2}}\).
Czy to rozwiązanie jest poprawne? Jeśli tak, to dlaczego.
\(\displaystyle{ {k+ {n \choose 2} - 1 \choose {n \choose 2} - 1 }}\)
Gdzie \(\displaystyle{ k}\) to suma liczby wystąpień krawędzi \(\displaystyle{ x_{i}}\) po indeksie \(\displaystyle{ i}\), gdzie \(\displaystyle{ i}\)to liczba całkowita od \(\displaystyle{ 1}\) do \(\displaystyle{ {n \choose 2}}\).
Czy to rozwiązanie jest poprawne? Jeśli tak, to dlaczego.