Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
529
questions
2
votes
2answers
335 views
Count number of pairs of elements whose product is a perfect square
Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a ...
0
votes
1answer
23 views
What is a good method for modelling combinatorial tree (sport competition results)?
Probably newbie question here, please point me out to relevant theories/tutorials if needed :
let say I want to evaluate the probabilities of the final rankings for a sport competition
the ...
0
votes
0answers
27 views
Sliding Puzzle w/ multiple solutions
I am trying to write an algorithm which produces a solution to a modified n by n sliding puzzle (assuming that an end state is reachable from the given start state). The change is as follows: tiles ...
1
vote
0answers
21 views
Find an algorithm to fully consume items with criteria and produce minimal result
So here are the prerequisites:
There are items to be consumed. Consider an item is just an object with a bunch of properties (e.g. size, weight), and there are tens or hundreds of properties.
Items ...
1
vote
1answer
80 views
Selection over combinatorics that satisfies a distribution
I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not.
Here is the problem :
Consider a list of M ...
1
vote
0answers
22 views
Counting number of binary trees with given node values and root
I came across following problem:
Find number of binary trees possible with 2 as roots. Nodes={1,2,3,4,5}
There was no solution given. I knew number of binary trees for given preorder is given by ...
0
votes
1answer
37 views
Counting strings with balanced substrings
Consider a string of characters $a, b, c$ only. Such a string is called good if the number of $a$'s + number of $b$'s is equal to the number of $c$'s.
Given an integer $n$, find the number of strings ...
4
votes
0answers
33 views
Largest sumset without multiplicity
Given a group $G$, the sumset of two sets $A,B$ is denoted as $A+B = \{a+b:a\in A,b\in B\}$. We say $A$ injects $B$, if $A+B$ has no multiplicities, i.e. $|A+B| = |A||B|$. We let $I(B) = \max \{|A|:A \...
0
votes
0answers
15 views
Maximizing a sequence of items under order and pairwise restriction
Suppose I have a number of items $\{A ... Z$} which are ordered accordingly. Each item has an associated weight, for example $W_A$. Between all items, there's a criterion $c$ which determines whether ...
1
vote
0answers
18 views
How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?
The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion:
$$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{...
1
vote
0answers
34 views
Is there an algorithm to generate all permutations of a multiset through swaps?
I am currently working on a project where I have to perform a computation over all possible permutations of a multiset $S$. In my setting, each multiset is a list of small positive integers such as $S ...
1
vote
1answer
146 views
Choose the kth choice of choosing n things out of m
Say I have a list, L, of m things.
I want to pick n things out of the total of m things in the list.
Suppose there are W ways of doing this. I want to choose the kth way where k is in the range 1..W....
1
vote
0answers
22 views
Number of ways to pass edges of a cycle exactly n times [closed]
Consider an undirected network consisting of a single cycle with 6 nodes according to the below image with a given starting node.
Is there a way to get an expression for the number of paths one may ...
0
votes
0answers
29 views
Schedule a Seminar in Minimum Time
There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
2
votes
1answer
45 views
(Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?
The following question is taken from Leetcode entitled 'Combination Sum'
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique ...
4
votes
2answers
110 views
Is it feasible to solve this subset cover problem with SAT solver?
The problem is to find $\mathcal{S}$, a minimal collect of subsets of $\{1,\dots, 17\}$ such that the two conditions are satisfied:
if $S \subseteq \mathcal{S}$ then $|S|=6$;
for any $A \subseteq \{1,...
3
votes
2answers
241 views
Proof of the inclusion-exclusion principle
The inclusion-exclusion principle for $n$ sets is proved by Kenneth Rosen in his textbook on discrete mathematics as follows:
THEOREM 1 — THE PRINCIPLE OF INCLUSION-EXCLUSION Let $A_1,...
2
votes
1answer
22 views
Algorithm for creating n-multiset out of x?
I have a problem that can be modelled by 15 undistinguishable balls to 21 boxes. The state of a node is defined by indices from 1 to 21 and corresponding values from 0 to 15, with the constraint that ...
1
vote
1answer
15 views
Predicting the outcome of sporting events with multiplicative scoring
In the Olympic format for sport climbing, eight athletes compete in three rounds of climbing. Their final score is the multiplication of their rankings in each round. For example, an athlete who comes ...
3
votes
1answer
60 views
An iterative algorithm for finding the partitions of a set into subsets of a fixed size
The question is whether someone could provide an algorithm for finding all the partitions of a set S into subsets of fixed size (assume the fixed size is 2, to make things simpler, in which case the ...
2
votes
1answer
59 views
Conditions under which the 3-partition problem is not strongly NP-complete?
I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article:
Let B denote the (desired) sum of each subset Si, or equivalently, let the ...
0
votes
0answers
22 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
45 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
50 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
88 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
319 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 ...
1
vote
0answers
41 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 ...
2
votes
1answer
37 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 ...
0
votes
0answers
60 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
35 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 ...
4
votes
0answers
34 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 ...
1
vote
1answer
32 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 ...
2
votes
0answers
72 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
50 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 ...
2
votes
1answer
212 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
169 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 ...
3
votes
1answer
72 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 ...
0
votes
0answers
66 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
10 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 ...
asked Aug 7 '19 at 17:18
Gilles 'SO- stop being evil'
37.8k7 gold badges101 silver badges166 bronze badges
3
votes
2answers
76 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 (...
2
votes
0answers
35 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
30 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
36 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 ...
0
votes
0answers
31 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
71 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
70 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 ...
1
vote
1answer
240 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 ...
5
votes
2answers
150 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
61 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 ...
