Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
1
vote
0answers
37 views

Finding the optimal combination of matrices to multiply that maximise the result when multiplied

I have a 100000×60000 matrix where each element is either a 1 or 0. A 1 represents a signal to do something whereas 0 means to do nothing. Each column represents a different strategy (where strategies ...
0
votes
0answers
22 views

Find the total no. of strings ( len n ) possible given a set of sets of letters such that no two letter from a single set should be in that string

This was an algorithm problem but I am having problems in formulating it. I have a certain approach but I do not know how to fully execute: Given 26 letters in total All possible strings of length n ...
2
votes
1answer
71 views

Faster algorithm for specific inversion count (part 2)

Following the issue from Faster algorithm for a specific inversion: We have a permutation (a derangement actually) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$. I want to compute ...
3
votes
1answer
524 views

Faster algorithm for a specific inversion

There is a permutation (more precisely a derangement) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$. I want to compute the following counts (a kind of inversion): $$K(\sigma )_{i}=\#\{j&...
1
vote
1answer
23 views

Simple problem of combinatorics

There are $3$ red socks, $4$ green socks and $3$ blue socks.You choose $2$ socks. The probability that they are of the same color is Answer: $\dfrac{^{3}C_{2}+^{4}C_{2}+^{3}C_{2}}{^{10}C_{2}}=\dfrac{4}...
1
vote
1answer
37 views

Equally coloring the edges of square tiles that form a grid

I need to generate a set of square tiles that are colored and are grid-able. Each square tile must have a unique set of 4 colors and each exterior edge of each tile is colored with a different color. ...
5
votes
2answers
118 views

Can this special case of bin packing be solved in polynomial time?

Consider a multiset of $n$ integers, where each integer is between $1$ and $3 M$. The sum of all integers is $3 S$. There are three bins. The capacity of each bin is $C = S + M$. Is there a polynomial-...
2
votes
0answers
76 views

An unknown combinatorial optimization problem

I have $N$ available sensors and $M$ devices. Each device needs $a$ sensors. One sensor cannot be used on multiple devices. Each sensor has two properties defined by $H$ and $R$. Let $\sigma_{i\_H}$ ...
6
votes
1answer
75 views

Number of combinations without given pairs

Given a set of elements {e1, e2, ... en}, a set of pairs of these elements (each element may be present in several pairs) and a number k. I need to count how many combinations of size k exist which ...
1
vote
0answers
26 views

Is the problem “find the sequence of $N$ numbers between 1 and $D$ with least cost”, NP-hard?

Consider sequences $p=(p_1,\dots,p_N)$ (the order matters) of length $N$, where $p_i\in\{1,\dots,D\}$ for fixed $D$. Moreover, consider a cost function $c:\{1,\dots,D\}^N\to\mathbb{R}$ which comply $c(...
0
votes
1answer
28 views

Is this variation of the traveling salesman problem NP-hard

Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c_{ij}>0$ where $c_{ij}\neq c_{ji}$. Moreover, if you are traveling to ...
0
votes
0answers
39 views

Is this combinatorial seach problem NP-complete?

The context: Consider the following optimization problem. Let $f_1,\dots,f_L:\mathbb{R}\to\mathbb{R}$ arbitrary (continous) functions for $L>1$ and $x_k\in\mathbb{R}$ evolve according to $$ x_{k+1}...
4
votes
0answers
49 views

Combinatorics - how many $c$-distinct sets are possible?

I'm not sure if CS SE is the right place for this question, but since originally this question was in the CS area (and I translated it to a mathematical form), I will post it here. I am given two ...
0
votes
1answer
35 views

reference request: solving problems by dynamic programming + quantization to avoid combinatorial explosion

The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to: $$ x_{k+1} = f(x_k,u_k), k=0,\dots,N-1 $$ given some $x_0$ and ...
0
votes
1answer
9 views

Divide members into multiple teams without overlap

I'm trying to separate people from a pool into several smaller groups. The group-size should always remain the same. People can be part of several groups - but no two people can be part of more than ...
1
vote
0answers
30 views

How to compute all inequivalent (under Aut(P)) nonnegative integer weight assignments (with fixed sum) to the vertices of a finite poset P?

Let $P$ be a poset on $n$ points, $\text{Aut}(P)$ its automorphism group, and $a_1,a_2,\dots,a_k$ the lengths of the orbits under $\text{Aut}(P)$. Goal: An algorithm to generate a member from each ...
2
votes
0answers
38 views

Efficient solution to this scheduling problem or integer optimization problem

Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to $$ P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)} $$ where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\...
3
votes
0answers
50 views

