# Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

534 questions
Filter by
Sorted by
Tagged with
14k 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. ...
495 views

### Problem similar to set packing

Call a family of sets $\mathcal{F} = \{S_1, \dotsc, S_k\}$ "diverse" if each set $S_i \in \mathcal{F}$ has at least one unique element. What are possible approaches for finding the largest diverse ...
15k 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)$....
18k 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 ...
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 ...
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 ...
223 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 ...
17k 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 ...
770 views

### What is the number of expressions containing n pairs of matching brackets with nesting limit?

I know the answer without nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing $n$ pairs of matching ...
421 views

### Is there a formal name for this graph operation?

I'm writing a small function to alter a graph in a certain way and was wondering if there is a formal name for the operation. The operation takes two distinct edges, injects a new node between the ...
17k views

### Finding the number of distinct permutations of length N with n different symbols

I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are. For example if the string is of length ten as $w = aabbbaabba$, the total number ...
101 views

### Probabilities of duplicate mail detection by comparing notes among servers

I have the following problem: We want to implement a filtering strategy in e-mail servers to reduce the number of spam messages. Each server will have a buffer, and before sending an e-mail, it ...
404 views

### Generating number of possibilites of popping two stacks to two other stacks

Context: I'm working on this problem: There are two stacks here: A: 1,2,3,4 <- Stack Top B: 5,6,7,8 A and B will pop out to other two stacks: C and D....
174 views

### Numbers of ways of expressing the sum of a number between [a,b]

I need an algorithm to calculate the number of ways of expressing a number N as sum of numbers inside the interval [a, b]
2k 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 ...
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 ...
4k 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 ...
156 views

### Extracting non-duplicate cells in a particular matrix with repeated entries

Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \left\{1,...,\frac{n^2}{2}\right\}$ is written to two cells so that each cell contains exactly one number. How ...
494 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 ...
336 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) ...
148 views

### How many possible ways are there?

Suppose I have the given data set of length 11 of scores: p=[2, 5, 1 ,2 ,4 ,1 ,6, 5, 2, 2, 1] I want to select scores 6, 5, 5, 4, 2, 2 from the data set. How ...
241 views

### What is a formula for the number of strings with no repeats?

I want to count the number of strings $s$ over a finite alphabet $A$, that contain no repeats, and by that I mean for any substring $t$ of $s$, $1< |t| < |s|$, there is no disjoint copy of $t$ ...
13k 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 ...
817 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 ...
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 ...
482 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 ...
417 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 ...
528 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$, ...
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 ...
230 views

### Distinguishing between uppercase and lowercase letters in the “move-to-front” method

Is it not necessary to encode both the uppercase and lowercase letter while encoding a message with the move-to-front transform? From an old computer science course exam, the problem was to encode <...
142 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 ...
930 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 =...
832 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 ...
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 ...