Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
1
vote
0answers
79 views
Shapley value and Mathematica [closed]
I use the TuGames package in Mathematica to analyze
cooperative games. Is it possible to calculate Shapley
value, Nucleolus, etc., for a large number of players like
400 or more?
5
votes
0answers
64 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 ...
0
votes
0answers
10 views
What is the number of possibilities? [migrated]
I have an excercise to do:
How many possibilities is for planting 12 apostoles if it is important who is siting next to who but it is not important from which side?
Answer possibilities:
a)
...
2
votes
1answer
65 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
34 views
How could I find the correct values for every array that would lead me to unique summation number for every unique chain? [migrated]
I have 9 arrays, each array has 9 values, I need to get the proper values in every value's position for every array, and that would give my a completely unique summations for every value's chain from ...
0
votes
0answers
34 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,
...
2
votes
1answer
59 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, where n >=3. For example, with n = 3, the sets {1,1,1}, {1,1,2}, ..., ...
0
votes
0answers
45 views
Generating partitions of a set [duplicate]
Is it possible to get Mathematica to generate all possible partitions of a set of objects?
(..or equivalently if it can be made to do the cumulant expansion or at least the Gaussian special case of ...
5
votes
1answer
83 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
119 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)!}$$
...
3
votes
1answer
88 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
182 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
102 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
165 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
149 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
146 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 ...
3
votes
2answers
127 views
What function returns all possible permutations with repeating list elements? [closed]
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
150 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
94 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 ...
1
vote
1answer
91 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
135 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
313 views
Exact cover solution
Is it possible to get a exact cover solution(s) and/or number of possible solutions in Mathematica?
14
votes
6answers
869 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
201 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 ...
2
votes
3answers
233 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
510 views
Get number of combinations without “forbidden patterns”
I need to get the number of all combinations of binary digits in an 8-digit binary number, but minus some "forbidden" patterns like:
xxxx0xx1
x1xxx0xx
x1xxx0x0
...
20
votes
2answers
741 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 ...
4
votes
1answer
285 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. ...
3
votes
0answers
165 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 ...
6
votes
4answers
237 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 ...
3
votes
1answer
197 views
3
votes
2answers
179 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
876 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 ...
6
votes
3answers
523 views
Find cycles of graphs with both directed and undirected edges
I need to enumerate all the simple cycles of a graph which has both directed and undirected edges, where we can treat the undirected edges as doubly directed. (Specifically, I am looking at the Cayley ...
11
votes
2answers
336 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
271 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 ...
6
votes
2answers
443 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.
...
3
votes
0answers
71 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
...
3
votes
1answer
379 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 ...
21
votes
4answers
2k views
Looking for “Longest Common Substring” solution
I'm looking for robust code to solve the "Longest Common Substring" problem. I can just code it up from that description, but I'd thought I'd ask here, first, in case someone knows of an ...
13
votes
3answers
346 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 ...
18
votes
3answers
476 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
383 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
287 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
176 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 ...
7
votes
1answer
200 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
212 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 ...
9
votes
2answers
148 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 ...
15
votes
4answers
439 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 ...
15
votes
5answers
815 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 ...
