All Questions
Tagged with combinatorics algorithms
1,045
questions
2
votes
0
answers
227
views
Counting permutation matrices
$J \in \{0,1\}^{n \times n}$ is a matrix with all elements being $1$. $S := \{P_1, P_2, ..., P_n\}$ is a set with $n$ permutation matrices $P_i \in \{0,1\}^{n \times n}$ such that $\sum\limits_{i=1}^n ...
- 1,008
1
vote
0
answers
11
views
Find Extremal Point over a Set of all Simple Cycle in a Directed Graph
Dearl all,
I recently stumbled across an interesting combinatorial problem and was wondering if someone here has faced something similar and would help me get a head start.
Problem Defintion
Let G be ...
- 11
1
vote
1
answer
259
views
Find a maximum-weight matching in general graph with constrained cardinality
Let $G=(V,E)$ be a general graph, where edges have weights $w(e)$ and $|V|$ is even.
One of the classic problem is to find a maximum-weight perfect matching (MWPM) of the graph G.
The MWPM problem can ...
- 13
2
votes
0
answers
23
views
Model Counting for Sum of Conjunctive Formulas
Problem:
Let $X=\{x_1, ..., x_N \}$ be a set of binary variables. Each variable can be assigned to either $0$ or $1$ so there are $2^N$ possible assignments.
Input: We are given a positive integer $C$ ...
- 21
7
votes
1
answer
132
views
A hat allocation problem
This is an abstraction of a problem that has come up in my research.
Imagine we have $N$ wizards and $N$ hats. The hats have $C$ different colours. There are $n_1>0$ hats with the first colour, $...
- 1,295
1
vote
0
answers
65
views
How to construct a set system with given set and pairwise intersection sizes
Consider a finite set $X$ and some subsets $X_i \subset X$, $i = 1,\dots,n$, with $\bigcup_i X_i = X$, of which one only knows the sizes $|X_i|$ and $|X_i \cap X_j|$.
How do I systematically ...
- 18.2k
3
votes
0
answers
86
views
Given $n\in\mathbb{N}_{\geqslant 2}$, find the partition $(a_1,...,a_k)\in\mathbb{N}^k:\sum_{i=1}^k a_i=n$ of $n$ that maximizes $\prod_{i=1}^k a_i$
I am a solving programming question in Leetcode in which, given a number $n \in \mathbb{N}_{\geqslant 2}$, I have to find $(a_1, ..., a_k) \in \mathbb{N}^k$ such that $k \in \mathbb{N}$, $2 \leqslant ...
4
votes
1
answer
168
views
Size of a union of sets when only their sizes and those of pairwise intersections are given
Consider a finite set $X$ and a set of subsets $X_i \subset X$ with $\bigcup_i X_i = X$.
Assume that only the sizes $|X_i|$ and $|X_i \cap X_j|$ are given.
Obviously
$\sum_i |X_i| - \sum_{ij}|X_i \cap ...
- 18.2k
2
votes
0
answers
34
views
Astronomer watching planets in a solar system
There is exactly one astronomer on every planet of a certain system. He watches the closest planet. The number of the planets is odd and all of the distances are different. Prove that there one planet ...
- 162
1
vote
1
answer
239
views
How would I find the minimum non-trivial cut in a graph?
I know that there is an algorithm which computes the minimum cut in a graph $G$.
I have a situation where I am trying to compute the minimum non-trivial cut of $G$, where I say that a cut is trivial ...
- 578
0
votes
0
answers
26
views
Approximating global extrema with the extrema of subsets of parameters
I don't have a particularly strong background on math;
I have a function of many boolean parameters $\theta_i$ :
$$ y = f( \theta_1 , ...., \theta_n ) $$
And I look for the values of the parameters ...
- 13
2
votes
0
answers
166
views
Greedy algorithm minimizes the sum
There are $n$ positive numbers (not necessarily distinct). In every step, we
can select two numbers and replace each of it with the sum of the two
numbers. Prove that in any amount of steps, selecting ...
- 1,919
0
votes
0
answers
32
views
How to describe these combinatorial sets in general and prove their cardinality
The sets I am looking at are defined as follows: for $k=1$ the set is defined as:
$\Sigma_1:=\Big\{ \frac{1}{1},\frac{1}{3}\Big\}$
whereas for $k=2$ we have
$\Sigma_{2}:=\Big\{ \frac{1}{1},\frac{2}{1},...
user830143
0
votes
0
answers
15
views
How to simplify this combinatorial formula and solve the cardinality of the intersection? [duplicate]
Define two sets: $\Sigma_1$ and $\Sigma_2$ where we have that $a$ is odd (i.e. $a=2n+1$ for some $n\in \mathbb{N}$) and $b\in \mathbb{N}$,
$\Sigma_1 = \Big\{ \frac{2}{a},\frac{2}{a-2},\frac{2}{a-4},....
user830143
0
votes
0
answers
46
views
Computing the cardinality of a combinatorial set
Define two sets: $S_1$ and $S_2$ where we have that $a$ is an odd natural number and $b\in \mathbb{N}$,
$S_1 = \Big\{ \frac{2}{a},\frac{2}{a-2},\frac{2}{a-4},...,\frac{2}{a-(a-1)},$
$\frac{2+4}{a+2},\...
user830143
0
votes
1
answer
39
views
Combinatorial Minimization Problem for sets of rational numbers.
If we have the set
$\Bigg\{ \frac{1}{1},\frac{1}{2},\frac{1}{3},...,\frac{1}{k} \Bigg\}=:A$
for some $k\in \mathbb{N}$ (known). We pick some $a\in \mathbb{Q}$ such that we have
$\Bigg\{ \frac{a}{1},\...
user830143
0
votes
0
answers
59
views
A sequence in which the number of positive bits is always $k$.
Thanks to this stack , I got the following Conjectures.
My question is as follows;
My question:
(Q1)Are the followng conjectures (1) and (2) correct?
(Q2)If these are correct, please prove them.
The ...
- 665
0
votes
1
answer
46
views
Positive bit count of the $S(n):=\sum_{i=1}^{n} 2^{(i-1)}$ always $n$?
From a discussion on a stack about the programing, I got the following mathematical Conjectures:
Conjectures:
Let n,m be positive integer, $S(n)$ and $CountPosbit(m)$ be as follows.
$S(n):=\sum_{i=1}...
- 665
0
votes
1
answer
277
views
Compute the minimum spanning tree in hypercube $Q_{k}$
Suppose that in the hypercube $Q_{k}$, each edge whose endpoints differ in coordinate i has weight $2^{i}$. Compute the minimum weight of a spanning tree.
I know I can use Kruskal's algorithm but not ...
- 415
1
vote
0
answers
34
views
How many variatons of winners are there in 15 1vs1 matchs
I am trying to find a program or some way to show me every variation of winners from just 5 matchs of 1vs1.
I think there should be 900 variation i just need a way to see it all written down ..
For ...
- 11
6
votes
1
answer
317
views
Math behind this SQL problem
I have the following 'sorted by row' lists (2nd column), in which every row produces an output (3rd column, and 4th column). This output has been found without using formulas and it represents a ...
- 121
0
votes
0
answers
30
views
How do we place $k$ lines in $\mathbb{R}^2$ to achieve only $n$ slopes?
So here's my problem: we have the total of $k$ lines in $\mathbb{R}^2$ that all must have a common intersection point. The lines are determined by even number of points each. For instance, we may have ...
user830143
0
votes
2
answers
70
views
Maximizing a combinatorial identity
So here is my problem. If we have a vector $\textbf{x}=(x_1,...,x_n)$ where $x_j \in \mathbb{N}$ for each $j \in \{1,...,n\}$, then is there a way to maximize the value of the following combinatorial ...
user830143
1
vote
0
answers
23
views
How much of a square is covered by $r$ sub-squares, expectation of the function $2^{-x}$ of that
Let natural numbers $n$ and $k\leq n$ be given. We consider the square made of $n\times n$ tiles. It has $M=(n-k+1)^2$ sub squares of dimensions $k\times k$. We pick $r$ out of these sub squares and ...
- 544
7
votes
1
answer
387
views
Robot moves from $(x,y)$ to $(x+y, y)$ or $(x,x+y)$
I was working on some coding related to this topic I found on Stack Overflow. This lead me to a math problem I thought would be interesting. I was wondering if one was given a starting point, what ...
- 71
0
votes
1
answer
44
views
Proof of greedy algorithm.
Given n numbers find the way to assign them to blocks of 3 (and possible one block of 1 or 2 if n is not divisible by 3) so that sum of smallest elements from each full block is maximal.
ie.
numbers ...
- 101
1
vote
0
answers
287
views
Rephrase a simple mathy logic problem (yielding solution of an ordered procedure), and its generalized counterpart, into a solvable algorithm.
I'm given a selection of logic puzzles about different entities crossing a river safely (either from the same side to the same other side, or switching sides; utilizing the same boat, with certain ...
- 29
1
vote
0
answers
120
views
Evaluating the Gauss Circle Problem $N(n)$ in $O(n^{\frac{1}{3}+\epsilon})$
I'm interested in the technique of counting the number of positive integer pairs $x$ and $y$ satisfying $x^2+y^2 \leq n$ in $O(n^{\frac{1}{3}+\epsilon})$. The basic idea is that we can only focus on ...
- 1,586
2
votes
0
answers
56
views
Unique number of combinations after $z$ steps of merging items by specific rules
I encountered an issue where I am trying to estimate the number of unique combinations:
There exists $N$ distinct molecules (or, for example, balls), where each molecule is labelled with some ...
- 21
0
votes
1
answer
56
views
Number of ways of traversing a graph through all of its nodes?
A lift has $N$ stops ($1,2,3,4,...,N$), hence have $N(N-1)$ distinct rides of travelling from floor $A$ to floor $B$ such that $A\neq B$. How many arrangements of these rides form a continuous trip ...
- 51
0
votes
1
answer
101
views
Possible to cover all vertices of a tri-partite graph with triangles?
I'm designing fictional fruits. Each fruit has three attributes; color, taste and smell. Also, each of the values of the attributes have some compatibility with the values of the other attributes. So, ...
- 6,943
4
votes
0
answers
103
views
Reducing column ranges of a matrix
I'm looking for an algorithm to reduce the sum of column ranges in a sparse integer matrix by subtracting $1$ from all nonzero elements in a subset of the rows.
Let $R = 1, \ldots, m$ and $C = 1, \...
- 146
3
votes
4
answers
276
views
Shuffle a poker deck between 4 players, with least required entropy
We are shuffling a standard poker deck of 52 cards between 4 players, each getting 13 cards. The order of cards for a particular player does not matter.
A naive algorithm is to first shuffle the whole ...
- 336
1
vote
1
answer
46
views
A combinatorial formula for different sums $a\cdot( k_1+ k_2+...+k_{n-1})+k_n$
I am looking for a combinatorial rule for the following: let $n \in \mathbb{N}$ and $k_1,k_2,...,k_n \in \mathbb{N}$ (these are known). Since we know what the sum $\sum_{j=1}^{n}k_i$ is, let's say ...
user830143
0
votes
0
answers
43
views
All combinatorial derangements of $1,2,3 \cdots k$ with specified rules [duplicate]
Let's say that we have the points $\{1,2,3,...,k\}$. I am looking for all the ways to create a derangement of these points with the following rule:
we define a derangement as a permutation $\sigma$ ...
user830143
2
votes
0
answers
50
views
Enumerating separating subcollections of a set
Let $S$ be a (finite) set, and let $C \subseteq 2^S$ be a collection of subsets of $S$. We say that a subcollection $C' \subseteq C$ is separating if for any two elements of $S$ there exists a subset ...
- 11.2k
1
vote
1
answer
770
views
Sorting an array using reverse
I ran into an Olympiad question recently, and one challenging question surprised me:
We have an array $A$ with $n$ elements. $\operatorname{Rev}(i, j)$ for $1 \leq i < j \leq n$ reverses subarray $...
6
votes
2
answers
214
views
a semi-hard problem on combinatory
I ran into a nice interview question.
the problem is as follows:
We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of ...
user871754
0
votes
1
answer
83
views
Determining the number of nontrivial families of increasing substrings of $\{1,...,k\}$
Let us say that we have the order $\{1,2,3,4,5,...,k\}$ of $k$ elements. Now, I want to determine in how many different ways can we pick a family of increasing substrings from $\{1,...,k\}$? The rules ...
user830143
1
vote
1
answer
89
views
How to determine the cardinality of this set?
I would like to determine the cardinality of this set (given that $a,b \in \mathbb{N}$ and we do not know which one is larger):
$\Big\{\frac{1}{1},\frac{2}{1},\frac{3}{1},...,\frac{a}{1},\frac{1}{2},\...
user830143
3
votes
0
answers
77
views
counting cycles and paths in simple graphs
I'm newly studying graphs in my school courses and I've been facing this common type of questions about how many cycles/paths are there between some vertices I asked my teacher for a simpler or more ...
- 176
1
vote
1
answer
36
views
Reach N from $0$ in the least number of moves where the n'th move comprises of n steps and each step is a $\pm 1$ movement
Reach the number $\text{N}$ from $0$ in the least number of moves where the $n\text{th}$ move comprises of $n$ many steps and each step is a $\pm 1$ movement. The same problem also exists here without ...
- 595
0
votes
1
answer
84
views
Optimal planning for mail box servicing and processing (for a message queue online consumer scheduling)
Consider I have $n$ mail boxes $\{m_1, m_2, \dots, m_n \}$. Messages come to each box at different rate/sec e.g., mail box $n$ has an arrival rate of messages equal say 5 per second. In general, let ...
- 131
1
vote
1
answer
247
views
parenthesis of expression in such a way value not changed
one example:
How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among ...
- 119
2
votes
0
answers
61
views
Deceptively Easy: Pairwise Coprime Tuple Counting
Suppose I have $M_1,...,M_n$ prime numbers in a specific range $[M_\min,M_\max]$ such that $M_i-1$ is not odd-squarefree ($\exists p^2|M_i-1, p$ odd). Let $n_i=\frac{M_i-1}{2}$. Find all the r-tuples ...
- 1,748
0
votes
1
answer
124
views
enumerating permutations with exactly $k$ inversions
For a few days, I've been unsuccessfully trying to come up with an algorithm that enumerates the permutations of a set (of cardinality $= n$) with exactly $k$ inversions.
Could you help me?
Thanks!
- 441
0
votes
0
answers
57
views
$m$ players choosing from $n$ integers game
$m$ players play a game in which they pick distinctive integers in the range $0:n$ one after another. Then we pick a random integer from $0:n$. Whoever is closest to our pick wins.
What's the optimal ...
1
vote
0
answers
66
views
Explanation Behind Combinatorial Enumeration Algorithm
Can any combinatorists here perhaps enlighten me about the rational behind this technique for enumerating combinations of size $l$ drawn from elements of a set of symbols of size $k$?
Please forgive ...
2
votes
0
answers
163
views
Quickly generating random Latin squares without aid of a computer
I'm looking for an easy/fast way of generating a random (alphabetic) 26x26 Latin square "by hand". So assume your tools are something along the lines of a 30 sided letter die, and/or a bunch ...
- 175
1
vote
2
answers
145
views
Couple problems and classic wolf/goat/cabbage and abstraction
I was reviewing Dijkstra's approach on the problem/puzzle of how 2 married couple can cross a river with 1 boat that can carry 2 people. The original problem's restriction is that the wife can't be in ...
- 1,609