One day, my friend texted me a problem out of the blue:

How many different bracelets can be made with 8 beads, where there are 2 red beads, 2 yellow beads, 2 green beads, and 2 blue beads?

(You must use all beads. Bracelets that can be transformed into one another by rotation or reflection do not count as different bracelets. That is, the bracelets have no beginning or end, no front or back. The beads are non-directed, it doesn’t matter which way they face.)

My initial strategy was to take the total number of “strings” that could be made from those beads (8! / 2^4) and then divide 8 to account for the number of possible rotational positions, then divide that by the number of axes of symmetry (8). However, my friend pointed out that this was wrong–some of these combinations are over-counted the same number of times.

I thought that it would be easiest to work through the problem if I started with the solution. So, I wrote up some quick code in Julia to count the number of unique combinations.

function is_equivalent(a, b)

    for i in 1:length(a)
        if a[i] != b[i]
            return false
        end
    end
    return true
end

is_equivalent (generic function with 1 method)

function is_rotationally_equivalent(a, b)
    a_temp = a
    for i in 1:length(a)
        if is_equivalent(a_temp, b)
            return true
        end
        a_temp = push!(a_temp[2:length(a)], a_temp[1])
    end
    return false

end

is_rotationally_equivalent (generic function with 1 method)

function is_symmetrically_and_rotationally_equivalent(a, b)
    a_reversed = reverse(a)
    if is_rotationally_equivalent(a, b)
        return true
    elseif is_rotationally_equivalent(a_reversed, b)
        return true
    else

        return false
    end
end
     
    

is_symmetrically_and_rotationally_equivalent (generic function with 1 method)

using Combinatorics
all_perms_list = collect(permutations(["r", "r", "g", "g", "b", "b", "y", "y"], 8))
keep_list = []
for i in 2:length(all_perms_list)
    already_in_list = false
    for j in 1:length(keep_list)
        if is_symmetrically_and_rotationally_equivalent(all_perms_list[i], keep_list[j])
            already_in_list = true
        end
    end
    if !already_in_list   
        push!(keep_list, all_perms_list[i])
    end
end
print(length(keep_list))

171

This code only took a couple of minutes to run (Julia’s speed always impresses me). The result was 171, and using the combinatorics techniques I had previously, I wasn’t able to reverse-engineer the answer.

Eventually, I came across a new technique that would help me solve this problem: Burnside’s lemma (also known as the Cauchy–Frobenius lemma).

This lemma is given as:

$|X/G| = \frac{1}{|G|} \sum_{g \in G}|X^g|$

I’ll explain some of the terms in this formula to make it more understandable:

X represents the set of all possible (non-unique) bracelets that can be made
G represents the group of possible reflections/rotations in our situation
|X/G| represents the number of “orbits” (or in our case, the number of unique bracelets that can be made)
|G| represents the number items in the “group” of reflections/rotations in our situation.
$g \in G$ indicates that the the summation iterates over all possible reflections/rotations in our situation
$X^g$ indicates the set of elements in X that are fixed by a given group. That is, the number of possible elements that do not change after the given reflection/rotation configuration is applied.

In order to understand how to apply burnside’s lemma, let’s first consider a simple situation: Imagine we want to determine how many unique combinations of 8 beads can be created, with 4 possible colors, and exactly 2 beads of each color in the string. Reverse sequences of the string count as the same string, so the following strings are equivalent:

using Graphs, GraphPlot
using Compose, Cairo, Fontconfig
using Colors

function create_graph(sequence, circular = true)
    colors_dict = Dict([('r', 1), ('b', 2), ('y', 3), ('g', 4)])

    membership_list = []

    for letter in sequence
        push!(membership_list, colors_dict[letter])
    end

    g = SimpleGraph(8)
    
    for i in 1:7
        add_edge!(g, i, i + 1)
    end
    if circular
        add_edge!(g, 8, 1)
    end

    nodelabel = fill("", length(8))


    nodecolor = [colorant"red", colorant"blue", colorant"yellow", colorant"green"]
    # membership color
    nodefillc = nodecolor[membership_list]
    if circular
        locs_x = [0, 1, 2, 3, 3, 2, 1, 0]
        locs_y = [2, 3, 3, 2, 1, 0, 0, 1]
    else
        locs_x = [1, 2, 3, 4, 5, 6, 7, 8]
        locs_y = repeat([0], 8)
    end



    g = gplot(g, locs_x, locs_y, nodefillc=nodefillc, )
    
    draw(PNG(sequence * ["","circular"][circular * 1 + 1] * ".png", 16cm, 16cm),g)
    g
end

create_graph (generic function with 2 methods)

create_graph("ryygbrbg", false)

<svg xmlns=“http://www.w3.org/2000/svg" xmlns:xlink=“http://www.w3.org/1999/xlink" version=“1.2” width=“141.42mm” height=“100mm” viewBox=“0 0 141.42 100” stroke=“none” fill="#000000” stroke-width=“0.3” font-size=“3.88”

 id="img-237f1acd">

]]>

create_graph(reverse("ryygbrbg"), false)

<svg xmlns=“http://www.w3.org/2000/svg" xmlns:xlink=“http://www.w3.org/1999/xlink" version=“1.2” width=“141.42mm” height=“100mm” viewBox=“0 0 141.42 100” stroke=“none” fill="#000000” stroke-width=“0.3” font-size=“3.88”

 id="img-7a975d17">

]]>

create_graph("ggbbyyrr", false)

<svg xmlns=“http://www.w3.org/2000/svg" xmlns:xlink=“http://www.w3.org/1999/xlink" version=“1.2” width=“141.42mm” height=“100mm” viewBox=“0 0 141.42 100” stroke=“none” fill="#000000” stroke-width=“0.3” font-size=“3.88”

 id="img-0176efc2">

]]>

In this situation, there are two groups G: the null group (with no reverse order) and the group which applies the action of reversing the string. The number elements fixed by each group is:

For the null group: 8! / 2^4
For the “reversing string” group: 4!

A string can be fixed under reversal only if the first four beads are identical to the reverse of the last four beads:

create_graph("rgbyybgr", false)

<svg xmlns=“http://www.w3.org/2000/svg" xmlns:xlink=“http://www.w3.org/1999/xlink" version=“1.2” width=“141.42mm” height=“100mm” viewBox=“0 0 141.42 100” stroke=“none” fill="#000000” stroke-width=“0.3” font-size=“3.88”

 id="img-f7654012">

]]>

The first four beads determine which arrangements are fixed under the reversal group, so there are 4! ways for strings to be fixed under reversibility.

So, $\sum_{g \in G}|X^g| = 8! / 2^4 + 4! = 2544$

Next, we just divide this by |G| (which is 2 in this situation) and we end up with 1272 possible strings.

We can double check this result using Julia:

function is_only_symmetrically_equivalent(a, b)
    a_reversed = reverse(a)
    if is_equivalent(a, b)
        return true
    elseif is_equivalent(a_reversed, b)
        return true
    else

        return false
    end
end

is_only_symmetrically_equivalent (generic function with 1 method)

all_perms_list = collect(permutations(["r", "r", "g", "g", "b", "b", "y", "y"], 8))
keep_list = []
for i in 2:length(all_perms_list)
    already_in_list = false
    for j in 1:length(keep_list)
        if is_only_symmetrically_equivalent(all_perms_list[i], keep_list[j])
            already_in_list = true
        end
    end
    if !already_in_list   
        push!(keep_list, all_perms_list[i])
    end
end
print(length(keep_list))

1272

Next, let’s apply burnside’s lemma to our original situation: a bracelet of 8 beads, with exactly 2 of each color, and taking into account non-distinctness of rotations and reflections. Here, we have 16 groups: the null group, 7 possible rotations, 4 reflections that intersect a bead, and 4 reflections that do not intersect a bead.

For the null group, we have 8! / 2^4 arrangements that remain “fixed”. When rotating 1-3 or 5-7 beads, there are 0 possible ways for an arrangement to remain “fixed” with this number of beads. You would need to have all lbeads be the same color for this to be valid.

