Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms

4
votes
3answers
76 views

How to enumerate a product set?

I am coding a procedure that takes an integer $d$, and generates $d$ finite lists $X_1 \ldots, X_d$ of elements. I would then like for it to output a list of the elements in the product set $X_1 ...
-1
votes
2answers
47 views

number of edges in a graph

I got a problem related to graph theory - Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is {(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, ...
1
vote
1answer
21 views

How many size $s$ circuits from $\{0, 1\}^n \to \{0, 1\}$ are there? [on hold]

For simplicity, we can assume that only NAND gates are allowed. An asymptotically correct solution is all I really need. Thanks!
5
votes
0answers
35 views

Union of 2 expander graphs [closed]

Suppose that $G$ and $H$ are both expander graphs on the same node set with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$. What can be said about the expansion of graph $G \cup H$? In ...
4
votes
1answer
106 views

What is average number of cycles in an undirected ordered graph of size n?

What is average number of cycles in an undirected ordered graph of size $n$? I've tried finding out sum of number of cycles in all sorts of a graph of size n but I couldn't find that out.
1
vote
2answers
85 views

What are efficient ways to compute the derivatives of iterated functions?

The derivatives of iterated functions at a fixed point $z_0$ are useful in constructing a Taylors series of iterated analytic functions - in other words, the Taylors series of a dynamical system ...
1
vote
0answers
22 views

Assigning packages to different points by minimizing distance: is this a known problem?

Imagine we have N houses, on a standard euclidean 2D plane. We also have N "packages", each of which contains several "objects" of different types, let's call them A, B, C, etc. We know the content of ...
2
votes
1answer
43 views

How to make this recursive relationship nonrecursive? [closed]

I need to make a recursive relationship for a function f(m, n) nonrecursive to make it more efficient and succinct in my code. I stumbled across an important ...
0
votes
1answer
41 views

How to reformulate my problem as a mixed-integer quadratic problem

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the ...
3
votes
2answers
154 views

Suboptimal Solution for a combinatorial problem

I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2} $. This matrix $X$ is ...
0
votes
1answer
35 views

the height of a tree given n nodes and a condition [closed]

I came across a question on which I got totally stuck :( a sort of homework question) A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at ...
1
vote
0answers
31 views

Binary search tree with $n$ internal vertices [closed]

How can we prove a binary search tree with $n$ internal vertices has height $h = \lceil \log(n+1) \rceil$?
2
votes
1answer
28 views

Total ordering of sets of fixed size

I'm curious if there is a name for this way of ordering finite sets of natural numbers (shown here for the case 3 elements, but can be extended to any number of them): ...
1
vote
1answer
166 views

Count numbers that can be generated by flipping bits according to position intervals

We have $M$ bits. $M\le10^5$ Also we have N ranges in the form $[L,R]$. $N\le10^5$ We can choose any range from the given ranges and flip all bits in our number from $L$ to $R$, both inclusive. We can ...
1
vote
2answers
79 views

Calculate number of ways to color matrix using inclusion-exclusion principle

This was asked in a recent contest. The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same ...
0
votes
4answers
300 views

How can one byte hold 256 possibilities?

Forgive this seemingly "troll-ish" question, but I must lack the ability to understand how one byte (two nibbles, eight bits, however you wish to describe it) can hold 256 different states, ...
2
votes
1answer
87 views

Counting elements that are greater than the median of medians

Short version: I want to know where the $-2$ comes from in the formula on p. 221 of CLRS 3rd edition. Long version: CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of ...
5
votes
2answers
281 views

What is combinatorial explosion?

In the theory of NP-completeness, researchers refer to the concept of combinatorial explosion. Some researchers use it as justification for intractability or NP-completeness. Others use it to refer ...
2
votes
0answers
26 views

Adversarial bin packing

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
3
votes
3answers
266 views

Number of ways to fill a 2xN grid with M colors

This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two ...
2
votes
1answer
37 views

Number of Matchings in a Bipartite

Given two sets A and B of sizes |A| = n and |B| = m, where m >= n. There are edges from set A to set B. I need to find the number of matchings where all of vertices ...
7
votes
1answer
114 views

Constructing inequivalent binary matrices

I am trying to construct all inequivalent $8\times 8$ matrices (or $n\times n$ if you wish) with elements 0 or 1. The operation that gives equivalent matrices is the simultaneous exchange of the i and ...
1
vote
2answers
56 views

Computing a histogram with the number of extant values not known in advance

(This may be more fitting for CSTheory, I'm not sure.) I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for ...
0
votes
2answers
69 views

help regarding combinatorics [closed]

I want to know if there is any good book or material that fully explains and fully covers all combinatorics.I even did not find even Kenneth H.Rousan for this.So can anyone tell me any Discrete ...
2
votes
1answer
52 views

Is there a proof of the recursive algorithm for generating all permutations of a sequence?

For clarity, I attach below a concise implementation of the algorithm in Python. I understand that it checks all possible element swaps, but I don't see how that necessarily means that all possible ...
2
votes
1answer
81 views

Task Dependency/Combinatorics

here is a competitive programming question: You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For ...
4
votes
2answers
114 views

Bipartite Graph Game

So say we have a bipartite graph G=(X,Y,E). Let's make a game out of it. I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it's ...
3
votes
1answer
53 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 ...
15
votes
0answers
314 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
45 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
129 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
38 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
164 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
109 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
62 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
76 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 ...
6
votes
1answer
245 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
73 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' = ...
9
votes
3answers
189 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
97 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
128 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
151 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
86 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
1k 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
439 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
45 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
126 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
343 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
62 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
216 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 ...