Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
4
votes
2answers
80 views

Min path cover for a three-layer graph with all paths traversing all layers

Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. ...
0
votes
0answers
27 views

Algorithm for specific load balancing/arbitration problem

I'm trying to design an algorithm for some specific arbitration requirements and I have a feeling I'm on well-trodden ground, but lack the maths background to properly analyse it. If someone could ...
1
vote
1answer
19 views

Upper bound on size of minimal binary coverage code

Let $1 \le r \le n$ b e integer(with $n$ large) and let $\mathscr X_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $\mathscr X_n$ such that ...
0
votes
1answer
26 views

Bottleneck TSP with repeated nodes

I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also ...
1
vote
2answers
37 views

Floating-point oblivious way to compute multiset numbers

I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be: $$ R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{...
4
votes
2answers
257 views

Given a row sum vector and a column sum vector, determine if they can form a boolean matrix

For example, for a boolean matrix of size $3x4$, the column sum vector $C = (3, 3, 0, 0)$ and the row sum vector $R = (2, 2, 2)$ form a match because I can construct the boolean matrix: $$ \begin{...
3
votes
0answers
70 views

Speeding up the Rummikub algorithm - explanation required

Regarding this question: Rummikub algorithm. I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four ...
1
vote
1answer
11 views

Populating a vector of numbers to expose an error in a function implementation

So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect ...
0
votes
1answer
53 views

Balanced sub-sequence

Consider two strings $S$ and $T$ of length $n$. Here both the strings $S$ and $T$ consists of only ( and ) that is made of ...
3
votes
1answer
52 views

Topological sort where some nodes can't come in between two other nodes

I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come "in between" node ...
2
votes
0answers
42 views

What is the largest sum that can be constructed with the given recipes?

There are $n$ sets of distinct positive integers, $S_1,\ldots,S_n$. There is a set of recipes that allows us to construct tuples of integers from these sets. For example, the recipe {1,2} allows us to ...
2
votes
0answers
22 views

How to linearly combine loss functions to preserve optimal substructure property?

I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
3
votes
1answer
45 views

Combinatorial Problem similar in nature to a special version of max weighted matching problem

I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem. I have a ...
0
votes
1answer
32 views

Approximate bin-packing?

Let $X_1,...X_n$ denote some bins, and $w_1,...w_m$ some positive real numbers, where $m \in \mathbb{N}$, and the order matters, so e.g. we can't switch the position of $w_n$ and $w_1$. The goal is to ...
2
votes
1answer
15 views

Maximum Chromatic number of Cayley Graphs with large degree

It is known that there does not exist a regular graph of order $n$ with clique size greater than $\lceil\frac{n}{2}\rceil$. My question pertains to Cayley graphs with large degree, say $\ge \frac{n}{2}...
0
votes
0answers
36 views

finding the combinatorial solutions of series and parallel nodes

I have n nodes, and I want to find the (non duplicate) number of possible ways in which these nodes can be combined in series and parallel, and also enumerate all the solutions. For example, for n=3, ...
0
votes
1answer
46 views

Combinations of set unions

I have a set $S = \{0,1,2,3,4,5,6,7,8,9\}$. $S_i \subset S$ for $i = {1,2,3,4,5}$. Any three $S_i$ has the same union, that is $S_1 \cup S_2\cup S_3 = S_1\cup S_2\cup S_4 = ...=S_3\cup S_4\cup S_5 = A$...
1
vote
0answers
53 views

Number of words of length n for special language

Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties: if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $...
2
votes
1answer
60 views

Counting circuits with constraints

Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one). In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
2
votes
1answer
82 views

Maximization problem on finite collection of finite sets

Problem I am considering the following maximization problem: Input is a finite collection of finite sets $\mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$. Goal is to find a subset $G \subseteq \mathcal{F}$...
0
votes
0answers
22 views

Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling

I'm trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are ...
0
votes
0answers
18 views

Is the number of sub-boolean algebras of a set with size of n equal to Bell(n)?

In boolean algebra (P(S),+,.,’) we must have S as 1 and {} as 0 in every possible sub-boolean algebra to hold id elements. We must have S-x for every subset x⊆S to hold complements. It seems like ...
-1
votes
1answer
79 views

Number of sequences of given type

Consider that there is sequence $a$ of length $n$ ,$a=[a_i,0\le i\le n]$. Now you are given with $\text{lcm}$ of some pairs of number from list that is, $\operatorname{lcm}(a_i,a_j)=k$ for $0\le i,j\...
0
votes
1answer
33 views

“Knapsack problem” with repetition, “lesser or equal” constraint, and recording all valid combinations

In a game I am developing I came across an interesting problem, that seems like it could be solved using some modified variant of the knapsack problem, but it's a bit over my head. Let $x_i$, $ 1\leq ...
1
vote
0answers
21 views

Space complexity of using a pairwise independent hash family

I'm trying to analyze the space complexity of using the coloring function $f$ which appears in "Colorful Triangle Counting and a MapReduce Implementation", Pagh and Tsourakakis, 2011, https:...
2
votes
1answer
39 views

Streaming algorithm for counting triangles in a graph

As described in the reference, the algorithm (see at the bottom) supposes to output an estimator $\hat T$ for the # of triangles in a given graph $G = (V, E)$, denoted $T$. It is written that "it ...
0
votes
0answers
17 views

How to consider combinatorial optimization problem with multiple objectives?

I am considering a combinatorial optimization problem with two objectives. The two objectives have a trade-off between each other which means if I minimized the first objective alone it gives the ...
1
vote
1answer
70 views

Lexicographic permutation

Consider that you have a permutation of $n$ elements from $1$ to $n$ and you need to sort the elements lexicographical . for example sorted permutation for $n=11$ is $1,10,11,2,3,4,5,6,7,8,9$ .Now ...
4
votes
1answer
54 views

Algoritm to sample an even subgraph of a graph

In some problems related to the Ising model in physics and mathematics the following problem comes up: Suppose I have a graph $G$. Then an even spanning subgraph of $G$ is a subgraph where you keep ...
0
votes
0answers
20 views

About number of NFSTs

Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.
1
vote
3answers
54 views

Proving a solution for the $n$-Queens Puzzle

Given an $n$ x $n$ board, assume that $n \geq 5$ and that $n$ is not divisible by $2$ or $3$. Prove that the following positioning of $n$ queens $Q_0, Q_2, ..., Q_{n-1}$ works, i.e no two queens ...
1
vote
0answers
98 views

Best algorithm for Renyi–Ulam Game with lies [closed]

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type). Game : $A$ chooses an element in $\{1,2,\dots,n\}$. $B$ tries ...
2
votes
2answers
59 views

