Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms

2
votes
1answer
66 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( ...
-3
votes
0answers
25 views

Number of ways to construct a Regular graph

For a regular graph (each vertex has same degree k), a part of graph upto level l is given, how to compute the total number of ways in which the graph can be completed given that m edges and n ...
0
votes
0answers
16 views

Finding edge disjoint spanning trees in certain graphs

I'm studying the problem of finding edge-disjoint spanning trees in a given graph. I would like to compare the performance of matroid partitioning algorithm that can be used to solve this problem and ...
1
vote
0answers
29 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
18 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
284 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
40 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
27 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
122 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
13 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
92 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
50 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 ...
3
votes
2answers
49 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
168 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
31 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
20 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
78 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
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
53 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
2answers
110 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
76 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
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
38 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
31 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
85 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
228 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
78 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
60 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
67 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
81 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
26 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
147 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 = ...