Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms

0
votes
2answers
19 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
25 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
121 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
12 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
80 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
47 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
25 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 ...
3
votes
2answers
47 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
44 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
167 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
29 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
19 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
69 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
22 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
66 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
51 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 ...
0
votes
1answer
95 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 ...
1
vote
1answer
62 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
28 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
28 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
37 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
27 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
76 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
24 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
82 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 ...
0
votes
2answers
218 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
73 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
59 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
24 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$, ...
3
votes
1answer
49 views

Counting words that satisfy SAT-like constraints with BDDs

I have the following #P-complete problem: Given an alphabet $\Sigma$ and a matrix $M$ where each entry can be a symbol from $\Sigma$ or the wildcard symbol $*$, find the number of strings $s$ with ...
3
votes
1answer
66 views

Creating an O(n log n) time and O(n) space algorithm for counting pairs in an array

Given an integer array $a$, create a function, $\text{int} \; \text{pairs}( \text{int} \;a[\;])$ that returns the number of equal element pairs in the array. For example, given the array ...
3
votes
1answer
111 views

Find the longest contiguous subsequence such that its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$

You are given $N$ $(1 \le N \le 10^6)$ positive integers $a_1, a_2, \ldots, a_N (1 \le a_i \le 10^6)$ and two positive integers $D$ $(1 \le D \le 10^6)$ and $M$ $(1 \le M \le 10^6)$ Find the longest ...
2
votes
1answer
20 views

Combinations of elements with mutual relationships

I need to create the combination of 3 elements from a array of given n elements, however every of those 3 el. has to be in "relationship" with each other. Here is an example I can describe my issue ...
5
votes
1answer
65 views

How to show all possible implied parenthesis?

Can I use recursion to find out the possible parenthesis we can add to this expression: 2*3-4*5 ? (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = ...
1
vote
1answer
68 views

Assignment based on ranked preference

Assume that there are n students, who have to be evenly assigned to m groups. For every student, a preference ranking of of the ...
1
vote
1answer
25 views

Number of states in classical planning

With reference to the Heuristics section of Classical planning in Artificial Intelligence: A Modern Approach by Russell and Norvig, there is a question: consider an air cargo problem with 10 ...
-2
votes
1answer
78 views

[Graph Problem algorithm] [closed]

I am new here . Please forgive me if there is anything wrong in that I am going to write . So , my question is about one problem given in last round of codeforces , pretty easy to handle it , but I do ...
4
votes
3answers
146 views

Help wrapping my head around a combinatorial optimization problem

Here's the problem I'm trying to solve: I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight ...
-4
votes
1answer
63 views

Write down at least 20 possible boolean functions of 3 inputs? [duplicate]

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 = 0 110 = 0 111 = 0 110 = 0 101 = 0 011 = 0 and 8 of $f(x_{1},x_{2},x_{3})=1$ 000 = ...
0
votes
5answers
175 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 = ...
1
vote
1answer
38 views

efficient cumulative all over combinations of boolean vector elements

Problem Given a vector of bools of length n I wish to compute the logical and over all subsets up to length k. By logical ...
6
votes
1answer
76 views

Time/Space Optimal k-Subset Operator Application - Is this a named problem?

I have searched extensively and unsuccessfully for references to a combinatorial problem that arises in my work. I am hoping someone can tell me if this type of problem has a "name" and provably ...
2
votes
2answers
38 views

Arden's rule expressed as matrix algebra

The following theorem is (in the context of languages) known as Arden's Lemma: Given a linear system $X = B+AX$ and the matrix A is quasiregular, then we have a solution which is unique and ...
1
vote
1answer
29 views

“Archiving” byte sequence into human-readable set of chars

Ok, lets assume we have sequence of 1000 bytes. So the possible number of value variations is 2^100. Is there a way to "index" each variation with letters and decimal numbers (A-Z, 0-9), having as ...
5
votes
0answers
29 views

Correctness of a zigzag algorithm to find the most similar vector in a bounded integer lattice

I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm. Given a real vector $u ...
2
votes
1answer
78 views

Number of DFAs of only one state

If I have a DFA with only one state that is not an accept state, it accepts only the empty set. I get confused when if the DFA of one state is an accept state. Does this mean it accepts everything? ...