Based on the answer and comments by @Corentin B, I believe the following upper bound holds:
$$
C_{k,t}^n \leq D_t \binom{n-1}{t}\cdot t! \cdot S(k/2,t)
$$
for $k \in 2 \mathbb N$ and $t \le k/2$, where $D_t = \frac1{t+1}\binom{2t}{t}$ is the Catalan number and $S(\cdot, \cdot)$ the Stirling number of the second kind.
The bound is tight when $k = 2t$.
Here is a tentative proof:
There are $C_t$ (plane) tree structures (when we try to encode the structure of the walk starting from the left we get one of these plane trees) and the count of walks for each structure is upper-bounded by the count for the star (*) Once we pick the leaves of the star, for which we have $\binom{n-1}{t}$ choices, then we have to choose how many times we want to visit each leaf and in what order, making sure we visit each leaf at least once.
The latter count is $t! \cdot S(k/2,t)$. To see this note that walks of the kind we want on a star with $n$ in the center, is equivalent to arranging $t$ objects into $m=k/2$ slots where (a) each object must be used at least once (to cover the tree), (b) objects can be used multiple times and (c) the order matters. This is equivalent to the number of surjections from a set of $m$ elements to a set of $t$ elements which is given by $ t! \cdot S(m,t)$.
The only really missing piece is formally proving the upper bound (*) which seems to be true.
The output of a bit of code that inspired this: The above upper bound is obtained by assuming all the $D_4$ = 14 counts are 1560.
Enter the number of nodes (n): 5
Enter the path length (k): 12
Enter the number of unique undirected edges (t): 4
Loopless paths grouped by tree structure:
Tree structure: (((),(),()))
Number of paths: 1560
Example path: 5 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 3 -> 1 -> 4 -> 1 -> 5
Tree structure: ((),(),(),())
Number of paths: 1560
Example path: 5 -> 1 -> 5 -> 1 -> 5 -> 1 -> 5 -> 2 -> 5 -> 3 -> 5 -> 4 -> 5
Tree structure: ((()),(),())
Number of paths: 1264
Example path: 5 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 5 -> 3 -> 5 -> 4 -> 5
Tree structure: ((),(()),())
Number of paths: 1264
Example path: 5 -> 1 -> 5 -> 1 -> 5 -> 1 -> 5 -> 2 -> 3 -> 2 -> 5 -> 4 -> 5
Tree structure: ((),(),(()))
Number of paths: 1264
Example path: 5 -> 1 -> 5 -> 1 -> 5 -> 1 -> 5 -> 2 -> 5 -> 3 -> 4 -> 3 -> 5
Tree structure: (((),()),())
Number of paths: 1260
Example path: 5 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 3 -> 1 -> 5 -> 4 -> 5
Tree structure: ((),((),()))
Number of paths: 1260
Example path: 5 -> 1 -> 5 -> 1 -> 5 -> 1 -> 5 -> 2 -> 3 -> 2 -> 4 -> 2 -> 5
Tree structure: (((),(())))
Number of paths: 1152
Example path: 5 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 3 -> 4 -> 3 -> 1 -> 5
Tree structure: (((()),()))
Number of paths: 1152
Example path: 5 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 3 -> 2 -> 1 -> 4 -> 1 -> 5
Tree structure: ((((),())))
Number of paths: 1032
Example path: 5 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 3 -> 2 -> 4 -> 2 -> 1 -> 5
Tree structure: ((()),(()))
Number of paths: 1008
Example path: 5 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 5 -> 3 -> 4 -> 3 -> 5
Tree structure: (((())),())
Number of paths: 900
Example path: 5 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 3 -> 2 -> 1 -> 5 -> 4 -> 5
Tree structure: ((),((())))
Number of paths: 900
Example path: 5 -> 1 -> 5 -> 1 -> 5 -> 1 -> 5 -> 2 -> 3 -> 4 -> 3 -> 2 -> 5
Tree structure: ((((()))))
Number of paths: 792
Example path: 5 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 5
Total loopless paths: 16368
Unique tree structures: 14
Our guess (Catalan number D_4): 14
Actual largest count: 1560 (for structure: (((),(),())))
Our guess: 1560 (comb(n-1, t) * factorial(t) * stirling2(k//2, t))
Star structure count: 1560
Is star structure the one with largest count? Yes
Upper bound on total count: 21,840
Actual total count: 16,368
Is the calculated upper bound valid? Yes
The tree structure is represented as nested parentheses, where each set of parentheses represents a node and its children. We sort the children before creating the representation. Let's call this the Cayley structure of the tree.
So why not Cayley's formula $(t+1)^{t-1}$ rather than the Catalan number? Consider $n=4$ and $t=3$, then Cayley's formula counts 3 different stars with $n=4$ as a leaf, let's call them $T_1,T_2$ and $T_3$, while Catalan's counts just 1, i.e. ((()())). Both formulas count a single star with $n=4$ as the hub, i.e., ((),(),()).
The count $\binom{n-1}{t} t! S(k/2,t)$ correctly gives the count of walks on the hub-star ((),(),()). For any of these walks, if we switch the hub with one of the leaves, we get a corresponding walk on either $T_1, T_2$ or $T_3$ (**). So the totality of walks on $T_1,T_2$ and $T_3$ is in 1-1 correspondence with walks on ((),(),()). That is, all possible walks on ((),(),()) are in 1-1 correspondence with all possible walks on ((()())).
This suggest that we partition the walks based on their Cayley structure, and assuming the above two star Cayley structures are maximal, we get a better bound.
(**) How the 1-1 correspondence work? Consider
$$4 \to 1 \to 2 \to 1 \to 3 \to 1 \to 4$$
We glue the two ends together and start the walk on the second node, 1, and continue for $k = 6$ steps to get
$$1 \to 2 \to 1 \to 3 \to 1 \to 4 \to 1$$
Now this is a walk on a ((),(),()) with hub node $1$. We just flip $1$ and $4$:
$$4 \to 2 \to 4 \to 3 \to 4 \to 1 \to 4$$
which gives our desired walk on ((),(),()) with 4 at the center.
Here is the code
from typing import List, Tuple, Set
from collections import defaultdict
from math import comb, factorial
def catalan(n):
return comb(2*n, n) // (n + 1)
def stirling2(n, k):
if n == k == 0:
return 1
if n == 0 or k == 0:
return 0
return stirling2(n-1, k-1) + k * stirling2(n-1, k)
def generate_paths(n: int, k: int, t: int) -> List[Tuple[List[int], int, str]]:
paths_without_loops = []
def has_loop(edges: Set[Tuple[int, int]]) -> bool:
graph = defaultdict(set)
for u, v in edges:
graph[u].add(v)
graph[v].add(u)
def dfs(node: int, parent: int) -> bool:
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True
return False
visited = [False] * (n + 1)
for node in range(1, n + 1):
if not visited[node]:
if dfs(node, -1):
return True
return False
def get_tree_structure(path: List[int]) -> str:
edges = set()
for i in range(len(path) - 1):
u, v = path[i], path[i+1]
edges.add((min(u, v), max(u, v)))
graph = defaultdict(set)
for u, v in edges:
graph[u].add(v)
graph[v].add(u)
def dfs_structure(node: int, parent: int) -> str:
children = sorted(neighbor for neighbor in graph[node] if neighbor != parent)
return f"({','.join(dfs_structure(child, node) for child in children)})"
root = path[0]
return dfs_structure(root, -1)
def backtrack(path: List[int], unique_edges: Set[Tuple[int, int]], returns: int):
if len(path) == k + 1:
if path[-1] == n and len(unique_edges) == t:
if not has_loop(unique_edges):
tree_structure = get_tree_structure(path)
paths_without_loops.append((path[:], returns, tree_structure))
return
for next_node in range(1, n + 1):
if next_node != path[-1]:
new_edge = (min(path[-1], next_node), max(path[-1], next_node))
new_unique_edges = unique_edges.copy()
new_unique_edges.add(new_edge)
if len(new_unique_edges) <= t:
new_returns = returns + (1 if next_node == n else 0)
path.append(next_node)
backtrack(path, new_unique_edges, new_returns)
path.pop()
backtrack([n], set(), 0)
return paths_without_loops
def display_paths(paths: List[Tuple[List[int], int, str]]):
print("\nLoopless paths grouped by tree structure:")
total_paths = 0
tree_structure_counts = defaultdict(int)
for path, returns, tree_structure in paths:
tree_structure_counts[tree_structure] += 1
total_paths += 1
for structure, count in sorted(tree_structure_counts.items(), key=lambda x: x[1], reverse=True):
print(f"Tree structure: {structure}")
print(f" Number of paths: {count}")
print(f" Example path: {' -> '.join(map(str, next(path for path, _, s in paths if s == structure)))}")
print()
print(f"Total loopless paths: {total_paths}")
print(f"Unique tree structures: {len(tree_structure_counts)}")
def display_paths(paths: List[Tuple[List[int], int, str]], n: int, k: int, t: int):
print("\nLoopless paths grouped by tree structure:")
total_paths = 0
tree_structure_counts = defaultdict(int)
for path, returns, tree_structure in paths:
tree_structure_counts[tree_structure] += 1
total_paths += 1
max_count = 0
max_structure = ""
star_structure = "(" + ",".join(["()" for _ in range(t)]) + ")"
star_count = 0
for structure, count in sorted(tree_structure_counts.items(), key=lambda x: x[1], reverse=True):
print(f"Tree structure: {structure}")
print(f" Number of paths: {count}")
print(f" Example path: {' -> '.join(map(str, next(path for path, _, s in paths if s == structure)))}")
print()
if count > max_count:
max_count = count
max_structure = structure
if structure == star_structure:
star_count = count
print(f"Total loopless paths: {total_paths}")
print(f"\nUnique tree structures: {len(tree_structure_counts)}")
# Catalan number estimate
catalan_estimate = catalan(t)
print(f"Our guess (Catalan number D_{t}): {catalan_estimate}")
#print(f"Actual number of unique tree structures: {len(tree_structure_counts)}")
# Exact count for the tree structure with largest walks
guess_max_count = comb(n-1, t) * factorial(t) * stirling2(k//2, t)
print(f"\nActual largest count: {max_count:6d} (for structure: {max_structure})")
print(f"Our guess: {guess_max_count:6d} (comb(n-1, t) * factorial(t) * stirling2(k//2, t))")
# Star structure count
print(f"\nStar structure count: {star_count}")
print(f"Is star structure the one with largest count? {'Yes' if star_count == max_count else 'No'}")
# Upper bound calculation
upper_bound = catalan_estimate * guess_max_count
print(f"\nUpper bound on total count: {upper_bound:6,d}")
print(f"Actual total count: {total_paths:6,d}")
print(f"Is the calculated upper bound valid? {'Yes' if upper_bound >= total_paths else 'No'}")
def main():
n = int(input("Enter the number of nodes (n): "))
k = int(input("Enter the path length (k): "))
t = int(input("Enter the number of unique undirected edges (t): "))
paths_without_loops = generate_paths(n, k, t)
display_paths(paths_without_loops, n, k, t)
if __name__ == "__main__":
main()
