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

learn more… | top users | synonyms

1
vote
0answers
70 views

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

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
99 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
102 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
174 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
78 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 ...
1
vote
1answer
82 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
96 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
52 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
63 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 ...
0
votes
1answer
104 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
224 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
123 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
185 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
0answers
81 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 ...
11
votes
1answer
348 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
79 views

Checking connectedness of a graph

I am trying to use the Combinatorica package in a Mathematica version 8 in the following code: ...
6
votes
1answer
111 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
122 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
194 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
90 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 ...
1
vote
0answers
123 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
364 views

Equivalent Nested Loop Structure

Consider the following examples: ...
2
votes
0answers
55 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
134 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
418 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 ...
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
118 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
326 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
283 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 ...
5
votes
1answer
468 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
252 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
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 ...
6
votes
2answers
335 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
95 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 ...
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 ...
0
votes
0answers
119 views

Pearl's Message Passing Algorithm

Has anyone tried to implement the Message Passing algorithm using Mathematica's Graph/Combinatorica features?
4
votes
4answers
336 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
125 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
166 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 ...
7
votes
0answers
303 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 ...
6
votes
0answers
110 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 ...
2
votes
1answer
100 views

PermuteSubgraph not working? (Combinatorica)

I am trying to write a code to perform the QAP partialling analysis (here's a paper to know more) but the part in which I "scramble" the graph with PermuteSubgraph does nothing, I am actually not ...
0
votes
0answers
39 views

Generating partitions of a set with a specified size of the parts [duplicate]

I tried the following (inspired by the answer here) myList = {a, b, c}; Needs["Combinatorica`"]; SetPartitions[myList] and I got this answer, ...
4
votes
2answers
156 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, ...
10
votes
1answer
123 views

How do I expand StirlingS2[n, 10] in terms of elementary functions?

I know that it is possible to expand StirlingS2[n, 10] in terms of elementary functions of n. I tried ...
4
votes
1answer
143 views

Combinations which do not have elements in common

I can choose 2 letters from the four letters $\{A,B,C,D\}$ in 6 combinations using the combination formula $$\frac{n!}{ r! (n-r)!}$$ ...
4
votes
1answer
247 views

Looking for a package regarding Schur Polynomials and Kostka numbers

I'm currently looking for any Mathematica package that involves Schur polynomials and/or Kostka numbers. More generally, I'd be happy with anything that expands on symmetric polynomials in general. ...
2
votes
2answers
272 views

How to determine all cases consistent with constraints

Suppose that $(i, j), (k, l)$ and $(m, n)$ are pairs of non-negative integers, satisfying the following constraints: $$i < j,\;\; k < l, \;\; m < n$$ and $$ (i, j) < (k, l) < (m, ...