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

learn more… | top users | synonyms

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 ...
6
votes
2answers
376 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
131 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
58 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 ...
4
votes
4answers
432 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 ...
1
vote
0answers
233 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
285 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
104 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
40 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
244 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
131 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
151 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)!}$$ ...
8
votes
1answer
363 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. ...
3
votes
2answers
337 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, ...
2
votes
1answer
247 views

How can I prevent these warnings while using ParallelTable

I have this code to find all the permutations of a set of letters that form legal words. ...
6
votes
3answers
454 views

Counting the number of a specific type of permutation

In the theory of cumulants of vector-valued random variables, the following types of formulas appear: \begin{equation} \theta^i \theta^{jk} [3] = \theta^i \theta^{jk} + \theta^j \theta^{ik} + \theta^k ...
7
votes
2answers
314 views

Solving variant of the knapsack/money-changing problem

I'm trying to solve a variant of the knapsack/changing money problem where I have a set of a few numbers and I'm trying to find the linear (integer) combinations of them which are close to a given ...
6
votes
2answers
313 views

Find all permutations with a condition

How can I find all the permutations of {a, b, c} where a + b + c = n? For instance: if ...
4
votes
2answers
928 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 ...
4
votes
2answers
269 views

Partition a set into $k$ non-empty subsets

The Stirling number of the second kind is the number of ways to partition a set of $n$ objects into $k$ non-empty subsets. In Mathematica, this is implemented as ...
2
votes
1answer
150 views

How to evaluate the sum over a hyperplane

I have difficulties in evaluating the following expression: $$\sum_{\small n_1+...+n_{k}=m-k}\; \prod_{i=1}^{k}\frac{1}{(n_i+1)(n_i+2)}$$ I have tried the function ...
2
votes
1answer
162 views

Finding integer partitions one at a time

I am writing a small program and I need to calculate integer partitions of a handful of numbers. In my code I just run IntegerPartitions[k,{n}] and then iterate through the results. Since I only use ...
3
votes
3answers
205 views

Need Help Writing (a Pascal) Matrix in Mathematica

I want to write a function $f[n]$ in Mathematica which gives me an $n\times n$ lower triangular Pascal matrix with a row of zeros in between each nonzero row. That is, I want the matrices ...
4
votes
2answers
664 views

Exact cover solution

Is it possible to get a exact cover solution(s) and/or number of possible solutions in Mathematica?
19
votes
6answers
1k views

Insert $+$, $-$, $\times$, $/$, $($, $)$ into $123456789$ to make it equal to $100$

Looks like a question for pupils, right? In fact if the available math symbol is limited to $+$, $-$, $\times$, $/$ then it's easy to solve: ...
2
votes
0answers
370 views

Generating a function which outputs possible chemical reactions

I want to make a list of chemical reactions and I write them down in a $\require{mhchem}\LaTeX$ format. They are of the following form $$NA_n^i+MB_m^j \rightarrow \hat NA_{\hat n}^{\hat i}+\hat ...
4
votes
3answers
820 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: ...
14
votes
5answers
712 views

Getting number of binary digits combinations without “forbidden” patterns

I need to get the number of all combinations of binary digits in an 8-digit binary number, but not including those that follow some "forbidden" patterns like these: ...
21
votes
2answers
854 views

Plotting an Unreasonable Function

Without getting into too much detail, the following (very complicated) function recently appeared as a solution to a combinatorics problem I've been thinking about: $$P(n) = \frac{52!}{52^{52}} \cdot ...
6
votes
1answer
571 views

(Efficiently) Generating graphs with vertex degree 3 for all vertices

I'm working on a graph theory problem, and given $n$ vertices, I would like to be able to generate all non-isomorphic connected graphs (not necessarily simple) with $n$ vertices, each having degree 3. ...
6
votes
1answer
519 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 ...
7
votes
4answers
360 views

permutation as product of transpositions

How can the permutation that takes{-f, -i, i, -e} into {-e, -i, i, -f} be realised as a sequence of nearest neighbour ...
4
votes
2answers
327 views

Combinatorica: Girth[] and FindCycle[] disagreement

Warning: run the following code in a fresh Mma session, as some symbols could be shadowed (depending on your Mma version) While trying to answer this question, I fell into the following: ...
23
votes
4answers
1k views

What is the fastest way to count square-free words?

Background A word is a string of letters in an alphabet. A square-free word has no adjacent repeating substring. For example, (in the ternary alphabet of {0,1,2}) the words 00, 012121, and 0212012021 ...
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 ...
11
votes
2answers
396 views

Word Squares and Beyond

A word square is a set of words which, when placed in a grid, read the same horizontally and vertically. For example, the following is an English word square of order 5: ...
10
votes
3answers
423 views

Generating Linear Extensions of a Partial Order

Given a set $S$ and a partial order $\prec$ over $S$, I'm looking for a way to "efficiently" generate a list of linear extensions of $\prec$. Suppose the partial order is given by a ...
8
votes
2answers
2k views

Finding all partitions of a set

I'm looking for straightforward way to find all the partitions of a set. IntegerPartitions seems to provide a useful start. But then things get a bit complicated. ...
4
votes
0answers
93 views

BipartiteMatching hangs with floating-point weights in Mathematica 7 (package Combinatorica)

I am trying to use Combinatorica's BipartiteMatching algorithm on a weighted graph. I need to use real numbers as weights. If I try the following ...
4
votes
1answer
571 views

How to create tournament bracket

I'd like to create a tournament bracket using Mathematica. I've looked around online, but haven't found any examples yet. Can someone show me how to do this? Specifically, I'd like to have a ...
29
votes
4answers
3k views

Looking for “Longest Common Substring” solution

I'm looking for robust code to solve the "Longest Common Substring" problem: Find the longest string (or strings) that is a substring (or are substrings) of two or more strings. I can just code it ...
14
votes
3answers
551 views

Determining all possible traversals of a tree

I have a list: B={423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, 40, 423}}}}; This list can be visualized as a tree using ...
23
votes
3answers
1k views

How to load a package without naming conflicts?

This question applies to any package, but I encountered this problem while working with graphs. There are symbols in the Combinatorica package (such as ...
4
votes
1answer
2k views

Is it possible to generate a Hasse Diagram for a defined relation?

I'm looking for a way to create a Hasse Diagram from a given partial order binary relation. The relation will be given explicitly, for example: ...
14
votes
1answer
401 views

When to use built-in Graph/GraphPlot vs. Combinatorica

What are the pros and cons of using built-in Graph/GraphPlot (and related) types vs. types in the Combinatorica package?
3
votes
1answer
401 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 ...
8
votes
1answer
420 views

Mathematica function/package for shuffle permutations

Does anyone knows a way to compute a list of all (p,q)-shuffles in mathematica? For a definition of the shuffle permutations see for example http://ncatlab.org/nlab/show/shuffle I'm dreaming of a ...
6
votes
1answer
490 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 ...
10
votes
2answers
199 views

NumberOfSpanningTrees command not working correctly

I am attempting to use the Combinatorica NumberOfSpanningTrees command for all n-cycle graphs from 3 to 30. I am trying to get a ...