Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
96 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.3k
3 votes
1 answer
2k views

Is it possible to easily reduce 0/1 subset sum to subset sum with multiplicities?

So both the 0/1 subset sum problem (find a subset of given numbers that add up to a target sum) and the subset sum problem with "multiplicities" (find non-negative integer coefficients for the set ...
user2566092's user avatar
  • 1,721
38 votes
4 answers
24k 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
31 votes
2 answers
13k 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
3 votes
1 answer
403 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
johnson's user avatar
  • 151
21 votes
1 answer
577 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
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
7 votes
2 answers
4k views

Example of graph with exponential many s-t minpaths and min cuts

I am trying to find a graph in which both s-t minpaths and min cuts are exponential. Individually I found examples in which s-t minpaths and s-t min cuts are exponential. Can some one provide me an ...
Kumar's user avatar
  • 367
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
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
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
4 votes
3 answers
2k views

Number of ways to fill a 2xN grid with M colors

This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two ...
Kyuubi's user avatar
  • 273
2 votes
1 answer
512 views

Number of substrings possible with even characters

Consider a string 'ABBAA' Possible substrings with even number of characters are $4$ 'ABBA' : Count of 'A' is even and 'B' is even 'AA' : Count of 'A' is even and 'B' is even - ($0$) Similarly 'BB' ...
nihar's user avatar
  • 57
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
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
15 votes
1 answer
652 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
9 votes
1 answer
270 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
4 votes
2 answers
97 views

Count paths of length $n$ that a player can take

I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move ...
kyle_williams's user avatar
4 votes
1 answer
742 views

Issues with using greedy algorithm (Interval scheduling variant)

I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have ...
user8153's user avatar
4 votes
1 answer
4k views

Rummikub algorithm

I have just played a few games of Rummikub and the manipulations I made during my turns became more and more complex transactions. A few turns reordered the whole field, so that other players did not ...
Martin Ueding's user avatar
2 votes
1 answer
1k views

Counting elements that are greater than the median of medians

Short version: I want to know where the $-2$ comes from in the formula on p. 221 of CLRS 3rd edition. Long version: CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of ...
Carl G's user avatar
  • 123
2 votes
1 answer
1k views

Convert integer of mixed radix to standard positional numeral system and vice versa

I have multiple numbers (e.g. [1, 4, 2]) where each number can be one of a specified range of numbers (e.g. [0-1, 0-5, 0-3]). I ...
mxscho's user avatar
  • 133
2 votes
1 answer
384 views

Approaches to the size constrained weighted set cover problem

I am trying to solve a weighted set cover problem where the number of selected subsets is limited by a constant $k$. Assuming this is a pretty straight-forward variation of weighted set cover I ended ...
martin's user avatar
  • 121
1 vote
1 answer
74 views

Order in a subset

Lets consider a range of "K" binary digit numbers. In that range, we want to take a subset of those values which have (<="n" consecutive 0s) AND (<="n" consecutive ...
Dave's user avatar
  • 23
0 votes
1 answer
122 views

How many segmentations are possible for a string length N?

I have a string with length N. I would like to know how many segmentations are possible to it. Consider the example abcdc the number of N = 5 All possible ...
Karun's user avatar
  • 3
0 votes
5 answers
1k views

Why are there $2^{2^{n}}$ possible boolean functions of n inputs?

Why are there $2^{2^{n}}$ possible boolean functions of n inputs? How to derive that? For 3, I can only write down 16 and cannot go further. 8 of $f(x_{1},x_{2},x_{3})=0$ 000 = 0 001 = 0 010 = ...
Ka Wa Yip's user avatar
  • 261
29 votes
1 answer
33k 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
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
19 votes
2 answers
470 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
13 votes
1 answer
702 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
12 votes
3 answers
9k 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
12 votes
2 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
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
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
  • 785
9 votes
1 answer
235 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
8 votes
4 answers
8k 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 ...
Patrick87's user avatar
  • 12.8k
7 votes
1 answer
2k views

Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph

Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes. I tried to look it up at a few places (including ...
Subhayan's user avatar
  • 1,696
6 votes
1 answer
4k views

What is the maximum number of shortest paths between any pair of vertices in a chordal graph?

A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a ...
Juho's user avatar
  • 22.5k
6 votes
1 answer
2k views

Which algorithm can calculate an optimal allocation of students to projects?

I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects ...
ingr8's user avatar
  • 63
6 votes
2 answers
337 views

Is the number of inequivalent elementary cellular automata rules really 88?

Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia ...
Vilius Normantas's user avatar
4 votes
2 answers
5k views

Efficiently enumerate all subsets of an ordered set

What's the most efficient way to enumerate all (ordered) subsets of an ordered set? So, for example, given the ordered set $\{2, 5, 6\}$ (using the normal ordering for integers), I need the following: ...
mistercake's user avatar
4 votes
2 answers
552 views

Counting trees (order matters)

As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In ...
user1419's user avatar
  • 153
4 votes
2 answers
191 views

Min path cover for a three-layer graph with all paths traversing all layers

Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. ...
Rohit Pandey's user avatar
4 votes
2 answers
3k views

How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?

Given a complete binary tree with $n$ nodes. I'm trying to prove that a complete binary tree has exactly $\lceil n/2 \rceil$ leaves. I think I can do this by induction. For $h(t)=0$, the tree is ...
Luc Peetersen's user avatar
3 votes
1 answer
562 views

Faster algorithm for a specific inversion

There is a permutation (more precisely a derangement) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$. I want to compute the following counts (a kind of inversion): $$K(\sigma )_{i}=\#\{j&...
Nikos M.'s user avatar
  • 957
3 votes
1 answer
101 views

Polynomial Computation of the probability of a number of independent events

Suppose to have $n$ independent events $E_1, E_2,..., E_n$, where the probability of occurrence of event $E_i$ is $p_i$ (i.e., each event has its own probability of occurrence). We can easily define ...
Corrado's user avatar
  • 33
3 votes
1 answer
624 views

Counting Colorings of a Grid

Given a $n \times m$ grid, define a valid coloring as mapping from the grid cells to a set of $k$ available colors such that no two adjacent cells have the same color. Cells are considered as adjacent ...
neutron-byte's user avatar
2 votes
0 answers
112 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). ...
Hang Wu's user avatar
  • 121
2 votes
2 answers
969 views

Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?

I want to learn computer science, SO is discrete math enough for computer science ? Or there other Math topics that I should also learn With it ? I don’t have specific topic that I care more about ...
Thuraya Otto's user avatar
2 votes
1 answer
355 views

Minimum number of vertices to remove to bound the largest connected component of a graph

I have this problem, maybe anybody could help. Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G \...
MindaugasK's user avatar