https://doi.org/10.53656/math2022-6-4-set

Резюме. The paper deals with counting the sets of non-self-intersecting paths whose nodes form a partitioning of the set of vertices of a given convex polygon. There turn to exist compact formulae when the magnitude of these sets is fixed. Some of these formulae provide new properties for some of the entries of the Online Encyclopedia of Integer Sequences, while others generate new entries therein.

Ключови думи: enumerative combinatorics; non-self-intersecting paths; convex polygons; OEIS

1. Introduction

This paper is inspired by a problem from the Winter Mathematics Contest 2020, a Bulgarian important and difficult high-school competition, asking for counting the number of non-self-intersecting paths whose nodes are vertices of a given convex \(n\)gon. This problem turned out to generate new properties for two of the sequences in the On-line Encyclopedia of Integer Sequences (OEIS) (Sloane A001792; A261064). As a result, the list of properties of these sequences was enriched. Similar combinatorial questions were answered in (Kortezov 2020) and they generated new sequences for OEIS (Sloane A308914; A332426). This paper finds further compact formulae when varying the number of paths whose nodes are disjoint subsets whose union is the set of vertices of the polygon; they depend on whether one-node paths are allowed.

2. Some preliminary definitions and results

All variables in this paper denote positive integers.

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 (NSP) and points \(A_{1}, A_{2}, \ldots, A_{k}\) are called nodes of the NSP.

Note that, according to the definition, NSPs are 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). We will call such an NSP a singleton. It is not immediately clear whether it is reasonable to include singletons among the NSPs, so below we will calculate the results both with and without them, obtaining outcomes of comparable compactness.

Definition 2. Let \(k \gt 2\) and \(A_{1} A_{2} \ldots A_{k}\) be a convex \(k\)-gon. We will denote by \(b_{k}\) the number of NSPs whose nodes are all the vertices of \(A_{1} A_{2} \ldots A_{k}\).

For example \(b_{4}=8\) =8, as the NSPs are \(A_{1} A_{2} A_{3} A_{4}, \) \(A_{1} A_{2} A_{4} A_{3}, \) \(A_{1} A_{4} A_{2} A_{3}, \) \(A_{1} A_{4} A_{3} A_{2}\) \(A_{2} A_{1} A_{3} A_{4}, \) \(A_{2} A_{1} A_{4} A_{3},\) \( A_{2} A_{3} A_{1} A_{4}\) and \(A_{3} A_{2} A_{1} A_{4}\)

The following proposition was part of the contest problem mentioned above. Its proof can be found in (Kortezov 2020), but written in Bulgarian. That is why we include it here for the sake of completeness. The statement of the proposition has been suggested by the author and accepted in the list of properties of A001792 (Sloane A001792).

Proposition 1. If \(k \gt 2\) then \(b_{k}=k \cdot 2^{k-3}\).

Proof. There are \(k\) choices for the first vertex of the NSP. For each subsequent vertex, except for the last one, there are 2 choices – the leftmost or the rightmost unused vertex (in all other cases part of the vertices remain separated from the rest ones and there is no way to conclude without self-intersection). In the above argument each NSP has been counted twice (once from each of its end-nodes), hence \(b_{k}=k .2^{k-2} / 2=k .2^{k-3}\).

For example \(b_{3}=3.2^{0}=3\) (one of the sides of the triangle has to be missing) and \(b_{4}=4.2^{1}=8\), in accord with the aforementioned observations.

Remark. Proposition 1 remains valid under the natural definition for \(k=2\) (there is a single segment and \(b_{2}=2.2^{-1}=1\) ), so we will use this, too. However, if we insist to use the formula for \(k=1\), we need to rephrase it as \(b_{k}=\left\lceil k \cdot 2^{k-3}\right\rceil\), or, if we exclude singletons, as \(b_{k}=\left\lfloor k \cdot 2^{k-3}\right\rfloor\).

