2
$\begingroup$

Have:

  • Circle
  • N * 2 equidistant points on circle
  • N chords connecting points into pairs
  • Exactly 1 chord connected to each points

Additional conditions:

  • Points are equivalent, so a1a2 = a2a1, aabbccdd = aaccbbdd
  • Circle can be rotated (excluding rotated copies of sequences), so aabbcc = caabbc
  • Circle can be mirrored (excluding mirror copies), so aabcbc = cbcbaa

Question is:

  • How many unique patterns P can be created for given N?

As I found, the problem refers to Pólya enumeration theorem with Necklaces and bracelets. But I don't know how to exclude patterns by additional conditions (especially by mirroring and swaping colors)

I manual-calculated soultions for N = 1, 2, 3, 4

N = 1, P = 1

N = 2, P = 2

N = 3, P = 5

N = 4, P = 17

Also I prepared visual representation of solutions for N = 1, 2, 3

1, 2 - https://i.stack.imgur.com/k2PqP.png

3 - https://i.stack.imgur.com/phOaK.png

Any suggestions for solution by single forumla? Is this correct collection? https://oeis.org/A054499

(Im novice level at combinatorics, so each step and solution I need to be re-checked and validated)

$\endgroup$
2
  • $\begingroup$ The title of OEIS A054499 does indeed seem to match your description and small examples $\endgroup$
    – Henry
    Apr 27, 2023 at 9:13
  • $\begingroup$ The bibliography at the link is extensive. The generalization to three instances each, four instances etc. does not appear to be in the OEIS yet. $\endgroup$ Apr 29, 2023 at 4:40

1 Answer 1

2
$\begingroup$

I would like to start by saying that OP has a good question that shows that effort was put into presentation and content. Note first that the OEIS says that this material is from a Ph.D. thesis by R. Read so we cannot hope for easy answers, also the formulae given by the OEIS look formidable. Note to the reader. The formulae for the case of two instances of $n$ colors each that are given at OEIS A054499 will produce an instant answer using negligable computational resources. Hence the reader is invited to study the cited papers and we will not discuss this problem here. We consider a generalization instead, namely to three, four or five instances of $n$ swappable colors. Let the parameter $k$ give the number of instances of each color. Here we have $k=3,4,5.$

The OP made good initial progress by noting that we might apply the Polya Enumeration Theorem (PET) but here we need something more general, which is Power Group Enumeration (PGE) as described by Harary and Palmer in their classic text Graphical Enumeration and by Fripertinger in his paper Enumeration in Musical Theory. PET is when we have objects with a generating function being distributed into slots while PGE also has a group acting on the objects, i.e. we count orbits with objects being distributed into slots where a permutation group permutes the slots and another the objects. This is a very simple algorithm where we just need to insert the corresponding cycle indices into the appropriate place and are ready to go. We need the cycle index of the slot permutation group and the cycle index of the object permutation group. Here we have $kn$ slots that receive one of $n$ types of labels or colors, with $k$ instances of each color and the symmetric group acting on the colors. The slot permutation group is the dihedral group on $kn$ slots $D_{kn}$ and the object permutation group is the symmetric group $S_n.$ The heart of the PGE algorithm is to compute the number of orbits by Burnside's lemma which says to average the number of assignments fixed by the elements of the power group. But this number is easy to compute. Suppose we have a permutation $\alpha$ from the slot permutation group $D_{kn}$ and a permutation $\beta$ from $S_n$. If we place the appropriate number of complete, directed and consecutive copies of a cycle from $\beta$ on a cycle from $\alpha$ then this assignment is fixed under the power group action for $(\alpha,\beta)$ , and this is possible iff the length of the cycle from $\beta$ divides the length of the cycle from $\alpha$ . The process yields as many assignments as the length of the cycle from $\beta$. The problem here is that it is not sufficient to count the assignments, we also need to classify them by the number of instances of each color that appear in the assignment, so that we may subsequently filter out the ones where each of the $n$ colors appears $k$ times. Hence we need a generating function and we track how many instances of each color have been placed when covering the cycles of $\alpha.$ This will produce a product of sums in the variables $A_1$ to $A_n$ of the generating function where the sum terms represent a single covering of a single cycle from $\alpha$ and the variables represent the colors. Once all of these have been collected for the pair we may extract the coefficient on $A_1^k \times\cdots\times A_n^k$ by sequentially differentiating $k$ times with respect to the variables and evaluating with the variable set to zero. We keep it compact by differentiating rather than expanding the product, which would produce an exponential number of terms. With the object permutation group being the symmetric group the generating function corresponding to the cycles from $\beta$ is obtained by constructing a representative in the $n$ variables for the colors whose factorization into cycles is $\beta$.

