Number of walks of length $l$ with restriction on edge visits Assume you want to build something out of Lego:

*

*You have N different types of lego.

*You have an unlimited amount of every type.

*Any type has a unique ID and a set of M>0 connectors, each of a connection type c.

*You can connect two lego pieces, if they have connectors of matching (let's assume: the same) type that are not in use already.

*An assembly of lego pieces consists of any number of pieces that are connected.

*Every piece in your set can be connected to any other piece either directly or via a path of intermediate pieces.

*Assume that these are the only constraints: If there is a free, matching connector-pair between lego pieces, you can always connect them. (There is no such thing as collisions, ...)

My question: How many different assemblies of length l can you build?
My thought process:

*

*An assembly of pieces can be described as undirected graph A.

*Let's create a graph C (I call it connectivity graph) in which every type of lego is represented by a node and for every pair of matching connectors between types, there is an edge in the graph.

*We know that C is a connected graph. However, we cannot assume it is fully connected.

*Self-loops in C are possible.

*I would like to map a walk in C to a unique assembly graph A. However, as long as loops in A are allowed, the mapping seems to be non-unique.

I failed coming closer to a solution without taking my first assumption: The assembly graph must be a chain. Then:

*

*If connections (=connector-pairs) could be used multiple times, the problem would be describing the number of walks of length l in the connectivity graph. (Because loops are no longer possible, unfolding the walk to an assembly graph should be trivial)

*As connector-pairs can only be used once, the same edge can never be used twice in a row in a path. Whenever a node is visited, a new lego piece of it's type is added to the assembly - so visiting an edge again later in the walk would mean "walking on copies" of the nodes, which would work again.

*So: How to find the number of walks of length l in graph C that do not include the same edge twice in a row.

EDIT: I changed the last to points regarding visiting edges twice (in a row) because I previously had a misconception. I think the assumption now is more reasonable.
If the above is not solvable, would these simplifications make it significantly easier?

*

*Every node in C is connected to itself.

*Consider only assemblies with a tree-structure.

*If using trees only, answer the question for a single starting piece that is only connected to one other piece.

*Consider only assemblies with a chain-structure like I did.

No idea if this problem is solvable, to me it sounds like there should be a solution, but my expertise in Graph Theory is by far not sufficient for that, so I'd appreciate any hints.
 A: You can find the number of walks of length $k$ between any pair of vertices in a graph by raising the adjacency matrix to the $k$-th power. To avoid duplicated edges, we will create a new graph. Consider your original graph as directed (each edge correspond two a directed edge in both direction). For each directed edge, create a vertex in your new graph. A vertex $e_1$ is linked to a vertex $e_2$ if the edges $e_1$ and $e_2$ are consecutive (and distinct) in the original graph. This construction is called the line graph. A walk in the original walk that avoid passing two times in a row on the same edge is equivalent to a a walk in the new directed graph. This solves the case where the build is a chain.
For an efficient computation of $A^k$ (with $A$ the adjacency matrix), you can use exponentiation by squaring, yielding an $\mathcal{O}(n^\omega\log(n))$, with $\omega$ the exponent of matrix multiplication and $n$ the size of the graph
The more general problem where the build is not restricted to a chain seems to be much more difficult.
