Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
509
questions
90
votes
11answers
17k views
Solving or approximating recurrence relations for sequences of numbers
In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
39
votes
0answers
1k 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 ...
29
votes
4answers
14k views
Generalised 3SUM (k-SUM) problem?
The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$.
It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$....
29
votes
2answers
5k views
Why are there more non-computable functions than computable ones?
I'm currently reading a book in algorithms and complexity. At the moment I'm, reading about computable and non-computable functions, and my book states that there are many more functions that are non-...
28
votes
2answers
10k views
Counting binary trees
(I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.)
Looking at Wikipedia page for Binary Trees, I've noticed this ...
28
votes
1answer
885 views
Asymptotics of the number of words in a regular language of given length
For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
24
votes
1answer
27k views
When can a greedy algorithm solve the coin change problem?
Given a set of coins with different denominations $c1, ... , cn$ and a value v you want to find the least number of coins needed to represent the value v.
E.g. for the coinset 1,5,10,20 this gives 2 ...
24
votes
2answers
692 views
Efficient algorithm for 'unsumming' a set of sums
Given a multiset of natural numbers X, consider the set of all possible sums:
$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$
For example, $\textrm{sums}(\left\{1,5\right\...
23
votes
1answer
1k views
How fundamental are matroids and greedoids in algorithm design?
Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy ...
20
votes
1answer
13k views
Pizza commercial claim of 34 million combinations
A pizza commercial claims that you can combine their ingredients to 34 million different combinations. I didn't believe it, so I dusted off my rusty combinatorics skills and tried to figure it out. ...
20
votes
1answer
459 views
Does every large enough string have repeats?
Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for ...
19
votes
1answer
7k views
How many different max-heaps exist for a list of n integers?
How many different max-heaps exist for a list of $n$ integers?
Example: list [1, 2, 3, 4]
The max-heap can be either 4 3 2 1:
...
19
votes
2answers
366 views
How many edges can a unipathic graph have?
A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex.
Unipathic graphs can have cycles. For example, a doubly linked list (not a ...
asked Mar 23 '12 at 0:57
Gilles 'SO- stop being evil'
35k7 gold badges100 silver badges166 bronze badges
19
votes
1answer
1k views
Complexity of finding binomial coefficient which equals to a number
Assume you are getting a number $m$ (using $O(\log m)$ bits in binary encoding).
How fast can you find (or determine such does not exist) $$n,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m$$
?
...
18
votes
4answers
3k views
Recurrences and Generating Functions in Algorithms
Combinatorics plays an important role in computer science. We frequently utilize combinatorial methods in both analysis as well as design in algorithms. For example one method for finding a $k$-vertex ...
18
votes
1answer
348 views
Number of Hamiltonian cycles on a Sierpiński graph
I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other ...
17
votes
3answers
773 views
Number of words in the regular language $(00)^*$
According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of ...
16
votes
1answer
877 views
Efficient encoding of sudoku puzzles
Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A naïve encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 =...
15
votes
8answers
2k views
Cardinality of the set of algorithms
Someone in a discussion brought up that (he reckons) there can be at least continuum number of strategies to approach a specific problem. The specific problem was trading strategies (not algorithms ...
15
votes
3answers
12k views
dynamic programming exercise on cutting strings
I have been working on the following problem from this book.
A certain string-processing language offers a primitive operation which splits a string into two
pieces. Since this operation involves ...
15
votes
1answer
384 views
On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
15
votes
1answer
508 views
Constructing inequivalent binary matrices
I am trying to construct all inequivalent $8\times 8$ matrices (or $n\times n$ if you wish) with elements 0 or 1. The operation that gives equivalent matrices is the simultaneous exchange of the i and ...
14
votes
2answers
16k views
Prove that every two longest paths have at least one vertex in common
If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common.
I think that that common vertex ...
14
votes
1answer
587 views
The number of different regular languages
Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state non-deterministic finite automaton?
As an example, let us consider $n=3$. ...
14
votes
2answers
2k views
How to practically construct regular expander graphs?
I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices.
What is the easiest method to do this in practice?
Constructing a random d-regular graph, which is ...
14
votes
2answers
5k views
Proving a binary tree has at most $\lceil n/2 \rceil$ leaves
I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction?
For people who were following in the ...
13
votes
2answers
674 views
Efficient algorithm to generate two diffuse, deranged permutations of a multiset at random
Background
$\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{...
12
votes
1answer
378 views
Filling bins with pairs of balls
A bin is called full if it contains at least $k$ balls. Our goal is to make as many bins as possible full.
In the simplest scenario, we are given $n$ balls and may arrange them arbitrarily. In that ...
11
votes
3answers
997 views
Represent a 5 card poker hand
A deck of cards is 52. A hand is 5 cards from the 52 (cannot have a duplicate).
What is the least amount of bits to represent a 5 card hand and how?
A hand is NOT order dependent (KQ = QK). 64329 =...
11
votes
2answers
4k views
Number of possible search paths when searching in BST
I have the following question, but don't have answer for this. I would appreciate if my method is correct :
Q. When searching for the key value 60 in a binary search tree, nodes containing the key ...
11
votes
1answer
2k views
Number of clique in random graphs
There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of ...
11
votes
2answers
2k views
Simplify complexity of n multichoose k
I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was wondering whether I could get a more simplified big-O expression. In my case, $k$ ...
11
votes
1answer
1k views
Towers of Hanoi but with arbitrary initial and final configuration
Recently, I came across this problem, a variation of towers of hanoi.
Problem statement:
Consider the folowing variation of the well know problem Towers of
Hanoi:
We are given $n$ towers ...
10
votes
3answers
254 views
When testing n items, how to cover all t-subsets by as few s-subsets as possible?
This problem arose from software testing. The problem is a bit difficult to explain. I will first give an example, then try to generalize the problem.
There are 10 items to be tested, say A to J, and ...
10
votes
1answer
126 views
Stability for couples in the Stable Matching Problem
In the Stable Matching Problem, it is stated that there can exist cases where the $m$ list of men can be content with their decisions, yet the list of $f$ cannot when the algorithm is run with men's ...
10
votes
2answers
326 views
How do I classify my emulator input optimization problem, and with which algorithm should I approach it?
Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) ...
10
votes
1answer
718 views
What is a compact way to represent a partition of a set?
There exist efficient data
structures for representing set
partitions. These data structures have good time complexities for operations
like Union and Find, but they are not particularly space-...
10
votes
2answers
3k views
What is the average height of a binary tree?
Is there any formal definition about the average height of a binary tree?
I have a tutorial question about finding the average height of a binary tree using the following two methods:
The natural ...
10
votes
2answers
196 views
Is this combinatorial optimisation problem similar to any known problem?
The problem is as follows:
We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
9
votes
1answer
524 views
Expressing an arbitrary permutation as a sequence of (insert, move, delete) operations
Suppose I have two strings. Call them $A$ and $B$. Neither string has any repeated characters.
How can I find the shortest sequence of insert, move, and delete operation that turns $A$ into $B$, ...
9
votes
1answer
185 views
Unique tilings of squares
We want to tile $m\times m$-square using two types of tiles: $1 \times 1$-square tile and $2 \times 2$-square tile such that every underlying square is covered without overlapping. Let us define a ...
9
votes
2answers
177 views
Find an optimal ordering
I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated!
Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example,
...
9
votes
1answer
161 views
Heaviest planar subgraph
Consider the following problem.
Given: A complete graph with real non-negative weights on the edges.
Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.)
...
9
votes
2answers
536 views
Minimum number of clues to fully specify any sudoku?
We know from this paper that there does not exist a puzzle that can be solved starting with 16 or fewer clues, but it implies that there does exist a puzzle that can be solved from 17 clues. Can all ...
9
votes
0answers
183 views
How to solve the loan graph problem
The problem
A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
8
votes
3answers
165 views
Upper bound of of fib(n+2)
I have a homework problem that is perplexing me because the math is beyond what I have done, although we were told that it was unnecessary to solve this mathematically. Just provide a close upper ...
8
votes
2answers
7k views
Algorithm to find optimal currency denominations
Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The ...
8
votes
2answers
2k views
Real world applications for Steiner Tree Problem?
Are there real-world applications of the Steiner Tree Problem (STP)?
I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ...
8
votes
2answers
1k views
Simple graph canonization algorithm
I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if ...
8
votes
1answer
70 views
Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?
As an example, here are all possible trees for the case $k=3$:
On each node written is its arity (= the number of children).
While this should be solvable by dynamic programming, I think there was a ...