Make Change in Linear Time

The question is motivated by this post on StackOverflow. Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a ...
1
vote
0answers
17 views

Streaming maximum pair matching with limited memory

I am trying to find as many pairs of elements as possible from two distinct data streams, while being constrained by the number of elements I can hold in memory at any given time. Once a pair of ...
3
votes
1answer
37 views

Upper bound on the number of subgraphs in a tree

Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc. For example, consider the ...
4
votes
1answer
39 views

Model Counting for Sum of Conjunctive Formulas

Problem: Let $X=\{x_1, ..., x_N \}$ be a set of binary variables. Each variable can be assigned to either $0$ or $1$ so there are $2^N$ possible assignments. Input: We are given a positive integer $C$ ...
2
votes
2answers
89 views

Produce all unordered unique combinations of N-sized subsets of an m·N-sized set

Say there is a set of m·N named elements. How to produce all the (unordered) combinations of N-sized subsets? For example, m=2 and N=2, the elements are called A, B, C and D. There will be 3 ...
2
votes
0answers
23 views

Is this a variant of “Path Covering”?

According to 1, "a path cover of a directed graph G is a set of disjoint paths in G which together contain all the vertices of G". In my research, I met a similar problem. There, you can add ...
4
votes
0answers
64 views

Number of permutations with satisfactory triangles

We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
1
vote
1answer
54 views

Not satisfiable 3SAT instance implications

