We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
0
votes
0answers
13 views

Possible number of DFAs, NFAs, DPDAs, NPDAs, NDTMs and DTMs for various input parameters

I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, ...
0
votes
0answers
39 views

Which is the most similar NP classic problem, if any exists, to this one?

Consider a given set $W = \{w_1, w_2,...,w_N\}$ of weights, such that $\sum_{i=1}^N w_i = 0$. Consider the given set of mutually different elements $A=\{a_1,a_2,...,a_M\}$ with $M\leq N$. Consider the ...
2
votes
1answer
36 views

Polynomial multiplications and counting

I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically ...
-1
votes
1answer
56 views

How to compute total number of subsequences of length k from a word of length N?

A subsequence of a word is obtained by dropping some letters from it. The letters that are dropped need not be consecutive. For instance, ba, bna and banaa are all subsequences of the word banana. We ...
0
votes
0answers
183 views

Help with an algorithm task

I've been given a task that I had issue solving. Problem statement: John likes jumping so he is about to build a new jumping terrain. The terrain consists of N blocks, and in each block he can ...
2
votes
1answer
23 views

Combinations and Permutations of M sets of distinct items?

I'm wokring on this problem for a while. I want to know: The correct name of this problem, so I can look it up in textbooks\online. Here is the problem descirption: The (un-ordered) combinations to ...
1
vote
0answers
37 views

coloring of an interval graph with constraints

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
0
votes
0answers
56 views

How to solve this dynamic programming puzzle on matrix?