Is there a dynamic programming solution to the student allocation problem?

The student project allocation problem I am trying to solve goes as follows. There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$. Each student makes a top $3$ of their ...
1
vote
1answer
25 views

Where is the theory about “binary toggling games”?

Let us -- using parameters $M, N$ and $L$ -- create an ordered set of size $M$ of $N$-bit long vectors $V$ and initialize them randomly: $V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in \{0\ ..\ N-1\}...
-1
votes
2answers
64 views

I am unable to understand the logic behind the code (I've added exact queries as comments in the code)

Our local ninja Naruto is learning to make shadow-clones of himself and is facing a dilemma. He only has a limited amount of energy (e) to spare that he must entirely distribute among all of his ...
2
votes
1answer
19 views

Enumerating every “partnering” without repeating partners

I'm taking a class. In this class every week we have a partner. There are an even number of people in the class. We'd like avoid having repeat partners if possible so that everyone gets to work with ...
0
votes
1answer
77 views

Asymptotic complexity of Combination sum problem vs Coin change problem

I've been looking at the following combination sum problem: ...
0
votes
0answers
12 views

How to get started with multi-level pairwise combinations

Let's say we have 4 ranks: 1-4 Every rank has a set of unique nodes, each pair of same-rank nodes can be combined to create a node of a rank 1 level higher, in any number of combinations: ...
2
votes
1answer
149 views

Organizing a “speedback”

Speedback is the merging of speed-dating with feedback: a 2 min. 1-on-1 talk with all members of a group of people. I'm in a team and I want to plan the ideal speedback setup: all team members have ...
0
votes
0answers
44 views

Counting a walk $i \rightarrow k \rightarrow l \rightarrow i \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph

This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \...
0
votes
0answers
21 views

Powells Method for 2 Variables?

I've been studying this YouTube video on Powells method and it looks like when we have a single variable we start at the upper and lower bounds of the variable and then we keep dividing the search ...
3
votes
2answers
297 views

Algorithm to generate combinations of n elements from n sets of m elements

Suppose I have 3 sets of 2 elements: [A, B], [C, D], [E, F], and I wanted to generate all possible combinations of 1 element from each set, such that the result of ...
0
votes
0answers
32 views

Fractional knapsack with setup costs

I am considering a variant of the classical fractional knapsack problem, it's written in the following integer programming form Here $v_i, c_i, w_i, b$ are all positive. $c_i$ can be interpreted as ...
0
votes
1answer
33 views

Counting directed graphs

I am trying to find a computable, injective and bijective function $f: \mathbb{N} \to A$ where $A$ is the set of all (finite) directed graphs up to isomorphism (also with no edge repetitions). Which ...
2
votes
1answer
61 views

How to solve the bin packing problem with conflicts?

I'm trying to devise an algorithm to solve the bin packing problem with conflicts (sometimes referred to as BPPC, or BPC). The problem is defined as follows: consider a set $V$ of $n$ items, where ...
2
votes
1answer
79 views

Algorithm to partition students in two groups maintaining brotherhood (related to COVID19 pandemic)

I need to find an algorithm for the following problem. Any idea to which kind of algorithm to look for as starting point is welcomed. Should I look for a graph algorithm? Combinatorial problem? ...
1
vote
0answers
184 views

Example of *small* non monotone circuit such that any equivalent monotone circuit has greater size?

A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies: fan-in=2 for the AND and OR nodes fan-n=1 for the NOT ...
2
votes
1answer
72 views

Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?

A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies: fan-in=2 for the AND and OR nodes fan-n=1 for the NOT ...
1
vote
0answers
44 views

Minimun k-union from a different angle

I'm looking for work done on solving some problem which is very similar to the minimum k-union. The problem: There's a set of elements $E=\{e_1,e_2,...,e_k\}$ of size $k$, and a family of sets $S_1,...
0
votes
1answer
41 views

Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria

You have to find out the number of good strings of length N characters in size which you can make using characters A B and C. A string is a good String if it satisfies the following three criteria: ...

1
2 3 4 5
12