# Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

127 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2k views

### Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
198 views

136 views

### Inexact cover, or cover with gaps

Dancing Links: wikipedia article, research paper is an implementation of algorithm X for exact cover problem. In the Knuth's research papaer, linked above it is shown how Polymino problem (that is ...
54 views

51 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 ...
102 views

### Number of binary trees of size $n$ such that all subtrees of same size are equal?

In the following, I consider rooted, unlabelled, ordered binary trees, where each node has exactly $0$ or $2$ children (I will simply call them binary trees). A binary tree $t'$ is a subtree of a ...
147 views

### Generating all directed multigraphs

I am trying to find an algorithm that generates all directed multigraphs with a given number of vertices and arcs up to isomorphism (no two generated graphs should be isomorphic). I also want to allow ...
62 views

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
1k views

### Dynamic Knapsack Problem - Algorithms and References

I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...
50 views

### Make Change in Linear Time

The question is motivated by this post on StackOverflow. Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a ...
114 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 ...
98 views

38 views

457 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 ...
77 views

### An unknown combinatorial optimization problem

I have $N$ available sensors and $M$ devices. Each device needs $a$ sensors. One sensor cannot be used on multiple devices. Each sensor has two properties defined by $H$ and $R$. Let $\sigma_{i\_H}$ ...
38 views

92 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). ...
10 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 ...
221 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 ...
78 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 ...
37 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 ...
98 views

93 views

### Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?

The Schensted insertion algorithm has an $O(n^2)$ running time, for constructing such a standard Young's Tableaux. But, since every permutation has a unique Young's tableau, there seems no reason as ...
32 views

### Is there a skippable, countable generator for unique permutations up to some symmetry?

Is there a good algorithm for generating all and only the unique permutations of a finite set respecting some kind of symmetry? For example, in Klondike solitaire, the two black suits are ...
43 views

### Computing the index in a structured way

I want to map the various combinations to an unique index: For a given $n$ and $r$, we would have $\binom{n}{r}$ arrangement for values:$[0,\dots,n)$: Ex: For n = 6, r = 3 [012, 013, 014, 015, ..., ...
83 views

### Activity scheduling with activities that can move around

In this problem. I have a set of "activities" which can happen. Each "activity" is associated with several values: Duration: The length of time the activity takes Earliest time to start: The earilest ...
52 views

### Smarter recursion to compute #tilings of $m \times n$ board with small shapes that fit in $2 \times 2$ square?

This is a generalization of another question I posted because I wasn't clear that I cared about more than $2 \times 1$ dominoes (it's just a special case), and there is an explicit tractable formula ...
226 views

### How to formalise efficient payment with a collection of coins in a wallet?

Context If you have to pay an amount of money at a store and have a limited collection of payment items (i.e. coins and banknotes) -- let's for simplicity assume there are only coins -- a trivial ...
52 views

### Counting permutations whose elements are not exactly their index ± 1

This is a special case of the question: Counting permutations whose elements are not exactly their index ± M The $M=0$ case has already been solved, but no one was sure how to work out the non-...
Given $N$ vertices and $K$ components what is the maximum number of edges that may exists ? I just got gut instinct that it will be maximum if we take one set with $k-1$ vertices and this will have no ...
### Is the problem "find the sequence of $N$ numbers between 1 and $D$ with least cost", NP-hard?
Consider sequences $p=(p_1,\dots,p_N)$ (the order matters) of length $N$, where $p_i\in\{1,\dots,D\}$ for fixed $D$. Moreover, consider a cost function $c:\{1,\dots,D\}^N\to\mathbb{R}$ which comply \$c(...