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

# Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

509 questions
Filter by
Sorted by
Tagged with
55 views

### Sampling numbers from a weighted set that sum to constant value

So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to ...
194 views

### Efficient n-choose-k random sampling

Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)? I have read this question but it asks for generations of all combinations, not ...
71 views

### Placing items into compatible bucket types to find an optimal total value

Suppose we have a list of buckets, each with a unique type and a maximum capaciy. We also have a list of items, each with a value and a list of compatible bucket types. An item is compatible with a ...
35 views

70 views

### Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?

As an example, here are all possible trees for the case $k=3$: On each node written is its arity (= the number of children). While this should be solvable by dynamic programming, I think there was a ...
18 views

### Bounds on “well dispersed” sparse matrices

Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is ...
49 views

### Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?

For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one. ...
50 views

### Find a partition of multiset of binomial coefficients with constriants

Given the multiset $S$ where the elements are defined by the binomial coefficient ${n \choose k}$ where $n \in \mathbb{N}$ and $0\leq k \leq n$ find the partition $P$ of $S$ such that the sum of ...
46 views

### O(1) algorithm to get approximate number that is larger as a binomial coefficient

Ideally I need a to calculate the binomial coefficient ${p \choose n}$. But since the fastest algorithm to do this is an $\mathcal{O}(n)$ algorithm I would look to do something different. I don't ...
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 ...
100 views

### Counting chords intersections in a circle

The problem is: Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point, that point counts as $\binom{n}{2}$ ...
83 views

### Given a bitstring generate all bitstring with n flipped bits

For an algorithm I need to be able to iterate over all bit strings where $k$ bits are flipped given a bit string with length $n$ and $n \geq k$. For instance let's say I have the bit string $1001$ and ...
431 views

### Hard connected instances for Weisfeiler-Lehman test of isomorphism

There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm. However, one of these graphs is disconnected. So what are the instances ...
18 views

### Relation between deficiency and color class parity of graphs

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
40 views

### invite 12 person from 24 that we have 6 men and 6 womens [closed]

i had a question and its "A man has 5 female and 7 male friends and his wife has 7 female and 5 male friends. In how many ways can they invite 6 males and 6 females if husband and wife are to invite ...
160 views

### Variant of interval scheduling (multiple machines with given availability)

I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks ...
32 views

### Linear ordering of all subsets of size k

I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into ...
84 views

### Alternate proof of the Caro-Wei theorem for lower bounding the independence number

Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
44 views

336 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 ...
142 views

### A problem on constrained combinatorics

Not sure if this is a proper place, but I really don't know where else to ask. I'm craving for an algorithm generating certain sequences of numbers (the problem comes from physics). I'm looking for ...
173 views

### Algorithm to organize a tournament where the team componentes change each round

So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
154 views

### Sum of unique elements in all sub-arrays of an array

Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$. Subarrays: ...
44 views

### Different iterations of regular expressions

A four-part question dealing with formal languages and regular expressions: How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string? How ...
98 views

### No. of subsets whose element multiply to give a square number

I have been given an array whose elements lie between [1,70] and the size of array [1,10^5]. I have to find the total number of subsets whose all elements multiply to give a perfect square number. ...
10 views

### Maximal number of rounds we can do distributing 64 diners on 8 groups in different ways if they can't meet each other more than once?

N=64 hungry diners come to a buffet. We sit them at 8 different (s=8 people at each table) tables so that they get to know each other while they eat. After a while we distribute them over the tables ...
35 views

### Count number of the ways to fill a N-lengthed binary string

From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more ...
116 views

### Maximum number of non-overlapping rectangles where each contains a minimum number of points

Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap. Each point is distinct from every other ...
2k views

### Cardinality of the set of algorithms

Someone in a discussion brought up that (he reckons) there can be at least continuum number of strategies to approach a specific problem. The specific problem was trading strategies (not algorithms ...
82 views

### How to generate a binary string so to minimize weighted bitwise distance?

I've got an array of weights, for example [1, 0, 3, 5] The distance between two strings is defined as a sum of weights for different bits, like this: ...
71 views

### Primary/Secondary On Call Rotations

I'm trying to setup a primary and secondary on call schedule with 6 people. I'm trying to schedule people to be on call, so that they will be paired with everyone and they have the longest "break" ...
57 views

### Inexact cover, or cover with gaps

Dancing Links: wikipedia article, research paper is an implementation of algorithm X for exact cover problem. In the Knuth's research papaer, linked above it is shown how Polymino problem (that is ...
115 views

### Integer Problem Solving with two boolean selection variables

I am trying to solve a two dimensional combinatorial problem. Hereis my input space {{RA1,RA2},{RB1,RB2},{RC1,RC2}} and i have to choose two out of three elements{A,B,C} and one out of two possible ...
625 views

### Making 5-tuples out of their respective 4-tuples

Let's take integer numbers from [1..36]. We can generate 376992 different (order is not important) five-number-combinations like (1,3,5,7,12), etc. Such five-number-combinations always have five ...
1k views

### Given n numbers How to find out a set of numbers whose sum equal to a certain given number

I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s. ...
20 views

### Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k

Say I had a list of numbers in the range of 1-20 for example: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19], and an integer k (let's say k = 40) How would I find the maximum possible size of S, where S is a ...
309 views

### Which algorithm can calculate an optimal allocation of students to projects?

I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects ...
23 views

### How many different strongly connected graphs can be created given n nodes?

Given some fixed number of nodes $n$, which we will number 1 to $n$ in order to tell them apart, how many different strongly connected graphs can be created? Multiple edges with the same starting and ...
I have a matrix $P \in M_n(\mathbb N)$, where  P = \begin{bmatrix} 0 & P_{12} & \ldots & P_{1n}\\ P_{21} & 0 & \ldots & P_{2n}\\ \vdots & \vdots & \ddots &...