[Solved]: How many permutations in a trainset?

I bought that set for my grand son (nice and cheap Ikea product, kids love it from 18 month to 80 years, though not rcommended before 3 years of age), so I am very experienced with the problem. For the uninitiated, the tracks are oriented because they connect with a hole on one end and a hooking tongue on the other end. So curved tracks have to be placed with one side or the other up, depending on which way you want to turn. The Ikea picture does not make it obvious: the little plastic pieces are actually glued as tongue on one end of a track, but the curves track have grooves for the wheels on both sides.

Counting the configurations

I will use the word configuration for a way of putting the track elements together. It seems more appropriate than the word “permutation” which has a precise technical meaning. The first analysis, described in this section, consist in evaluating the total number of possible configurations. This will help us to actually enumerate them in the next part. You have 16 track elements, including 4 straight and 12 curved. If you consider your 16 elements in succession, you have $binom {16} 4 =frac{16!}{4!times 12!} $ ways of choosing a combination of positions for the 4 straights tracks, among 16. Now, if you consider the curved tracks, they can be placed either as left curve or as right curve. For 12 tracks that makes $2^{12}$ possibilities (using train tracks to implement binary numbers makes for heavy duty computers). So the total number of “permutations” (that use of the word does not seem too appropriate) is the product of the two numbers, since they correspond to independent choices, i.e., $$frac{2^{12}times 16!}{4!times 12!} $$ But this answer may not be quite correct: if you have a closed circuit, you can consider it to start with any of the track elements, so that it counts for 16 “permutations”, though one might consider it should count for 1. Hence, it might be appropriate to substract 15 from the result for each closed circuit that can be constructed. Geometric analysis of the shape of track elements shows that there are several closed circuits that can be constructed. Note that, except for the eight shape with crossing tracks, circuits are oriented, and each shape must me counted twice. Other closed circuits are possible with with less track elements, in particular with exactly 8 curves, and 0, 2, or 4 straight. But we now ignore the issue of closed curves. If you consider $n$ elements, $8leq nleq 16$, of which $m$ are straight, with $0leq mleq 4$, the number of circuits is $$frac{2^{n-m}times n!}{m!times (n-m)!}$$ Thus, for all possible values of $m$, with a number $n$ of elements, including at most 12 curved, the total number of circuits is: $$sum_{m=max(0, n-12)}^{m=4}frac{2^{n-m}times n!}{m!times (n-m)!}$$ Finally, considering all possible values of $n$ in $[8,16]$, we get the number of circuits: $$sum_{n=8}^{n=16} sum_{m=max(0, n-12)}^{m=4}frac{2^{n-m}times n!}{m!times (n-m)!}$$ Then there is the small number of cases when the circuit is closed, which one can analyse to count all their starting element variants as the same circuit. Note that when the track does not cross itself, each closed shape comes in two variants: clockwise and counter-clockwise. But should I go in so many details.

Enumerating the configurations

The analysis used for counting configurationscan be repeated identically to enumerate them. We consider $n$ track elements, of which $m$ are straight and $p$ are curved: $n=m+p$. We want to enumerate all the circuits that use all these elements. First, we want to place the $m$ straight track in the sequence of $n$ track element position. For this you must enumerate all combinations of $m$ integers among the first $n$ integers. Algorithms already exists to enumerate these conbinations, available in wikipedia, or fromn other sources, so there is no point in developing that further here. Then, for each such combination, you simply try all possible combinations of left or right positionning of curved track elements, which you can do by enumerating all possible sequences of$0$ and $1$, hence simply using a counter to enumerate in binary all integers from $0$ to $2^p-1$. It is advisable to use the fast changing bits in the enumeration on the end side of the configuration, in order to factor the beginning of computations that might be used to check whether the configurations give a closed circuit. Of course, this can be repeated for other values of $m$ and $p$. But configurations for smaller values are just prefixes of the configurations for the maximum values of $n$ and $m$. So, doing it only for the maximum values should be enough to observe on the fly whatever we are interested in regarding smaller configurations. THis is detailed regarding closed circuits in the next section.

Checking a configuration

Given a configuration for a sequence of track elements, and starting from porition (0,0), and direction angle 0, one can compute the position and direction at the end of the first track element, then propagate to the end of the second, and so on till the last. The circuit is closed if the end of the last track element is in position (0,0) with direction angle 0. The shape of the track elements is determined by the fact that 8 curves make a full circle, and 12 cuves and 4 straight make an eight shaped curve. One can use the radius of the circle as distance unit, Then the staight track elements have a length of 1 radius. For simplification, one can also take$45^o$ as the angle unit, so that each curved track changes the orientation by plus (left) or minus (right) one unit, and 8 units make a full circle. Hence orientation can be represented byrf an integer modulo 8. Positions of track elements ends should not be computed as real numbers, but as expression using integers and $sqrt 2/2$, of the form $a+bsqrt 2/2$, a bit like complex numbers where $i$ is replaced by $sqrt 2/2$. That makes the computations much cheaper, based on integer arithmetics on pairs $(a,b)$, and the $sqrt 2/2$ ultimately cancel each other for closed circuits. Actually, to explain it formally, plane coordinates reachable from the origin with straight and curved track elements are all expressible as $a+bsqrt 2/2$. Hence, since 2 coordinates are used on the plane, and since $1$ is incommensurable with $sqrt 2$, plane coordinates can be seen as a 4-dimensional vector space over the field $mathbb Q$ of rationals, or better, since we use only integer coordinates in that vector space, as a 4-dimensional module over the ring $mathbb Z$ of integer. See this mathematics question which is a followup to the question answered here. Hence following track element by track element the configuration of a circuit, for the purpose of checking whether it is closed, can be done using only integer addition and substraction. A circuit starts at the origin with orientation $0$. The circuit is closed when it ends also at the origin with orientation $0$. In the four dimensional space, the coordinates of the origine are $(0,0,0,0)$ I guess any reader can further develop the computation details, for each type of track element. (this answer is already very long). As explained in the previous section, doing the enumeration for maximum values of $n$ and $m$ will include smaller configurations as prefixes. In particular, if you are looking for closed circuits of all sizes, the simplest is to compute all configurations with the maximum values of $n$ and $m$, and check closure not just at the end, but at every step of the computation of track elements positions. However, there is a possibility for some optimization in performing these checks, as no closed circuit can be found with less than eight curved track elements.