Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
4
votes
2answers
87 views
How to obtain all the distinct De Bruijn sequences?
In combinatorial mathematics, a $k$-ary De Bruijn sequence $B(k, n)$ of order $n$ is a cyclic sequence of a given alphabet $A$ with size $k$ for which every possible subsequence of length $n$ in $A$ ...
2
votes
2answers
167 views
Making a flag with six vertical stripes
A flag is to be made with six vertical stripes by using colours yellow, blue, green and red in such a way that no two adjacent stripes should have the same colour. In how many ways is this possible? ...
4
votes
1answer
95 views
The algorithm of ListGraphs[n,m]
I'm not sure if this is a Mathematica problem, math problem or a CS problem, so if this is off-topic please transfer it.
In the package Combinatorica there is a ...
1
vote
1answer
43 views
Numbering of cases implied by a subset of Boolean vectors
In the course of a programming problem I stumbled upon the following sub-problem.
Given an arbitrary, but fixed, number of Boolean variables, I would like to be able to pick a subset of the ...
0
votes
0answers
19 views
In how many ways can i partition a stick [migrated]
I have a stick (or a ruler) of 10 cm length.
I want to cut the stick into pieces.
Each cm (1 cm, 2cm, 3cm, ... 0 cm) is a possible cutting point.
In how many different ways can i cut the stick?
One ...
1
vote
1answer
78 views
Symbolic multiplicative partitions
Let $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial):
p[n_] := Times @@ Prime[Range[n]]
then the multiplicative partitions of $p_{1,2,3,4}\#$ are
$$
\{\{2\}\},$$$$
...
2
votes
1answer
91 views
How to compute the `Automorphisms` of graphs with multiple edges?
I try to compute the Automorphisms of graphs with multiple edges from its AdjacencyMatrix but failed. The following code shows ...
0
votes
1answer
51 views
How should my data be formatted for use with BetweennessCentrality?
A few weeks ago I asked this question. I am trying to upload my data which is an adjacency list for an undirected, unweighed graph and find the betweenness centrality. At the time I tried to use the ...
0
votes
1answer
95 views
How do I upload a graph as an adjacency list and find the betweenness centrality?
I have an undirected simple graph in a .txt file formatted as an adjacency list like this:
100 200
200 300
300
400 500 600 700 800 900
...
Every number is a node ...
0
votes
1answer
53 views
Generating all “from n choose k” configurations of a simple list [closed]
Suppose that I have a 1-D list called myList. Here's an example:
myList = {"A", "B", "C", "D"};
I want to write (or find ...
3
votes
1answer
350 views
Combinatorica Graph from Edge List
Can someone provide an example of a Combinatorica-based graph which uses ShowGraph and Graph and takes in an explicitly defined list of edges (not some auto-generated graph). I have not been able to ...
9
votes
4answers
403 views
Permutations[Range[12]] produces an error instead of a list
This input:
Permutations[Range[12]]
Results in this (error) output:
...
6
votes
2answers
222 views
Binomial[-1,-1]
According to various sources e.g.
http://www.proofwiki.org/wiki/Definition:Binomial_Coefficient
and Wolfram themselves
http://functions.wolfram.com/GammaBetaErf/Binomial/02/
, the binomial ...
1
vote
2answers
104 views
Mathematica can't minimize a function
Mathematica seems not to be able to minimize this univariate function over integer arguments, $r>2, r \in \mathbb{Z}$.
...
6
votes
3answers
179 views
Enumerate the 1-factors (perfect matchings) of $K_n$
Introduction
I would like to enumerate the 1-factors, or (near-)perfect matchings, of the complete graph Kn. The adjacency list representation for Kn is basically { (x, y) | 1 ≤ x < y ≤ n }.
For ...
11
votes
1answer
336 views
Generating Gelfand-Tsetlin patterns
I am doing some research on some combinatorial object called GT-patterns.
They are generated from three parts of data.
Two integer, partitions (sequences of weakly decreasing numbers),
$\lambda = ...
2
votes
0answers
70 views
Young Tableaux Miscellanea
I have a problem which is mostly neatly described by using Young Tableaux. Mathematica seems to have these Tableaux built in, except that the Tableaux function is ...
2
votes
2answers
78 views
Checking connectedness of a graph
I am trying to use the Combinatorica package in a Mathematica version 8 in the following code:
...
1
vote
2answers
364 views
Create simple table with function of column values
I just want to create a simple table:
Three input columns, one output column
Call the inputs {x,y,z}, each can take values ...
6
votes
1answer
103 views
Better way to get Fisher Exact?
I want to perform a Pearson's $\chi^2$ test to analyse contingency tables; but because I have small numbers, it is recommended to perform instead what is called a Fisher's Exact Test.
This requires ...
4
votes
3answers
119 views
Permutation count for sets with multiplicities
I am able to do a permutation counr for the set {a, a, b} which gives me 3 groups. I am happy with that result. However, if the set is ...
3
votes
7answers
324 views
Concise way to generate multiset lists
I wrote the following to generate a multiset with the same number of items over a fixed range:
ConstantArray[#, 3]& /@ Range[9] // Flatten
...
5
votes
1answer
193 views
Shortest polygonal path
I'd like to find the shortest distance between some points (every point must be visited), such as between these 3 points:
...
0
votes
1answer
88 views
How can I find the derivative of a combinatorial expression? [closed]
I want to differentiate the following equation:
n = (nchoosek)*p*(1 - p)^(n - k)
After differentiating my result is:
...
1
vote
0answers
69 views
The number of real values assumed by combinations of complex roots of a decic
Define complex conjugate as the pair of complex numbers $a+bi,a-bi$. Assume you have 5 such pairs and they are the 10 roots $x_i$ of a 10th-deg equation with integer coefficients. In general, how many ...
12
votes
4answers
355 views
1
vote
0answers
119 views
Tools for finding minimal or almost-minimal graph vertex colorations in Mathematica v9?
I'm looking to compute minimum vertex colorations (s.t. no two vertices of the same color share an edge: http://en.wikipedia.org/wiki/Graph_coloring) for graphs in Mathematica v9 with potentially up ...
3
votes
3answers
580 views
How to find all graph isomorphisms in FindGraphIsomorphism
I found the second definition of the function FindGraphIsomorphism not working.
Here's the definition Mathematica 8 gives:
...
1
vote
0answers
54 views
How to use Automorphisms[] on a graph? [duplicate]
I am having difficulty mixing the new post-Combinatorica graph data structure, with functionality apparently only in Combinatorica.
I have constructed a graph using ...
2
votes
2answers
133 views
Rook walk and RecurrenceTable in Mathematica
This appears in a combinatorics book:
$a(m,n)=2 a(m,n-1)+2 a(m-1,n)-3 a(m-1,n-1)$
It is a recurrence equation for the number of rook walks from $(0,0)$ to $(m,n)$.
The initial conditions are:
$ ...
16
votes
5answers
589 views
How do I generate the upper triangular indices from a list?
I have some list
{1,2,3}.
How do I generate nested pairs such that I get
{{1,2},{1,3},{2,3}}?
That is I'd like a way to ...
4
votes
1answer
140 views
Random filling of L-length line with l-length segments
I have discrete L-length line filled randomly with 2-length segments so its cover line with gaps 0 or 1. So we can describe cover configuration as sequence of gaps such as {0,0,1,0,1}. How I can ...
3
votes
3answers
117 views
Finding specific compositions of an Integer
I need to find all compositions of an integer L wherein all parts do not exсeed l and parts less then l cound not be neighbor. Here is my code
...
7
votes
0answers
295 views
Generating all spanning trees in an undirected graph [closed]
I was wondering if there is explicit source code for generating all spanning
trees on undirected graphs. I don’t need anything very fancy – perhaps Minty's algorithm or Gabow & Myers. I've only ...
2
votes
4answers
278 views
find the number of integral solutions a+b+c+d+e+f = 18 [duplicate]
Find the number of integral solutions of
a + b + c + d + e + f = 18
where a, b, c, d, e, f are elements of the range ...
0
votes
0answers
117 views
Pearl's Message Passing Algorithm
Has anyone tried to implement the Message Passing algorithm using Mathematica's Graph/Combinatorica features?
5
votes
1answer
449 views
All possible topological orderings of a graph
TopologicalSort[] returns one of many unique orderings.
From wikipedia:
if a topological sort does not form a Hamiltonian path, the DAG will have two or ...
0
votes
1answer
78 views
how to permute bit strings and manipulate their elements
I want to write a function(has 2 paremeter, n=range,k=number of 1 digits) which finds all probable combinatorics of arbitrary bit strings and evaluate sum of tensor ...
5
votes
4answers
235 views
How can I generate permutations of bit strings with repetition?
How can I write a function which has two parameters and it should generate combination of arbitrary range bits, for example: function[n, k], with ...
4
votes
2answers
152 views
How to enumerate multisets?
Given the eight-element set {1,2,3,4,5,6,7,8}, I would like to enumerate all multisets (subsets with repetition) of size n, ...
3
votes
0answers
64 views
Listing all combinations produced by picking one element from each of several sets [duplicate]
I have a problem like this, I am given the following sets {a,b,c}, {d,e,f}, {h,i,j}. I want to pick one element from each set, and output a list of all the ...
12
votes
4answers
989 views
Finding elementary cycles of (directed) graphs
I need to enumerate all the simple cycles (i.e. elementary cycles where no vertex is repeated other than the starting) of a graph which has both directed and undirected edges, where we can treat the ...
6
votes
2answers
331 views
Sierpinski carpet with GraphData
Is this graph in the list among the so-called "standard" structures used in GraphData? However, I have not found, yet, anything like "Carpet" or "Sponge" in the ...
-1
votes
1answer
93 views
Permutation of arguments of product of functions
Given a function, g, which is symmetric in its argument, g(a,b)=g(b,a), consider the product g(a,b)*g(c,d)*g(e,f). I would like to get all the permutations of this product with respect to the ...
4
votes
4answers
331 views
Listing matrices up to symmetry
I am interested in the equivalence relation on N x N binary matrices, in which two matrices are equivalent if one can be obtained by rotating/reflecting the other. I would like to obtain a list
...
0
votes
0answers
51 views
Identify columns of a huge matrix just polynomially many rows chosen at random
I am interested in the following problem in combinatorics $\Cap$ Probability. Let $\lambda \in \mathbb{N}$ be a parameter. Consider a matrix of $2^\lambda$ rows and $2^\lambda$ columns. Each column ...
6
votes
1answer
348 views
Find all permutations with reversals / cyclic permutations removed
I have a list of all non-cyclic permutations of n labels. How can I get rid of all elements which are redundant in the sense that they are the inverse of another one. For instance if n=4, the ...
0
votes
0answers
124 views
My algorithm produces too many permutations
Imagine the following problem. A population of size $n$ consists of $i$ men and $n-i$ women. The population goes to the casino. Call $g_m$ ,$g_w$ the amount of money won by men and women respectively. ...
1
vote
0answers
159 views
Get path to end nodes in directed (partially cyclic) graph
I have a large directed graph containing small loops. I would like to extract all paths to all end nodes (no VertexOutComponent) with a given path length $n$. I ...
20
votes
5answers
1k views
Partition a set into subsets of size $k$
Given a set $\{a_1,a_2,\dots,a_{lk}\}$ and a positive integer $l$, how can I find all the partitions which includes subsets of size $l$ in Mathematica? For instance, given ...
