1
$\begingroup$

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.

| improve this question | |
$\endgroup$
  • $\begingroup$ ListNeclaces is a Combinatorica function. It is not a built-in. You must provide a list for the second argument, representing the colors. $\endgroup$ – ciao Jun 10 '14 at 22:48
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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.:

Combinatorica`SetPartitions[{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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Laura Jun 10 '14 at 23:45
  • $\begingroup$ @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... $\endgroup$ – ciao Jun 11 '14 at 0:04
  • $\begingroup$ 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 ." $\endgroup$ – Laura Jun 11 '14 at 0:05
  • $\begingroup$ @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. $\endgroup$ – ciao Jun 11 '14 at 0:18
  • $\begingroup$ 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. $\endgroup$ – Laura Jun 11 '14 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.