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

learn more… | top users | synonyms

3
votes
3answers
224 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 ...
11
votes
2answers
264 views

Efficiently generating samples from an urn with maximum per element constraint?

I need to sample from a distribution that is a hybrid of uniform and hypergeometric in the sense that all elements are sampled uniformly until an element reaches some specified maximum observations, ...
0
votes
0answers
3 views

How many ways are there to distribute pens between two girls and one guy? [migrated]

There are two girls and one guy and 121 pens. How many ways are there to distribute pens between two girls and one guy, so that the girls have been an equal the amount of pens. Please can you explain ...
10
votes
1answer
371 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 $V=\...
1
vote
1answer
58 views

Consecutive generation of subsets

It is well known that the array of subsets of even small set is very big. This leads to problems with machine memory. Is there an effective way to generate subsets sequentially?
2
votes
1answer
72 views

How to split a SymmetricGroup into some PermutationGroup with smaller GroupOrder

Background I want to get a permutation list, so I use the SymmetricGroup(or use Permutations) to produce it when the ...
0
votes
0answers
10 views

combinatorics questions [migrated]

How much words we can make from $0,1,2$ ? The restriction is we cant put the digit $2$ after the digit $2$. My solution: I tried to solve it with Inclusion-Exclusion Principle count the number of ...
16
votes
4answers
489 views

How to enumerate all possible binary associations?

Suppose I have a list of symbols like: {a,b,c,d} I would like to enumerate all possible binary associations (combining symbols and/or sublists pairwise): ...
0
votes
1answer
88 views

Accessing the elements in a table is slower than calculating each time?

This is a follow-up of How to accelerate combinations and sum calculations here? I have tried all tricks but when N reaches 35 the time is still intimidating in a 16-core server, which is far better ...
7
votes
1answer
109 views

Generalizing LongestCommonSequence to 3 or more arguments?

The function LongestCommonSequence finds a longest common subsequence between 2 lists. Apparently, this built-in function does not accept more than 2 arguments. How ...
2
votes
1answer
59 views

How to accelerate combinations and sum calculations here?

I have a 4d matrix H defined as below (embedded with combinations and sums) ...
3
votes
1answer
51 views

Returning maxima of multiple sets

I am trying to prove a conjecture which involves the SetParitions[n] function (which requires the Combinatorica package). This function returns a list of all the set partitions of n. I'd like to take ...
15
votes
1answer
135 views

Is it better to completely forget about the existence of PowersRepresentations?

