Research Project: Combinatorial Enumeration and Generation Setup: Let n 2 be an integer. Let Cn (with parameter n) be a circle subdivided onto n equal pieces - at each subdivision point there is a position also called a seat. We say also that Cn has n positions each situated on equal distances from its two neighbors or equivalently, there are n seats placed on regular distances around the circle. In some situations, it will be convenient to number the positions from 1 to n starting from the top position. A Combinatorial Structure is a circle Cn together with a set of weights - one for each position; to each position i, we assign a weight wi with 2 wi (n-1). We can denote a Combinatorial Structure with a sequence of the following type:(n, w1, w2, w3, , wn) where n 2 is an integer and each wi is an integer between 2 and (n-1), both limits inclusive. When n is fixed, we will drop it. So (n, w1, w2, w3, , wn) becomes just (w1, w2, w3, , wn). Equivalent transformation: Two Combinatorial Structures are considered equivalent when the first can be transformed by rotation to look as the second with respect to its weights. It is obvious that every two equivalent Combinatorial Structures must reside on circles with an equal number of positions. In analytical form, the combinatorial structure (n, w1, w2, w3, , wn) is equivalent to (n, w'1, w'2, w'3, , w'n) if there is a cycle shift such that when applied to the sequence of weights w1, w2, w3, , wn we get the sequence w'1, w'2, w'3, , w'n. For example, if w4, w5, w6, , wn, w1, w2, w3 = w'1, w'2, w'3, , w'n, then (n, w1, w2, w3, , wn) is equivalent to (n, w'1, w'2, w'3, , w'n). Canonical form: A Combinatorial Structure is in canonical form iff it is alphabetically greater or equal to all equivalent to it Combinatorial Structures. For example, when n = 5, the structure (5, 2, 3, 2, 3) is in canonical form because it is alphabetically greater than the other four equivalent to it Combinatorial Structures: (2, 3, 2, 3, 5), (3, 2, 3, 5, 2), (2, 3, 5, 2, 3), (3, 5, 2, 3, 2). Question: What is the total number of combinatorial structures for a given value of the parameter n? Each weight could be between 2 and (n-1). Answer: We can apply the product rule. The total = (n-2)*(n-2)*... *(n-2) = (n - 2)n To Do: 1) Prove that the above relation between two combinatorial structures is really an equivalent relation. 2) Develop an algorithm to compare two Combinatorial Structures and decide if the two are equivalent or not. Then encode the above algorithm in your favorite programming language. (Trivial!) 3) Develop an algorithm to find the canonical form of a given Combinatorial Structure. Then encode the algorithm in your favorite programming language. (Trivial!) 4) Develop an algorithm to find the number of equivalence classes for all structures of size n. Then encode the algorithm in your favorite programming language. (Not so Trivial!) In the examples below, the Combinatorial structure in red is in canonical form. Example1: For n = 3, obviously, the number of equivalence classes is one because there is only one combinatorial structure: (2, 2, 2). Example2: For n= 4, we can find the number of equivalence classes by hand: From the restriction 2 wi (n-1) we have that 2 wi (4-1) which is 2 wi 3. Bellow all Canonical forms are red in color. CLASS 1: (2,2,2,2) // only 2s CLASS 2: (3,2,2,2), (2,3,2,2), (2,2,3,2), (2,2,2,3) // only one 3 CLASS 3: (3,2,3,2), (2,3,2,3) // only two 3s and not next to each other CLASS 4: (3,3,2,2), (2,3,3,2), (2,2,3,3), (3,2,2,3)// two 3s and next to each other CLASS 5: (3,3,3,2), (2,3,3,3), (3,2,3,3), (3,3,2,3) //only one 2s CLASS 6: (3,3,3,3) // only 3s Notice that 1 + 4 + 2 + 4 + 4 + 1 = 16 = (4 - 2)4 = 24 = 16 So, for n = 4, the number of equivalence classes is 6. Example3: For n= 5, we will find the number of equivalent classes also by hand. From the restriction 2 wi (n-1) we have that each wi: 2 wi 4. CLASS 1: (2, 2, 2, 2, 2) // only 2s CLASS 2: (3,2,2,2,2), (2,3,2,2,2), (2,2,3,2,2), (2,2,2,3,2), (2,2,2,2,3) // only one 3 CLASS 3: (3,2,3,2,2), (2,3,2,3,2), (2,2,3,2,3), (3,2,2,3,2), (2,3,2,2,3) // only two 3s and not next to each other CLASS 4: (3,3,2,2,2), (2,3,3,2,2), (2,2,3,3,2), (2,2,2,3,3), (3,2,2,2,3) //only two 3s and next to each other CLASS 5: (3,3,2,3,2), (2,3,3,2,3), (3,2,3,3,2), (2,3,2,3,3), (3,2,3,2,3) // only three 3s and two 3s are next to each other CLASS 6: (3,3,3,2,2), (2,3,3,3,2), (2,2,3,3,3), (3,2,2,3,3), (3,3,2,2,3) // only three 3s and next to each other CLASS 7: (3,3,3,3,2), (2,3,3,3,3), (3,2,3,3,3), (3,3,2,3,3), (3,3,3,2,3) // 4 3s and one 2 CLASS 8: (3, 3, 3, 3, 3) // only 3s REPEAT classes from 2 to 8 but exchange every 3 with 4 CLASS 9: (4,3,3,3,3), (3,4,3,3,3), (3,3,4,3,3), (3,3,3,4,3), (3,3,3,3,4) // only one 4, everything else is 3 CLASS 10: (4,3,4,3,3), (3,4,3,4,3), (3,3,4,3,4), (4,3,3,4,3), (3,4,3,3,4) // only two 4s and not next to each other CLASS 11: (4,4,3,3,3), (3,4,4,3,3), (3,3,4,4,3), (3,3,3,4,4), (4,3,3,3,4) //only two 4s and next to each other CLASS 12: (4,4,3,4,3), (3,4,4,3,4), (4,3,4,4,3), (3,4,3,4,4), (4,3,4,3,4) // only three 4s and two 4s are next to each other CLASS 13: (4,4,4,3,3), (3,4,4,4,3), (3,3,4,4,4), (4,3,3,4,4), (4,4,3,3,4) // only three 4s and next to each other CLASS 14: (4,4,4,4,3), (3,4,4,4,4), (4,3,4,4,4), (4,4,3,4,4), (4,4,4,3,4) //4 4s and 1 3 CLASS 15: (4,4,4,4,4) // only 4s REPEAT classes from 9 to 15 but exchange every 3 with 2 CLASS 16: (4,2,2,2,2), (2,4,2,2,2), (2,2,4,2,2), (2,2,2,4,2), (2,2,2,2,4) // only one 4, everything else is 2 CLASS 17: (4,2,4,2,2), (2,4,2,4,2), (2,2,4,2,4), (4,2,2,4,2), (2,4,2,2,4) // only two 4s and not next to each other CLASS 18: (4,4,2,2,2), (2,4,4,2,2), (2,2,4,4,2), (2,2,2,4,4), (4,2,2,2,4) //only two 4s and next to each other CLASS 19: (4,4,2,4,2), (2,4,4,2,4), (4,2,4,4,2), (2,4,2,4,4), (4,2,4,2,4) // only three 4s and two 4s are next to each other CLASS 20: (4,4,4,2,2), (2,4,4,4,2), (2,2,4,4,4), (4,2,2,4,4), (4,4,2,2,4) // only three 4s and next to each other CLASS 21: (4,4,4,4,2), (2,4,4,4,4), (4,2,4,4,4), (4,4,2,4,4), (4,4,4,2,4) //4 4s and 1 2 // From here on, every combinatorial structure must have at least one 4, at least one 3 and at least one 2 CLASS 22: (4,3,2,2,2), (2,4,3,2,2), (2,2,4,3,2), (2,2,2,4,3), (3,2,2,2,4) 3 2s next to each other CLASS 23: (4,2,3,2,2), (2,4,2,3,2), (2,2,4,2,3), (3,2,2,4,2), (2,3,2,2,4) CLASS 24: (4,2,2,3,2), (2,4,2,2,3), (3,2,4,2,2), (2,3,2,4,2), (2,2,3,2,4) CLASS 25: (4,2,2,2,3), (3,4,2,2,2), (2,3,4,2,2), (2,2,3,4,2), (2,2,2,3,4) CLASS 26: (4,3,3,2,2), (2,4,3,3,2), (2,2,4,3,3), (3,2,2,4,3), (3,3,2,2,4) CLASS 27: (4,3,2,2,3), (3,4,3,2,2), (2,3,4,3,2), (2,2,3,4,3), (3,2,2,3,4) CLASS 28: (4,2,3,3,2), (2,4,2,3,3), (3,2,4,2,3), (3,3,2,4,2), (2,3,3,2,4) CLASS 29: (4,2,2,3,3), (3,4,2,2,3), (3,3,4,2,2), (2,3,3,4,2), (2,2,3,3,4) CLASS 30: (4,3,2,3,2), (2,4,3,2,3), (3,2,4,3,2), (2,3,2,4,3), (3,2,3,2,4) CLASS 31: (4,2,3,2,3), (3,4,2,3,2), (2,3,4,2,3), (3,2,3,4,2), (2,3,2,3,4) CLASS 32: (4,2,3,3,3), (3,4,2,3,3), (3,3,4,2,3), (3,3,3,4,2), (2,3,3,3,4) CLASS 33: (4,3,2,3,3), (3,4,3,2,3), (3,3,4,3,2), (2,3,3,4,3), (3,2,3,3,4) CLASS 34: (4,3,3,2,3), (3,4,3,3,2), (2,3,4,3,3), (3,2,3,4,3), (3,3,2,3,4) CLASS 35: (4,3,3,3,2), (2,4,3,3,3), (3,2,4,3,3), (3,3,2,4,3), (3,3,3,2,4) CLASS 36: (4,4,4,3,2), (2,4,4,4,3), (3,2,4,4,4), (4,3,2,4,4), (4,4,3,2,4) CLASS 37: (4,3,4,2,4), (4,4,3,4,2), (2,4,4,3,4), (4,2,4,4,3), (3,4,2,4,4) CLASS 38: (4,4,2,3,4), (4,4,4,2,3), (3,4,4,4,2), (2,3,4,4,4), (4,2,3,4,4) CLASS 39: (4,4,2,2,3), (3,4,4,2,2), (2,3,4,4,2), (2,2,3,4,4), (4,2,2,3,4) CLASS 40: (4,4,2,3,2), (2,4,4,2,3), (3,2,4,4,2), (2,3,2,4,4), (4,2,3,2,4) CLASS 41: (4,4,3,2,2), (2,4,4,3,2), (2,2,4,4,3), (3,2,2,4,4), (4,3,2,2,4) CLASS 42: (4,3,4,2,2), (2,4,3,4,2), (2,2,4,3,4), (4,2,2,4,3), (3,4,2,2,4) CLASS 43: (4,3,2,4,2), (2,4,3,2,4), (4,2,4,3,2), (2,4,2,4,3), (3,2,4,2,4) CLASS 44: (4,2,4,3,2), (2,4,2,4,3), (3,2,4,2,4), (4,3,2,4,2), (2,4,3,2,4) CLASS 45: (4,2,4,2,3), (3,4,2,4,2), (2,3,4,2,4), (4,2,3,4,2), (2,4,2,3,4) CLASS 46: (4,4,3,3,2), (2,4,4,3,3), (3,2,4,4,3), (3,3,2,4,4), (4,3,3,2,4) CLASS 47: (4,4,3,2,3), (3,4,4,3,2), (2,3,4,4,3), (3,2,3,4,4), (4,3,2,3,4) CLASS 48: (4,4,2,3,3), (3,4,4,2,3), (3,3,4,4,2), (2,3,3,4,4), (4,2,3,3,4) CLASS 49: (4,2,4,3,3), (3,4,2,4,3), (3,3,4,2,4), (4,3,3,4,2), (2,4,3,3,4) CLASS 50:(4,2,3,4,3), (3,4,2,3,4), (4,3,4,2,3), (3,4,3,4,2), (2,3,4,3,4) CLASS 51: (4,3,4,2,3), (3,4,3,4,2), (2,3,4,3,4), (4,2,3,4,3), (3,4,2,3,4) CLASS 52: (4,3,4,3,2), (2,4,3,4,3), (3,2,4,3,4), (4,3,2,4,3), (3,4,3,2,4) // Maybe there is a duplicate class above. So, for n = 5, the number of equivalence classes is (3 + (243-3)/5) = 3 + 48 = 51. Check if the total number of combinatorial structures equals to (n - 2)n = 35 = 243. 5) Run the above algorithm to find the number of equivalence classes for the parameter n from 3 to the maximum you can on your computer. Like maybe n 20. Present your result in a table with two columns:

n =	Number of equivalent classes
3	1
4	6
5	???
6
7

8