Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms

1
vote
1answer
20 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
31 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
21 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 ...
5
votes
0answers
60 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
20 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
75 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
186 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
49 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
56 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
23 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
47 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
63 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
102 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
18 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
63 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) = ...
0
votes
1answer
40 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
24 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
74 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
139 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 ...
-5
votes
1answer
54 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
171 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
31 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
73 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
29 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
26 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 ...
4
votes
0answers
25 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
66 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? ...
5
votes
1answer
35 views

Distribution of the number of bits changed during generation of all binary tuples

Knuth's TAOCP chapter 7.2.1 discusses generating all the $n$-bit binary strings. I am interested in the total number of bits that change during this process. During generation we store an $n$-bit ...
4
votes
1answer
97 views

How many words are in this sets?

I have problems to determine the size of the following sets in dependancy of the parameters $m, n>0$: $$M_{m,n}=\{a^iwa^{m-i}\mid 0\le i \le m,\;w\in\{a,b\}^n\}$$ It is easy to see that ...
1
vote
0answers
38 views

Find subsets with one common item [closed]

Given a set with $n$ items, find $x$ subsets, each one of them of size $y$, such that every two subsets share exactly one item. I've tried to solve it with a reduction to a graph, but I got lost... ...
20
votes
2answers
594 views

Efficient algorithm for 'unsumming' a set of sums

Given a multiset of natural numbers X, consider the set of all possible sums: $$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$ For example, ...
3
votes
0answers
45 views

Hardness of approximation for Disjoint Group Steiner Tree

Does anyone know any constant factor approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group? The (intuitive) ...
1
vote
0answers
39 views

Multidimensional 0-1 knapsack as the solution to 0-1 goal programming problem

I am trying to find the algorithm for the 0-1 goal programming problem. Actually I don't have any recent references for explicit algorithms, all the recent articles are about the modelling and not ...
2
votes
1answer
52 views

What is the graph with $8$ vertices and $12$ edges that has the most spanning trees? [closed]

I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?
2
votes
1answer
55 views

Hardness of problem related to number of subsets that satisfy a particular property

I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example: ...
0
votes
1answer
47 views

Graph theory, $n$ people sitting around table [closed]

$n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice. How big can $k$ be in terms of $n$? Does everybody get to sit next to everybody ...
1
vote
1answer
31 views

Combinatorial optimization - is there a formal name for this problem?

I am looking for a formal name and an algorithmic approach to the following problem. Given is a set of services each coming with a price: {s1, 300} {s2, 400} {s3, 800} Additionally there is a ...
2
votes
1answer
50 views

Find the subset of k element between n that maximize the total distance

Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm. ...
1
vote
1answer
71 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
0
votes
0answers
22 views

Time varying handshaking problem with memory: optimal matching

I have to analyse the following problem. I have a set of users $M = [m_0,m_i,\ldots,m_n]$. Between each pair of users I there is a certain Temporal Affinity $F$ defined as $F(m_i,m_j,t_k)$ that is: ...
4
votes
2answers
166 views

Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

A test is consisted of $N$ multiple choice questions, each has $k$ possible answers. A test solution is the sequence of answers $S\in[k]^N$. Given is a black box which receives a solution as input ...
0
votes
1answer
69 views

Random uniform sampling of position restricted permutations

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...
-2
votes
2answers
214 views

Undirected graph G that has 12 vertices, 66 edges and 3 connected components?

Why would it be impossible to draw an undirected graph G that has 12 vertices, with 3 connected components if G had 66 edges?
1
vote
1answer
122 views

Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
3
votes
0answers
109 views

permutations sampling by probability matrix

I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = ...
0
votes
1answer
38 views

Is the number of nodes in an ORBDD 2n + 2?

Wikipedia says that the number of nodes in a ORBDD (Order Reduced Binary Decision Diagrams) of order $x_1 < x_2 < \dots < x_{2n}$ is $2n + 2$. But I can't find proof. Anyone?
5
votes
0answers
55 views

Upper bound on the number of hamiltonian cycles on a $n \times n $ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
6
votes
1answer
93 views

Algorithm to compose identity from a set of permutations

Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity ...
1
vote
0answers
48 views

Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon [closed]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...