# Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

628 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
524 views

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 ...
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 ...
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 ...
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 ...
38 views

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 ...
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 ...
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...
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 ...
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' ...
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 '...
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 ...
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$...
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 ...
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 ...
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 ...
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 ...
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 ...
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$...
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. ...
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 ...
79 views

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{... 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 ... 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, ... 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 ... 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, ... 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 ... 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 ...