Научно-методически статии
TRIPLES OF DISJOINT PATHS BETWEEN POINTS ON A CIRCLE
https://doi.org/10.53656/math2023-4-1-tri
Резюме. The paper deals with counting the triples of disjoint non-selfintersecting paths with nodes from a fixed set of labelled points on a circle. Some of the obtained formulae provide new properties of entries in the Online Encyclopaedia of Integer Sequences, while others generate new entries therein.
Ключови думи: enumerative combinatorics; non-self-intersecting paths; convex polygons; OEIS
Below we will prove formulae for counting the triples of disjoint non-self-intersecting paths whose sets of nodes cover a set of \(n\) fixed labelled points on a circle. The formulae depend on whether one-node paths are allowed. The question about counting the sets of fixed magnitude containing non-self-intersecting paths that are allowed to intersect one another has been discussed in (Kortezov 2022), (Kortezov 2022a) and (Kortezov 2023). The formulae obtained in these papers had similar compactness both when singletons were allowed and when not. Here we will also count the pairs of disjoint non-self-intersecting paths when singletons are allowed, a question seemingly not discussed before.
Both for pairs and for triples, the formulae obtained seem to be more aesthetic when singletons are not allowed.
Definition 1. Let \(A_{1}, A_{2}, \ldots, A_{k}\) be different points in the plane such that no three of them are collinear. If the segments \(A_{1} A_{2}, A_{2} A_{3}, \ldots, A_{k-1} A_{k}\) have no common internal points, then the union of these segments is called a non-self-intersecting path (\(N S P\) ); \(A_{1}, A_{2}, \ldots, A_{k}\) are called nodes of the NSP.
Note that, according to the definition, the NSP is direction-independent – e.g. \(A_{1} A_{2} A_{4} A_{3}\) and \(A_{3} A_{4} A_{2} A_{1}\) is the same NSP. Also, the definition allows a NSP to have just one node (and zero segments); in this case we will call it a singleton. It is not immediately clear whether it is reasonable to include the singletons among the NSPs. Below we will mostly consider only non-singleton NSPs; only at the end we will discuss what happens if they are allowed.
We will use the known formula:
\[ \sum_{k=1}^{n-1} k(n-k)=\binom{n+1}{3} \] that follows from double-counting the strings of length \(n+1\) whose all digits are zeroes, except three that are ones: if the middle " 1 " is at position \(k+1, k \in[1 ; n-1]\), then there are \(k\) choices for the place of the first " 1 " and \(n-k\) for the last " 1 ".
The following can be found in equivalent form in (Kortezov 2020):
Proposition 1. Let there be \(n \geq 2\) given points on a circle. Then the number of all non-self-intersecting paths whose nodes are all these \(n\) points is \(a_{n}=n .2^{n-3}\).
For example, \(a_{3}=3\) as the NSPs are \(A_{1} A_{2} A_{3}, A_{1} A_{3} A_{2}\) and \(A_{2} A_{1} A_{3}\).
The above property has been added to the list of properties of (Sloane 2020):
Proposition 2. Let there be \(n \geq 3\) given points on a circle. Denote by \(c_{n}\) the number of unordered pairs of disjoint non-self-intersecting paths whose nodes are all these \(n\) points. Then
\[ c_{n}=\tfrac{1}{3} n(n-1)(n-3)(n+4) 2^{n-8} . \]
For example, \(c_{4}=2\) asthe pairs ofNSPsare \(\left\{A_{1} A_{2}, A_{3} A_{4}\right\}\) and \(\left\{A_{1} A_{4}, A_{2} A_{3}\right\}\). Also, \(c_{5}=\tfrac{1}{3} \cdot 5 \cdot 4 \cdot 2 \cdot 9 \cdot 2^{-3}=15\). The sequence generated by the above formula has been accepted in oeis.org} (Sloane 2022).
Definition 2. Let \(n \geq 3\) and the points \(A_{1}, A_{2}, \ldots, A_{n}\) lie on a circle in the given order. Denote by \(\ddot{c}_{n}\) the number of all unordered pairs of disjoint non-self-intersecting paths whose nodes are \(A_{1}, A_{2}, \ldots, A_{n}\) such that \(A_{1}\) and \(A_{n}\) belong to different paths.
For example \(\ddot{c_{4}}=1\) as the only such pair is \(\left\{A_{1} A_{2}, A_{3} A_{4}\right\}\). Also \(\ddot{c_{5}}=2.3=6\) since one of the NSPs is \(A_{1} A_{2}\) or \(A_{5} A_{4}\), while for the other one there are \(a_{3}=3\) choices.
Lemma 1. \(\ddot{c}_{n}=\tfrac{1}{3}(n-1)(n-3)(n+4) 2^{n-7}\).
Proof: If \(n=3\) then the formula yields for \(\ddot{c}_{3}=0\) which is trivially true. Now let \(n \geq 4\). If the NSP containing \(A_{1}\) has \(k\) nodes (\(2 \leq k \leq n-2\) ) then by Proposition 1 there are \(k .2^{k-3}\) variants for this NSP and \((n-k) .2^{n-k-3}\) variants for the other NSP, so
\[ \ddot{c_{n}}=\sum_{k=2}^{n-2} k \cdot 2^{k-3} \cdot(n-k) \cdot 2^{n-k-3}=2^{n-6} \sum_{k=2}^{n-2} k(n-k) \]
\[ \begin{gathered} =2^{n-6}\left(\binom{n+1}{3}-1 \cdot(n-1)-(n-1) \cdot 1\right)= \\ =\tfrac{1}{3}(n-1)\left(n^{2}+n-12\right) 2^{n-7}=\tfrac{1}{3}(n-1)(n-3)(n+4) 2^{n-7} . \end{gathered} \]
Let is illustrate this for small \(n\). We have \(\ddot{c_{4}}=\tfrac{1}{3} \cdot 3 \cdot 1 \cdot 8 \cdot 2^{-3}=1\) and \(\ddot{c_{5}}=\tfrac{1}{3} \cdot 4 \cdot 2 \cdot 9 \cdot 2^{-2}=6\) in accord with our initial observations.
Definition 3. Let \(n \geq 3\) and the points \(A_{1}, A_{2}, \ldots, A_{n}\) lie on a circle in the giventersecting paths whose order. Denote by \(\overline{c_{n}}\) nodes arethe number \(A_{1}, A_{2}, \ldots, A_{n}\) of all unorderedsuch that pairs \(A_{1}\) ofand disjoint \(A_{n}\) belong to the non-self-insame path.
For example, \(\overline{c_{4}}=1\) as the only such pair is \(\left\{A_{1} A_{4}, A_{2} A_{3}\right\}\). Also \(\overline{c_{5}}=3.3=9\) since one of the NSPs is \(A_{1} A_{5}, A_{2} A_{3}\) or \(A_{3} A_{4} A_{3} A_{4}\), while for the other one there are \(a_{3}=3\) choices.
Lemma 2. \(\overline{c_{n}}=\tfrac{1}{3}(n-1)(n-2)(n-3)(n+4) 2^{n-8}\).
Proof: Follows from \(\overline{c_{n}}=c_{n}-\ddot{c_{n}}\).
Let is illustrate this for small \(n\). We have \(\overline{c_{4}}=\tfrac{1}{3} \cdot 3 \cdot 2 \cdot 1 \cdot 8 \cdot 2^{-4}=1\), \(\overline{c_{5}}=\tfrac{1}{3} \cdot 4 \cdot 3 \cdot 2 \cdot 9 \cdot 2^{-3}=9\) in accord with our initial observations.
Definition 4. Call two NSPs neighbours if we can choose one node from each NSP so that the two points are adjacent on the circle (i.e. there are no other nodes on one of the arcs connecting them).
Definition 5. Let \(n \geq 3\) and there be \(n\) given points on a circle. Denote by \(t_{n}^{*}\) the number of unordered triples of disjoint non-singleton non-self-intersecting paths whose nodes are all these \(n\) points and each two paths are neighbours.
Denote by \(\overline{t_{n}}\) the number of unordered triples of disjoint non-singleton non-self-intersecting paths whose nodes are all these \(n\) points and two of the paths are not neighbours; call the third NSP the central one (it is necessarily a neighbour to each of the first two paths). Denote by \(t_{n}\) the number of unordered triples of disjoint non-singleton non-self-intersecting paths whose nodes are all these \(n\) points. Thus \(t_{n}=t_{n}^{*}+\overline{t_{n}}\).
For example, \(t_{6}^{*}=2\) with the triples being \(\left\{A_{1} A_{2}, A_{3} A_{4}, A_{5} A_{6}\right\}\) and \(\left\{A_{1} A_{6}, A_{2} A_{3}, A_{4} A_{5}\right\}\), while \(\mathrm{m} \overline{t_{6}}=3\) with the central NSP being \(\left\{A_{i} A_{i+3}\right\}\) (enumerated modulo 6) for \(i=1,2,3\). Thus \(t_{6}=2+3=5\).
Also, \(t_{7}^{*}=21\) since there are 7 choices for the set of nodes for the 3 -node NSP and \(a_{3}=3\) ways to connect them, and the 2 -node NSPs are uniquely determined. To find \(\overline{t_{7}}\), note that:
– if the 3-node NSP is the central one, then there are 7 choices for its 3 nodes and \(a_{3}=3\) ways to connect them, and then the 2-node NSPs are uniquely determined;
– if the 3-node NSP is not the central one, then there are 7 choices for its 3 nodes and \(a_{3}=3\) ways to connect them, and then the 2-node NSPs are uniquely determined;
hence \(\overline{t_{7}}=7.3+7.3=42\). Thus \(t_{7}=21+42=63\).
Further, \(t_{8}^{*}=136\). Indeed:
– if the three NSPs have \(3,3,2\) vertices respectively, then there are 8 choices for the 2-node path and then \(a_{3} . a_{3}=9\) ways to form the 3-node NSPs;
– if the three NSPs have \(4,2,2\) vertices respectively, then there are 8 choices for the set of vertices of the 4-node path and \(a_{4}=8\) ways to connect them;
hence \(t_{8}^{*}=8.9+8.8=136\).
On order to find \(\overline{t_{8}}\) we have the following cases:
– the central NSP has 2 nodes (4 choices) and the other two NSPs have 3 nodes each (\(a_{3} . a_{3}=9\) choices);
– a non-central NSP has 2 nodes (8 choices) and the other two NSPs have 3 nodes each (2 choices for the sets of nodes and then \(a_{3} \cdot a_{3}=9\) ways to form the 3-node NSPs);
– the central NSP has 4 nodes (\(4+8=12\) choices for the nodes and \(a_{4}=8\) ways to connect them) and the other two NSPs have 2 nodes each (single choice);
– a non-central NSP has 4 nodes (8 choices for the nodes and \(a_{4}=8\) ways to connect them) and the other two NSPs have 2 nodes each (single choice); hence \(\overline{t_{8}}=4.9+8.2 .9+12.8+8.8=340\). Thus \(t_{8}=136+340=476\).
In addition, for \(n=3,4,5\) we have \(t_{n}^{*}=\overline{t_{n}}=t_{n}=0\) for trivial reasons.
Proposition 3. If \(n \geq 4 n \geq 4\) then
\[ t_{n}^{*}=\tfrac{2^{n-12}}{45} n(n-2)(n-4)(n-5)(n+2)(n+9) . \]
Proof: If \(n=4,5\) then the formula yields \(t_{n}^{*}=0\) which is trivially true.
If one of the NSPs contains \(n-k\) nodes (\(4 \leq k \leq n-2, n\) choices for the set of nodes), then by Proposition 1 there are \((n-k) 2^{n-k-3}\) variants for this NSP. If we denote by \(A_{1}, A_{2}, \ldots, A_{k}\) the points allocated for the other two NSPs then by Lemma 1 there are:
\[ \ddot{c_{k}}=\tfrac{1}{3}(k-1)(k-3)(k+4) 2^{k-7} \]
choices for these NSPs.
Considering that thus each unordered triple of NSPs will be counted three times, we conclude that:
(*) \(\begin{gathered} t_{n}^{*}=\tfrac{1}{3} \sum_{k=4}^{n-2} n(n-k) 2^{n-k-3} \cdot \tfrac{1}{3}(k-1)(k-3)(k+4) 2^{k-7}= \\ =\tfrac{n}{9} 2^{n-10} \sum_{k=4}^{n-2}(n-k)(k-1)(k-3)(k-2+6)= \\ =\tfrac{n}{9} 2^{n-10} \sum_{k=4}^{n-2}(n-k)((k-1)(k-2)(k-3)+6(k-1)(k-2)-6(k-1)) . \end{gathered}\)
In order to calculate
\[ \sum_{k=4}^{n-2}(n-k)(k-1)(k-2)(k-3) \] let us note that there are \(\binom{n}{5}\) strings of length \(n\) whose all digits are " 0 ", except three " 1 ", one " 2 " to the right of them and one " 3 " to the right of it. On the other side, if the " 2 " is at position \(k, k \in[4 ; k-1]\), then there are \((k-1)(k-2)(k-3) / 3\) ! ways to choose the places of the ones and \((n-k)\) for the place of the " 3 ", hence:
\[ \sum_{k=4}^{n-1}(n-k)(k-1)(k-2)(k-3)=6\binom{n}{5} . \] Thus
\[ \sum_{k=4}^{n-2}(n-k)(k-1)(k-2)(k-3)=6\binom{n}{5}-(n-2)(n-3)(n-4) . \]
In order to calculate \[ \sum_{k=4}^{n-2}(n-k)(k-1)(k-2) \] note that there are \(\binom{n}{4}\) strings of length \(n\) whose all digits are “0”, except two"1", one “2” to the right of them and one “3” to the right of it. On the other side, if “2” is at position , \(k \in[3 ; k-1]\), then there are \((k-1)(k-2) / 2\) ! ways to choose the places of the ones and \((n-k)\) for the place of the “3”, hence:
\[ \sum_{k=3}^{n-1}(n-k)(k-1)(k-2)=2\binom{n}{4} . \]
Thus
\(\sum_{k=4}^{n-2}(n-k)(k-1)(k-2)=2\binom{n}{4}-2(n-3)-(n-2)(n-3)=2\binom{n}{4}-n(n-3)\).
In order to calculate
\[ \sum_{k=4}^{n-2}(n-k)(k-1) \] note that there are \(\binom{n}{3}\) strings of length \(n\) whose all digits are “0”, except one “1”, one “2” to the right of it and one “3” to the right of the “2”. On the other side, if the “2” is at position \(k, k \in[2 ; n-1]\), then there are \(k-1\) choices of the place of “1” and \((n-k)\) for the place of “3”, hence:
\[ \sum_{k=2}^{n-1}(n-k)(k-1)=\binom{n}{3} \]
Thus
\(\sum_{k=4}^{n-2}(n-k)(k-1)=\binom{n}{3}-(n-2)-2(n-3)-(n-2)=\binom{n}{3}-4 n+10\).
Substituting these three results in (*) we get
\(t_{n}^{*}=\tfrac{n}{9} 2^{n-10}\left(6\binom{n}{5}-(n-2)(n-3)(n-4)+12\binom{n}{4}-6 n(n-3)-6\binom{n}{3}+24 n-60\right)=\)
\(=\tfrac{n}{180} 2^{n-10}(n(n-1)(n-2)(n-3)(n-4)-20(n-2)(n-3)(n-4)+\)
\(+10 n(n-1)(n-2)(n-3)-120 n(n-3)-20 n(n-1)(n-2)+480 n-1200=\)
\(=\tfrac{n}{180} 2^{n-10}(n(n-1)(n-2)(n-3)(n-4)-20(n-2)(n-3)(n-4)+\)
\(\left.+10 n(n-1)(n-2)(n-3)-120\left(n^{\wedge} 2-3 n-4 n+10\right)-20 n(n-1)(n-2)\right)=\)
\(=\tfrac{n}{45} 2^{n-12}(n(n-1)(n-2)(n-3)(n-4)-20(n-2)(n-3)(n-4)+\)
\[ \begin{gathered} +10 n(n-1)(n-2)(n-3)-120(n-2)(n-5)-20 n(n-1)(n-2))= \\ =\tfrac{n(n-2)}{45} 2^{n-12}((n-5)(n-3)(n-4)(n+4)+10 n(n-1)(n-5)-120(n-5))= \\ =\tfrac{n(n-2)(n-5)}{45} 2^{n-12}((n-3)(n-4)(n+4)+10(n-4)(n+3))= \\ =\tfrac{n(n-2)(n-4)(n-5)}{45} 2^{n-12}\left(n^{2}+n-12+10 n+30\right)= \\ =\tfrac{n(n-2)(n-4)(n-5)}{45} 2^{n-12}\left(n^{2}+11 n+18\right)= \\ =\tfrac{2^{n-12}}{45} n(n-2)(n-4)(n-5)(n+2)(n+9) \end{gathered} \] Remark. The above formula yields:
\[ \begin{gathered} t_{4}^{*}=t_{5}^{*}=0, t_{6}^{*}=\tfrac{2^{-6}}{45} 6 \cdot 4 \cdot 2 \cdot 1 \cdot 8 \cdot 15=2, t_{7}^{*}=\tfrac{2^{-5}}{45} 7 \cdot 5 \cdot 3 \cdot 2 \cdot 9 \cdot 16=21 \text { and } \\ t_{8}^{*}=\tfrac{2^{-4}}{45} 8 \cdot 6 \cdot 4 \cdot 3 \cdot 10 \cdot 17=2 \cdot 4 \cdot 17=136 \end{gathered} \] that all comply with our initial observations. However if we insist on applying on the formula for \(n=3\), we need to round its result \(\left(2^{-6}\right)\) to the nearest integer 0.
Proposition 4. If \(n \geq 3\) then
\[ \overline{t_{n}}=\tfrac{2^{n-12}}{90} n(n-2)(n-3)(n-4)(n-5)(n+2)(n+9) \]
Proof: If \(n=3,4,5\) then the formula yields \(t_{n}^{*}=0\) which is trivially true.
If one of the non-central NSPs contains \(n-k\) nodes (\(4 \leq k \leq n-2, n\) choices for the set of nodes), then by Proposition 1 there are \((n-k) 2^{n-k-3}\) variants for this NSP. If we denote by \(A_{1}, A_{2} \ldots, A_{k}\) the points allocated for the other two NSPs then by Lemma 2 there are
\[ \overline{c_{k}}=\tfrac{1}{3}(k-1)(k-2)(k-3)(k+4) 2^{k-8} \] choices for these NSPs. Taking into account that thus each unordered triple of NSPs will be counted twice, we conclude that:
(**) \[ \begin{gathered} \overline{t_{n}}=\tfrac{1}{2} \sum_{k=4}^{n-2} n(n-k) 2^{n-k-3} \cdot \tfrac{1}{3}(k-1)(k-2)(k-3)(k+4) 2^{k-8}= \\ \quad=\tfrac{n}{3} 2^{n-12} \sum_{k=4}^{n-2}(n-k)(k-1)(k-2)(k-3)(k+4) \end{gathered} \]
From the previous proof we infer that
\(4 \sum_{k=4}^{n-2}(n-k)(k-1)(k-2)(k-3)=24\binom{n}{5}-4(n-2)(n-3)(n-4)\).
In order to calculate
\[ \sum_{k=4}^{n-2}(n-k) k(k-1)(k-2)(k-3) \] note that there are \(\binom{n+1}{6}\) strings of length \(n+1\) whose all digits are “0”, except four “1”, one “2” to the right of them and one “3” to the right of it. On the other side, if the “2” is at position \(k+1, k \in[4 ; n-1]\), then there are \(k(k-1)(k-2)(k-3) / 4!\) ways to choose the places of the ones and \((n-k)\) for the place of the “3”, hence:
\[ \sum_{k=4}^{n-1}(n-k) k(k-1)(k-2)(k-3)=24\binom{n+1}{6} . \]
Thus
\[ \sum_{k=4}^{n-2}(n-k) k(k-1)(k-2)(k-3)=24\binom{n+1}{6}-(n-1)(n-2)(n-3)(n-4) . \]
Substituting these two results in (**) we get:
\[ \begin{aligned} & \overline{t_{n}}=\tfrac{n}{3} 2^{n-12}\left(24\binom{n+1}{6}-(n-1)(n-2)(n-3)(n-4)+24\binom{n}{5}\right. \\ & -4(n-2)(n-3)(n-4))= \\ = & \tfrac{n}{90} 2^{n-12}((n+1) n(n-1)(n-2)(n-3)(n-4)-30(n-1)(n-2)(n-3)(n-4)+ \\ + & 6 n(n(n-1)(n-2)(n-3)(n-4)-120(n-2)(n-3)(n-4))= \\ = & \tfrac{n(n-2)(n-3)(n-4)}{90} 2^{n-12}\left(n^{3}-n-30 n+30+6 n^{2}-6 n-120\right)= \end{aligned} \]
\[ \begin{gathered} =\tfrac{n(n-2)(n-3)(n-4)}{90} 2^{n-12}\left(n^{3}+2 n^{2}+4 n^{2}+8 n-45 n-60\right)= \\ =\tfrac{n(n-2)(n-3)(n-4)(n+2)}{90} 2^{n-12}\left(n^{2}+4 n-45\right)= \\ =\tfrac{2^{n-12}}{90} n(n-2)(n-3)(n-4)(n+2)(n-5)(n+9) \end{gathered} \]
Remark. The above formula yields \(\overline{t_{3}}=\overline{t_{4}}=\overline{t_{5}}=0, \overline{t_{6}}=\tfrac{2^{-6}}{90} 6.4 .3 .2 .1 .8 .15=3\), \(\overline{t_{7}}=\tfrac{2^{-5}}{90} 7 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 9 \cdot 16=42\) and \(\overline{t_{8}}=\tfrac{2^{-4}}{90} 8 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 10 \cdot 17=2 \cdot 4 \cdot 17=340\) that all comply with our initial observations.
Proposition 5. If \(n \geq 4\) then
\[ t_{n}=\tfrac{2^{n-12}}{90} n(n-1)(n-2)(n-4)(n-5)(n+2)(n+9) . \]
Proof: \(t_{n}=t_{n}^{*}+\overline{t_{n}}=\tfrac{2^{n-12}}{45} n(n-2)(n-4)(n-5)(n+2)(n+9)+\) \[ \begin{aligned} & +\tfrac{2^{n-12}}{90} n(n-2)(n-3)(n-4)(n-5)(n+2)(n+9)= \\ = & \tfrac{2^{n-12}}{90} n(n-2)(n-4)(n-5)(n+2)(n+9)(2+n-3)= \\ & =\tfrac{2^{n-12}}{90} n(n-2)(n-4)(n-5)(n+2)(n+9)(n-1) \end{aligned} \]
Remark. The above formula yields \(t_{4}=t_{5}=0, t_{6}=\tfrac{2^{-6}}{90} 6 \cdot 5 \cdot 4 \cdot 2 \cdot 1 \cdot 8 \cdot 15=5\), \(t_{7}=\tfrac{2^{-5}}{90} 7 \cdot 6 \cdot 5 \cdot 3 \cdot 2 \cdot 9 \cdot 16=63\) and \(t_{8}=\tfrac{2^{-4}}{90} 8 \cdot 7 \cdot 6 \cdot 4 \cdot 3 \cdot 10 \cdot 17=2 \cdot 4 \cdot 17=476\), in accordance with our initial observations. However if we insist on applying on the formula for \(n=3\), we need to round its result \(\left(2^{-6}\right)\) to the nearest integer 0. The sequence generated by the above formula has been accepted in oeis.org (Sloane 2023).
Let us now check what happens if singletons are allowed.
Definition 6. Let \(n \geq 2\) and there be \(n\) given points on a circle. Denote by \(c_{n}^{\prime}\) the number of unordered pairs of disjoint non-self-intersecting paths, singletons included, whose nodes are all these \(n\) points.
For example, \(c_{2}^{\prime}=1\) (both NSPs are singletons) and \(c_{3}^{\prime}=3\) (a singleton and a segment). To find \(c_{4}^{\prime}\), note that if among the NSPs there is a singleton (4 choices), then there are \(a_{3}=3\) choices for the other NSP, and otherwise for the two NSPs there are \(c_{4}=2\) choices, thus obtaining \(c_{4}^{\prime}=c_{4}+4 a_{3}=2+4.3=14\). Similarly by Propositions 1 and 2 we get \(c_{5}^{\prime}=c_{5}+5 a_{4}=15+5.8=55\).
Proposition 6. If \(n \geq 3\) then
\[ c_{n}^{\prime}=\tfrac{2^{n-8}}{3} n(n-1)\left(n^{2}+n+36\right) . \]
Proof: The number of singletons among the two NSPs can be:
– one: \(n a_{n-1}=n(n-1) 2^{n-4}\) choices;
– zero: \(c_{n}=\tfrac{1}{3} n(n-1)(n-3)(n+4) 2^{n-8}\) choices.
Thus
\(c_{n}^{\prime}=\tfrac{1}{3} n(n-1) 2^{n-8}\left(3.2^{4}+(n-3)(n+4)\right)=\tfrac{2^{n-8}}{3} n(n-1)\left(n^{2}+n+36\right)\).
Remark. Indeed, the above formula yields
\(c_{3}^{\prime}=2^{-5} \cdot 2(9+3+36)=3, c_{4}^{\prime}=2^{-4} \cdot 4(16+4+36)=14\) and \(c_{5}^{\prime}=\tfrac{1}{24} \cdot 5 \cdot 4 \cdot(25+5+36)=55\).
However, if we insist on applying it for \(n=2\), we need to round the result to the nearest integer 1.
Definition 7. Let \(n \geq 3\) and there be \(n n\) given points on a circle. Denote by \(t_{n}^{\prime}\) the number of unordered triples of disjoint non-self-intersecting paths, singletons included, whose nodes are all these \(n\) points.
For example, \(t_{3}^{\prime}=1\) (all three NSPs are singletons) and \(t_{4}^{\prime}=\binom{4}{2}=6\) (one NSP is a segment and the other are singletons). Using Propositions 1 and 2, we conclude that \(t_{5}^{\prime}=\binom{5}{2} a_{3}+\binom{5}{1} c_{4}=10.3+5.2=40\), since either there are two singletons and a three-node NSP, or one singleton and two disjoint two-node NSPs.
Let us find \(t_{6}^{\prime}\). The number of singletons among the three NSPs can be:
– two: \(\binom{6}{2} a_{4}=15.8=120\) choices;
– one: \(6 c_{5}=6.15=90\) choices;
– zero: \(t_{6}=5\) choices.
Thus \(t_{6}^{\prime}=120+90+5=215\).
Proposition 7. If \(n \geq 4\) then
\[ t_{n}^{\prime}=\tfrac{2^{n-12}}{90} n(n-1)(n-2)\left(n^{4}+2 n^{3}+179 n^{2}-182 n+3240\right) . \]
Proof: The number of singletons among the three NSPs can be:
– two: \(\binom{n}{2} a_{n-2}=n(n-1)(n-2) 2^{n-6}\) choices;
– one: \(n_{n-1}=\tfrac{1}{3} n(n-1)(n-2)(n-4)(n+3) 2^{n-9}\) choices;
– zero: \(t_{n}=\tfrac{1}{90} n(n-1)(n-2)(n-4)(n-5)(n+2)(n+9) 2^{n-12}\) choices.
Thus
\[ \begin{gathered} t_{n}^{\prime}=\tfrac{2^{n-12}}{90} n(n-1)(n-2)(5760+240(n-4)(n+3)+(n-4)(n-5)(n+2)(n+9))= \\ =\tfrac{2^{n-12}}{90} n(n-1)(n-2)\left(5760+240 n^{2}-240 n-2880+n^{4}+2 n^{3}-61 n^{2}+58 n+360\right)= \\ \quad=\tfrac{2^{n-12}}{90} n(n-1)(n-2)\left(n^{4}+2 n^{3}+179 n^{2}-182 n+3240\right) . \end{gathered} \]
Remark. The formula yields \(t_{4}^{\prime}=6, t_{5}^{\prime}=40\) and \(t_{6}^{\prime}=215\) that comply with our initial observations. However, if we insist on applying it for \(n=3\), we need to round the result to the nearest integer 1.
REFERENCES
KORTEZOV, I., 2020. How the Winter Mathematics Contest appeared in OEIS, Matematika, vol. 58, no. 2, pp. 20 – 24. ISSN: 0204-6881 [in Bulgarian]
KORTEZOV, I., 2022. Sets of Non-self-intersecting Paths Connecting the Vertices of a Convex Polygon, Mathematics and Informatics, vol. 65, no. 6. ISSN:1310-2230.
KORTEZOV, I., 2022a. Sets of Paths between Vertices of a Polygon, Mathematics Competitions, vol. 35, no. 2, pp. 35 – 43. AUSTRALIAN MATHEMATICS TRUST, produced by AMT Publishing on behalf of the World Federation of National Mathematics Competitions. ISSN:1031-7503, http://www.wfnmc.org/journal.html
KORTEZOV, I., 2023. Counting paths between points on a circle, submitted in Commentationes Mathematicae Universitatis Carolinae, ISSN: 0010-2628
SLOANE, N.J.A., 2020.On-line Encyclopaedia of Integer Sequences, https://oeis.org/A001792.
SLOANE, N.J.A., 2022. On-line Encyclopaedia of Integer Sequences, https://oeis.org/A308914.
SLOANE, N.J.A., 2023. On-line Encyclopaedia of Integer Sequences, https://oeis.org/A362786.