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

learn more… | top users | synonyms

1
vote
2answers
146 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) ...
4
votes
2answers
577 views

What function returns all possible permutations with repeating list elements?

Let's say I want to find a sample space of such experiment: There are three exits from the box: Left (L), right (R) and front (F). Three mice have been put in that box. Find the sample space of an ...
6
votes
1answer
402 views

Finding all length-n words on an alphabet that have a specified number of each letter

For example, I might want to generate all length n=6 words on the alphabet {A, B, C} that have one ...
0
votes
1answer
64 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
2answers
84 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
0answers
78 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
102 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
183 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
104 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
84 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
101 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
108 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
77 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
364 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 ...
10
votes
4answers
449 views

Permutations[Range[12]] produces an error instead of a list

This input: Permutations[Range[12]] Results in this (error) output: ...
6
votes
2answers
226 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
134 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
187 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
360 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
88 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
80 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
496 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
119 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
127 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
331 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
197 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
92 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
70 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
365 views
1
vote
0answers
128 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 ...
4
votes
3answers
612 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: ...
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 ...
3
votes
2answers
140 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: $ ...
15
votes
5answers
607 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
141 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
121 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 ...
2
votes
4answers
288 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
492 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
270 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
161 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
67 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
1k 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
337 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
102 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
341 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
375 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
126 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. ...