Skip to main content

Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
98 votes
11 answers
29k 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 ...
Raphael's user avatar
  • 72.6k
43 votes
0 answers
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})$? [closed]

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 ...
john_leo's user avatar
  • 1,901
38 votes
4 answers
25k 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)$....
bitmask's user avatar
  • 1,755
35 votes
2 answers
7k 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-...
hsalin's user avatar
  • 733
31 votes
2 answers
14k 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 ...
Stéphane Gimenez's user avatar
29 votes
1 answer
34k 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 ...
The Unfun Cat's user avatar
29 votes
1 answer
1k 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 ...
Yuval Filmus's user avatar
24 votes
2 answers
756 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\...
Uri Granta's user avatar
23 votes
1 answer
10k 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: ...
Pratik Deoghare's user avatar
23 votes
1 answer
2k 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 ...
Nicholas Mancuso's user avatar
21 votes
1 answer
15k 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. ...
gebuh's user avatar
  • 321
21 votes
1 answer
582 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 ...
Alex ten Brink's user avatar
19 votes
4 answers
5k 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 ...
Nicholas Mancuso's user avatar
19 votes
2 answers
471 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 ...
Gilles 'SO- stop being evil''s user avatar
19 votes
1 answer
491 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 ...
flonk's user avatar
  • 291
19 votes
1 answer
2k 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$$ ? ...
R B's user avatar
  • 2,634
17 votes
3 answers
1k 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 ...
Alex ten Brink's user avatar
17 votes
2 answers
28k 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 ...
Saurabh's user avatar
  • 919
17 votes
1 answer
996 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$. ...
john_leo's user avatar
  • 1,901
17 votes
3 answers
18k 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 ...
Mark's user avatar
  • 373
17 votes
3 answers
2k 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 =...
Kevin's user avatar
  • 1,082
16 votes
8 answers
4k 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 ...
qwe2's user avatar
  • 263
15 votes
2 answers
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 ...
user2145167's user avatar
15 votes
1 answer
443 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" ...
Christian Rinderknecht's user avatar
15 votes
1 answer
657 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 ...
Heterotic's user avatar
  • 391
14 votes
2 answers
7k 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 ...
avi's user avatar
  • 1,463
14 votes
2 answers
8k 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 ...
varatis's user avatar
  • 463
13 votes
1 answer
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 ...
user1374864's user avatar
13 votes
1 answer
705 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 ...
Erel Segal-Halevi's user avatar
13 votes
2 answers
840 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{...
hftf's user avatar
  • 181
12 votes
3 answers
3k 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 ...
Peter's user avatar
  • 1,505
12 votes
2 answers
3k 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$ ...
yoniLavi's user avatar
  • 245
12 votes
3 answers
10k 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 ...
Kevin's user avatar
  • 1,082
11 votes
3 answers
1k 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 =...
paparazzo's user avatar
  • 431
11 votes
1 answer
1k 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-...
cberzan's user avatar
  • 213
11 votes
1 answer
2k 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 ...
Null's user avatar
  • 211
10 votes
3 answers
293 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 ...
wookie919's user avatar
  • 343
10 votes
1 answer
3k views

The buckets of water problem

Let's consider the following problem (buckets/pails of water problem) (This problem may be known with different name. If does, please correct me). Let $B=\{b_1,...,b_n\}$ be a set of $n$ buckets. ...
George's user avatar
  • 103
10 votes
1 answer
226 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 ...
phwd's user avatar
  • 621
10 votes
2 answers
385 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) ...
GManNickG's user avatar
  • 269
10 votes
2 answers
4k 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 ...
Timeless's user avatar
  • 795
10 votes
2 answers
272 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 ...
fiftyeight's user avatar
9 votes
1 answer
547 views

Is there a linear-time algorithm for randomly sampling weighted combinations?

For concreteness, here's the specific problem description: suppose we have a set $S$ of $n$ items $a_1, a_2, \ldots, a_n$ with weights $w_1, w_2, \ldots, w_n$ respectively. The goal is to select a ...
Steven Stadnicki's user avatar
9 votes
1 answer
565 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$, ...
Geoff's user avatar
  • 191
9 votes
3 answers
3k views

Counting Deterministic Finite Automata

I have a question regarding counting DFAs: Given a Σ = {0, 1} input string, with the state set Q = {1...n}, how would I find ...
Heplar's user avatar
  • 101
9 votes
1 answer
238 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 ...
Mohammad Al-Turkistany's user avatar
9 votes
2 answers
407 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, ...
haijo's user avatar
  • 91
9 votes
1 answer
278 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.) ...
Helen F. 's user avatar
9 votes
3 answers
3k 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 ...
guskenny83's user avatar
9 votes
0 answers
224 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, ...
coderodde's user avatar

1
2 3 4 5
16