Questions tagged [combinatorics]
Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
472
questions
2
votes
1
answer
154
views
Enumeration of a certain sequence
Denote by $a(n)$ the number of families $\mathcal{F} \subseteq \mathcal{P}(X)$ on a finite set $X$ with $n$ elements satisfying:
$\emptyset, X \in \mathcal{F}$
For all $U, V \in \mathcal{F}$ it holds ...
2
votes
1
answer
105
views
Code to enumerate a certain sequence
Denote by $a(n)$ the number of families $\mathcal{F} \subseteq \mathcal{P}(X)$ on a finite set $X$ with $n$ elements satisfying:
$\emptyset, X \in \mathcal{F}$
For all $U, V \in \mathcal{F}$ it holds ...
3
votes
3
answers
269
views
How to get all possible sums or possiblity of sum three numbers?
Got motivation from this and I'm trying to do this:
{#1 , #2 , #3, #1 + #2 + #3}
Where #1, #2, #3 are integer numbers from 1 to ...
1
vote
2
answers
180
views
Generating Lyndon words modulo mirroring operation and substituion
I have two letters A,B. I want to generate all words say up to length 22 with the following properties. There is no "canonical" list so any such list will suffice, though there are many ...
-2
votes
1
answer
89
views
0
votes
1
answer
56
views
Create list with integer partitions satisfying some conditions
I want to create a function PartSet[N_,M_] of two positive integer variables which outputs a list of all pairs of integer partitions for all integers up to $M$ ...
1
vote
1
answer
55
views
Sorted Tuples without Filtering
Say I have a list $L$ where the elements can be sorted into some canonical order. I want to use Tuples[L,m] but I only want the output lists to be sorted and ...
2
votes
2
answers
87
views
Using the generalised binomial theorem to expand an expression
I would like to use Mathematica to compute the following expansion: $(1+x)^\rho= 1 + \rho x +\dots$ for some $|\rho|<1$ as for example explained here. I tried the Series expansion functions ...
2
votes
1
answer
49
views
Choosing numbers whose divisors can be partitioned into subsets having the equal sum
How can we find the list of natural numbers between 100 to 10000, whose positive divisors can be partitioned into three subsets such that sum of all the elements in three subsets will be equal?
5
votes
1
answer
56
views
Picking integer compositions with certain descent patterns
I am trying to find a nice way to pick out all the integer compositions (ordered partitions) of an integer $n$ that satisfy a given pattern of descents between some adjacent elements. Writing a ...
7
votes
1
answer
424
views
Tuples optimization challenge
Consider a function that for a given integer $0\le n <256$ computes the number of leading zeros in its binary representation.
...
4
votes
1
answer
148
views
Choosing a subset of a set based on the sum of its elements
How can we choose a subset of a set based on the sum of the elements of the subset?
For instance,
n=6
dn=Divisors[n]
sn=DivisorSum[n,#&]
Is it possible to ...
6
votes
1
answer
166
views
Combine each element with all the others in sublists
Suppose that I have a list of numbers
list = {{{1, 0}, {-1, 1}, {0, -1}}, {{-1, 0, 1}, {-1, 1, -1}, {-1, -1, 0}, {1, 1, 0}, {1, -1, 1}, {1, 0, -1}}}
I would like ...
0
votes
1
answer
95
views
Deleting sublists based on a criterion
I generated a list as follows
...
1
vote
0
answers
41
views
Enumerating labeled graphs on n vertices
I'm trying to enumerate the labeled graphs on $n$ vertices having at most $e$ edges. I thought GraphData /@ GraphData[n] and then filtering by edge count would do ...
3
votes
1
answer
53
views
How can I convert sequences to sharings and vice versa?
Given positive integers $k,n$, a $k$-sequence of $I_n$ is a list of $k$ not necessarily distinct elements of $\{1,\dots, n\}$. And an $n$-sharing of $I_k$ is a list of $n$ possibly empty, disjoint ...
4
votes
1
answer
78
views
Implementing summation under combinatorial restriction
For $m,n\in\mathbb N$, I am interested in the numerical evaluation of
$$f(m,n) = \sum_{s_j\in\{\pm1\}}' \prod_{k=1}^{2n-1} (1-e^{\frac{2i\pi}{m} s_k(s_{k+1}+s_{k+2}+\cdots+s_{2n})}),$$
where the ...
2
votes
1
answer
199
views
Is there a Mathematica function that generates all ordered partitions?
My book defines a length $k$ ordered partition of $I_n$ as a sequence of $k$ disjoint, possibly empty subsets of $\{1,\dots, n\}$ that union up to $\{1,\dots, n\}$. Is there a mathematica function ...
2
votes
1
answer
87
views
Mathematica code for q-Stirling numbers
In the paper [A new $q$-Analog of Stirling Numbers],(https://hal.archives-ouvertes.fr/hal-01372920/document)[PDF] J. Cigler defined $q$-Stirling numbers of the second
kind as the following:
He ...
3
votes
1
answer
101
views
A code that returns the partial permutations on {1,2,...,n}
A partial permutation is a bijective partial function. A partial function is a map from a subset of {1,2,...,n} into {1,2,...,n}.
I want a list of the matrix representations of all the partial ...
0
votes
0
answers
30
views
Building and Plotting a discrete CDF
I'm trying to plot the CDF of a simple "nCr" experiment:
A box contains 4 screws and 6 nails. Two items are drawn at random without replacement. Let X be the number of nails drawn.
I built a ...
6
votes
1
answer
223
views
Producing a random Wang Tile tiling image more efficiently
I'm following along with this SIGGRAPH 2006 paper Recursive Wang Tiles for Real-Time Blue Noise - there's a video here too. Eventually I want to try to produce the blue noise results in the paper, and ...
4
votes
1
answer
134
views
Permutations with Repetition
I am working with a function of type
F[a,b,c,d,e,f]
that obeys the following symmetries:
...
0
votes
0
answers
60
views
Conditional Statement and Loop in Mathematica to find bound
I have a question regarding loop and conditional statements. I have an equation where I would like to find the bound for n and m based on the value of h. Here is what I have so far;
...
1
vote
0
answers
62
views
Triangulation of Point Configuration
I was going through the documentation of Mathematica but couldn't find any built-in function that can find all possible triangulations for a given set of points.
For example, if I have the following ...
2
votes
1
answer
138
views
2
votes
0
answers
70
views
Matroids in Mathematica?
I can't seem to find a "standard" way to implement/manipulate matroids in Mathematica. (They do not seem to be included in Combinatorica, for instance, and googling has turned up nothing.) ...
3
votes
2
answers
145
views
Find different combinations of 3 lists with given constraints
My inputs are 3 lists of unequal length:
A={a,b,c,d}
B={i,j,k}
C={v,w,x,y,z}
And I want to find the combine set X which looks like
...
2
votes
1
answer
58
views
2
votes
1
answer
49
views
Extract only a few coefficients of the multiple of extremely many polynomials
I want to extract some informations, say the coefficients of $x^{500}$ and $x^{1000}$ terms (numerical values are acceptable), of the multiple of
...
7
votes
3
answers
335
views
Partition a nested list such that no repeated elements in every subsets?
I have a large list and for simplicity, let's take the simple list as an example:
lists = {{1, 2}, {1, 6}, {2, 3}, {2, 5}, {3, 4}, {3, 6}, {4, 5}, {5, 6}}
I would ...
1
vote
0
answers
57
views
How do I generate a random permutation of a (long [millions-length]) list of symbols? [closed]
I have a list of length twelve:
p = {t[1, 1], t[1, 2], t[1, 3], t[1, 4], t[2, 2], t[2, 3], t[2, 4],
t[1, 5], t[3, 3], t[3, 4], t[1, 6], t[4, 4]}
and a set of ...
1
vote
1
answer
58
views
Construct all possible 3-letter words from A,B. Repetition of letters is allowed [closed]
I have two letters A and B. I need to construct all possible 3-letter words. Repetition of letters is allowed. I know that the answer to this problem is 2^3=8. But ...
4
votes
1
answer
137
views
Fast enumeration of all perfect matchings in complete graph
I have a code that generates the list with all possible Perfect Matchings (PM) of a fully connected graph. Each edge of the graph is mono or bi-colored with up to ...
3
votes
5
answers
445
views
Finding all Latin Squares of order 5
A Latin Square is a square of size n × n containing numbers 1 to n inclusive. Each number occurs once in each row and column.
An example of a 3 × 3 Latin Square is:
$$
\left(
\begin{array}{ccc}
1 &...
1
vote
1
answer
60
views
Edge thickness in directed path graph doesn't respond
I have the following code to draw a lattice path in 3D:
...
5
votes
6
answers
430
views
Count number of balls in each bin, given a two-element sequence of balls and bins
If I have a list:
{ball,ball,BINDIVIDER,ball,ball,ball,BINDIVIDER,BINDIVIDER,ball,BINDIVIDER,ball}
The balls and bins can be in any permutation.
Then, the ...
0
votes
1
answer
101
views
How to create all possible permutations? [closed]
there is a problem:
I have 5 letters - a,b,c,d,e and 20 places. I have to use each letter at least once but no more than 10 times. So the result can look like {a,a,a,a,a,a,a,a,a,a,b,b,b,b,b,b,b,c,d,e},...
1
vote
1
answer
137
views
How to generate all the combinations with repetition and another conditions? [duplicate]
I want to generate all the combinations with repetition for k variables with values from a set of n elements.
There are some ways, I like this formula, which I found on this forum (it is for n = 2 and ...
11
votes
8
answers
1k
views
Transform a number to a factorial
I came across the need to transform a number into a factorial n, with positive integer n. I have searched in the MMA information but I can't find anything like that.
I imagine an input, which verifies ...
2
votes
1
answer
93
views
Splitting balls over sized bins
This is strongly related to Splitting a set of integers over a set of bins, but a much simpler case.
If we have $N$ indistinguishable balls and $k$ arbitrarily large distinguishable bins, we know the ...
6
votes
1
answer
92
views
Splitting a set of integers over a set of bins
I have a problem that feels like it should be simple but I'm just drawing a blank on. I've got a set of integers, e.g.
...
3
votes
2
answers
87
views
Generating representatives of rotation classes of tuples of ones and zeros with a fixed number of ones
In a related question I asked how to generate all the tuples of ones and zeroes with a fixed number of ones (generating tuples of ones and zeroes with a fixed number of ones). I wish to consider a ...
9
votes
6
answers
482
views
generating tuples of ones and zeroes with a fixed number of ones
I would like to generate all the tuples of ones and zeros of a given length and with a given number of ones without generating all the possible tuples, which is impossible for tuples of large enough ...
1
vote
1
answer
135
views
How to efficiently replace the repetitive sequence?
The problem is how to determine the repetitive sequences and replace the part with consecutive sequences
For example:
A={{1,3,4},{2,3,5},{1,6}}
Then, detect there ...
6
votes
3
answers
883
views
How many graphs are there on 4 nodes with degrees 1, 1, 2, 2?
I know just the basic operations on graphs using Mathematica. But I want to know how to write a code that prints all the possible combinations of a graph with a specified number of edges.
Take for ...
11
votes
4
answers
589
views
Scan through (partial) tuples
I have a list of list of positive integers $s = \{s_1, s_2, ..., s_k\}$, each list $s_i$ is possibly of different lengths, and I want to find out if there exists a $k$-tuple of the $s_i$ that sums ...
1
vote
0
answers
45
views
Custom Table, for iterating over permutations
It is common that I iterate over all permutations of 1,2...,n, either by making a table or performing a sum.
Instead of creating the set of all permutations, it would be better to iterate over them.
...
3
votes
3
answers
171
views
How to delete duplicate graphics of the same kind?
A054247: Number of n X n binary matrices under action of dihedral group of the square D_4.
...
1
vote
1
answer
88
views
How to solve this problem by the way of saving memory?
Eight different boys and five different girls are in a row. Girls are required to be next to each other. How many ways are there (the answer is $9!\times5!$)?
...