Suppose we have an instance of 3SAT that is NOT satisfiable and we say $S$. If in $S$ there are the following $8$ clauses $\left(a\vee b\vee c\right)\wedge\left(a\vee\bar{b}\vee c\right)\wedge\left(a\...
2
votes
1answer
21 views

Find all the ways to choose $k$ objects from a list of $n$ objects (using a graph?)

I was playing around with graph theory and I noticed that a directed integer graph with unique vertices $V$ and edges $E$ such that each vertex only points to vertices with a higher value can be used ...
0
votes
1answer
43 views

Combinations (repetition not allowed & order not important)

How to compute a table of numbers (all possibilities), where repetition is not allowed and order is not important. Example: I have a set of prime numbers. In this example I have four: {3,5,7,11}, but ...
2
votes
1answer
41 views

Compressing a bit string when I know how many 1s and 0s there are

Say I have a 256 bit bit-string, and I know that there are 16 ones and 240 zeros. I know that this bit string can be compressed, because there are only 256 choose 16...
4
votes
2answers
96 views

Why does my code work: bijecting binary trees to Dyck paths

The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan ...
2
votes
1answer
125 views

Number of substrings possible with even characters

Consider a string 'ABBAA' Possible substrings with even number of characters are $4$ 'ABBA' : Count of 'A' is even and 'B' is even 'AA' : Count of 'A' is even and 'B' is even - ($0$) Similarly 'BB' ...
2
votes
0answers
12 views

Number of substrings possible with even characters [duplicate]

Consider a string 'ABBAA' Possible substrings with even number of characters are 4 'ABBA' : Count of 'A' is even and 'B' is even 'AA' : Count of 'A' is even and 'B' is even ($0$) Similarly 'BB' and '...
1
vote
1answer
21 views

Probability of arising of simple graph in configuration model

I am studying a configuration model building $d$-regular graphs and reading the following article: The expansion of random regular graphs by David Ellis. I am stuck on the following step: Each simple ...
1
vote
1answer
74 views

Create binary numbers with a described pattern

I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$...
1
vote
2answers
116 views

Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?

I want to learn computer science, SO is discrete math enough for computer science ? Or there other Math topics that I should also learn With it ? I don’t have specific topic that I care more about ...
0
votes
0answers
36 views

How to solve this combinatoric problem without bruteforce

I'm trying to solve the following problem : A tile results of a number and a color. a tile can be black, red, orange or blue. a tile number is >= 1 and <= 15. Given a random set a tiles (a ...
1
vote
1answer
46 views

Number of substrings with exactly k distinct characters

Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return ...
0
votes
1answer
26 views

Matching with specific cardinality

In a weighted graph $G(\mathcal{V},\mathcal{E})$ where $w(i,j)$ is the weight of the edge $(i,j) \in \mathcal{E}$. How can I find a maximum weighted matching with a specific size (i.e specific ...
4
votes
1answer
71 views

Bin packing when items can be broken

In the bin packing problem, there are some $m$ items of size less than $1$, and they have to be packed into as few as possible bins of size $1$. The problem is NP-hard, but if we are allowed to break ...
1
vote
0answers
70 views

Covering Variation of Longest Common Substring

Given three binary strings, find the maximum possible length of a contiguous block of 1's formed by shifting and overlapping the strings. This may be interpreted as finding the maximum window size $k$...
1
vote
0answers
32 views

Binary ↔ Gray permutation matrix

Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $n$-bit Gray code is a permutation of $2^n$ elements. ...
0
votes
0answers
34 views

How many different values can a shared variable take in concurrent computing?

Question: Is there a way to find out number of different values that a shared variable can take in concurrent computing, in general, without listing all the possibilities and then counting the ones ...
2
votes
1answer
79 views

maximum cardinality weighted matching

I am looking for a reference for maximum cardinality weighted matching and the best running time algorithm for it. Maximum Cardinality Weighted Matching: Given an undirected weighted graph $G(\mathcal{...
0
votes
1answer
33 views

Combinatorial optimization algorithm with constraints and objective function

I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function. .e.g Say each ...
2
votes
1answer
54 views

This costs minimization problem, is it solvable in polynomial time?

I have the following problem: I have $c$ conflicts, named $(c_1, \ldots, c_c)$, where each conflict $c_i$ has certain size $s_i\in\mathbb{N}_0$: the number of times conflict $c_i$ has happened. Also, ...
1
vote
1answer
187 views

number of ways evaluation of expression such that value not changed [closed]

one example: How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among ...
4
votes
4answers
503 views

Enumerating all partial permutations of given length in lexicographic order

I need to generate all unique tuples of length k chosen from a series of unique, positive integers. In my case n choose k will have n=10, 1 <= k <= 10; and the series I am choosing from is { 0, ...
0
votes
0answers
16 views

Efficiently compressing and decompressing an array of combinations

I'm wondering if there exists a way to efficiently compress an array containing combinations ${n}\choose{k}$, so that it can be easily decompressed minimizing the data read from that array. An example ...
1
vote
1answer
34 views

What is the combinatorial reasoning for the $n$ factor in $n \times n! / (b!(n - b)!)$?

I am currently studying the textbook Artificial Intelligence: A Modern Approach, 4th Edition, by Russell and Norvig. Chapter 3 Solving Problems by Searching says the following: Another type of grid ...
1
vote
0answers
9 views

Creating neighbours of solutions to binary knapsack instances

I am currently trying to implement a Tabu Search algorithm for the binary knapsack problem. Part of my goal is to have a variety of different configurations of attributes used and stopping conditions. ...
0
votes
1answer
25 views

Find sets of weighted objects to maximize number of sets with weight >= X

I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...

1
2 3 4 5
13