Definition 3. Let \(n \gt 3\) and \(A_{1} A_{2} \ldots A_{n}\) be a convex \(n\)-gon. Denote by \(d_{n}\) the number of all unordered pairs of non-singleton NSPs whose sets of nodes are disjoint and their union is the set of all vertices of the \(n\)-gon.

For example \(d_{4}=3\) with the corresponding pairs of NSPs being \(\left\{A_{1} A_{2} ; A_{3} A_{4}\right\}\), \(\left\{A_{1} A_{3} ; A_{2} A_{4}\right\}\) and \(\left\{A_{1} A_{4} ; A_{2} A_{3}\right\}\). The next proposition is proven in (Kortezov 2020) but for completeness the proof is given below. Its statement has been suggested by the author for publishing in oeis.org and accepted as A332426 (Sloane A332426).

Proposition 2. If \(n \geq 3\) then

\[ d_{n}=n(n-1) 2^{n-6}\left(2^{n-3}-1\right) \] or equivalently

\[ d_{n}=\binom{n}{2} 2^{n-5}\left(2^{n-3}-1\right) . \]

Proof. Let the first NSP have \(k\) nodes \((2 \leq k \leq n-2)\). There are \(\binom{n}{k}=\tfrac{n!}{k!(n-k)!}\) choices for the \(k\) vertices of the \(n\)-gon covered by it. By Proposition 1 there are \(k .2^{k-3}\) NSPs with these nodes and \((n-k) 2^{n-k-3}\) NSPs with nodes at the remaining vertices of the \(n\)-gon. Each unordered pair of NSPs is thus counted twice, so:

\[ \begin{aligned} & d_{n}=\tfrac{1}{2} \sum_{k=2}^{n-2} \tfrac{n!}{k!(n-k)!} \cdot k 2^{k-3} \cdot(n-k) 2^{n-k-3}= \\ & =n(n-1) 2^{n-7} \sum_{k=2}^{n-2} \tfrac{(n-2)!}{(k-1)!((n-2)-(k-1))!}=n(n-1) 2^{n-7} \sum_{k=2}^{n-2}\binom{n-2}{k-1}= \\ & \quad=n(n-1) 2^{n-7}\left((1+1)^{n-2}-1-1\right)=n(n-1) 2^{n-6}\left(2^{n-3}-1\right) . \end{aligned} \]

Let us illustrate the validity of the above formula for small \(n\). We have \(d_{4}=4.3 \cdot 2^{-2}(2-1)=3\) in accord with the initial observations. Also \(d_{5}=5.4 .2^{-1}\left(2^{2}-1\right)=30\). Indeed, in a pentagon one NSP will be a segment \(\left(\binom{5}{2}=10\right.\) choices) and for the remaining 3 vertices there are 3 choices for the pair NOT connected by a segment. Further, \(d_{6}=6.5 .2^{0}\left(2^{3}-1\right)=210\) and for a hexagon the variants are:

– one NSP is a segment \(\left(\binom{6}{2}=15\right.\) choices) and for the remaining 4 vertices there are \(b_{4}=8\) choices, leading to \(15.8=120\) variants;

– each NSP has three nodes: there are \(\tfrac{1}{2}\binom{6}{3}=10\) choices for the three vertices (as it is not important which NSP is chosen first) and 3 choices for the pair NOT connected by a segment in each triple of vertices, leading to 10.3.3 \(=90\) variants;

-so indeed \(120+90=210\).

Remark. The above formula is valid also for \(n=3\) since \(d_{3}=0\) is trivially true.

3. New results

Definition 4. Let \(n \gt 4\) and \(A_{1} A_{2} \ldots A_{n}\) be a convex \(n\)-gon. Denote by \(e_{n}\) the number of all unordered triples of non-singleton NSPs whose sets of nodes are disjoint and their union is the set of vertices of the \(n\)-gon. For example \(e_{6}=\tfrac{6!}{2!2!2!3!}=15\) and \(e_{7}=\tfrac{7!\cdot 3}{2!2!3!2!}=315\) (the latter holds since the 7 vertices have to be split into two pairs and one triple, the order of the two pairs is irrelevant, and there are 3 choices of the segment in the triple not connected by a segment).