however, when rotating 4 beads, it is possible for an arrangement to remain “fixed” if the last 4 beads repeat the first 4 beads. So, there are 4! fixed arrangments for that rotation group.

create_graph("rgybrgyb", true) ## RGYBRGYB plot

<svg xmlns=“http://www.w3.org/2000/svg" xmlns:xlink=“http://www.w3.org/1999/xlink" version=“1.2” width=“141.42mm” height=“100mm” viewBox=“0 0 141.42 100” stroke=“none” fill="#000000” stroke-width=“0.3” font-size=“3.88”

 id="img-d4b3dbc5">

]]>

For each of the 8 reflections, there are 4! arrangements that remain fixed across that arrangement.

create_graph("rgybbygr", true) ## RGYBRGYB plot

<svg xmlns=“http://www.w3.org/2000/svg" xmlns:xlink=“http://www.w3.org/1999/xlink" version=“1.2” width=“141.42mm” height=“100mm” viewBox=“0 0 141.42 100” stroke=“none” fill="#000000” stroke-width=“0.3” font-size=“3.88”

 id="img-227aef66">

]]>

create_graph("gybrbygr", true) ## RGYBRGYB plot

<svg xmlns=“http://www.w3.org/2000/svg" xmlns:xlink=“http://www.w3.org/1999/xlink" version=“1.2” width=“141.42mm” height=“100mm” viewBox=“0 0 141.42 100” stroke=“none” fill="#000000” stroke-width=“0.3” font-size=“3.88”

 id="img-711cb9d3">

]]>

using Plots

create_graph("gybrbygr", true) ## RGYBRGYB plot
plot!(0, 1)

[ Info: Precompiling Plots [91a5bcdd-55d7-5caf-9e0b-520d859cae80]

signal (2): Interrupt: 2
in expression starting at none:1



Failed to precompile Plots [91a5bcdd-55d7-5caf-9e0b-520d859cae80] to /Users/zacharyclement/.julia/compiled/v1.8/Plots/jl_TVq3hx.



Stacktrace:

 [1] error(s::String)

   @ Base ./error.jl:35

 [2] compilecache(pkg::Base.PkgId, path::String, internal_stderr::IO, internal_stdout::IO, keep_loaded_modules::Bool)

   @ Base ./loading.jl:1707

 [3] compilecache

   @ ./loading.jl:1651 [inlined]

 [4] _require(pkg::Base.PkgId)

   @ Base ./loading.jl:1337

 [5] _require_prelocked(uuidkey::Base.PkgId)

   @ Base ./loading.jl:1200

 [6] macro expansion

   @ ./loading.jl:1180 [inlined]

 [7] macro expansion

   @ ./lock.jl:223 [inlined]

 [8] require(into::Module, mod::Symbol)

   @ Base ./loading.jl:1144

import Pkg; Pkg.add("Plots")

    Updating registry at `~/.julia/registries/General.toml`
   Resolving package versions...
   Installed x265_jll ───────────────────── v3.5.0+0
   Installed GR_jll ─────────────────────── v0.71.7+0
   Installed LERC_jll ───────────────────── v3.0.0+1
   Installed libfdk_aac_jll ─────────────── v2.0.2+0
   Installed StatisticalTraits ──────────── v1.1.0
   Installed Xorg_xkbcomp_jll ───────────── v1.4.2+4
   Installed JpegTurbo_jll ──────────────── v2.1.91+0
   Installed Opus_jll ───────────────────── v1.3.2+0
   Installed RelocatableFolders ─────────── v1.0.0
   Installed Grisu ──────────────────────── v1.0.2
   Installed TimerOutputs ───────────────── v0.5.22
   Installed JLSO ───────────────────────── v2.7.0
   Installed Contour ────────────────────── v0.6.2
   Installed Highlights ─────────────────── v0.5.2
   Installed RCall ──────────────────────── v0.13.14
   Installed Xorg_xcb_util_wm_jll ───────── v0.4.1+1
   Installed StaticArrays ───────────────── v1.5.16
   Installed Xorg_xcb_util_image_jll ────── v0.4.0+1
   Installed PlotUtils ──────────────────── v1.2.0
   Installed MLJScientificTypes ─────────── v0.4.5
   Installed HTTP ───────────────────────── v0.9.17
   Installed Memento ────────────────────── v1.4.1
   Installed GPUArrays ──────────────────── v8.3.2
   Installed DataFrames ─────────────────── v0.22.7
   Installed Xorg_xcb_util_jll ──────────── v0.4.0+1
   Installed BFloat16s ──────────────────── v0.2.0
   Installed RecipesPipeline ────────────── v0.6.11
   Installed CEnum ──────────────────────── v0.4.2
   Installed RandomNumbers ──────────────── v1.5.3
   Installed MLJModels ──────────────────── v0.13.3
   Installed CodeTracking ───────────────── v1.2.1
   Installed ColorSchemes ───────────────── v3.20.0
   Installed Polynomials ────────────────── v3.2.5
   Installed CUDA_Runtime_jll ───────────── v0.3.1+0
   Installed Xorg_libxkbfile_jll ────────── v1.1.0+4
   Installed Xorg_libXinerama_jll ───────── v1.1.4+4
   Installed Distances ──────────────────── v0.10.7
   Installed Fontconfig ─────────────────── v0.4.1
   Installed FFMPEG ─────────────────────── v0.4.1
   Installed FiniteDiff ─────────────────── v2.18.0
   Installed Showoff ────────────────────── v1.0.3
   Installed XGBoost_jll ────────────────── v1.7.4+0
   Installed LLVM ───────────────────────── v4.16.0
   Installed Qt5Base_jll ────────────────── v5.15.3+2
   Installed CUDA_Driver_jll ────────────── v0.3.0+1
   Installed Xorg_xcb_util_keysyms_jll ──── v0.4.0+1
   Installed xkbcommon_jll ──────────────── v1.4.1+0
   Installed SpecialFunctions ───────────── v1.8.8
   Installed ProgressLogging ────────────── v0.1.4
   Installed Term ───────────────────────── v2.0.1
   Installed Pipe ───────────────────────── v1.3.0
   Installed NaNMath ────────────────────── v1.0.2
   Installed PlotThemes ─────────────────── v3.1.0
   Installed MyterialColors ─────────────── v0.3.0
   Installed GR ─────────────────────────── v0.71.7
   Installed fzf_jll ────────────────────── v0.29.0+0
   Installed TranscodingStreams ─────────── v0.9.11
   Installed SnoopPrecompile ────────────── v1.0.3
   Installed Rmath_jll ──────────────────── v0.4.0+0
   Installed UnicodeFun ─────────────────── v0.4.1
   Installed Random123 ──────────────────── v1.6.0
   Installed ScikitLearn ────────────────── v0.7.0
   Installed MLJBase ────────────────────── v0.16.3
   Installed Graphs ─────────────────────── v1.8.0
   Installed GLFW_jll ───────────────────── v3.3.8+0
   Installed ComputationalResources ─────── v0.3.2
   Installed x264_jll ───────────────────── v2021.5.5+0
   Installed JLFzf ──────────────────────── v0.1.5
   Installed LinearAlgebraX ─────────────── v0.1.11
   Installed Compat ─────────────────────── v3.46.1
   Installed ExprTools ──────────────────── v0.1.8
   Installed libaom_jll ─────────────────── v3.4.0+0
   Installed CodecZlib ──────────────────── v0.7.1
   Installed DiffRules ──────────────────── v1.13.0
   Installed ColorTypes ─────────────────── v0.10.12
   Installed Scratch ────────────────────── v1.1.1
   Installed Conda ──────────────────────── v1.8.0
   Installed JSON3 ──────────────────────── v1.12.0
   Installed Zstd_jll ───────────────────── v1.5.4+0
   Installed Parsers ────────────────────── v2.5.7
   Installed TensorCore ─────────────────── v0.1.1
   Installed Plots ──────────────────────── v1.38.6
   Installed MLJ ────────────────────────── v0.15.2
   Installed PrettyTables ───────────────── v0.10.1
   Installed PersistenceDiagramsBase ────── v0.1.1
   Installed ScientificTypes ────────────── v1.1.2
   Installed PyCall ─────────────────────── v1.95.1
   Installed AbstractFFTs ───────────────── v1.2.1
   Installed ConstructionBase ───────────── v1.5.1
   Installed CategoricalArrays ──────────── v0.9.7
   Installed Libtiff_jll ────────────────── v4.4.0+0
   Installed LLVMExtra_jll ──────────────── v0.0.16+2
   Installed Ogg_jll ────────────────────── v1.3.5+1
   Installed Xorg_libXi_jll ─────────────── v1.7.10+4
   Installed ColorVectorSpace ───────────── v0.9.10
   Installed AbstractTrees ──────────────── v0.4.4
   Installed ArrayInterface ─────────────── v7.1.0
   Installed ChainRulesCore ─────────────── v1.15.7
   Installed LogExpFunctions ────────────── v0.3.23
   Installed Xorg_xcb_util_renderutil_jll ─ v0.3.9+1
   Installed Xorg_libXcursor_jll ────────── v1.2.0+4
   Installed Wayland_protocols_jll ──────── v1.25.0+0
   Installed SparseMatricesCSR ──────────── v0.6.7
   Installed Compose ────────────────────── v0.9.5
   Installed MLJTuning ──────────────────── v0.6.0
   Installed libass_jll ─────────────────── v0.15.1+0
   Installed StableRNGs ─────────────────── v1.0.0
   Installed Rmath ──────────────────────── v0.7.1
   Installed Adapt ──────────────────────── v3.5.0
   Installed Latexify ───────────────────── v0.15.18
   Installed MLJModelInterface ──────────── v0.3.8
   Installed Wayland_jll ────────────────── v1.21.0+0
   Installed OpenSSL_jll ────────────────── v1.1.20+0
   Installed FFMPEG_jll ─────────────────── v4.4.2+2
   Installed GPUCompiler ────────────────── v0.17.2


   Installed MakieCore ──────────────────── v0.6.2
   Installed Xorg_xkeyboard_config_jll ──── v2.27.0+4
   Installed RecipesBase ────────────────── v1.3.3
   Installed Xorg_libXfixes_jll ─────────── v5.0.3+4
   Installed Xorg_libXrandr_jll ─────────── v1.5.2+4
   Installed URIs ───────────────────────── v1.4.2
   Installed XGBoost ────────────────────── v2.2.5
   Installed LAME_jll ───────────────────── v3.100.1+0
   Installed FilePathsBase ──────────────── v0.9.20
   Installed libvorbis_jll ──────────────── v1.3.7+1
   Installed Libglvnd_jll ───────────────── v1.6.0+0
   Installed ForwardDiff ────────────────── v0.10.35
   Installed FillArrays ─────────────────── v0.11.9
   Installed LearnBase ──────────────────── v0.4.1
   Installed QuadGK ─────────────────────── v2.8.1
   Installed BSON ───────────────────────── v0.3.6
   Installed Observables ────────────────── v0.5.4
   Installed Unzip ──────────────────────── v0.2.0
   Installed Lathe ──────────────────────── v0.1.6
   Installed DecisionTree ───────────────── v0.12.3
   Installed ChangesOfVariables ─────────── v0.1.6
   Installed LossFunctions ──────────────── v0.6.2
   Installed Distributions ──────────────── v0.24.18
   Installed CUDA ───────────────────────── v3.13.1
   Installed LatinHypercubeSampling ─────── v1.8.0
    Updating `~/.julia/environments/v1.8/Project.toml`
  [a81c6b42] ↑ Compose v0.9.4 ⇒ v0.9.5
⌅ [a93c6f00] ↑ DataFrames v0.19.4 ⇒ v0.22.7
  [7806a523] ↑ DecisionTree v0.12.1 ⇒ v0.12.3
⌅ [31c24e10] ↑ Distributions v0.21.12 ⇒ v0.24.18
  [186bb1d3] ↑ Fontconfig v0.4.0 ⇒ v0.4.1
  [da1fdf0e] ↑ FreqTables v0.3.1 ⇒ v0.4.5
  [38e38edf] ↑ GLM v1.4.2 ⇒ v1.8.1
  [86223c79] ↑ Graphs v1.5.0 ⇒ v1.8.0
⌃ [38d8eb38] ↑ Lathe v0.0.9 ⇒ v0.1.6
⌃ [add582a8] ↑ MLJ v0.2.3 ⇒ v0.15.2
  [91a5bcdd] + Plots v1.38.6
⌅ [08abe8d2] ↓ PrettyTables v2.2.2 ⇒ v0.10.1
  [6f49c342] ↑ RCall v0.13.5 ⇒ v0.13.14
  [3646fa90] ↑ ScikitLearn v0.5.0 ⇒ v0.7.0
  [009559a3] ↑ XGBoost v1.5.2 ⇒ v2.2.5
    Updating `~/.julia/environments/v1.8/Manifest.toml`
  [621f4979] + AbstractFFTs v1.2.1
  [1520ce14] ↑ AbstractTrees v0.4.3 ⇒ v0.4.4
  [79e6a3ab] + Adapt v3.5.0
  [7d9fca2a] - Arpack v0.4.0
  [4fba245c] + ArrayInterface v7.1.0
⌅ [ab4f0b2a] + BFloat16s v0.2.0
  [fbb218c0] + BSON v0.3.6
  [fa961155] + CEnum v0.4.2
  [336ed68f] - CSV v0.4.0
⌃ [052768ef] + CUDA v3.13.1
  [49dc2e85] - Calculus v0.5.1
⌅ [324d7699] ↑ CategoricalArrays v0.5.5 ⇒ v0.9.7
  [d360d2e6] ↑ ChainRulesCore v1.15.6 ⇒ v1.15.7
  [9e997f8a] ↑ ChangesOfVariables v0.1.4 ⇒ v0.1.6
  [da1fd8a2] + CodeTracking v1.2.1
  [944b1d66] + CodecZlib v0.7.1
  [35d6a980] + ColorSchemes v3.20.0
⌅ [3da002f7] ↓ ColorTypes v0.11.4 ⇒ v0.10.12
  [c3611d14] + ColorVectorSpace v0.9.10
⌅ [34da2185] ↑ Compat v2.2.1 ⇒ v3.46.1
  [a81c6b42] ↑ Compose v0.9.4 ⇒ v0.9.5
  [ed09eef8] + ComputationalResources v0.3.2
  [8f4d0f93] ↑ Conda v1.7.0 ⇒ v1.8.0
  [187b0558] + ConstructionBase v1.5.1
  [d38c429a] + Contour v0.6.2
⌅ [a93c6f00] ↑ DataFrames v0.19.4 ⇒ v0.22.7
  [9a8bc11e] - DataStreams v0.4.2
  [864edb3b] ↑ DataStructures v0.17.20 ⇒ v0.18.13
  [7806a523] ↑ DecisionTree v0.12.1 ⇒ v0.12.3
  [01453d9d] - DiffEqDiffTools v0.14.0
  [b552c78f] ↑ DiffRules v1.7.0 ⇒ v1.13.0
  [b4f34e82] ↑ Distances v0.8.2 ⇒ v0.10.7
⌅ [31c24e10] ↑ Distributions v0.21.12 ⇒ v0.24.18
  [e2ba6199] + ExprTools v0.1.8
  [c87230d0] + FFMPEG v0.4.1
  [5789e2e9] - FileIO v1.16.0
  [48062228] + FilePathsBase v0.9.20
⌅ [1a297f60] ↑ FillArrays v0.8.14 ⇒ v0.11.9
  [6a86dc24] + FiniteDiff v2.18.0
  [186bb1d3] ↑ Fontconfig v0.4.0 ⇒ v0.4.1
  [f6369f11] ↑ ForwardDiff v0.10.34 ⇒ v0.10.35
  [da1fdf0e] ↑ FreqTables v0.3.1 ⇒ v0.4.5
  [38e38edf] ↑ GLM v1.4.2 ⇒ v1.8.1
⌃ [0c68f7d7] + GPUArrays v8.3.2
  [61eb1bfa] + GPUCompiler v0.17.2
  [28b8d3ca] + GR v0.71.7
  [86223c79] ↑ Graphs v1.5.0 ⇒ v1.8.0
  [42e2da0e] + Grisu v1.0.2
⌅ [cd3eb016] ↑ HTTP v0.8.19 ⇒ v0.9.17
  [eafb193a] + Highlights v0.5.2
  [1019f520] + JLFzf v0.1.5
  [9da8a3cd] + JLSO v2.7.0
  [0f8b85d8] + JSON3 v1.12.0
  [2d691ee1] - LIBLINEAR v0.5.1
  [b1bec4e5] - LIBSVM v0.4.0
  [929cbde3] + LLVM v4.16.0
  [23fbe1c1] + Latexify v0.15.18
⌃ [38d8eb38] ↑ Lathe v0.0.9 ⇒ v0.1.6
  [a5e1c1ea] + LatinHypercubeSampling v1.8.0
⌅ [7f8f8fb0] + LearnBase v0.4.1
  [d3d80556] ↑ LineSearches v7.1.1 ⇒ v7.2.0
  [9b3f67b0] ↑ LinearAlgebraX v0.1.10 ⇒ v0.1.11
  [2ab3a3ac] ↑ LogExpFunctions v0.3.19 ⇒ v0.3.23
⌅ [30fc2ffe] + LossFunctions v0.6.2
⌃ [add582a8] ↑ MLJ v0.2.3 ⇒ v0.15.2
⌅ [a7f614a8] ↑ MLJBase v0.2.1 ⇒ v0.16.3
⌅ [e80e1ace] + MLJModelInterface v0.3.8
⌅ [d491faf4] ↑ MLJModels v0.2.3 ⇒ v0.13.3
⌃ [2e2323e0] + MLJScientificTypes v0.4.5
⌅ [03970b2e] + MLJTuning v0.6.0
  [20f20a25] + MakieCore v0.6.2
  [f28f55f0] + Memento v1.4.1
  [1c23619d] + MyterialColors v0.3.0
  [d41bc354] ↑ NLSolversBase v7.5.0 ⇒ v7.8.3
  [77ba4419] ↑ NaNMath v0.3.7 ⇒ v1.0.2
  [86f7a689] ↑ NamedArrays v0.9.4 ⇒ v0.9.6
  [510215fc] + Observables v0.5.4
  [429524aa] ↑ Optim v0.20.1 ⇒ v1.7.4
  [90014a1f] ↑ PDMats v0.9.12 ⇒ v0.11.16
  [69de0a69] ↑ Parsers v2.5.2 ⇒ v2.5.7
  [b1ad91c1] + PersistenceDiagramsBase v0.1.1
  [b98c9c47] + Pipe v1.3.0
  [ccf2f8ad] + PlotThemes v3.1.0
⌃ [995b91a9] + PlotUtils v1.2.0
  [91a5bcdd] + Plots v1.38.6
  [f27b6e38] ↑ Polynomials v3.2.0 ⇒ v3.2.5
  [2dfb63ee] ↑ PooledArrays v0.5.3 ⇒ v1.4.2
⌅ [08abe8d2] ↓ PrettyTables v2.2.2 ⇒ v0.10.1
  [33c8b6b6] + ProgressLogging v0.1.4
  [438e738f] ↑ PyCall v1.94.1 ⇒ v1.95.1
  [1fd47b50] ↑ QuadGK v2.6.0 ⇒ v2.8.1
  [6f49c342] ↑ RCall v0.13.5 ⇒ v0.13.14
  [74087812] + Random123 v1.6.0
  [e6cf234a] + RandomNumbers v1.5.3
  [3cdcf5f2] ↑ RecipesBase v0.7.0 ⇒ v1.3.3
  [01d81517] + RecipesPipeline v0.6.11
  [05181044] + RelocatableFolders v1.0.0
  [cbe49d4c] - RemoteFiles v0.3.1
  [79098fc4] ↑ Rmath v0.7.0 ⇒ v0.7.1
⌅ [321657f4] + ScientificTypes v1.1.2
  [3646fa90] ↑ ScikitLearn v0.5.0 ⇒ v0.7.0
  [6c6a2e73] + Scratch v1.1.1
  [efcf1570] + Setfield v1.1.1
  [1277b4bf] ↑ ShiftedArrays v1.0.0 ⇒ v2.0.0
  [992d4aef] + Showoff v1.0.3
  [66db9d55] ↑ SnoopPrecompile v1.0.1 ⇒ v1.0.3
  [a0a7dd2c] + SparseMatricesCSR v0.6.7
⌅ [276daf66] ↑ SpecialFunctions v0.9.0 ⇒ v1.8.8
  [860ef19b] + StableRNGs v1.0.0
  [90137ffa] ↑ StaticArrays v0.12.5 ⇒ v1.5.16
⌅ [64bff920] + StatisticalTraits v1.1.0
  [82ae8749] + StatsAPI v1.5.0
  [2913bbd2] ↑ StatsBase v0.32.2 ⇒ v0.33.21
  [3eaba693] ↑ StatsModels v0.6.21 ⇒ v0.6.33
  [892a3eda] - StringManipulation v0.3.0
  [856f2bd8] + StructTypes v1.10.0
  [bd369af6] ↑ Tables v0.2.11 ⇒ v1.10.0
  [62fd8b95] + TensorCore v0.1.1
  [22787eb5] + Term v2.0.1
  [a759f4b9] + TimerOutputs v0.5.22
  [3bb67fe8] + TranscodingStreams v0.9.11
  [5c2747f8] + URIs v1.4.2
  [1cfade01] + UnicodeFun v0.4.1
  [41fe7b60] + Unzip v0.2.0
  [ea10d353] - WeakRefStrings v0.5.8
  [009559a3] ↑ XGBoost v1.5.2 ⇒ v2.2.5
  [68821587] - Arpack_jll v3.5.1+1
  [4ee394cb] ↑ CUDA_Driver_jll v0.2.0+0 ⇒ v0.3.0+1
  [76a88914] ↑ CUDA_Runtime_jll v0.2.3+2 ⇒ v0.3.1+0
  [b22a6f82] + FFMPEG_jll v4.4.2+2
  [0656b61e] + GLFW_jll v3.3.8+0
  [d2c73de3] + GR_jll v0.71.7+0
  [aacddb02] + JpegTurbo_jll v2.1.91+0
  [c1c5ebd0] + LAME_jll v3.100.1+0
  [88015f11] + LERC_jll v3.0.0+1
  [dad2f222] + LLVMExtra_jll v0.0.16+2
  [7e76a0d4] + Libglvnd_jll v1.6.0+0
  [89763e89] + Libtiff_jll v4.4.0+0
  [e7412a2a] + Ogg_jll v1.3.5+1
  [458c3c95] + OpenSSL_jll v1.1.20+0
  [91d4177d] + Opus_jll v1.3.2+0
  [ea2cea3b] + Qt5Base_jll v5.15.3+2
  [f50d1b31] ↑ Rmath_jll v0.3.0+0 ⇒ v0.4.0+0
  [a2964d1f] + Wayland_jll v1.21.0+0
  [2381bf8a] + Wayland_protocols_jll v1.25.0+0
  [a5c6f535] ↑ XGBoost_jll v1.7.2+0 ⇒ v1.7.4+0
  [935fb764] + Xorg_libXcursor_jll v1.2.0+4
  [d091e8ba] + Xorg_libXfixes_jll v5.0.3+4
  [a51aa0fd] + Xorg_libXi_jll v1.7.10+4
  [d1454406] + Xorg_libXinerama_jll v1.1.4+4
  [ec84b674] + Xorg_libXrandr_jll v1.5.2+4
  [cc61e674] + Xorg_libxkbfile_jll v1.1.0+4
  [12413925] + Xorg_xcb_util_image_jll v0.4.0+1
  [2def613f] + Xorg_xcb_util_jll v0.4.0+1
  [975044d2] + Xorg_xcb_util_keysyms_jll v0.4.0+1
  [0d47668e] + Xorg_xcb_util_renderutil_jll v0.3.9+1
  [c22f9ab0] + Xorg_xcb_util_wm_jll v0.4.1+1
  [35661453] + Xorg_xkbcomp_jll v1.4.2+4
  [33bec58e] + Xorg_xkeyboard_config_jll v2.27.0+4
  [3161d3a3] + Zstd_jll v1.5.4+0
⌅ [214eeab7] + fzf_jll v0.29.0+0
  [a4ae2306] + libaom_jll v3.4.0+0
  [0ac62f75] + libass_jll v0.15.1+0
  [f638f0a6] + libfdk_aac_jll v2.0.2+0
  [f27f6e37] + libvorbis_jll v1.3.7+1
  [1270edf5] + x264_jll v2021.5.5+0
  [dfaa095f] + x265_jll v3.5.0+0
  [d8fb68d0] + xkbcommon_jll v1.4.1+0


  [9abbd945] - Profile
  [05823500] + OpenLibm_jll v0.8.1+0
        Info Packages marked with ⌃ and ⌅ have new versions available, but those with ⌅ are restricted by compatibility constraints from upgrading. To see why use `status --outdated -m`
    Building Conda ─→ `~/.julia/scratchspaces/44cfe95a-1eb2-52ea-b672-e2afdf69b78f/e32a90da027ca45d84678b826fffd3110bb3fc90/build.log`
    Building PyCall → `~/.julia/scratchspaces/44cfe95a-1eb2-52ea-b672-e2afdf69b78f/62f417f6ad727987c755549e9cd88c46578da562/build.log`
    Building RCall ─→ `~/.julia/scratchspaces/44cfe95a-1eb2-52ea-b672-e2afdf69b78f/2c0ffd39860c9a48259a0f57214ced2024ab63bc/build.log`



Error building `RCall`: 
ERROR: could not load library "/Volumes/SanDisk/opt/anaconda3/lib/R/lib/libR.dylib"
dlopen(/Volumes/SanDisk/opt/anaconda3/lib/R/lib/libR.dylib, 0x0001): Library not loaded: @rpath/libreadline.6.2.dylib
  Referenced from: <185433D7-8B40-31AA-8BD9-465D23C57257> /Volumes/SanDisk/opt/anaconda3/lib/R/lib/libR.dylib
  Reason: tried: '/Volumes/SanDisk/opt/anaconda3/lib/R/lib/../../libreadline.6.2.dylib' (no such file), '/Volumes/SanDisk/opt/anaconda3/lib/R/lib/../../libreadline.6.2.dylib' (no such file), '/Applications/Julia-1.8.app/Contents/Resources/julia/lib/julia/libreadline.6.2.dylib' (no such file), '/Applications/Julia-1.8.app/Contents/Resources/julia/lib/libreadline.6.2.dylib' (no such file), '/System/Volumes/Preboot/Cryptexes/OS@rpath/libreadline.6.2.dylib' (no such file), '/Volumes/SanDisk/opt/anaconda3/lib/R/lib/../../libreadline.6.2.dylib' (no such file), '/Volumes/SanDisk/opt/anaconda3/lib/R/lib/../../libreadline.6.2.dylib' (no such file), '/Applications/Julia-1.8.app/Contents/Resources/julia/lib/julia/libreadline.6.2.dylib' (no such file), '/Applications/Julia-1.8.app/Contents/Resources/julia/lib/libreadline.6.2.dylib' (no such file), '/usr/local/lib/libreadline.6.2.dylib' (no such file), '/usr/lib/libreadline.6.2.dylib' (no such file, not in dyld cache)
ERROR: LoadError: Try adding /Volumes/SanDisk/opt/anaconda3/lib/R/lib to the "LD_LIBRARY_PATH" environmental variable and restarting Julia.
Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:35
 [2] validate_libR(libR::String)
   @ Main ~/.julia/packages/RCall/Wyd74/deps/setup.jl:26
 [3] locate_libR(Rhome::SubString{String})
   @ Main ~/.julia/packages/RCall/Wyd74/deps/setup.jl:43
 [4] top-level scope
   @ ~/.julia/packages/RCall/Wyd74/deps/build.jl:58
 [5] include(fname::String)
   @ Base.MainInclude ./client.jl:476
 [6] top-level scope
   @ none:5
in expression starting at /Users/zacharyclement/.julia/packages/RCall/Wyd74/deps/build.jl:11

caused by: could not load library "/Volumes/SanDisk/opt/anaconda3/lib/R/lib/libR.dylib"
dlopen(/Volumes/SanDisk/opt/anaconda3/lib/R/lib/libR.dylib, 0x0001): Library not loaded: @rpath/libreadline.6.2.dylib
  Referenced from: <185433D7-8B40-31AA-8BD9-465D23C57257> /Volumes/SanDisk/opt/anaconda3/lib/R/lib/libR.dylib
  Reason: tried: '/Volumes/SanDisk/opt/anaconda3/lib/R/lib/../../libreadline.6.2.dylib' (no such file), '/Volumes/SanDisk/opt/anaconda3/lib/R/lib/../../libreadline.6.2.dylib' (no such file), '/Applications/Julia-1.8.app/Contents/Resources/julia/lib/julia/libreadline.6.2.dylib' (no such file), '/Applications/Julia-1.8.app/Contents/Resources/julia/lib/libreadline.6.2.dylib' (no such file), '/System/Volumes/Preboot/Cryptexes/OS@rpath/libreadline.6.2.dylib' (no such file), '/Volumes/SanDisk/opt/anaconda3/lib/R/lib/../../libreadline.6.2.dylib' (no such file), '/Volumes/SanDisk/opt/anaconda3/lib/R/lib/../../libreadline.6.2.dylib' (no such file), '/Applications/Julia-1.8.app/Contents/Resources/julia/lib/julia/libreadline.6.2.dylib' (no such file), '/Applications/Julia-1.8.app/Contents/Resources/julia/lib/libreadline.6.2.dylib' (no such file), '/usr/local/lib/libreadline.6.2.dylib' (no such file), '/usr/lib/libreadline.6.2.dylib' (no such file, not in dyld cache)
Stacktrace:
 [1] dlopen(s::String, flags::UInt32; throw_error::Bool)
   @ Base.Libc.Libdl ./libdl.jl:117
 [2] dlopen (repeats 2 times)
   @ ./libdl.jl:116 [inlined]
 [3] validate_libR(libR::String)
   @ Main ~/.julia/packages/RCall/Wyd74/deps/setup.jl:16
 [4] locate_libR(Rhome::SubString{String})
   @ Main ~/.julia/packages/RCall/Wyd74/deps/setup.jl:43
 [5] top-level scope
   @ ~/.julia/packages/RCall/Wyd74/deps/build.jl:58
 [6] include(fname::String)
   @ Base.MainInclude ./client.jl:476
 [7] top-level scope
   @ none:5



Stacktrace:

  [1] pkgerror(msg::String)

    @ Pkg.Types /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/Types.jl:67

  [2] (::Pkg.Operations.var"#66#73"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String})()

    @ Pkg.Operations /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/Operations.jl:1060

  [3] withenv(::Pkg.Operations.var"#66#73"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, ::Pair{String, String}, ::Vararg{Pair{String}})

    @ Base ./env.jl:172

  [4] (::Pkg.Operations.var"#107#112"{String, Bool, Bool, Bool, Pkg.Operations.var"#66#73"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, Pkg.Types.PackageSpec})()

    @ Pkg.Operations /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/Operations.jl:1619

  [5] with_temp_env(fn::Pkg.Operations.var"#107#112"{String, Bool, Bool, Bool, Pkg.Operations.var"#66#73"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, Pkg.Types.PackageSpec}, temp_env::String)

    @ Pkg.Operations /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/Operations.jl:1493

  [6] (::Pkg.Operations.var"#105#110"{Dict{String, Any}, Bool, Bool, Bool, Pkg.Operations.var"#66#73"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, Pkg.Types.Context, Pkg.Types.PackageSpec, String, Pkg.Types.Project, String})(tmp::String)

    @ Pkg.Operations /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/Operations.jl:1582

  [7] mktempdir(fn::Pkg.Operations.var"#105#110"{Dict{String, Any}, Bool, Bool, Bool, Pkg.Operations.var"#66#73"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, Pkg.Types.Context, Pkg.Types.PackageSpec, String, Pkg.Types.Project, String}, parent::String; prefix::String)

    @ Base.Filesystem ./file.jl:764

  [8] mktempdir(fn::Function, parent::String) (repeats 2 times)

    @ Base.Filesystem ./file.jl:760

  [9] sandbox(fn::Function, ctx::Pkg.Types.Context, target::Pkg.Types.PackageSpec, target_path::String, sandbox_path::String, sandbox_project_override::Pkg.Types.Project; preferences::Dict{String, Any}, force_latest_compatible_version::Bool, allow_earlier_backwards_compatible_versions::Bool, allow_reresolve::Bool)

    @ Pkg.Operations /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/Operations.jl:1540

 [10] build_versions(ctx::Pkg.Types.Context, uuids::Set{Base.UUID}; verbose::Bool)

    @ Pkg.Operations /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/Operations.jl:1041

 [11] build_versions

    @ /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/Operations.jl:956 [inlined]

 [12] add(ctx::Pkg.Types.Context, pkgs::Vector{Pkg.Types.PackageSpec}, new_git::Set{Base.UUID}; preserve::Pkg.Types.PreserveLevel, platform::Base.BinaryPlatforms.Platform)

    @ Pkg.Operations /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/Operations.jl:1286

 [13] add(ctx::Pkg.Types.Context, pkgs::Vector{Pkg.Types.PackageSpec}; preserve::Pkg.Types.PreserveLevel, platform::Base.BinaryPlatforms.Platform, kwargs::Base.Pairs{Symbol, IJulia.IJuliaStdio{Base.PipeEndpoint}, Tuple{Symbol}, NamedTuple{(:io,), Tuple{IJulia.IJuliaStdio{Base.PipeEndpoint}}}})

    @ Pkg.API /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/API.jl:275

 [14] add(pkgs::Vector{Pkg.Types.PackageSpec}; io::IJulia.IJuliaStdio{Base.PipeEndpoint}, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})

    @ Pkg.API /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/API.jl:156

 [15] add(pkgs::Vector{Pkg.Types.PackageSpec})

    @ Pkg.API /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/API.jl:145

 [16] #add#27

    @ /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/API.jl:144 [inlined]

 [17] add

    @ /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/API.jl:144 [inlined]

 [18] #add#26

    @ /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/API.jl:143 [inlined]

 [19] add(pkg::String)

    @ Pkg.API /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/Pkg/src/API.jl:143

 [20] top-level scope

    @ In[37]:1

Now, we can put this together:

$\frac{1}{|G|} \sum_{g \in G}|X^g| = \frac{8! / 2^4 + 4! + 8 * 4!}{ 16} = 2736 / 16 = 171$

So, $\frac{1}{|G|} \sum_{g \in G}|X^g| = 2736 / 16 = 171$

This corresponds to our brute-force solution.

using Graphs, GraphPlot
using Compose, Cairo, Fontconfig
using Colors

g = SimpleGraph(8)
for i in 1:7
    add_edge!(g, i, i + 1)
end
#add_edge!(g, 8, 1)

nodelabel = fill("", length(8))

membership = [1, 2, 3, 4, 1, 2, 3, 4]

nodecolor = [colorant"red", colorant"blue", colorant"yellow", colorant"green"]
# membership color
nodefillc = nodecolor[membership]

locs_x = [0, 2, 3, 2]
locs_y = [0, -1, 1, 0]

nodestrokelw = [0, 0, 0, 0, 0]

g = gplot(g, nodefillc=nodefillc)#, locs_x, locs_y, #nodelabel=nodelabel, 
    #nodestrokec = "black", nodestrokelw = nodestrokelw, NODESIZE = .15)
draw(PNG("smoking.png", 16cm, 16cm),g)
g

<svg xmlns=“http://www.w3.org/2000/svg" xmlns:xlink=“http://www.w3.org/1999/xlink" version=“1.2” width=“141.42mm” height=“100mm” viewBox=“0 0 141.42 100” stroke=“none” fill="#000000” stroke-width=“0.3” font-size=“3.88”

 id="img-a1fe2ea6">

]]>

import Pkg; Pkg.add("Colors")

   Resolving package versions...
    Updating `~/.julia/environments/v1.8/Project.toml`
  [5ae59095] + Colors v0.12.10
  No Changes to `~/.julia/environments/v1.8/Manifest.toml`

factorial(8) / 2^4 + factorial(4) * 9

2736.0

using Combinatorics
all_permutations = permutations(["r", "r", "g", "g", "b", "b"], 6)

Combinatorics.Permutations{Vector{String}}(["r", "r", "g", "g", "b", "b"], 6)

all_perms_list

720-element Vector{Vector{String}}:
 ["r", "r", "g", "g", "b", "b"]
 ["r", "r", "g", "g", "b", "b"]
 ["r", "r", "g", "b", "g", "b"]
 ["r", "r", "g", "b", "b", "g"]
 ["r", "r", "g", "b", "g", "b"]
 ["r", "r", "g", "b", "b", "g"]
 ["r", "r", "g", "g", "b", "b"]
 ["r", "r", "g", "g", "b", "b"]
 ["r", "r", "g", "b", "g", "b"]
 ["r", "r", "g", "b", "b", "g"]
 ["r", "r", "g", "b", "g", "b"]
 ["r", "r", "g", "b", "b", "g"]
 ["r", "r", "b", "g", "g", "b"]
 ⋮
 ["b", "b", "g", "r", "r", "g"]
 ["b", "b", "g", "r", "g", "r"]
 ["b", "b", "g", "r", "r", "g"]
 ["b", "b", "g", "r", "g", "r"]
 ["b", "b", "g", "g", "r", "r"]
 ["b", "b", "g", "g", "r", "r"]
 ["b", "b", "g", "r", "r", "g"]
 ["b", "b", "g", "r", "g", "r"]
 ["b", "b", "g", "r", "r", "g"]
 ["b", "b", "g", "r", "g", "r"]
 ["b", "b", "g", "g", "r", "r"]
 ["b", "b", "g", "g", "r", "r"]

keep_list_symmetry = [join(x) for x in keep_list]

48-element Vector{String}:
 "rrggbb"
 "rrgbgb"
 "rrgbbg"
 "rrbggb"
 "rrbgbg"
 "rrbbgg"
 "rgrgbb"
 "rgrbgb"
 "rgrbbg"
 "rggrbb"
 "rggbrb"
 "rggbbr"
 "rgbrgb"
 ⋮
 "grbbrg"
 "ggrrbb"
 "ggrbrb"
 "ggbrrb"
 "gbrrgb"
 "gbrrbg"
 "gbrgrb"
 "gbgrrb"
 "brrggb"
 "brgrgb"
 "brggrb"
 "bgrrgb"

all_perms_list = collect(permutations(["r", "r", "g", "g", "b", "b"], 6))
keep_list = []
for i in 2:length(all_perms_list)
    already_in_list = false
    for j in 1:length(keep_list)
        if is_equivalent(all_perms_list[i], keep_list[j])
            already_in_list = true
        end
    end
    if !already_in_list   
        push!(keep_list, all_perms_list[i])
    end
end
print(length(keep_list))

90

keep_list_no_symmetry = [join(x) for x in keep_list]

90-element Vector{String}:
 "rrggbb"
 "rrgbgb"
 "rrgbbg"
 "rrbggb"
 "rrbgbg"
 "rrbbgg"
 "rgrgbb"
 "rgrbgb"
 "rgrbbg"
 "rggrbb"
 "rggbrb"
 "rggbbr"
 "rgbrgb"
 ⋮
 "bggrrb"
 "bggrbr"
 "bggbrr"
 "bgbrrg"
 "bgbrgr"
 "bgbgrr"
 "bbrrgg"
 "bbrgrg"
 "bbrggr"
 "bbgrrg"
 "bbgrgr"
 "bbggrr"

double_counted_list = []
for x in keep_list_no_symmetry 
    if !(x in keep_list_symmetry)
        push!(double_counted_list, x)
    end
end

single_counted_list = []
for x in keep_list_symmetry 
    if !(reverse(x) in double_counted_list)
        push!(single_counted_list, x)
    end
end
single_counted_list

6-element Vector{Any}:
 "rgbbgr"
 "rbggbr"
 "grbbrg"
 "gbrrbg"
 "brggrb"
 "bgrrgb"

reverse("rrbbgg") in keep_list_symmetry

false

reverse("rrbbgg")

"ggbbrr"

factorial(6) / factorial(4) / factorial(2) * factorial(4) / factorial(2) / 2

90.0

using Combinatorics
all_permutations = permutations(["a", "a", "b", "b", "c", "c", "d", "d"], 8)

Combinatorics.Permutations{Vector{String}}(["a", "a", "b", "b", "c", "c", "d", "d"], 8)

using Combinatorics
all_permutations = permutations(["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"], 10)

Combinatorics.Permutations{Vector{String}}(["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"], 10)

all_perms_list = collect(all_permutations)

3628800-element Vector{Vector{String}}:
 ["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"]
 ["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"]
 ["a", "a", "b", "b", "c", "c", "d", "e", "d", "e"]
 ["a", "a", "b", "b", "c", "c", "d", "e", "e", "d"]
 ["a", "a", "b", "b", "c", "c", "d", "e", "d", "e"]
 ["a", "a", "b", "b", "c", "c", "d", "e", "e", "d"]
 ["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"]
 ["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"]
 ["a", "a", "b", "b", "c", "c", "d", "e", "d", "e"]
 ["a", "a", "b", "b", "c", "c", "d", "e", "e", "d"]
 ["a", "a", "b", "b", "c", "c", "d", "e", "d", "e"]
 ["a", "a", "b", "b", "c", "c", "d", "e", "e", "d"]
 ["a", "a", "b", "b", "c", "c", "e", "d", "d", "e"]
 ⋮
 ["e", "e", "d", "d", "c", "c", "b", "a", "a", "b"]
 ["e", "e", "d", "d", "c", "c", "b", "a", "b", "a"]
 ["e", "e", "d", "d", "c", "c", "b", "a", "a", "b"]
 ["e", "e", "d", "d", "c", "c", "b", "a", "b", "a"]
 ["e", "e", "d", "d", "c", "c", "b", "b", "a", "a"]
 ["e", "e", "d", "d", "c", "c", "b", "b", "a", "a"]
 ["e", "e", "d", "d", "c", "c", "b", "a", "a", "b"]
 ["e", "e", "d", "d", "c", "c", "b", "a", "b", "a"]
 ["e", "e", "d", "d", "c", "c", "b", "a", "a", "b"]
 ["e", "e", "d", "d", "c", "c", "b", "a", "b", "a"]
 ["e", "e", "d", "d", "c", "c", "b", "b", "a", "a"]
 ["e", "e", "d", "d", "c", "c", "b", "b", "a", "a"]

keep_list = [all_perms_list[1]]

1-element Vector{Vector{String}}:
 ["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"]

for i in 2:length(all_perms_list)
    already_in_list = false
    for j in 1:length(keep_list)
        if is_symmetrically_equivalent(all_perms_list[i], keep_list[j])
            already_in_list = true
        end
    end
    if !already_in_list   
        push!(keep_list, all_perms_list[i])
    end
end

keep_list

["r", "g", "g", "b", "r", "b"] ?rbrggb


"r", "g", "b", "r", "b", "g"]


["r", "g", "b", "g", "r", "b"] ?rbrgbg

 

171 / 3

57.0

is_symmetrically_equivalent(all_perms_list[i], keep_list[j])

reverse(a)

8-element Vector{String}:
 "d"
 "d"
 "c"
 "c"
 "b"
 "b"
 "a"
 "a"

a_temp = push!(a[2:8], a[1])

8-element Vector{String}:
 "a"
 "b"
 "b"
 "c"
 "c"
 "d"
 "d"
 "a"

a[2:8] + a[1]

MethodError: no method matching +(::Vector{String}, ::String)
Closest candidates are:
  +(::Any, ::Any, ::Any, ::Any...) at operators.jl:591
  +(::Array, ::Array...) at arraymath.jl:12
  +(::Array, ::SparseArrays.AbstractSparseMatrixCSC) at /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/SparseArrays/src/sparsematrix.jl:1833
  ...



Stacktrace:

 [1] top-level scope

   @ In[31]:1

x = true

true

reverse(a)

8-element Vector{String}:
 "d"
 "d"
 "c"
 "c"
 "b"
 "b"
 "a"
 "a"

import Pkg; Pkg.add("Primes")

    Updating registry at `~/.julia/registries/General.toml`
   Resolving package versions...
    Updating `~/.julia/environments/v1.8/Project.toml`
  [27ebfcd6] + Primes v0.5.3
  No Changes to `~/.julia/environments/v1.8/Manifest.toml`

using Primes
my_factor = Set([i[1] for i in collect(factor(18))])

Set{Int64} with 2 elements:
  2
  3

length(union!(my_factor, [3, 2, 5]))

3

my_factor

UndefVarError: set not defined



Stacktrace:

 [1] top-level scope

   @ In[23]:1

?factor

search: factor factorial my_factor eachfactor prodfactors TaskFailedException

factor(n::Integer) -> Primes.Factorization

Compute the prime factorization of an integer n. The returned object, of type Factorization, is an associative container whose keys correspond to the factors, in sorted order. The value associated with each key indicates the multiplicity (i.e. the number of times the factor appears in the factorization).

julia> factor(100)
2^2 ⋅ 5^2

For convenience, a negative number n is factored as -1*(-n) (i.e. -1 is considered to be a factor), and 0 is factored as 0^1:

julia> factor(-9)
-1 ⋅ 3^2

julia> factor(0)
0

julia> collect(factor(0))
1-element Array{Pair{Int64,Int64},1}:
 0=>1

factor(ContainerType, n::Integer) -> ContainerType

Return the factorization of n stored in a ContainerType, which must be a subtype of AbstractDict or AbstractArray, a Set, or an BitSet.

julia> factor(DataStructures.SortedDict, 100)
DataStructures.SortedDict{Int64,Int64,Base.Order.ForwardOrdering} with 2 entries:
  2 => 2
  5 => 2

When ContainerType <: AbstractArray, this returns the list of all prime factors of n with multiplicities, in sorted order.

julia> factor(Vector, 100)
4-element Array{Int64,1}:
 2
 2
 5
 5

julia> prod(factor(Vector, 100)) == 100
true

When ContainerType == Set, this returns the distinct prime factors as a set.

julia> factor(Set, 100)
Set([2,5])

using Primes
function is_relative_prime(x, y)
    x_factors = factor(Set, x)
    y_factors = factor(Set,y)
    for factor in y_factors
        if factor in x_factors
            return false
        end
    end
    ## none of them had a match
    return true
    
    
end

is_relative_prime (generic function with 1 method)

function euler_totient(x)
    output_sum = 0
    for i in 1:x
        if is_relative_prime(i, x)
            output_sum += 1
        end
    end
    return output_sum
        
end

euler_totient (generic function with 1 method)

using Combinatorics
function get_factors(x)
    prime_factors = factor(Vector, x)
    all_prime_factors = vcat(prime_factors, fill(1, length(prime_factors))) ## add 1s so smaller numbers are included

    factor_list = [prod(i) for i in combinations(all_prime_factors, length(prime_factors))]
    return Set(factor_list)

end

get_factors (generic function with 1 method)

get_factors(12)

Set{Int64} with 6 elements:
  12
  1
  4
  6
  2
  3