I noticed that in several cases the performance of PowersRepresentations is hugely worse than that of IntegerPartitions. (Mma 10....
2
votes
1answer
98 views

Mathematica doesn't know about the absorption identity? [closed]

The well-known binomial absorption identity states that $$n\binom{n-1}{k-1} = k \binom{n}{k}$$ However, Mathematica gives ...
4
votes
2answers
109 views

`IntegerPartitions` without duplicates

I need to apply a function to integer partitions of many integers, but only the partitions without duplicate numbers. Select[IntegerPartitions[n], DuplicateFreeQ] ...
2
votes
2answers
150 views

Refining subset relations

People who do combinatorics (like me) are often faced with the following problem: For a list of combinatorial objects (vectors, permutations graphs,etc.), we know what multi-set of values it ...
5
votes
3answers
129 views

How to partition a set with a condition on subsets?

I want to partition a set of $n$ elements into $k$ subsets with a condition For example: partitioning this set {1,...,5} into 3 subsets with this condition: if $|i-j|<d$ then $i$ can't be with $j$ ...
8
votes
3answers
579 views

Finding all sublists or substrings of a given list/string

Given a list or string, how do I get a list of all (contiguous) sublists/substrings? The order is not important. Example for lists: ...
0
votes
0answers
63 views

Enumerating all orientations of an undirected graph

Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in ...
1
vote
1answer
64 views

grouping binary vectors into minimal number of sets

I have a set of binary vectors that I would like to group into a minimal number of sets. A set can be formed when it contains all combinations of elements that vary within that set. Example: for <...
4
votes
1answer
149 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
60 views

Fast way to compute intersection of equivalence classes

There is a set $S=\{1, 2, \dots, m\}$ and $n$ equivalence relations on the set: $a \sim_i b $, where $a,b \in S$, $i=1, \dots, n$. Now we define $a \sim b$ iff $ a \sim_i b$ $\forall i=1, \dots, n$. ...
4
votes
1answer
89 views

Closed form probability random walk will hit k >=1 times in n steps

I'm using Mathematica to try to solve http://quant.stackexchange.com/questions/24970 and came across what seems like a simple question: if you take a standard random walk of ...
8
votes
3answers
253 views

How to count all cliques (not just maximal ones) in graphs?

How can I count the numbers of $r$-cliques in a graph? In other words, the number of triangles, the number of $K_4$, the number of $K_5$ etc. I have tried for example ...
8
votes
4answers
853 views

Tuples with one “joker” digit?

I'd like to create an array of all possible length 11 combinations of 1, 2, and the number 3, BUT with the number 3 only appearing zero or once in each combination. I tried: ...
14
votes
6answers
853 views

How to correct my code for solving the Josephus problem?

Problem Decription Recently, I have been reading the book Schaum's Outline of Mathematica (2nd Edition), where I encounted the problem: Flavius Josephus was a Jewish historian of the first ...
3
votes
5answers
282 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 \begin{...
10
votes
4answers
336 views

Efficient way to make subsets of list with placeholders

I have an arbitrary list of unique elements: lst = {a, b, c, d} Documentation allows finding subsets with same number of elements, say ...
6
votes
1answer
198 views

How to efficiently find all combinations of the letters in an alphabet given a condition

Problem: I want to find all unique expressions with n number of terms that contain all the digits (or characters) in alphabet. ...
3
votes
1answer
136 views

Efficiently generating tuples with Outer

I'm trying to efficiently generate tuples of lists of objects that satisfy a given criterion. The similar questions that I have found on this website end up finding a specific workaround for the given ...
15
votes
3answers
485 views

Generating Tuples with restrictions

I am interested in a certain subset of all tuples. Generating all with Tuples and then filtering is wasteful, and will "blow up" very quickly. For a concrete ...
1
vote
1answer
50 views

Construct all possible sets of pairs [duplicate]

I am looking for a nice way of constructing all possible pairings of a given list. Currently I am using the brute force approach of sieving the 2-partitions of all permutations. ...
4
votes
2answers
123 views
8
votes
2answers
476 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
3answers
106 views

Permutations and recurrence equation

First problem: I need to show all Permutations with length 4 of this elements {x, y, z, w, t} but with this condition: the element z mustn't be after element t. I ...
14
votes
5answers
877 views

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

This input: Permutations[Range[12]] Results in this (error) output: ...
1
vote
1answer
30 views

No of integral solutions with restrictions [closed]

x+y+z+w=n,where x<=w,y<=w. total number of non negative integral solutions of this equation?is there any closed form formula. what is the generalized formula across any number of variables?
1
vote
0answers
62 views

Finding correct combination of functions

I am trying to write code where I have an array $S$ or numbers in any order [5,4,2,1,....] Then I have a specific set of functions that I can write. ...
6
votes
5answers
148 views

Simple Enumeration of Coin Tosses

How do I enumerate a sample space with up to 6 coin tosses where 4 Heads ensures a win. For e.g {HHHH},{HTHHH},{TTHHHH},{HTTHHH} etc.I tried the following but I do not know how to do a variable length ...
5
votes
2answers
157 views

How to make pairs of Young diagrams appear?

I have the following Young diagrams {{{0}, {2}}, {{0}, {1, 1}}, {{1}, {1}}, {{2}, {0}}, {{1, 1}, {0}}} where you can interpret each pair as following: For ...
1
vote
1answer
78 views

Combinatorica and DualPartition function (for a Young diagram)

I am trying to understand how to evaluate the arm and leg functions of a Young tableaux using Mathematica. To do so I need the Combinatorica package. Then apparently the command ...
5
votes
1answer
104 views

Finding the reduced permutations of six numbers

I am trying to use Mathematica to find the following set of permutations: $$\sum_{\rho\in \tilde{S}_{n+2}} {\rm sgn}(\rho)\eta^{\mu_{\rho_{(1)}}\mu_{\rho_{(2)}}} $$ where $$ \tilde{S}_{n+2}:=\{\rho\...
27
votes
6answers
2k 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: ...
1
vote
0answers
184 views

Exceeding time constraint of 300 seconds when taking coefficients of some expressions from schur polynomial [closed]

I have written a code that takes coefficients of some expressions from schur function, but it seems to take a lot of time, and Mathematica will stop after 300 seconds saying that it's over the time ...
6
votes
2answers
198 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 ...
5
votes
1answer
75 views

What does the Combinatorica function: NumberOfPermutationsByType return?

I am using Mathematica 9. If I input: NumberOfPermutationsByType[{2, 2, 1, 1}] Mathematica returns 1/8. I was expecting <...
5
votes
1answer
287 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
1answer
210 views

Random Partitions

I want to write a function RandomPartition to partition a vector of length n into p partitions of varying (random) lengths. For example with ...
0
votes
1answer
182 views

How to get all possible combinations of this list? [closed]

I'm trying to get all possible combinations of {0,-1} for a certain length. So let's say I want length 2. Then I want my output to be ...