Questions tagged [combinatorics]
Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
489
questions
5
votes
3
answers
222
views
Plot diagonal lattice path
I'd like to plot lattice paths like RUURUD where R is a step to the right, U is a step above ...
- 21.1k
25
votes
5
answers
2k
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 ...
1
vote
1
answer
96
views
Arrange 1-n^2 in n×n grid satisfy products of rows equal to products columns
For which $n\in\mathbb{N}$ is it possible to arrange $\{1,…,n^2\}$ in an $n\times n$ grid so that the set of products of columns equals the set of products of rows?
I can find solution for $3\times 3$ ...
- 37.1k
3
votes
0
answers
56
views
Can FindMinimumCostFlow be trusted?
So, I recently began to use graphs algorithms in Mathematica notebooks to solve an unbalanced assignment problem.
After running the algorithm, I wanted to check that the total flow was equal to the ...
- 151
7
votes
3
answers
228
views
Permutations with subsets not containing the same elements
I would like to define a function of two integer variables $ \{n, k\} $, with $ k | n $, that would print all the possible permutations of the first $ n$ positive integers, such that the subsets of $ ...
- 4,095
1
vote
0
answers
58
views
Find all ways to split a list into k sublists (of different length)
I would like to write an efficient code for splitting a set into k disjoint subsets, whose union would be the input set. The input set is represented by sorted lists with no repetitions, and the ...
- 73
1
vote
2
answers
114
views
Delete the subsets containing the same $2$ integers present in other subsets
From my previous question, if I consider a list like this:
$\{$$\{$$\{$$1,2,3$$\}$,$\{$$4,5,6$$\}$$\}$,
$\{$$\{$$1,2,4$$\}$,$\{$$3,5,6$$\}$$\}$,
$\{$$\{$$1,2,5$$\}$,$\{$$3,4,6$$\}$$\}$,
$\{$$\{$$1,2,6$...
- 356k
5
votes
3
answers
277
views
Distribute arguments over a function in all ordered combinations
I'm looking for a function that can do this
...
- 28.8k
4
votes
1
answer
150
views
How to generate 3-subsets that satisfy certain conditions without post-filtering?
Edits: In fact it is a set partition problem.
I have a set as follows:
...
- 1,495
6
votes
1
answer
164
views
Issues with FindPlanarColoring
I tried to use FindPlanarColoring on the following planar graph:
...
- 52.2k
3
votes
1
answer
74
views
Generating all $k$ combinations from $n$ objects [closed]
Suppose I have $n$ numbers $\{1,2,\cdots,n\}$, is there a very quick way of generating $k$-combinations using Mathematica?
- 11.8k
0
votes
1
answer
80
views
Counting number of (non distinct) integer partitions into k
I want to count and generate the number of non distinct integer partitions into k. I know that IntegerPartitions[n,{k}] returns the partitions of integer n into k.
E.g. IntegerPartitions[4, {2}]
...
- 15.6k
2
votes
1
answer
215
views
Enumeration of a certain sequence III
Let’s call a collection $\mathcal{F} \subseteq \mathcal{P}(X)$ satisfying:
$\emptyset, X \in \mathcal{F}$
For all $U, V \in \mathcal{F}$ it holds that $U \cap V \in \mathcal{F}$.
special. And let us ...
- 45
5
votes
1
answer
395
views
Enumeration of a certain sequence I
Lets 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 ...
- 45
0
votes
0
answers
43
views
Arranging 4 identical items in 7 spots [closed]
There are 4 unique items, for the sake of the example call them balls. Each ball is exactly the same, and we need to see how many different ways those 4 balls can fit in those 7 slots.
I am not sure ...
- 1
5
votes
2
answers
215
views
Groupings of the Elements of a List with at Most $k$ Elements
Given a list with $n$ elements and an integer $k$ I want to get a list with all possible groupings of these n elements in sets with at most k elements. For example, given $n=\{1,2,3,4\}$ and $k=3$ I ...
- 529
16
votes
2
answers
6k
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.
...
- 529
42
votes
6
answers
4k
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 ...
- 529
4
votes
2
answers
194
views
Mathematica can't find Minimum sum under integer constrains
I'm trying to verify a solution to a simple probability problem using Mathematica. Here's the problem:
A drawer contains red socks and black socks. When two socks are drawn at random, the probability ...
- 64.1k
3
votes
4
answers
269
views
Verifying a combination problem using subsets
The question is shown below. The handwritten answer is one of the methods of the mark scheme.
This method "seemed" ok, but we are not so convinced about the Total of 140 ways.
Also, there is ...
- 599
4
votes
3
answers
219
views
How to solve combination problem with mathematica?
How to find the smallest n s.t:
$$\binom{2500-n}{50}/\binom{2500}{50} < 0.5$$
- 41.3k
1
vote
1
answer
76
views
Enumerating unlabeled phylogenetic trees
The following code comes from OEIS A000311 which is labeled phylogenetic trees. The function mtot enumerates the labeled trees.
...
- 1,440
4
votes
0
answers
106
views
Finding a large clique of an impractically large generalised Kneser graph
My original problem statement is simple. Find a maximal clique of $k$-length subsets of of a set of $n$ items, clique members sharing at most $s$ items with any other.
This is the maximal clique of a ...
- 18.3k
2
votes
1
answer
139
views
Enumeration of a certain sequence II
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 ...
- 45
3
votes
3
answers
328
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 ...
- 41.3k
5
votes
2
answers
2k
views
Cartesian product of more than two sets
Here you see how to produce a cartesian product of two sets. How can we obtain the cartesian product of three or more sets? CartesianProduct[l1,l2,l3] doesn't work....
- 530
3
votes
5
answers
582
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 &...
- 14.6k
4
votes
1
answer
184
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 ...
2
votes
1
answer
59
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?
1
vote
2
answers
192
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 ...
- 647
12
votes
4
answers
1k
views
generating integer partitions
Mathematica can generate integer partitions of an integer $N$. For example, IntegerPartitions[4] quickly gives
...
- 14.6k
-2
votes
1
answer
89
views
5
votes
3
answers
266
views
How the solve the parameter of the conjugate permutations
As we know the definition of conjugate permutations is:
$$\exists p \quad p^{-1} \alpha p=\beta$$
When I have an alpha=Cycles[{{1,4},{2,5,6,3}}] and a ...
- 25.3k
6
votes
1
answer
135
views
Why Does Subsets[...,{n}] not Output a Packed List, Even Though it Doesn't Unpack?
Assume list is packed.
I expect Subsets[] is a structural operation because it depends on the number of elements, not on what ...
- 14.6k
6
votes
3
answers
504
views
Non-descending Tuples
I want to get all the non-descending tuples of a list with given length, for example:
f[{1,2,3,4},{3}]
...
0
votes
1
answer
82
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$ ...
13
votes
3
answers
606
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:
...
- 1,141
1
vote
1
answer
60
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 ...
- 37.7k
6
votes
1
answer
224
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 ...
- 11.8k
0
votes
1
answer
105
views
2
votes
2
answers
232
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 ...
- 64.1k
7
votes
1
answer
435
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.
...
- 18.3k
5
votes
1
answer
60
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 ...
- 17k
9
votes
2
answers
2k
views
All possible topological orderings of a graph
TopologicalSort[] returns one of many unique orderings.
From wikipedia:
if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid ...
- 3
1
vote
0
answers
45
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 ...
- 21
3
votes
1
answer
57
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 ...
- 356k
4
votes
1
answer
90
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 ...
- 9,503
2
votes
1
answer
224
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 ...
- 356k
3
votes
1
answer
95
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,435
6
votes
1
answer
262
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,285