Математика / Графы, логика

Число ребер полного графа

Формула описывает прием «подсчет пар вершин» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Опубликовано: 2 июня 2026 г.Обновлено: 2 июня 2026 г.

Формула

E(K_n)=\binom n2=\frac{n(n-1)}2

Обозначения

$N$: искомое число вариантов или объектов подсчета, штука
$n$: размер исходного конечного множества или число позиций, штука
$k$: число выбранных элементов, шагов или учитываемых случаев, штука

Условия применения

Все объекты должны соответствовать модели «подсчет пар вершин», без скрытого изменения правил между этапами подсчета.
Множества и варианты считаются конечными; порядок, повторения и несовместность случаев определяют до подстановки чисел.
Если случаи пересекаются, пересечения нужно явно учесть, иначе одни и те же объекты будут посчитаны несколько раз.

Ограничения

Формула «подсчет пар вершин» не исправляет неверную модель: при другом отношении к порядку или повторениям получится другой ответ.
Для бесконечных множеств и зависимых вероятностных моделей прямой конечный подсчет требует отдельного обоснования.
При больших параметрах лучше сохранять факториалы и биномиальные коэффициенты до сокращения, чтобы не вносить арифметические ошибки.

Подробное объяснение

Формула «подсчет пар вершин» переводит словесное условие в точный счет конечных объектов. Ее смысл состоит в выборе модели: считаются случаи, последовательные шаги, группы без порядка, пересечения множеств, рекуррентные члены или пары вершин.

Основание формулы лежит в разбиении множества вариантов. Несовместные случаи складываются, последовательные выборы перемножаются, одинаковые внутренние порядки сокращаются, а пересечения вычитаются и добавляются так, чтобы каждый объект был учтен один раз.

При росте параметров ответ может увеличиваться очень быстро: факториалы, биномиальные коэффициенты и рекуррентные последовательности дают заметный скачок даже при небольшом n. Поэтому полезно сначала оценить масштаб и проверить крайние случаи, например k=0, k=n или пустое пересечение.

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

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

Как пользоваться формулой

Определите объекты, которые считает прием «подсчет пар вершин».
Уточните, важен ли порядок и разрешены ли повторения.
Разбейте условие на случаи, шаги или пересечения.
Подставьте параметры и выполните сокращение выражения.
Проверьте результат малым примером или крайним случаем.

Историческая справка

Элементарная комбинаторика развивалась из счета игр, календарных задач, торговли, переписки и алгебраических разложений. В XVII-XVIII веках Паскаль, Ферма, Якоб Бернулли, Эйлер и другие авторы связали конечный подсчет с вероятностью, биномиальными коэффициентами и алгеброй, хотя многие правила существовали в практическом виде раньше.

Формула «подсчет пар вершин» в нынешней записи является результатом учебной стандартизации XIX-XX веков. Комбинаторные идеи стали использоваться в алгебре, теории графов, статистике и информатике; закрепились обозначения факториала, мощности множества, биномиального коэффициента и рекуррентной последовательности. Поэтому обычно говорят о традиции, а не о единственном авторе.

Историческая линия формулы

У формулы «подсчет пар вершин» нет единственного автора в современном учебном смысле. Ее правильнее относить к длительной комбинаторной традиции, где практические задачи счета, алгебраические обозначения и теория конечных множеств постепенно пришли к компактной записи.

Пример

Задача: применить прием «подсчет пар вершин» к конечному набору вариантов. Дано: имеется 8 различных объектов, нужно выполнить выбор по правилу, соответствующему формуле, и найти число вариантов. Подстановка: сначала определяем, важен ли порядок и есть ли пересечения; затем записываем параметры n=8 и k=3 либо соответствующие мощности множеств. Выполняем вычисление по формуле и получаем числовой ответ. Ответ: количество вариантов равно найденному значению в штуках. Проверка: на маленькой модели с n=3 можно перечислить все варианты вручную и увидеть, что каждый объект подсчета появляется ровно один раз.

Частая ошибка

Для полного графа важно, что ребро между двумя вершинами неориентированное и петли не считаются. Если считать упорядоченные пары, получится n(n-1), то есть каждое ребро будет учтено дважды; деление на 2 исправляет именно это. При наличии направленных дуг, кратных ребер или разрешенных петель формула уже другая. Малый контроль: у K_4 должно быть 6 ребер, потому что пар вершин ровно шесть.

Практика

Задачи с решением

Посчитать малую модель

Условие. Применить ту же формулу к параметрам 4 и 2.

Решение. Определяем порядок и повторения, затем подставляем малые параметры в формулу.

Ответ. Получается ответ, проверяемый прямым перечислением.

Проверить крайний случай

Условие. Подставить минимальный допустимый параметр.

Решение. Сравниваем результат с очевидным смыслом пустого выбора, одного случая или одной вершины.

Ответ. Формула согласуется с прямым смыслом.

Дополнительные источники

Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics
Rosen K. H. Discrete Mathematics and Its Applications
van Lint J. H., Wilson R. M. A Course in Combinatorics

Связанные формулы

Математика

Правило суммы в комбинаторике

$N=m_1+m_2+\cdots+m_k$

Формула описывает прием «сложение несовместных случаев» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Правило произведения в комбинаторике

$N=m_1m_2\cdots m_k$

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число перестановок без повторений

$P_n=n!$

Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число размещений без повторений

$A_n^k=\frac{n!}{(n-k)!}$

Формула описывает прием «упорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число сочетаний без повторений

$C_n^k=\binom nk=\frac{n!}{k!(n-k)!}$

Формула описывает прием «неупорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.