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

learn more… | top users | synonyms

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 ...
1
vote
1answer
59 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?
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 ...
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, ...
2
votes
1answer
77 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
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
111 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
52 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 ...
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$ ...
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 <...
1
vote
1answer
61 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
90 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
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: ...
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 ...
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

How can I make this code to count Hamiltonian paths faster?

I have this very basic code to count Hamiltonian paths in a graph: ...
15
votes
3answers
486 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 ...
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] ...
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
158 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\...
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
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 <...
1
vote
0answers
186 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 ...
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
188 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 ...
3
votes
1answer
124 views

Way to generate all multisets

I have a set $\left\{\{1,2\}, \{3,4\}, \{5,6\}, \{7,8\}\right\}$ (for example) and want to generate all sets of $n$ elements with repetition but without counting the same multiset twice. So I want my ...
2
votes
2answers
161 views

How to find all possible paths with as many edges between two same vertices?

Suppose I have an undirected graph G = Graph[{1 <-> 2, 2 <-> 3, 2 <-> 3, 3 <-> 4}] I used ...
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 ...
5
votes
0answers
130 views

Number of 4-colorings of Johnson solids

I want to know the number of 4-colorings for all Johnson solids. This is equivalent to evaluating the flow polynomial for the corresponding polyhedral graphs at $k=4$. I tried the following to get ...
24
votes
1answer
708 views

Efficient lazy weak compositions

In Mathematica all weak k-compositions of integer n can be generated using permutations of integer partitions: ...
5
votes
0answers
170 views

Visualising a 1-(50,15,15) design

The problem I have is the visualisation of a $1-(50,15,15)$ design. That is a set of $50$ points and $50$ blocks (lines), so that each point is on $15$ lines, and each line contains $15$ points. My ...
7
votes
3answers
214 views

generating integer partitions

Mathematica can generate integer partitions of an integer $N$. For example, IntegerPartitions[4] quickly gives ...
2
votes
1answer
118 views

Need Help Writing code to find Capparelli Partitions

I am trying to add multiple criterion to IntegerPartitions[n] so that it sorts only partitions that fit the criterion. It creates a list of list of numbers in ...
17
votes
3answers
473 views

Improving speed of code computing number of nonrepeating partitions

I need to answer the following for a number of parameters: How many ways can the integer $k$ be written as a sum of $n$ different integers ranging from $1$ to $m$? My initial attempt was the ...
0
votes
0answers
40 views

How to get partial results from Subsets[]? [duplicate]

Oftentimes I am searching for the first item in a sequence that satisfies some property. For example, consider the subsets of prime numbers whose total is prime. To start generate them, we could ...
11
votes
5answers
551 views

Find all the possible ways of partitioning a list into a set of pairs of element

I have a list {x1,...,xN} where N is even, and I need to find all the possible ways to split it into pairs of elements, e.g. the ...
5
votes
3answers
87 views

Conditional subset generation

I am trying to accomplish the following task: Given a list of coordinates of n points in the plane, I need to find subsets of all points that share the same x-...
0
votes
2answers
92 views

Generating polynomials with conditions on coefficients

I want to define polynomials with coefficients given in some range. Namely, let $p$ be a prime number and $n$ be a positive integer. For all positive integer $k\leq n$ I want to generate all ...
8
votes
1answer
362 views

Alternative to Subsets to generate k-combinations

I need to generare a huge number of k-combinations for a quite big set of numbers (more than 100), so I would avoid Subsets because it requires too much memory (it generates all subsets at once). I ...