Proposition 3. If \(n \geq 6\) then

\[ \begin{aligned} & e_{n}=n(n-1)(n-2) 2^{n-10}\left(3^{n-4}-2^{n-3}+1\right) \\ & e_{n}=\binom{n}{3} 2^{n-9}\left(3^{n-3}-3.2^{n-3}+3\right) \end{aligned} \]

Proof. Let first NSP have \(n-k\) nodes \((3 \leq k \leq n-2)\). There are \(\tfrac{n!}{k!(n-u)!}\) choices for the \(n-k\) vertices of the \(n\)-gon it must include and \(b_{n-k}=(n-k) 2^{n-k-3}\) ways of connecting them via a NSP. By Proposition 2 there are \(d_{k}=k(k-1) 2^{k-6}\left(2^{k-3}-1\right)\) variants for the two NSPs connecting the remaining vertices. This way each unordered triple of NSPs is counted three times depending on which NSP is chosen first, hence

\[ \begin{aligned} & e_{n}=\tfrac{1}{3} \sum_{k=3}^{n-2} \tfrac{n!}{k!(n-k)!}(n-k) 2^{n-k-3} \cdot k(k-1) 2^{k-6}\left(2^{k-3}-1\right)= \\ & =\tfrac{1}{3} \sum_{k-3}^{n-2} \tfrac{n!}{(k-2)!(n-k-1)!} 2^{n-9}\left(2^{k-3}-1\right)= \\ & =\tfrac{2^{n-9}}{3} \sum_{j=1}^{n-4} \tfrac{n!}{j!(n-3-j)!}\left(2^{j-1}-1\right)= \\ & =\tfrac{n(n-1)(n-2) 2^{n-9}}{3} \sum_{j=1}^{n-4} \tfrac{(n-3)!}{j!(n-3-j)!}\left(2^{j-1}-1\right)= \\ & =\tfrac{n(n-1)(n-2) 2^{n-9}}{3}\left(\tfrac{1}{2} \sum_{j=1}^{n-4} \tfrac{(n-3)!}{j!(n-3-j)!} 2^{j}-\sum_{j=1}^{n-4} \tfrac{(n-3)!}{j!(n-3-j)!}\right)= \\ & =\tfrac{n(n-1)(n-2) 2^{n-9}}{3}\left(\tfrac{1}{2}\left(3^{n-3}-2^{n-3}-1\right)-\left(2^{n-3}-1\right)\right)= \\ & =\tfrac{n(n-1)(n-2) 2^{n-10}\left(3^{n-3}-3 \cdot 2^{n-3}-3\right)}{3}= \\ & =n(n-1)(n-2) 2^{n-10}\left(3^{n-4}-2^{n-3}+1\right) . \quad \text {. } \end{aligned} \]

Let us illustrate the validity of the formula for small \(n\). We have

\[ \begin{aligned} & e_{6}=6 \cdot 5 \cdot 4 \cdot 2^{-4}\left(3^{2}-2^{3}+1\right)=15 \cdot 2^{-1} \cdot 2=15 \text { and } \\ & e_{7}=7 \cdot 6 \cdot 5 \cdot 2^{-3}\left(3^{3}-2^{4}+1\right)=105 \cdot 2^{-2} \cdot 12=315 \end{aligned} \] both in accord with the initial observations. In addition

\[ e_{8}=8.7 .6 .2^{-2}\left(3^{4}-2^{5}+1\right)=42.100=4200 \] and indeed \(e_{8}=\tfrac{8!b_{4}}{2!2!4!2!}+\tfrac{8!b_{3} b_{3}}{2!3!3!2!}=1680+2520=4200\) (here the first summand corresponds to the case when the 8 vertices are split into two pairs and a set of four, the order of the two pairs being irrelevant; the second one corresponds to splitting into a pair and two triples, the order of the triples being irrelevant).

