Questions related to combinatorics and discrete mathematical structures
3
votes
1answer
31 views
Unranking paths in a graph/lattice
A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified ...
-3
votes
1answer
57 views
Detecting combinations [on hold]
In my program I am getting Input of N numbers, and then different combinations of those numbers, in different order. I need to detect when I am getting the same combination of numbers twice(order is ...
13
votes
0answers
230 views
Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?
We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
3
votes
1answer
39 views
What's the correct definition of the $\Upsilon$ category of schedules?
I'm reading this article about game semantics and I'm a bit puzzled with the definition given for $\Upsilon$ in section $3.3$. There are some points that are either unintelligible or that don't make ...
7
votes
1answer
113 views
Estimating the time until we obtain five-in-a-row?
Consider the following random process. We have a $10\times 10$ grid. At each time step, we pick a random empty grid cell (selected uniformly at random from among all empty cells) and place a marker ...
2
votes
1answer
28 views
Counting involving equivalence classes and languages
Let $\Sigma$ be the alphabet $\{a, b, c, d\}$ and let $R$ be the following relation on $\Sigma^*$: $R(x, y)$ is true if every letter in string $x$ also occurs in $y$, and every letter in string $y$ ...
4
votes
1answer
77 views
Simple graph canonization algorithm
I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if ...
3
votes
2answers
65 views
Probability that a uniformly random sequence is already sorted
Now I tried tackling this question from different perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I have no good ...
3
votes
2answers
50 views
Solution for a combinatorial minimization problem
Let's say we have an inequality, $p \le {a \choose b}$ where $p$ is a fixed constant and $a, b$ are variables. The problem is that, we are trying to find the minimum $a$ with respect to the inequality ...
0
votes
1answer
52 views
Count the number of integers satisfying two conditions using DP
Given two integers $n$ and $m$, how many numbers exist such that all integers have all digits from $0$ to $n-1$, the difference between two adjacent digits is exactly $1$, and the number of digits in ...
5
votes
1answer
132 views
Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph
Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes.
I tried to look it up at a few places (including ...
0
votes
1answer
60 views
Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?
I am new to this and an amateur... please help.
My Question in practical terms:
Given The three following inputs... determine the number of unique group arrangements as an ordered set.
INPUT:
'a' = ...
8
votes
3answers
139 views
When testing n items, how to cover all t-subsets by as few s-subsets as possible?
This problem arose from software testing. The problem is a bit difficult to explain. I will first give an example, then try to generalize the problem.
There are 10 items to be tested, say A to J, and ...
2
votes
1answer
86 views
No of ways in which n indistinguishable items can be placed in m indistinguishable boxes [closed]
This problem is the same as
number of ways to partition n into exactly m parts.
The recurrence given in Wikipedia has
p(n,k) = the number of partitions of n using only natural numbers ≥ k
How ...
1
vote
1answer
91 views
Number of Combinations of Connected Bipartite Graphs
Given two sets of vertices $U$ (size $n$) and $V$ (size $m$), how many possibilities of set of edges $E$ exist that make the bipartite graph $G = (U, V, E)$ connected?
Obviously there are $2^{n m}$ ...
1
vote
1answer
139 views
Recurrence formula for a known sequence?
Problem: How do we can generate some mathematical close form of the following sequence, which has following 256 entries:
1 7 7 7 7 9 9 9 7 9 9 9 7 9 9 9 7 11 11 11 ...
1
vote
3answers
64 views
How can I produce a summation function from this set of production rules for a grammar?
I am not entirely sure if the title is the correct way to phrase what is occurring. There is a recurring process which I decided to attempt to model using production rules similar to those used in a ...
2
votes
2answers
493 views
Time complexity of a backtrack algorithm
I've developed the following backtrack algorithm, and I'm trying to find out it time complexity.
A set of $K$ integers defines a set of modular distances between all pairs of them. In this
algorithm, ...
-1
votes
1answer
201 views
Dynamic Programming To calculate the combinations [closed]
This is a problem from a past contest at topcoder : Problem.
Its solution is given here : Solution [Scroll Down to Penguin Emperor]
I am unable to understand how the section with subheading ...
2
votes
1answer
38 views
Combination with a minimum number of elements in a fixed length subset
I have been searching for long but unable to find a solution for this. My question is "Suppose you have n street lights(cannot be moved) and if you get any m from them then it should have atleast k ...
2
votes
1answer
95 views
Minimum number of vertices to remove to bound the largest connected component of a graph
I have this problem, maybe anybody could help.
Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G ...
2
votes
1answer
319 views
Count number of special onto functions
We define an onto function from $[n] \times [n]$ to $[n-2] \cup \{0\}$ as follows, where $[n] = \{1,2,3,\ldots ,n\}$,
$$f : [n] \times [n] \rightarrow [n-2] \cup \{0\}.$$
1) $f(x,x) = 0$.
2) ...
4
votes
1answer
55 views
serial number of combination
How can I find the serial number of an n-choose-k combination?
I would like a function that gets as input:
$n$,
$k$,
a set of $k$ elements out of the set ${0, 1, ... n-1}$.
The output should be ...
4
votes
1answer
149 views
Finding a winning strategy for toads and frogs
Recently I got interested in a game called Toads and Frogs and I'm trying my best to come up with some software which would be able to beat an average (i.e. not knowing the strategy) human though I'm ...
6
votes
5answers
170 views
Team construction in tri-partite graph
The government wants to create a team with one alchemist, one builder, and one computer-scientist.
In order to have good cooperation, it is important that the 3 team-members like each other.
...
-1
votes
1answer
112 views
Why is the size of the search space 2057 in the 8-queen puzzle?
In the 8-queen puzzle, to reduce the search space, we can use an incremental approach. We put the first queen in the first column, then the 2nd queen in the 2nd column etc., avoiding the slots that ...
-4
votes
1answer
113 views
Proving that the largest number of leaves in an $n$-ary tree of height $k$ is $k^n$
How to prove that the largest number of leaves in an $n$-tree of height $k$ is $k^n$?
4
votes
1answer
160 views
Issues with using greedy algorithm (Interval scheduling variant)
I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.
I have ...
3
votes
1answer
35 views
Chazelle's discrepancy book: greedy method
In Bernard Chazelle's book The Discrepancy Method, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem ...
10
votes
1answer
319 views
Towers of Hanoi but with arbitrary initial and final configuration
Recently, I came across this problem, a variation of towers of hanoi.
Problem statement:
Consider the folowing variation of the well know problem Towers of
Hanoi:
We are given $n$ towers ...
9
votes
1answer
114 views
How to practically construct regular expander graphs?
I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices.
What is the easiest method to do this in practice?
Constructing a random d-regular graph, which is ...
20
votes
0answers
284 views
Asymptotics of the number of words in a regular language of given length
For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
5
votes
1answer
127 views
What is a compact way to represent a partition of a set?
There exist efficient data
structures for representing set
partitions. These data structures have good time complexities for operations
like Union and Find, but they are not particularly ...
2
votes
1answer
231 views
Maximum number of augmenting paths in a network flow
Let's say we a have flow network with $m$ edges and integer capacities.
Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.
A good way to start thinking ...
3
votes
1answer
107 views
Number of possible search paths when searching in BST
I have the following question, but don't have answer for this. I would appreciate if my method is correct :
Q. When searching for the key value 60 in a binary search tree, nodes containing the key ...
2
votes
1answer
70 views
How to enumerate combinations in parallel
I have $n\times k$ matrix with $k<n$ and I would like to find all its $n\choose k$ submatrices which are $k\times k$ matrices that are the concatenations of all possible $k$ rows. Actually I tried ...
1
vote
1answer
128 views
How to enumerate all combinations of $n$ binary variables s.t. their sum is $k$?
Suppose we are given $n$ variables $X_i, i=1,\dots,n$, each taking values from $\{0,1\}$, and a constant integer $k$ with $ 0\leq k \leq n$.
What are some efficient ways to enumerate all possible ...
3
votes
1answer
86 views
Counting solutions to system of linear equations modulo prime
I have implemented Gaussian elimination for solving system of linear equations in the field of modulo prime remainders. If there is a pivot equal to zero I assume the system has no solution but how to ...
2
votes
1answer
224 views
Height of a full binary tree
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:
I ...
4
votes
1answer
126 views
What is the maximum number of shortest paths between any pair of vertices in a chordal graph?
A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a ...
4
votes
2answers
105 views
How many Turing Machines are there that run in time $t$ or in space $s$ on inputs of length $k$?
I think half the battle in answering this question lies in formulating it precisely! A search engine doesn't turn up much, so I was wondering if this is a well-known or well-studied question.
My ...
10
votes
1answer
102 views
Number of Hamiltonian cycles on a Sierpiński graph
I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other ...
2
votes
1answer
94 views
Tiling of squares
Motivation: This question is motivated by my previous question . In that question, my statment of the uniqueness requirement is not interesting since it leads to easily computable function. I am ...
7
votes
2answers
396 views
Why are there more non-computable functions than computable ones?
I'm currently reading a book in algorithms and complexity. At the moment I'm, reading about computable and non-computable functions, and my book states that there are many more functions that are ...
7
votes
1answer
146 views
Unique tilings of squares
We want to tile $m\times m$-square using two types of tiles: $1 \times 1$-square tile and $2 \times 2$-square tile such that every underlying square is covered without overlapping. Let us define a ...
3
votes
0answers
131 views
Dynamic Knapsack Problem - Algorithms and References
I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...
1
vote
2answers
112 views
How optimal is Lempel-Ziv at reaching the Shannon limit?
I find this a bit difficult to describe, but I am interested in the following idea :
The LZ algorithm factors (verb) an input stream into adjacent factors, these are by definition the maximal ...
1
vote
1answer
27 views
On the generalization of two recreational problems: request for references, if there's any
I wonder if two famous (and, IMHO, very nice) recreational problems are been studied in some general form.
Here's the first.
We have 13 balls, all looking absolutely the same, with 12 of them having ...
5
votes
1answer
82 views
Application of Expander Codes
I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon ...
7
votes
2answers
268 views
Simplify complexity of n multichoose k
Edit: In my case, $k$ may be greater than $n$ and they grow independently.
I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was ...