For the two cycle indices we have the usual index for the dihedral group starting from the cyclic group where we have

$$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}.$$

and

$$Z(D_n) = \frac{1}{2} Z(C_n) + \begin{cases} \frac{1}{2} a_1 a_2^{(n-1)/2} & n \text{ odd} \\ \frac{1}{4} \left( a_1^2 a_2^{n/2-1} + a_2^{n/2} \right) & n \text{ even.} \end{cases}$$

For the object permutation group there is the recurrence by Lovasz for the cycle index $Z(S_n)$, which is

$$Z(S_n) = \frac{1}{n} \sum_{\ell=1}^n a_\ell Z(S_{n-\ell}) \quad\text{where}\quad Z(S_0) = 1.$$

With these two cycle indices we are ready to run the PGE algorithm, iterating over pairs $(\alpha,\beta)$ and collecting the respective contributions. The code below shows how to implement this, which is extremely straightforward, requiring no additional data structures. There are some minor tweaks such as that we cannot cover a cycle from $\alpha$ with more than $k$ copies of a cycle from $\beta$ as we cannot use a variable more than $k$ times. We obtain the sequence for the number of chord diagrams:

$$1, 2, 5, 17, 79, 554, 5283, 65346, 966156, 16411700, 312700297, \\ 6589356711, 152041845075, 3811786161002, 103171594789775, \ldots$$

which points to OEIS A054499 as noted by OP. Here is the value for $n=42$

$$3192542278675493533067925669542823243829694232124271825606504.$$

As we can see these values match the OEIS data, which shows the algorithm is working. Here is the sequence for three instances which is now at OEIS A362657:

$$1, 1, 3, 25, 713, 47283, 5301453, 862284559, \\ 190869905951, 55139769554236, \ldots$$

Four instances is at OEIS A362658:

$$1, 1, 7, 297, 83488, 63698215, 93945180662, 235528677557853, \ldots$$

Five instances is at OEIS A362659:

$$1, 1, 13, 4378, 12233517, 103894521686, 2056311437607449, \\ 81740134830144396361, \ldots$$

This was the code:

with(combinat); with(numtheory);

pet_cycleind_symm :=
proc(n)
option remember;
local l;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;


pet_cycleind_cyclic :=
proc(n)
local d;

    add(phi(d)*a[d]^(n/d), d in divisors(n))/n;
end;

pet_cycleind_dihedral :=
proc(n)
local s;

    s := 1/2*pet_cycleind_cyclic(n);

    if(type(n, odd)) then
        s := s + 1/2*a[1]*a[2]^((n-1)/2);
    else
        s := s + 1/4*(a[1]^2*a[2]^((n-2)/2) + a[2]^(n/2));
    fi;

    s;
end;


pet_prod2vrep :=
proc(varp)
    local v, d, q, res, len, cyc, p;

    q := 1; res := [];

    for v in indets(varp) do
        d := degree(varp, v);
        len := op(1, v);

        for cyc to d do
            res :=
            [op(res), mul(A[p], p=q..q+len-1)];
            q := q+len;
        od;
    od;

    res;
end;

BRACL_CONTRIB :=
proc(gf, n, k)
local q, contr;

    contr := gf;
    for q to n do
        contr := diff(contr, A[q]$k);
        contr := 1/k!*subs(A[q]=0, contr);
    od;

    contr;
end;

BRACL :=
proc(n, k)
option remember;
local idx_slots, idx_colors, res, term_a, term_b,
    v_a, cyc_b, inst_a, inst_b, len_a, len_b, p, q, rep;

    if n = 0 or n = 1 then return 1 fi;

    idx_slots := pet_cycleind_dihedral(k*n);
    idx_colors := pet_cycleind_symm(n);

    res := 0;

    for term_b in idx_colors do
        rep := pet_prod2vrep(term_b);

        for term_a in idx_slots do
            p := 1;

            for v_a in indets(term_a) do
                len_a := op(1, v_a);
                inst_a := degree(term_a, v_a);

                q := 0;

                for cyc_b in rep do
                    len_b := nops(cyc_b);

                    if len_a mod len_b = 0 then
                        if len_a/len_b <= k then
                            q := q + len_b*cyc_b^(len_a/len_b);
                        fi;
                    fi;
                od;

                p := p*q^inst_a;
            od;

            res := res +
            lcoeff(term_a)*lcoeff(term_b)
            *BRACL_CONTRIB(p, n, k);
        od;
    od;

    res;
end;
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .