# Using CombinatoricaListNecklaces in v9

I am using Mathematica for visualization of DeBruijn graphs. However, I am having a bit of trouble using ListNecklaces.

I want to know how many cyclic shifts of length n with variables x and y. This is equivalent to looking at the number of necklaces (cyclic) with n beads and 2 colors.

However, I'm not sure how to use the command ListNecklaces. I don't get anything back when I input ListNecklaces[n ,2, Cyclic].

I also am having trouble with some of the graph theory commands. In versions older than V9, I would need to load the Combinatorica package. Is it true that now I don't have to? Sometimes, Mathematica doesn't recognize ListNecklaces, DeBruijnGraph, etc. What is the proper way to set up Mathematica to use these? I am using Version 9, Student's Edition.

-
ListNeclaces is a Combinatorica function. It is not a built-in. You must provide a list for the second argument, representing the colors. –  rasher Jun 10 at 22:48

You can get the result using the builtin CycleIndexPolynomial. For example, imagine you are interested in the group CyclicGroup[5].

In[1]:= poly = CycleIndexPolynomial[CyclicGroup[5], {a[1], a[2], a[3], a[4], a[5]}]
Out[1]= a[1]^5/5 + (4 a[5])/5


Suppose you have three types of beads (r, g, b):

In[2]:= poly /. a[i_] -> r^i + g^i + b^i // Expand
Out[2]= b^5 + b^4 g + 2 b^3 g^2 + 2 b^2 g^3 + b g^4 + g^5 + b^4 r +  4 b^3 g r + 6 b^2 g^2 r + 4 b g^3 r + g^4 r + 2 b^3 r^2 +  6 b^2 g r^2 + 6 b g^2 r^2 + 2 g^3 r^2 + 2 b^2 r^3 + 4 b g r^3 +  2 g^2 r^3 + b r^4 + g r^4 + r^5


Each monomial is a possibility, so 6 b^2 g^2 r means you have 6 possibilities reordering {b,b,g,g,r}. To get the actual 6 possibilities use

In[3]:= GroupOrbits[CyclicGroup[5], Permutations[{b, b, g, g, r}], Permute]
Out[3]= {
{{b, b, g, g, r}, {b, g, g, r, b}, {g, g, r, b, b}, {g, r, b, b, g}, {r, b, b, g, g}},
{{b, b, g, r, g}, {b, g, r, g, b}, {g, b, b, g, r}, {g, r, g, b, b}, {r, g, b, b, g}},
{{b, b, r, g, g}, {b, r, g, g, b}, {g, b, b, r, g}, {g, g, b, b, r}, {r, g, g, b, b}},
{{b, g, b, g, r}, {b, g, r, b, g}, {g, b, g, r, b}, {g, r, b, g, b}, {r, b, g, b, g}},
{{b, g, b, r, g}, {b, r, g, b, g}, {g, b, g, b, r}, {g, b, r, g, b}, {r, g, b, g, b}},
{{b, g, g, b, r}, {b, r, b, g, g}, {g, b, r, b, g}, {g, g, b, r, b}, {r, b, g, g, b}}
}


Each line there are the equivalent configurations (under the group symmetry) for the 6 possibilities.

-

ListNecklaces is a Combinatorica function. It is not a built-in. You must provide a list for the second argument, representing the colors, e.g.:

<< Combinatorica
ListNecklaces[5, {1, 2, 3}, Cyclic]

(*
{{1, 2, 3, 1, 2}, {1, 1, 2, 2, 3}, {1, 1, 2, 3, 2}, {1, 1, 3, 2, 2}, {1, 2, 1, 3, 2}, {1, 2, 2, 1, 3}}
*)


You must still load the Combinatorica package to use Combinatorica functions, with Get (like above) or

Needs["Combinatorica"]


Note that there is overlap in functions and some names with built-ins.

You can (somewhat) circumvent this via using

Block[{$ContextPath}, Needs["Combinatorica"]]  or Needs["Combinatorica"]$ContextPath = DeleteCases[$ContextPath, "Combinatorica"]  instead of straight use of Needs or Get, and then prepending Combinatorica when you want the Combinatorica version, e.g.: CombinatoricaSetPartitions[{1, 2, 3}]  N.B.: Because of the way some Combinatorica functions were written, AFAIK you can only use them by having it in the $ContextPath (I think ListNecklaces is one example).

The canonical documentation for Combinatorica is the book: the Mathematica documentation for the package is... scanty.

-
Thanks. I managed to put it in for my desired variables. However, I realized that I might be using the wrong code. I reread the definition of necklaces and saw that it is for not necessarily distinct colors. Is there a way to make the colors distinct? –  Laura Jun 10 at 23:45
@Laura: Not sure what you mean: If you provide a list of distinct "colors", the results are for that. You don't have to have distinct colors, however - try it with each case and observe the results... –  rasher Jun 11 at 0:04
Thanks. I meant that I get {xyxyx,xxxyy} as my least, which doesn't include the possibility of xxxxx, xxxxy, etc. Also, when I load Combinatorica, I no longer can use DeBruijnGraph - it turns up red. ? And I get "Block[{$ContextPath}, Needs[Combinatorica]] Syntax::sntxf: "Block[{$ContextPath}," cannot be followed by "Needs[Combinatorica]]". Syntax::tsntxi: "Needs[Combinatorica]" is incomplete; more input is needed. Syntax::sntxi: Incomplete expression; more input is needed ." –  Laura Jun 11 at 0:05
@Laura: Are you sure ListNecklaces is what you're after, and not simply a list of tuples of some size with all combinations of your "colors"? No idea why you're getting a syntax error - that statement is correct. The reason DeBruijnGraph goes wacky is there's a built-in and a Combinatorica function with that name. Hence the caution re: name clashes. You can prepend the System context to the call to get the Mathematica one. Do note: the graph structures are different between most Combinatorica and built-ins: you can't in general mix/match/use outputs between them. –  rasher Jun 11 at 0:18
Thanks. I guess I will just have to do the work on DeBruijn graphs in separate documents before loading Combinatorica to use those functions. I am looking for all of the shift cycles for two variables, x and y. I'm looking for the list of vertices of the DeBruijnGraph[2,n] for some specific value of n. So, for a word of length 5, I want all the cycles of length 5 - <x^5>,<x^4y>, <x^3y^2>,<x^2yxy>, etc. But I want just the unique cycles - x^4y is the same as x^3yx. Perhaps ListNecklaces is not what I am looking for. –  Laura Jun 11 at 0:29