Number of loops of size k starting from a specific node

Problem

Given two positive integers n and k, consider a complete undirected graph with n nodes. Find the number of distinct cycles (loops) of length k that start and end at a specific node, visiting exactly k nodes (nodes may not repeat except for the start/end).

Examples

Example 1

Input:
n = 3, k = 3
Output: 2
Explanation: See the graphs below for 2 paths:
- 1 -> 2 -> 3 -> 1
- 1 -> 3 -> 2 -> 1

graph LR;
	A(1) --- B(2) --- C(3) --- A
	D(1) --- F(3) --- E(2) --- D

Example 2

Input:
n = 4, k = 2
Output: 3

Solution

Method 1 – Combinatorial Recurrence

Intuition

In a complete graph, every node is directly connected to every other node. To count the number of cycles (loops) of length $k$ that start and end at a specific node, we need to consider all possible ways to visit $k-1$ other nodes (since the start/end node is fixed), making sure that:

• Each node in the cycle (except the start/end) is visited exactly once (no repeats).
• The path returns to the starting node after $k$ steps.

At first glance, it might seem like we can simply count all possible sequences of $k-1$ nodes chosen from the remaining $n-1$ nodes, but this would overcount cycles that revisit nodes or form smaller loops within the $k$ steps. We need a way to count only the valid cycles of length exactly $k$.

Approach

Let $f(n, k)$ be the number of cycles of length $k$ that start and end at a specific node in a complete graph with $n$ nodes.

1. First Step:

• We start at a fixed node. For the first move, we can go to any of the $n-1$ other nodes.

2. Subsequent Steps:

• For each of the next $k-2$ steps, we must move to a new node that we haven't visited yet (to avoid revisiting nodes and forming smaller cycles). For each step, there are fewer choices, but in a complete graph, the number of ways to choose a sequence of $k-1$ distinct nodes is $(n-1) \times (n-2) \times \ldots \times (n-k+1)$.

3. Returning to Start:

• After $k-1$ moves, we must return to the starting node to complete the cycle.

4. Avoiding Overcounting:

• However, this approach still overcounts cycles that contain smaller loops (i.e., cycles of length less than $k$ that are traversed multiple times). To correct for this, we use a recurrence relation that subtracts the number of cycles of smaller length already counted.

The recurrence relation is:

with the base case:

This recurrence can be solved to obtain a closed formula:

Code

C++

class Solution {
public:
  int countCycles(int n, int k) {
    int p = (k % 2 == 0) ? 1 : -1;
    return (pow(n-1, k) + p * (n-1)) / n;
  }
};

Java

class Solution {
  public int countCycles(int n, int k) {
    int p = (k % 2 == 0) ? 1 : -1;
    return (int)((Math.pow(n-1, k) + p * (n-1)) / n);
  }
}

Python

class Solution:
  def count_cycles(self, n: int, k: int) -> int:
    p = 1 if k % 2 == 0 else -1
    return ((n-1)**k + p * (n-1)) // n

Complexity

• ⏰ Time complexity: O(1), as the formula is direct and does not require iteration.
• 🧺 Space complexity: O(1), only a few variables are used.