Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.

learn more… | top users | synonyms

16
votes
7answers
666 views

Enumerating tuples from a larger space such that all pairs of values are present at least once

I am trying to write a function that will accept a list of N lists and returns a list of N-tuples that represent all pairs of values from the original N lists at least once. To illustrate with an ...
2
votes
1answer
162 views

defining Associated Stirling numbers of the Second Kind

First, I'm new to Mathematica. Spent my undergraduate programming with Maple and my computer crashed and I lost it. Fortunately, my university offers free Mathematica downloads to students, so here ...
3
votes
2answers
259 views

Constructing a list of Cartesian coordinates of the Icosahedron

I’m learning Mathematica and I need the coordinates of the Icosahedron vertices. This is my attempt at writing a program for it. The vertex coordinates are simply all cyclic permutations and ...
5
votes
2answers
224 views

How to define even permutations correctly?

I define even permutations as following, but there may be some error. I use it in two different way and get different output. ...
0
votes
1answer
207 views

Inclusion-Exclusion Principle Implementation

I would like to know how I can write a Mathematica code for the Inclusion–exclusion principle. The formulas governing it are: $ P(\bigcup_{i=1}^n A_i)=\sum_{k=1}^n (-1)^{k-1} ...
1
vote
0answers
163 views

How to sequentially select, from a large set of tuples (of matrices), those with a certain property [closed]

I'm interested in finding a computationally efficient way for selecting all tuples of matrices which have a certain property. The property I'm interested in is that I want the column sum, of f[the ...
4
votes
2answers
186 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$ ...
4
votes
1answer
131 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 ...
2
votes
2answers
393 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? ...
1
vote
2answers
96 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 ...
3
votes
2answers
132 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\}\},$$$$ ...
3
votes
2answers
174 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
64 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
530 views

Generating all “from n choose k” configurations of a simple list [duplicate]

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 ...
0
votes
1answer
224 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 ...
6
votes
2answers
320 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 ...
6
votes
2answers
185 views

Challenge: Creating Compilable Permutations Function

As Mathematica's implemented Permutations function is not compilable I tried to write my very own Permutations implementation, called ...
1
vote
2answers
264 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
303 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 ...
2
votes
1answer
243 views

Using IntegerPartitions for distinct integers

What I would like to do is to find a way to test how many ways m distinct integers from the set {1,..., n} where ...
1
vote
2answers
199 views

Permutations with restrictions

I have a problem that can be modeled as: there are 8 boxes in total, and 60 different items. I want to put all items into boxes (all of them can be put into a single box). Now I want to find: 1) ...
8
votes
2answers
433 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 ...
14
votes
2answers
551 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
2answers
99 views

Checking connectedness of a graph

I am trying to use the Combinatorica package in a Mathematica version 8 in the following code: ...
7
votes
1answer
319 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
189 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 ...
5
votes
1answer
725 views

How to implement Kemeny-Young method? (rank aggregation problem)

Prehistory I am trying to make some statistical analysis of some experimental data, arises from measurements made ​​on an ordinal scale. I faced with the problem of rank aggregation: to get from ...
6
votes
1answer
256 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
161 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: ...
2
votes
0answers
75 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 ...
4
votes
1answer
250 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 ...
12
votes
4answers
406 views

Equivalent Nested Loop Structure

Consider the following examples: ...
2
votes
0answers
58 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 ...
3
votes
2answers
172 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: $ ...
1
vote
2answers
2k 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
188 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
155 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 ...
3
votes
7answers
406 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 ...
2
votes
4answers
554 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 ...
6
votes
1answer
1k 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
106 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
539 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 ...
3
votes
0answers
70 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 ...
9
votes
2answers
468 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
171 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
513 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 ...
7
votes
2answers
529 views

Memory efficient generation and selection of tuples

The short of this question: I need to find a bunch of n-tuples of {0,1} which do not fail to satisfy a set of (non-linear polynomial) equations, without hogging up all of my memory by trying to ...
14
votes
6answers
496 views

Partitioning an integer into $k$ equal parts

Say I have an integer $M$. Is there a one-line command to create a partition of $M$ into $k$ integers s.t. the difference between any two integers is as small as possible? For example, with $M = ...
1
vote
0answers
326 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 ...
10
votes
1answer
324 views

Is there a function to generate a minimal clique cover?

This is a graph problem known as the "Clique Edge Cover" or "Intersection Number" problem, and the goal is to find, from a given graph like $E=\{\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\}\}$ and ...