Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms

3
votes
1answer
27 views

Minimum number of transpositions

Let's have two permutations $A$ and $B$ of $n$ numbers. What is the minimal number $m$ of transpositions to transform $A$ to B in the worst case? After analysing some algorithms my guess is that $m \...
2
votes
1answer
26 views

Big Theta for finding combinations of arbitrarily sized subsets from n total elements

Given n elements, where the n elements are grouped into arbitrarily sized subsets, what is the Big Theta (tight bounds) of outputting all permutations of items from each subset? Assume the elements ...
7
votes
2answers
589 views

Finding a fixed-size set whose members are contained by the largest number of other sets

I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to ...
4
votes
1answer
29 views

How to find greatest set intersection of at least a given cardinality?

While dealing with a problem, I uncovered this subproblem: Input: A set of sets $S = \{S_1,...,S_r\}$ where $\mid$ $S_1$ $\cup$ ... $\cup$ $S_r$$\mid = n$, as well as a number $k<n$. Output: A ...
1
vote
1answer
50 views

Faster way of calculating how many ways can $2n$ elements be paired?

So the problem is in how many ways $2n$ elements can be paired, my approach was multiply all odd numbers less then $2n$. $(2n-1)*(2n-3)*...*1$ but my professor claimed it can be done much faster in ...
1
vote
1answer
29 views

Probability distribution of runs given k bits set in an n-bit circular buffer

Imagine you have a circular buffer holding n bits. You (uniformly) randomly set k of those n ...
-1
votes
0answers
25 views

Number of ways to join n distinct trees

I have been trying to solve a problem in which i need to join N distinct trees with disjoint set of nodes. After searching a lot I came across this formula but i am not able to understand it. Please ...
0
votes
2answers
58 views

Describe an algorithm for painting cards in the following game

It's my first question out here, so please don't judge me too strictly. I heard of the following game: there's set of cards with different set of objects (but the same number of them on every card) ...
7
votes
1answer
191 views

Binary rooted tree isomorphism

My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below: How many isomorphism classes of trees with n vertices are ...
4
votes
2answers
138 views

How do I do sum of first k elements of a row of a Pascal's Triangle efficiently?

More specifically, I want to: $^nC_0 + ^nC_1 + ^nC_2 + ..... + ^nC_k$ I tried doing it linearly by calculating $^nC_{j+1}$ by multiplying $^nC_{j}$ with (n-j+1)/j. The answer it gives is correct ...
1
vote
1answer
30 views

What is the cardinality of the set of regular grammars?

What is the cardinality of the set of regular grammars? The caveat is that I'm only interested in grammars which are 'structurally' different. Sorry I don't know how to talk about this in a formal ...
4
votes
1answer
85 views

How much data could I store on a Rubik's Cube?

Google tells me that a standard 3x3x3 Rubik's Cube has 43,252,003,274,489,856,000 permutations. If I wanted to store data on that Rubik's Cube, how much could I store? The only way I see to store ...
3
votes
1answer
127 views

is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation

I am searching for an algorithm for this! Cannot find anything useful in textbook so far. Thanks in advance! Question: The input is a $N \times K$ matrix, where $N$ and $K$ are positive numbers( ...
1
vote
0answers
30 views

Counting the number of non-overlapping squares and cubes in a string

Given a string S of length n that contains exactly $\lceil\frac{n}{3}\rceil$ b's and $\lceil\frac{2n}{3}\rceil$ a's: Suppose the charge is 2 for each non-overlapping occurrence of aaa, and 1 for each ...
1
vote
1answer
22 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 ...
1
vote
2answers
296 views

How Is a Computer Able to Store and Quickly Manipulate All the Data Required For A Computer Display?

I did some quick math on how much data is contained on a screen at any given instant and I ended up with a number well beyond what I thought was possible. 256 colors for Red, Green, and Blue each ...
1
vote
1answer
45 views

Letter Combinations of a Phone Number

I came across this problem in the “Elements of Programming Interviews” interview preparation book, and also on the site, leetcode.com (link to problem). Problem statement – Letter Combinations of a ...
0
votes
2answers
20 views

Find k compatible objects with minimum total penalty

Assume we have a set of $n$ objects $X=\{x_1,x_2,\ldots,x_n\}$, where each object $x_i$ has a penalty $p_i$. Additionally, we have a set of incompatibility constraints $C=\{(x_i,x_j),\ldots\}$, where ...
0
votes
0answers
33 views

Get all possible combinations of distributing x*n balls into n boxes

I'm trying to figure out how to get all combinations of putting x*n balls into n boxes. ...
6
votes
0answers
128 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, ...
1
vote
0answers
16 views

How to encode each possible b-tree of a sequence of n numbers?

Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of ...
3
votes
1answer
114 views

How many number of different binary trees are possible for a given postorder (or preorder) traversal

I came across the problem: What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C? Now 3 being small number I was quick to draw all possible ...
1
vote
1answer
53 views

Upper bound for #Monotone k-SAT

(I've recently started studying satisfiability problems. I've tried to be as clear as possible, but I'm not sure if all of the terminology used is correct.) Consider a collection of $n$ Boolean ...
1
vote
1answer
27 views

Exhaustive list of ways to distribute n objects to k sets

I am working on a research paper and we are developing a brute force algorithm to examine another clustering technique. In this brute force algorithm we test every possible clustering example and see ...
4
votes
3answers
71 views

Showing that the number of primitive-recursion programs for each function is countably-infinite

Problem Statement Prove that if a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$ Yes, this is a homework question. My ...
3
votes
1answer
48 views

3SUM problem solution on the basis of cubic function and a line?

The 3SUM problem formulation: in a given set of n real numbers find 3 elements that sum to specified value S. I am trying to understand mathematical solution of the 3SUM problem based on a polynomial ...
6
votes
0answers
172 views

Filling bins with balls

There are $n$ bins. 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 ...
1
vote
1answer
34 views

Relation between Hamming distances of columns and rows

You're given a $0-1$ $n\times n$ matrix such that for every distinct columns $C_i$ and $C_j$, $d_H(C_i,C_j)\gt 2t$ for some $t$. What could be said about the Hamming distances of the rows? It it true ...
1
vote
1answer
32 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 ...
0
votes
0answers
23 views

Extending the Knapsack Problem - Value of complementary items

I'm looking for literature related to the following combinatorial optimization problem, which can be generalized to other applications too. I'm wondering what people's thoughts are on how to approach ...
-2
votes
1answer
91 views

Count number of automata with 3 states and alphabet of size 2

How many different finite automata are there that have 3 states $q_0$, $q_1$ and $q_3$, have an alphabet of size 2, and where $q_0$ is starting state?
3
votes
1answer
22 views

Find which bundles can be demanded together

This question comes from economics. There is a market $M$ that contains $m$ items. There is a value function $v:2^M\to \mathbb{R}$, that assigns a monetary value to each "bundle" (- subset of $M$). ...
-2
votes
1answer
23 views

Given Q constraints find the number of binary arrays of N elements

You have to find the number of arrays having N binary elements (0/1), that satisfy the Q given constraints. The constraints are of the form Li Ri Bi. Where if Bi is 0, then it means that the sum of ...
3
votes
1answer
71 views

What's the fastest known algorithm for generating $k$-subsets of an $n$-set?

We are given a set of $n$ elements and we'd like to generate all $k$-subsets of this set. For example, if $S=\{1,2,3\}$ and $k=2$, then the answer would be $\{1,2\}, \{1,3\}, \{2,3\}$ (order not ...
0
votes
1answer
57 views

Count all pairs of x,y such as x + y = c && x XOR y = d

Given two decimals $c$ and $d$; $1 \le c,d \le 10^{12}$. Count all pairs of $x$ and $y$ that satisfy the following statements: $$ x+y = c\\ x \text{ XOR } y = d $$ Killed already a day still can'...
0
votes
2answers
121 views

Countability of a binary tree

Problem: We'll define a binary tree as a tree where the degree of every internal node is exactly 3. Show that the set of all binary trees is countable. My attempt: A set is countable if it is ...
2
votes
2answers
81 views

How many $(x, y)$-paths of length $20$ are there, where $x$, $y$ adjacent vertices in cycle $C_5$?

As the title of the question suggests, let $x$ and $y$ be two adjacent vertices in the cycle $C_5$. How many $(x, y)$-paths of length $20$ are there?
3
votes
0answers
29 views

Computing the index in a structured way

I want to map the various combinations to an unique index: For a given $n$ and $r$, we would have $\binom{n}{r}$ arrangement for values:$[0,\dots,n)$: Ex: For n = 6, r = 3 [012, 013, 014, 015, ..., ...
0
votes
1answer
29 views

CLRS: Asked to prove a result and then told to give a counter example [closed]

I am reading Introduction to Algorithms, and I am stuck at this execercise in the Appendix: Argue for any integers $n \ge 0$, $j \ge 0$, $k \ge 0$ and $j + k \le n$. $${n \choose j + k} ...
1
vote
1answer
23 views

Finding a closed form for a discrete sum using generating functions

Consider this sum: for context sake, the summand appears in the counting of the possible ways to have one cigarette box empty and the other having left N cigarettes when both boxes start with N ...
2
votes
2answers
43 views

Shortest path in divisors graph

There is a graph with N vertices numbered from 1 to N. Edge between a and b exists if and only if a|b or b|a. If a|b then the weight of the edge is b/a. If b|a then the weight of the edge is a/b. ...
0
votes
0answers
36 views

Poly-variadic Y combinator

I have written a lambda calculus interpreter, and it seems to work. I cant find the combinator for something I want though. I want to be able to define an arbitrary number of mutually recursive ...
6
votes
0answers
80 views

Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
1
vote
0answers
27 views

Best combination of elements with defined constraints

My goal is to find the best combination, or good approximation, of weighted elements with different constraints / relations, for example: B can only be there after A B have to be there after A B ...
0
votes
4answers
93 views

Is it feasible to generate every possible RGB image?

This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent ...
0
votes
1answer
26 views

Help coming up with a solution to a combinatorial problem

So here is the problem: Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions. I know this ...
1
vote
2answers
236 views

Number of finite strings over a countably infinite alphabet

If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?
4
votes
1answer
89 views

Counting the number of permutations of string with given repeated interwoven subsequence

Given string $S$ of length $n$, count the number of distinct permutations $P_n$ of a string of length $2n$ such that each of them contains $S$ twice as an interwoven subsequence. Example. $S=abc$. ...
4
votes
1answer
64 views

Number of words within Hamming distance $\delta$

This is a problem I'm having reading Arora & Barak's book, page 378-379. They define: For two words $x, y \in \{0, 1\}^m$, the fractional Hamming distance of $x$ and $y$ is equal to the ...
0
votes
0answers
25 views

Approximate algorithm to find the minimum score

Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle. Query: let $v \in P$, ...