Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Combinatorics deals with discrete mathematical structures. The structures can be either finite or countable.

For problems about algorithms and complexity of computations on discrete structures, consider using the and tags.

784 questions
99
votes
11 answers

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 mainly in the sequence's asymptotic growth .…
Raphael
  • 73,461
  • 31
  • 185
  • 415
44
votes
0 answers

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 regular tree grammar (Chapter 2). Both formalisms hold…
john_leo
  • 1,921
  • 14
  • 26
38
votes
4 answers

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)$. Or to put it differently: $\mathcal{o}(n \log(n)…
bitmask
  • 1,783
  • 2
  • 16
  • 20
35
votes
2 answers

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-computable than computable, in fact the majority…
hsalin
  • 733
  • 7
  • 7
31
votes
2 answers

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 assertion that the number of rooted binary trees of…
Stéphane Gimenez
  • 1,490
  • 1
  • 14
  • 29
30
votes
1 answer

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 coins for the sum 6 and 6 coins for the sum 19. My…
The Unfun Cat
  • 1,833
  • 2
  • 20
  • 29
29
votes
1 answer

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 for large enough $n$, $$ c_n(L) = \sum_{i=1}^k…
Yuval Filmus
  • 281,565
  • 27
  • 323
  • 519
24
votes
2 answers

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\}) = \left\{0, 1, 5, 6\right\}$ while…
Uri Granta
  • 343
  • 1
  • 6
23
votes
1 answer

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 : 4 / \ 3 2 / 1 or 4 2 3 1 : 4 / \ 2 3 / 1
Pratik Deoghare
  • 1,751
  • 2
  • 14
  • 23
23
votes
1 answer

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 algorithms to find optimal solutions. The…
Nicholas Mancuso
  • 3,937
  • 1
  • 26
  • 40
21
votes
1 answer

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 some string $\gamma$. Now, my question is whether…
Alex ten Brink
  • 9,226
  • 3
  • 37
  • 63
21
votes
1 answer

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. Here's what I have so far: From the online ordering…
gebuh
  • 321
  • 1
  • 3
  • 8
19
votes
2 answers

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 circular one!) is a unipathic graph; if the list has…
Gilles 'SO- stop being evil'
  • 44,219
  • 8
  • 122
  • 187
19
votes
1 answer

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$$ ? For example, given the input $m=8436285$, one may…
R B
  • 2,654
  • 18
  • 37
19
votes
4 answers

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 cover set in a graph might just inspect all…
Nicholas Mancuso
  • 3,937
  • 1
  • 26
  • 40
1
2 3
…
52 53