We are given 4 integers N,M ,Q and Z. Initially,the matrix has all zeroes in it. We have to perform Q operations on the matrix. In each operation, any cell of the matrix can be selected(same cell ...
2
votes
1answer
32 views

What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?

In other words, what is the likelihood that a recognizer of a given regular language will accept a random string of length $n$?   If there is only a single non-terminal $A$, then there are only ...
1
vote
1answer
27 views

Average number of full nodes in rooted m-ary tree

I am looking for a formula to express the average number of full nodes (i.e. nodes having exactly $m$ children) in a $m$-ary tree having $n$ nodes, i.e., $$ \mu_{n}^{(m)} = \frac{\# \text{full nodes ...
0
votes
1answer
334 views

Hiring problem from CLRS

Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions. However, for Exercise question 5.2-2 my solution deviates from the one given in the ...
0
votes
1answer
35 views

Generation of all combinations of a set in max-differing/random order

I'm looking for an algorithm that generates all k-combinations of a set, such that each successive combination generated differs as much as possible (or in practice, a lot) from all previous ...
4
votes
0answers
31 views

Karger's min-cut (contraction): Combinatorial argument for success probability?

The contraction algorithm for min-cut is: pick an edge $(u,v)$ uniformly at random, and "contract" it by merging $u$ and $v$ into a single vertex, deleting self-loops. Continue until two vertices ...
2
votes
0answers
70 views

Set of maximum overlaps

Assume I have a list of $N$ surfaces $\{S_i\}, i \in [1,N]$ which may or may not overlap. I also have a boolean function $F(S_{i_1},\dots,S_{i_k})$ (with $1 \le k \le N$) which tests whether all ...
0
votes
2answers
348 views

Prove that the set of recursive languages is infinite

I know that set of all deciders is countable. I am wondering whether it is infinite.In other words can we prove that the set of recursive languages is infinite ? Edit : The above question has small ...
0
votes
2answers
44 views

generating all pairs

suppose I have 6$\{0,1,2,3,4,5\}$ numbers.I should generate following 4 pairings of numbers where there will be 3 pairs in each pairing s.t each number should be in one pair and also every number ...
14
votes
2answers
16k views

Prove that every two longest paths have at least one vertex in common

If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common. I think that that common vertex ...
3
votes
1answer
69 views

Problem in downvote system

Problem For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated ...
1
vote
1answer
106 views

algorithm for number of subsequences containing at most k numbers with no element repeated in each of the subsequence

For e.g if the array is 2,2,3,3,5 and k=3 there are total 18 subequences 1 subequence of length 0(i.e empty subsequence) 5 subsequences of length 1 8 subsequences with length 2 4 subsequences with ...
2
votes
2answers
110 views

Algorithm to count the number of subsets of size k with sum of all its elements minimum possible

An array is given eg:-1 2 2 2 and we need to count the number of subsets for it of size k which has the sum of elements minimum possible here the subsets of size k=3 are:- 122 122 122 222 we see ...
0
votes
1answer
132 views

Matching 2 sets of items by price

I'm trying to solve the following problem in the most efficient way I can find. I want to trade my items for someone elses items, every item have a price and a value. I want to maximize the value of ...
3
votes
2answers
64 views

Which order is “lexicographic order”?

To choose 3 items out of 5 items [1, 2, 3, 4, 5], Donald Knuth's lexicographic algorithm (The Art of Computer Programming, Vol 4A, 2011, p. 358, Algorithm L (...
0
votes
0answers
42 views

Algorithm and Time Complexity for k-Sum problems

In fact, there are three different k-Sum problems: Problem1: Given unsorted integer array $\{a_1, a_2, ..., a_n\}$ and a target number $T$, determine whether there exist at least one solution $\{a_{...
0
votes
0answers
8 views

Count compound words with an ambiguous decomposition

I have a set of words $D$, and I make compound words by concatenating a fixed number $n$ of words from $D$ (repetitions are allowed). Let's call such words $n$-compounds. I want to know how many ...
2
votes
0answers
31 views

8-puzzle problem [duplicate]

8-puzzle problem: The puzzle consists of an area divided into a grid, 3 by 3. On each grid square is a tile, except for one square which remains empty. A tile that is next to the empty grid square can ...
1
vote
1answer
28 views

Recover boolean vector from dot products

Question: I want to determine a boolean vector $b \in \{0,1\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product ...
1
vote
1answer
29 views

Selecting the right partition in NAUTY

Graph isomorphism solver Nauty has two main procedures, individualization and refinement, to get to a discrete partition. During refinement procedure, we take some cell of the current partition and ...
0
votes
0answers
19 views

maximum eigenvalue across subsamples

I have an $N$-dimensional vector of data, say $X_{t}$, with $1 \leq t \leq T$. Of this vector $X_{t}$, I want to consider sub-vectors, say $X_{t}^{b}$, which are $m$-dimensional combinations of ...
39
votes
0answers
1k 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 ...
1
vote
1answer
170 views

combinatoric grouping optimization problem based on time interval overlap, weight constraint, and distance minimization

Let each element be an individual. Consider that an individual is defined such that each individual has a time range, weight, and location. The goal is to group together individuals whose time ranges ...
0
votes
0answers
28 views

count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]

Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths of a given length n from a given start node, so that fjor every path applies: a) no vertex ...
4
votes
2answers
67 views

Count paths of length $n$ that a player can take

I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move ...
2
votes
1answer
59 views

Conditions for a binary tree being balanced

Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced. If you disprove, the counterexample should consist of an infinite ...
5
votes
2answers
140 views

Finding row wise sum of transpose of hv-convex binary matrix

I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m). ...
2
votes
2answers
50 views

Number of possible heaps on $\{1,…,2^h-1\}$

Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it. Definition A binary tree ...
1
vote
0answers
71 views

Tree Optimization, Combinatorics, algorithm [closed]

My Partners and me, we are trying to optimize frequency process... I used Java to show our Problem, but the question is about algorithm NOT about Java implementation. Although implementations in java ...
2
votes
0answers
26 views

Linear order minimizing weighted distance from special element

Let's say I have a set of beads, $b_0,\dots,b_n$, and let $b_0$ be the 'special bead'. I want to lay out the beads on a string to minimize the total cost, defined as $\sum_{i=1}^n w_i \cdot d(b_0, b_i)...
1
vote
0answers
68 views

Approporiate algorithm for a graph theory problem

So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm. The problem is pretty ...
1
vote
2answers
59 views

Maximal cliques in a multipartite graph - efficient?

I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class. Now I am looking for the optimal subset such that each of the N classes is represented ...
2
votes
1answer
121 views

Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria

Given a collection of sets $S_i$ of disjoint subsets $sub_i$ of a set $X$, find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in ...
0
votes
0answers
47 views

Minimum Ratio Spanning Tree

Problem statement: Given an undirected graph $G = (V, E)$ with edge $e_i$ having two associated positive values $c_1, c_2$. Find a spanning tree $ST$ such that (ratio of the spanning tree): $$\frac{...
5
votes
0answers
51 views

Number of strings at given edit distance

I would like to know the number of strings at edit distance $n$ of a string $s$. I guess this is textbook knowledge... but I cannot find the textbook in question. More formally, I have an alphabet $\...
2
votes
1answer
60 views

how many boolean functions exist that satisfy the condition

How many boolean functions exist that satisfy the following condition? $$\neg f(x_1,x_2,x_3,....,x_n) = f(\neg x_1, \neg x_2,...,\neg x_n)$$
0
votes
1answer
56 views

How many possible ways to go right and up in an array

Let's say we have a 2D matrix, and we begin at $(0, 0)$. We must travel $m$ steps to the right and $n$ steps up, in any order. Each step moves the position right or up by $1$. For example if $n = 5$...
1
vote
1answer
109 views

How to calculate combination from given n,r and rank?

Suppose that $S=\{1,2,...,n\}$ and we are given an integer $r\leq n$. An $r$-combination of $S$ is obtained by selecting $r$ distinct integers out of the $n$. We order all $r$-combinations for a ...
2
votes
1answer
51 views

Bound covariance of two discrete random variables

Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$. I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is ...
6
votes
0answers
111 views

Algorithms to generate random nowhere-neat rectangulation?

I want to generate random rectangular partition of a given $m*n$ rectangle under the constraint that it must be nowhere-neat partition. Nowhere-neat partition means that a dissection of a rectangle ...
0
votes
1answer
60 views

Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint

I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
1
vote
1answer
12 views

Software metric for data growth

I'm writing a paper for some software that uses combinatorics to generate large result sets. I would like to describe that if I put in $n$ elements, I will get in return $2^n$ elements. Is there a ...
2
votes
1answer
125 views

Permutation of n-size array with possible repeated elements. E.g [1, 2, 1]

What would it be a recursive algorithm to get permutations for any list of n elements that might contain or not repeated elements? For the following 3-element list ...