Remark. The above formula is valid also for \(n=4\) and \(n=5\) since \(e_{4}=e_{5}=0\) holds for trivial reasons; we will use these, too. However, the result from the above Proposition for \(n=3\) (which is outside its scope) would be \(e_{3}=3.2 \cdot 1.2^{-7}\left(3^{-1}-1+1\right)=2^{-6}\), so if we insist on applying it, we can modify it to \(\left\lfloor n(n-1)(n-2) 2^{n-10}\left(3^{n-4}-2^{n-3}+1\right)\right\rfloor\) or just round it to the closest integer to get \(e_{3}=0\) that corresponds to reality.

Definition 5. Let \(n \geq 4\). Given a convex \(n\)-gon, denote by \(g_{n}\) the number of all unordered quadruples of non-singleton NSPs whose sets of nodes are disjoint and their union is the set of vertices of the \(n\)-gon.

For example \(g_{8}=\tfrac{8!}{2!2!2!2!4!}=105\) and \(g_{9}=\tfrac{9!\cdot 3}{2!2!2!3!3!}=3780\) (the latter holds since have to split the 9 vertices into three pairs and one triple, the order of the three pairs is irrelevant, and there are 3 choices of the segment in the triple not connected by a segment).

Proposition 4. If \(n \geq 8\) then

\[ g_{n}=\tfrac{1}{3} n(n-1)(n-2)(n-3) 2^{n-15}\left(4^{n-4}-4 \cdot 3^{n-4}+6 \cdot 2^{n-4}-4\right) \] or equivalently \[ g_{n}=\binom{n}{4} 2^{n-12}\left(4^{n-4}-4.3^{n-4}+6.2^{n-4}-4\right) . \]

Proof. Let the first NSP have \(n-k\) nodes (\(4 \leq k \leq n-2\) ). There are \(\tfrac{n!}{k!(n-k)!}\) choices for the \(n-k\) vertices of the \(n\)-gon it must include and \(b_{n-k}=(n-k) 2^{n-k-3}\) ways of connecting them via a NSP. By Proposition 3 there are \(e_{k}=k(k-1)(k-2) 2^{k-10}\left(3^{k-4}-2^{k-3}+1\right)\) variants for the three NSPs connecting the remaining vertices. This way each unordered quadruple of NSPs is counted four times depending on which NSP is chosen first, hence

\[ \begin{aligned} & g_{n}=\tfrac{1}{4} \sum_{k=4}^{n-2} \tfrac{n!}{k!(n-k)!}(n-k) 2^{n-k-3} \cdot k(k-1)(k-2) 2^{k-10}\left(3^{k-4}-2^{k-3}+1\right)= \\ & =\tfrac{1}{4} \sum_{k=4}^{n-2} \tfrac{n!}{(k-3)!(n-k-1)!} 2^{n-13}\left(3^{k-4}-2^{k-3}+1\right)= \\ & =2^{n-15} \sum_{j=1}^{n-5} \tfrac{n!}{j!(n-4-j)!}\left(3^{j-1}-2^{j}+1\right)= \\ & =n(n-1)(n-2)(n-3) 2^{n-15} \sum_{j=1}^{n-5} \tfrac{(n-4)!}{j!(n-4-j)!}\left(3^{j-1}-2^{j}+1\right) \end{aligned} \] This sum can be split into the following three:

\(\tfrac{1}{3} \sum_{j=1}^{n-5} \tfrac{(n-4)!}{j!(n-4-j)!} 3^{j}=\tfrac{1}{3}\left(4^{n-4}-3^{n-4}-1\right)\)

