Для полного пронумерованного графа

количество связных подграфов (порядка

)равно

Где сумма берется по всем разбиениям(их будет

) числа

на упорядоченные натуральные слагаемые.
Это мое решение.
Более простая формула
здесь.
Результаты
здесь.
Если вам нужно количество связных подграфов размера

в

то надо результат умножить на

.