num_beads = 4
necklace_size = 4

sum = 0

for d in get_factors(num_beads)
    sum = sum + euler_totient(d) * necklace_size ^ (num_beads / d)
end

sum = sum / num_beads
print(sum)

70.0

function get_number_necklaces(n, k)
    sum = 0

    for d in get_factors(n)
        sum = sum + euler_totient(d) * k ^ (n / d)
    end

    sum = sum / n
end

get_number_necklaces (generic function with 1 method)

You can check your work here https://oeis.org/A000031

function get_number_bracelets(n, k)
    if round(n / 2) == n / 2
        return get_number_necklaces(n, k) / 2 + (k + 1) * k^(n / 2)/4
    else
        return get_number_necklaces(n, k) / 2 +  k^((n+1) / 2)/2
    end
end

get_number_bracelets (generic function with 1 method)

get_number_necklaces(12, 2)

352.0

for i in 1:12
    println(get_number_necklaces(i, 12))
end

12.0
78.0
584.0
5226.0
49776.0
498004.0
5.11884e6
5.3750346e7
5.7330932e8
6.191761368e9
6.7546215528e10
7.43008623292e11

(get_number_bracelets(8, 4) 
- 4 ### bracelets of all of each of the 4 colors
- 6 * get_number_bracelets(8, 2)
- 4 * get_number_bracelets(8, 3)

)

2259.0

get_number_bracelets(5, 2)

8.0

tril!(prime_factors * transpose(prime_factors))

UndefVarError: tril! not defined



Stacktrace:

 [1] top-level scope

   @ In[78]:1

Burnside’s lemma takes into account rotations, and it also works for reflections.

https://math.stackexchange.com/questions/3246995/number-of-bracelets-with-6-white-3-blue-and-5-red-beads?rq=1

(factorial(8) / (2 ^ 4) + factorial(4)  * 9) / 16

171.0

(factorial(6) / (2 ^ 3) + factorial(3)  * 7) / 12

11.0

24 * 171 - factorial(8) / (2 ^ 4) - factorial(4)  * 17 * 3

360.0

factor(Vector, 1992)

5-element Vector{Int64}:
  2
  2
  2
  3
 83

?combinations

search: combinations all_combinations multiset_combinations CoolLexCombinations

combinations(a, n)

Generate all combinations of n elements from an indexable object a. Because the number of combinations can be very large, this function returns an iterator object. Use collect(combinations(a, n)) to get an array of all combinations.

combinations(a)

Generate combinations of the elements of a of all orders. Chaining of order iterators is eager, but the sequence at each order is lazy.

factorial(14) / factorial(14 - 6) / factorial(6) * factorial(8) / factorial(5) / factorial(3)

168168.0

factorial(14) / factorial(14 - 3) / factorial(3) * factorial(11) / factorial(6) / factorial(5)

168168.0

factorial(8) / 2 ^4

2520.0

factorial(8) / factorial(6) * factorial(6) / factorial(4) * factorial(4) / factorial(2) / 2^3

2520.0

How many possible chords are there, accounting for transposition?

1: 1
2: 6
3: 19
4: 43
5: 66
6: 80
7: 66
8: 43
9: 19
10: 6
11: 1
12: 1

(1 + 6 + 19 + 43 + 66) * 2 + 80 + 1

351

function comb(n, k)
    return factorial(n) / factorial(k) / factorial(n - k)
end

comb (generic function with 1 method)

## 2/10
(comb(12, 2) + 6)/ 12 # at 6 o clock, there are 6 different fixed points

## 3 / 9
(comb(12, 3) + 4*2)/ 12
## 4 and 8 o clock both have 4 fixed

19.0

## 4/8
(comb(12, 4) + 
    comb(6, 2) + #rotation at half
    3*2 #at 3 and 9 o clock there are 3 possible combinations
    )/ 12

43.0

## 5/7
(comb(12, 5))/ 12 ## no way for there to be any fixed points beyond the null

66.0

comb(12, 6) / 12

77.0

## 6
(comb(12, 6) + 
    2 * 2 + #2, and 10 o clock both have 2 choices
    comb(4, 2) * 2 + #4 and 8 o clock rotations can distribute 1/3 the beads (2) among 4 possible slots
    
    comb(6, 3) # 6 o clock can distribute 3 beads among 6 possible slots
    )/ 12

80.0

sum = 0 ## chord of 1
for i in 1:12
    current_number = factorial(11) / factorial(i - 1) / factorial(11 - i + 1)
    sum += current_number
    println(i, " ", current_number)
end
print(sum)

1 1.0
2 11.0
3 55.0
4 165.0
5 330.0
6 462.0
7 462.0
8 330.0
9 165.0
10 55.0
11 11.0
12 1.0
2048.0

If there were 4 different notes
0. 1 option

1. 1 options.
2. 2 options
3. 1 option
4. 1 option

get_number_necklaces(4, 2)

6.0

If there were 5 notes:

0. 1 option
1. 1 option
2. 4 options
3. 4 options
4. 1 option
5. 1 option

get_number_necklaces(5, 2)

8.0

using Combinatorics
n_played = 1
n_notes = 12
perms = permutations(
            vcat(repeat([true], n_played), repeat([false], n_notes - n_played)), 
            n_notes)

Combinatorics.Permutations{Vector{Bool}}(Bool[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 12)

length(perms)

479001600

output_list = []
for arrangement in perms
    if !( arrangement in output_list)
        push!(output_list, arrangement)
    end
        
end
output_list

12-element Vector{Any}:
 Bool[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 Bool[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 Bool[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 Bool[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
 Bool[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
 Bool[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
 Bool[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
 Bool[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
 Bool[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
 Bool[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
 Bool[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 Bool[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

collect(combinations([1, 2, 3], 3))

1-element Vector{Vector{Int64}}:
 [1, 2, 3]

function get_all_perms_list(n_played, n_notes = 12)
    perms = permutations(
                vcat(repeat([true], n_played - 1), repeat([false], n_notes - n_played)), 
                n_notes - 1)
    output_list = []
    for arrangement in perms
        if !( arrangement in output_list)
            push!(output_list, arrangement)
        end

    end
    for i in 1:length(output_list)
        push!(output_list[i], true) #endlways end with a note played
        
    end
    return output_list
end

get_all_perms_list (generic function with 2 methods)

get_all_perms_list(2, 5)

4-element Vector{Any}:
 Bool[1, 0, 0, 0, 1]
 Bool[0, 1, 0, 0, 1]
 Bool[0, 0, 1, 0, 1]
 Bool[0, 0, 0, 1, 1]

using Combinatorics
function get_num_note_combinations(n_played)
    all_perms_list = get_all_perms_list(n_played)
    keep_list = []
    for i in 2:length(all_perms_list)
        already_in_list = false
        for j in 1:length(keep_list)
            if is_rotationally_equivalent(all_perms_list[i], keep_list[j])
                already_in_list = true
            end
        end
        if !already_in_list   
            push!(keep_list, all_perms_list[i])
        end
    end
    println(n_played, ": ", length(keep_list))
end

get_num_note_combinations (generic function with 1 method)

for i in 2:12
    get_num_note_combinations(i)
end

2: 6
3: 19
4: 43
5: 66
6: 80
7: 66
8: 43
9: 19



InterruptException:



Stacktrace:

 [1] copy

   @ ./array.jl:369 [inlined]

 [2] nextpermutation(m::Vector{Bool}, t::Int64, state::Vector{Int64})

   @ Combinatorics ~/.julia/packages/Combinatorics/Udg6X/src/permutations.jl:53

 [3] iterate

   @ ~/.julia/packages/Combinatorics/Udg6X/src/permutations.jl:44 [inlined]

 [4] get_all_perms_list(n_played::Int64, n_notes::Int64)

   @ Main ./In[42]:11

 [5] get_all_perms_list

   @ ./In[42]:2 [inlined]

 [6] get_num_note_combinations(n_played::Int64)

   @ Main ./In[44]:3

 [7] top-level scope

   @ ./In[45]:2