\[ -\sum_{j=1}^{n-5} \tfrac{(n-4)!}{j!(n-4-j)!} 2^{j}=-\left(3^{n-4}-2^{n-4}-1\right) \] and

\[ \sum_{j=1}^{n-5} \tfrac{(n-4)!}{j!(n-4-j)!}=\left(2^{n-4}-1-1\right) \]

Hence

\[ \begin{aligned} & g_{n}=\tfrac{n(n-1)(n-2)(n-3) 2^{n-12}}{3.2^{3}}\left(4^{n-4}-3^{n-4}-1-3.3^{n-4}+3.2^{n-4}+3+3.2^{n-4}-6\right)= \\ & =\binom{n}{4} 2^{n-12}\left(4^{n-4}-4.3^{n-4}+6.2^{n-4}-4\right) . \end{aligned} \] Let us illustrate the validity of the formula for small \(n\). We have \(g_{8}=70.2^{-4}(256-324+96-4)=70.2^{-4} .24=35.3=105\) and \(g_{9}=126.2^{-3}(1024-972+192-4)=63.2^{-2} .240=63.60=3780\) both in accord with the initial observations.

Remark. The above formula is valid also for \(n=1,2,3\) and \(n=5,6,7\) since it yields 0 and \(g_{n}=0\) holds in all these cases for trivial reasons (we will further use the formula for \(g_{n}\) for \(n \geq 5\) ). However if we insist to use it for \(n=4\), we need to round it to the closest integer.

Let us now consider what happens if singletons are allowed.

Definition 6. Given a convex \(n\)-gon ( \(n \geq 3\) ), denote by \(d_{n}^{\prime}\) the number of all unordered pairs of NSPs whose sets of nodes are disjoint and their union is the set of all the vertices of the \(n\)-gon.

For example \(d_{4}^{\prime}=4.3+3=15\) since the respective pairs of NSP are:

– a NSP with one node (4 choices), while for the other one there are \(b_{3}=3\) choices;

– two NSP of two nodes each: \(d_{4}=3\) choices.

Proposition 5. If \(n \geq 3\) then

\[ \begin{aligned} & d_{n}^{\prime}=n(n-1) 2^{n-6}\left(2^{n-3}+3\right) \\ & d_{n}^{\prime}=\binom{n}{2} 2^{n-5}\left(2^{n-3}+3\right) . \end{aligned} \]

Proof: We need to add to the formula for \(d_{n}\) the cases when one NSP has 1 node (\(n\) choices) and the other one includes the remaining \(n-1\) vertices \(\left(b_{n-1}=(n-1) 2^{n-4}\right.\) choices \()\), hence:

\[ d_{n}^{\prime}=n(n-1) 2^{n-6}\left(2^{n-3}-1\right)+n(n-1) 2^{n-4}=n(n-1) 2^{n-6}\left(2^{n-3}+3\right) . \]

Let us illustrate the validity of the above formula for small \(n\). We have \(d_{3}^{\prime}=3.2 .2^{-3} .4=3\) (which is clearly true) and \(d_{4}^{\prime}=4.3 .2^{-2} .5=15\) in accord with the initial observations. Also \(d_{5}^{\prime}=5.4 .2^{-1} .7=70\); indeed, in the pentagon either one of the NSPs is a side or a diagonal (10 choices) and for the remaining 3 vertices there are 3 choices for the pair NOT connected by a segment, or one of the NSPs is has just one node (5 choices), while for the other one there are \(b_{4}=8\) \(b_{4}=8\) choices, totalling to \(10.3+5.8=70\) pairs of NSPs.

Definition 7. Given a convex \(n\)-gon (\(n \geq 3\) ), denote by \(e_{n}^{\prime}\) the number of all unordered triples of NSP whose sets of nodes are disjoint and their union is the set of vertices of the \(n\)-gon.

