Questions tagged [combinatorics]
Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
507
questions
0
votes
1
answer
48
views
Using UnrankPermutation with Maximize
I want to try and use Maximize with UnrankPermutation to find Costas Arrays (or as close as possible) for a given length l with first two elements l, 1. A permutation array that maximizes the number ...
- 817
0
votes
2
answers
77
views
How to make a function that outputs a mesh region object or some other geometric object that represents a cake number?
The lazy caterer's sequence, more formally known as the central
polygonal numbers, describes the maximum number of pieces of a disk (a
pancake or pizza is usually used to describe the situation) that ...
- 1,653
8
votes
2
answers
484
views
Drawing Delannoy paths
I want to take the code for a Wolfram Demonstration for a Delannoy number and make a function that can return a list of Delannoy plots. The code is available from the download link. The demonstration ...
- 1,653
9
votes
1
answer
352
views
Can you give a faster implementation with Mathematica for these q-analog functions?
Now(2023), Mathematica has some QFunctions for q-anlaog. See Official Documentation. e.g.:
QPochhammer
QFactorial
...
- 787
1
vote
0
answers
77
views
How to generate a list of Langfor pairings?
I am wondering how to make a function that makes a list of Langford pairings named LangfordPairings that takes an integer n as output and if Langford pairings exist for that number, they output the ...
- 1,653
3
votes
1
answer
101
views
How to make a function that returns all super distinct partitions?
I am working on distinct partitions. I recently created a function StrictIntegerPartitions.
This is from the book Integer Partitions by George E. Andrews at Pennsylvania State University and Kimmo ...
- 1,653
8
votes
4
answers
686
views
Design a function that gives all strict partitions of an integer
A strict partition of an integer has all distinct parts. There are no duplicates like 1 in {5,3,1,1} for 10. All the parts are unique. Sylvester created a bijection between the partitions of an ...
- 1,653
4
votes
3
answers
169
views
Generating all complete pair-wise listing of a starting list
It might well turn out that this question has already been asked; my problem is that I don't know how to describe it succinctly enough to search.
I have a list of 12 elements. If I take 2 elements ...
- 227
1
vote
0
answers
37
views
Sequence reconstruction from ordered subsamples
Given a sequence (we'll assume of integers) like
seq = {1, 0, 0, 1, 2, 0, 1}
I can take a random permutation
...
- 46.6k
0
votes
1
answer
121
views
How to calculate the number of partial derangements of a multiset in Mathematica?
I have found some helpful information on enumerating derangements at https://math.stackexchange.com/questions/4645664/the-number-of-partial-derangements-of-a-52-card-deck-ignoring-suits, https://sites....
- 1,653
1
vote
1
answer
120
views
Fixing code for a combinatorics problem
The problem I am solving is:
Determine all possible values of positive integer $n$, such that there are $n$ different $3$-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap ...
- 6,744
1
vote
1
answer
251
views
Enumeration of a sequence involving closure operators
Let us call a collection $\mathcal{F} \subseteq \mathcal{P}(X)$ special if it satisfies the following two conditions:
$\emptyset, X \in \mathcal{F}$
For all $U, V \in \mathcal{F}$, it holds that $U \...
- 75
7
votes
2
answers
526
views
How can I correctly use LazySubsets from Wolfram's Lazy package?
I know that Subsets[list] gives the power set of list and Subsets[list,{k}] gives all subsets containing exactly $k$ elements.
...
- 1,851
2
votes
1
answer
172
views
Finding induced subgraphs that are also trees
Given a graph $G$ with $n$ vertices, I need to find a subgraph consisting of $m$ vertices $\{v_1,\ldots,v_m\}$, and the induced subgraph of this subgraph should also be a tree.
For example, suppose $G$...
- 376
1
vote
1
answer
66
views
Additive graphs code
For $n\geq 1$ the fibonacci sum graph on the set $[n]=\{1,2,\ldots,n\}$ denoted by $G_n$, is the graph with vertex set $[n]$ and edge set $\{uv, u+v=F_i, \text{for some}\quad i\}$. I wrote the ...
- 143
2
votes
0
answers
105
views
Is FindShortestTour really exact? [closed]
I have read online that the FindShortestTour function on Mathematica uses the Concorde TSP solver, which is meant to provide exact solutions. However, I have been playing with this problem on my own, ...
- 123
4
votes
2
answers
191
views
How to find a Hamiltonian walk of a graph?
Edit: After John L.'s reminder, there is a specific term, namely "Hamiltonian walk" for my previous question. See How can we find a shortest closed walk passing through all vertices?. So I ...
- 1,851
4
votes
4
answers
264
views
Efficient generation of n-bit base-m Gray code with adjacent bit changes
How can I generate n-bit base-m Gray code in Mathematica, where only 1 bit changes at a time and all possibilities are covered? I have been hitting my head against a metaphorical wall for a few hours ...
- 53
5
votes
3
answers
242
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 ...
- 53
1
vote
1
answer
97
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$ ...
- 5,562
4
votes
0
answers
66
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 ...
- 185
1
vote
2
answers
123
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$...
- 245
5
votes
3
answers
284
views
Distribute arguments over a function in all ordered combinations
I'm looking for a function that can do this
...
- 946
4
votes
1
answer
158
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,851
7
votes
3
answers
237
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 $ ...
- 245
2
votes
1
answer
98
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 ...
- 95
6
votes
1
answer
165
views
Issues with FindPlanarColoring
I tried to use FindPlanarColoring on the following planar graph:
...
- 351
3
votes
1
answer
82
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?
- 379
0
votes
1
answer
95
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}]
...
- 23
0
votes
0
answers
45
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
3
votes
1
answer
260
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.
We can ...
- 75
4
votes
2
answers
195
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 ...
- 119
3
votes
4
answers
304
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 ...
- 1,460
4
votes
3
answers
237
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$$
- 163
1
vote
1
answer
79
views
Enumerating unlabeled phylogenetic trees
The following code comes from OEIS A000311 which is labeled phylogenetic trees. The function mtot enumerates the labeled trees.
...
- 165
4
votes
0
answers
112
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.6k
5
votes
1
answer
413
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 ...
- 75
2
votes
1
answer
151
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 ...
- 75
3
votes
3
answers
350
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 ...
- 2,678
1
vote
2
answers
198
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
-2
votes
1
answer
92
views
0
votes
1
answer
109
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,317
1
vote
1
answer
61
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 ...
- 187
2
votes
2
answers
402
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 ...
- 483
2
votes
1
answer
67
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?
- 37
5
votes
1
answer
63
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 ...
- 227
7
votes
1
answer
440
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.
...
- 17.5k
4
votes
1
answer
199
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 ...
- 41
6
votes
1
answer
235
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
110
views