# Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

178 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
224 views

215 views

### Upper bound on the number of hamiltonian cycles on a $n \times n$ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n$ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
• 161
78 views

### Rank and unrank for Heap's Algorithm

I am looking for an unranking (and ranking) algorithm for permtuations that is consistent with the order that Heap's Algorithm generates permutations. I have been researching a bit on ranking and ...
60 views

• 395
73 views

### Karger's min-cut (contraction): Combinatorial argument for success probability?

The contraction algorithm for min-cut is: pick an edge $(u,v)$ uniformly at random, and "contract" it by merging $u$ and $v$ into a single vertex, deleting self-loops. Continue until two vertices ...
• 4,129
129 views

• 222
42 views

• 103
492 views

### computing permanent of a 0-1 rectangular matrix

I need to compute the permanent of a 10*100 matrix. All the entries are either 0 or 1. All I know is that I can compute the permanent of all 10*10 submatrices and then sum it to get the desired ...
67 views

### Expected Entropy of the Empirical Distribution

Given a distribution on $n$ outcomes where outcome $i$ has probability $p_i$, the Shannon entropy of the distribution is defined as $- \sum_{i = 1}^n p_i \cdot \log_2 p_i$. Let's suppose I sample from ...
• 121
41 views

### Bananagrams decision problem - computational complexity

I've been playing Bananagrams recently, and have begun to wonder about the math behind it from a computational perspective. I've tried to formalize the problem as a decision problem below. Loosely ...
45 views

### Designing Shortest Route

Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
• 63
73 views

71 views

### Is this a variant of "Path Covering"?

According to 1, "a path cover of a directed graph G is a set of disjoint paths in G which together contain all the vertices of G". In my research, I met a similar problem. There, you can add ...
• 259
27 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 ...
• 21
259 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 ...
• 201
264 views

• 215
113 views

### Balls in Bins with Pairwise Distance

Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
• 121
14 views

### Maximal number of rounds we can do distributing 64 diners on 8 groups in different ways if they can't meet each other more than once?

N=64 hungry diners come to a buffet. We sit them at 8 different (s=8 people at each table) tables so that they get to know each other while they eat. After a while we distribute them over the tables ...
• 121
324 views

### Maximum number of non-overlapping rectangles where each contains a minimum number of points

Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap. Each point is distinct from every other ...
80 views

### Grouping elements optimally other than NP-hard approach

Given a number $N$, I need to make a new array $B$ of size $n$ (index-1 based) such that the product of $B[i]-(i-1)$ for $1 \le i \le n$ is equal to $N$ and $B[n]$ is minimum and $B[i] \ge B[i-1]$ and ...
• 21
41 views

### Constrained selection of a random sample from a set of items with multiple attributes

Suppose I have a collection of N items, each of which has A different attributes, a1, a2, ..., aA. Attribute ai can take on Vi different possible (discrete) values, distributed across the population ...
109 views

### Efficient algorithm for "group-sum-min" problem

Given two finite sets $A, B \subseteq \mathbb{C} \times \mathbb{R}$, each stored as an array, define $$S = \{ (z_1 + z_2, x + y, z_1, z_2, x, y) : (z_1, x) \in A, (z_2, y) \in B \}$$ and  f(s) = \...
• 121