For example \(e_{3}^{\prime}=1, e_{4}^{\prime}=\binom{4}{2}=6\) and \(e_{5}^{\prime}=\tfrac{5!}{2!2!2!}+\tfrac{5!b_{3}}{3!2!}=15+30=45\).

Proposition 6. If \(n \geq 4\) then

\( e_{n}^{\prime}=n(n-1)(n-2) 2^{n-10}\left(3^{n-4}+3.2^{n-3}+9\right) \)

or equivalently

\(e_{n}^{\prime}=\binom{n}{3} 2^{n-9}\left(3^{n-3}+9.2^{n-3}+27\right) . \)

Proof. The number of singletons among the NSPs can be:

– two \(\left(n(n-1) 2^{-1}\right.\) choices); for the remaining points there are \(b_{n-2}=(n-2) 2^{n-5}\) choices, yielding \(n(n-1)(n-2) 2^{n-6}\) variants;

– one (\(n\) choices); for the remaining points there are \(d_{n-1}=(n-1)(n-2) 2^{n-7}\left(2^{n-4}-1\right)\) choices, yielding \(n(n-1)(n-2) 2^{n-7}\left(2^{n-4}-1\right)\) variants;

– zero: \(e_{n-1}=n(n-1)(n-2) 2^{n-10}\left(3^{n-4}-2^{n-3}+1\right)\) variants.

Hence

\[ \begin{aligned} & e_{n}^{\prime}=n(n-1)(n-2)\left(2^{n-6}+2^{n-7}\left(2^{n-4}-1\right)+\left(3^{n-4}-2^{n-3}+1\right)\right)= \\ & =n(n-1)(n-2) 2^{n-10}\left(16+8\left(2^{n-4}-1\right)+3^{n-4}-2^{n-3}+1\right)= \\ & =n(n-1)(n-2) 2^{n-10}\left(3^{n-4}+3.2^{n-3}+9\right) . \end{aligned} \]

Let us check the validity of the above formula for small \(n\). We have \(e_{4}^{\prime}=4.3 \cdot 2.2^{-6}\left(3^{0}+3.2+9\right)=6 \quad\) and \(\quad e_{5}^{\prime}=5.4 .3 .2^{-5}\left(3^{1}+3.4+9\right)=45\) both in accord with the initial observations. However the result from the above Proposition for \(n=3\) (which is outside its scope) would be \(e_{3}^{\prime}=3 \cdot 2 \cdot 1 \cdot 2^{-7}\left(3^{-1}+3+9\right)=2^{6}(1+36)=\tfrac{37}{64}\), so if we insist on applying it, we can modify it to \(e_{n}^{\prime}=\left\lceil n(n-1)(n-2) 2^{n-10}\left(3^{n-4}+3.2^{n-3}+9\right)\right\rceil\) or just round it to the closest integer.

Definition 8. Given a convex \(n\)-gon (\(n \geq 3\) ), denote by \(g_{n}^{\prime}\) the number of all unordered triples of NSP whose sets of nodes are disjoint and their union is the set of vertices of the \(n\)-gon.

For example \(g_{3}^{\prime}=0, g_{4}^{\prime}=1, g_{5}^{\prime}=\binom{5}{2}=10\) and \(g_{6}^{\prime}=\tfrac{6!}{2!2!2!2!}+\tfrac{6!b_{8}}{3!3!}=45+60=105\).

Proposition 7. If \(n \geq 5\) then

\[ g_{n}^{\prime}=\binom{n}{4} 2^{n-12}\left(4^{n-4}+12.3^{n-4}+54.2^{n-4}+108\right) \]

Proof. The number of singletons among the NSPs can be:

– three \(\left(\tfrac{1}{6} n(n-1)(n-2)\right.\) choices); for the remaining points there are \(b_{n-3}=(n-3) 2^{n-6}\) choices, yielding \(\tfrac{1}{6} n(n-1)(n-2)(n-3) 2^{n-6}\) variants;

–two \(\left(n(n-1) 2^{-1}\right.\) choices);fortherestthereare \(d_{n-2}=(n-2)(n-3) 2^{n-8}\left(2^{n-5}-1\right)\) choices, yielding \(n(n-1)(n-2)(n-3) 2^{n-9}\left(2^{n-5}-1\right)\) variants;

– one (\(n\) choices); for the rest there are \(e_{n-1}=(n-1)(n-2)(n-3) 2^{n-11}\left(3^{n-5}-2^{n-4}+1\right)\) choices, yielding \(n(n-1)(n-2)(n-3) 2^{n-11}\left(3^{n-5}-2^{n-4}+1\right)\) variants:

– zero: \(g_{n}=\tfrac{1}{3} n(n-1)(n-2)(n-3) 2^{n-15}\left(4^{n-4}-4.3^{n-4}+6.2^{n-4}-4\right)\) variants.

Hence

\[ \begin{aligned} & g_{n}^{\prime}=\binom{n}{4} 2^{n-12}\left(2^{8}+3.2^{6}\left(2^{5}-1\right)+3.2^{4}\left(3^{n-5}-2^{n-4}+1\right)+4^{n-4}-4.3^{n-4}+6.2^{n-4}-4\right)= \\ & =\binom{n}{4} 2^{n-12}\left(4^{n-4}+(16-4) 3^{n-4}+\left(3.2^{5}-3.2^{4}+6\right) 2^{n-4}+2^{8}-3.2^{6}+3.2^{4}-2^{2}\right)= \\ & =\binom{n}{4} 2^{n-12}\left(4^{n-4}+12.3^{n-4}+54.2^{n-4}+2^{2}\left(2^{2}-1\right)^{3}\right) . \end{aligned} \]

Let us check the validity of the above formula for small \(n\). We have \(g_{5}^{\prime}=5.2^{7}(4+12.3+54.2+108)=5.2^{-7} .256=10 \quad\) and \(g_{6}^{\prime}=5.2^{-6}(16+12.9+54.4+108)=15.2^{-6} .448=15.7=105\) both in accord with the initial observations.Also the statement is trivially true for \(n=1,2,3\). However the result from the above Proposition for \(n=4\) (which is outside its scope) would be \(g_{4}^{\prime}=2^{-8}(1+12+54+108)=\tfrac{175}{256}\) (instead of 1), so if we insist on applying it, we can just round it to the closest integer.

4. Conclusion

Let us wrap up the obtained results for the number of \(t\)-sets of NSPs whose sets of nodes form apartition of the set of vertices of the \(n\)-gon, with the natural extension for \(n=2\) (a segment):

From the above it can be conjectured that for all positive integers \(n, t\) such that \(n \gt t\) the number of \(t\)-sets of NSPs whose sets of nodes form a partition of the set of vertices of the \(n\)-gon, with thenatural extension for \(n=2\) (a segment), is

\[ 2^{n-3 t}\binom{n}{t} \sum_{i=0}^{t}\binom{t}{i} i^{n-t} 3^{t-i} \] and, when singletons are excluded,

\[ 2^{n-3 t}\binom{n}{t} \sum_{i=0}^{t}\binom{t}{i} i^{n-t}(-1)^{t-i} \]

A proof could be carried out using induction on the above scheme.

REFERENCES

KORTEZOV I., 2020. How the Winter Mathematics Contest appeared in OEIS (in Bulgarian), Matematika, 58, 20 – 24, No.2, ISSN: 0204-6881.

SLOANE N.J.A., On-line Encyclopedia of Integer Sequences, https://oeis. org/A001792.

SLOANE N.J.A., On-line Encyclopedia of Integer Sequences, https://oeis. org/A261064.

SLOANE N.J.A., On-line Encyclopedia of Integer Sequences, https://oeis. org/A308914.

SLOANE N.J.A., On-line Encyclopedia of Integer Sequences, https://oeis. org/A332426.