Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
1
vote
2answers
127 views

Computational complexity of Bell numbers

I've been recently dealing with a problem which, when worst case is considered, results in exploration of $B_{n}$ options, where $B_{n}$ is th $n^{th}$ Bell number. I am trying to rigorously prove, ...
2
votes
0answers
78 views

Grouping elements optimally other than NP-hard approach

Given a number $N$, I need to make a new array $B$ of size $n$ (index-1 based) such that the product of $B[i]-(i-1)$ for $1 \le i \le n$ is equal to $N$ and $B[n]$ is minimum and $B[i] \ge B[i-1]$ and ...
2
votes
1answer
167 views

Subset sum into a consecutive range vs. standard subset sum

The following problems live in integer domain. I want to find a subset of $\{x_0, x_1, \ldots, x_{n-1}\}$ such that the subset's elements sum to any number in a prescribed interval $[X,X+k]$, $k\geq ...
2
votes
1answer
75 views

Find the maximizing row-column matches in a matrix

I have a set of R x C matrices similar to the following (can be much longer): C1 C2 C3 C4 C5 C6 R1 0.32 0.81 NA NA NA NA R2 0.90 -0.44 0.95 ...
0
votes
0answers
60 views

Optimise 1D cutting stock problem - maximum waste that can be removed with n cuts

The problem statement can be made as follows. There is a 1D length of raw material that contains "net" and "waste" intervals. Using 2n cuts, sections of material can be removed so that less waste has ...
1
vote
1answer
131 views

Efficient alternatives to inclusion-exclusion

Say you've got a number of sets $S_1,...,S_n$ given and are supposed to calculate $\,\,\displaystyle\big|\bigcup_{i=1}^n S_i\big|$ . The basic approach probably would be to use the classic inclusion-...
1
vote
1answer
57 views

Number of words in $\{pi,po\}^*$ of length at most 9

I have a language $L^*$ for $L = \{pi,po\}$ (I think pi counts as one letter and po also as one letter otherwise a max length of 9 is not possible). The question is how many words I can make with $L^*...
1
vote
1answer
38 views

Group tuples to satisfy constraints

This is a problem that involves matching students with various skills into groups so that there are as many groups as possible while ensuring that each group has certain skills present. I've reduced ...
0
votes
1answer
59 views

sub-optimal but fast partition generation

I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. ...
2
votes
2answers
67 views

Why is the number of digits (bits) in the binary representation of a positive integer $n$ is the integral part of $1 + \log_2 n$?

I've stumbled on this definition on Wikipedia, and I can't figure out why. I could probably start the demonstration by saying that, with $n$ bits, you can create $2^n$ possible different numbers, so $...
0
votes
0answers
48 views

Multi-trip travel salesman problem

Given a graph $G$, I want to find a shortest tour visiting each vertex. Different to the classical formulation of TSP, my tour needs to be divided into several subtours, each upper-bounded by a ...
1
vote
1answer
61 views

Minimum capacity cut reduction from digraph with two edge weight sets

Given a digraph $G$ and $f, g : E(G) \mapsto \mathbb{R}$, how would you find a cut $(X,\bar{X})$ with $s \in X$ and $t \in \bar{X}$ such that $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{...
0
votes
1answer
100 views

Knapsack problem with diminishing prices

I wonder if the knapsack problem with diminishing prices is already studied? The problem is similar to the regular knapsack problem, except the price of each item is a decreasing function of the total ...
2
votes
1answer
42 views

Finding the maximum of a random forest

If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is ...
2
votes
0answers
35 views

Constrained selection of a random sample from a set of items with multiple attributes

Suppose I have a collection of N items, each of which has A different attributes, a1, a2, ..., aA. Attribute ai can take on Vi different possible (discrete) values, distributed across the population ...
2
votes
1answer
39 views

Fast computation of k-fibonacci numbers

Let's define the sequence of $k$-Fibonacci numbers as $$ F_i = 2^i, ~~ 0 \leq i \leq k-1 $$ $$ F_i = F_{i-1} + \dots + F_{i-k}, ~~ i \geq k $$ I have a problem which requires to compute $n$-th $k$-...
2
votes
1answer
52 views

Counting restricted partitions

Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$: $$ N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq ...
0
votes
0answers
268 views

Permutation of multiple groups of different sizes

While working on my research for my master thesis I have stumbled upon the following problem: Given $N$ groups of different sizes, create all the possible combinations $p$ such that: $p = \{e_{0,j_0}...
0
votes
0answers
24 views

Assign team members to groups to maximize outcome

Team A has 2 Spots Team B has 1 Spot Player 1: 10 Units when on team A, Can't work on team B Player 2: 8 Units when on team A, Can't work on team B Player 3: 9 Units when on team A, 2 Units when ...
1
vote
1answer
57 views

Portfolio allocation with a few twists

A similar question has been asked here, but this one is more complicated and has more constraints. I'm trying to find an algorithm to solve the following (real-life) problem: A customer has $M$ ...
1
vote
1answer
24 views

Find the best set of triples of objects, using each object at max one time

I stumbled upon an interesting problem and I'm stuck with it, since I can't find parallels to other problems or algorithms to solve it. We have a set of objects $O = \{a,b,c,...,z\}$, objects can ...
3
votes
0answers
43 views

How to determine the maximum valued play in Rummikub?

This question is meant as a follow-up this question and my answer here. The question asked multiple questions about algorithms for playing Rummikub and my answer provided an algorithm that, given a ...
1
vote
1answer
416 views

Control of the combinatorial aspects of a dynamic programming solution

I am exploring how a Dynamic Programming design approach relates to the underlying combinatorial properties of problems. For this, I am looking at the canonical instance of the coin exchange problem: ...
0
votes
1answer
21 views

Online Set Filling

Suppose we have 3 sets $A, B, C$ which can can hold a maximum of two elements, each. So the total number of elements that the sets can hold together i.e. total capacity (TC) is $ 3*2 = 6$. Now, ...
1
vote
1answer
82 views

Shift Organization algorithms (Constraint Programming + Marriage problem)

I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition: Daily shifts must be covered by workers, who are divided in three groups: ...
1
vote
1answer
38 views

Obtaining a recurrence from a rational generating function

Looking at some Generating functions of a series, I have conjectured - If $G(x) \ =\ \frac{1}{1-x^{t_1}-x^{t_2}-...-x^{t_n}}$, then the recurrence equation of the the series is - $a_n = a_{n-t_1}+...
2
votes
2answers
291 views

A 4-bit combinatorial circuit that outputs 1 when integer greater than 7 and is odd number

I need to draw a combinatorial circuit that when an integer is greater than 7 and is an odd number, the output will be 1. There are 4 inputs representing 4 bits and 1 output wire. The output wire is ...
1
vote
1answer
343 views

Reverse cartesian product matching all given rows

I´m looking for an efficient algorithm that will find reverse cartesian products. Mathematically, given $S \subseteq T^n$, I want to express $S$ as a union of sets $A_{i,1} \times A_{i,2} \times \...
2
votes
1answer
196 views

Fastest (fast enough to compute) algorithm for finding permutations

I have a set of letters, and a list of words, and I'd like to find all the possible "sentences" that can be built using the words from the list, while using up all the letters in the process. (A word ...
1
vote
0answers
39 views

Number of binary trees of size $n$ such that all subtrees of same size are equal?

For a binary tree $t$, let the size $|t|$ be the number of leaves of $t$. I am interested in the following property of a binary tree $t$: If two subtrees $t'$ and $t''$ of $t$ have the same size, i.e. ...
1
vote
0answers
88 views

Hanoi Tower Variation: Place Maximum Number of Balls on $N$ Pegs

Problem Statement. There are many interesting variations on the Tower of Hanoi problem. This version consists of $N$ pegs and one ball containing each number from $1, 2, 3, \dots$ Whenever the sum of ...
2
votes
1answer
122 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 ...
4
votes
1answer
625 views

Rummikub algorithm

I have just played a few games of Rummikub and the manipulations I made during my turns became more and more complex transactions. A few turns reordered the whole field, so that other players did not ...
0
votes
1answer
236 views

Get a fixed-size family of k-element subsets

I have an n-element set, and I want to consider families of its k-element subsets of fixed size s. For example, if n = 3, k = 1, s = 2, we have these families: ...
1
vote
1answer
682 views

The maximum number of nodes in a heap tree of degree d and depth k

The maximum number of nodes in a binary tree of depth k is defined by 2^(k+1)-1, but the same rule doesn't appear to work for heap trees of different degrees. Let's say I have the following tree of ...
1
vote
2answers
53 views

For a cycle with $n$ vertices, how many distinct chords are possible?

Note: This is almost certainly an elementary problem with a well known solution. Therefore pointers to existing references will be accepted as good answers. Question: Given a cycle with exactly $n$ ...
3
votes
0answers
119 views

How to find an optimal sequence of matching

Given a graph $G(V.E,w)$ Here $w: E \mapsto R$. We need to find optimal set of matchings(set of edges that have no common vertices) and $t_i$'s such that after all these matchings, it results in $\...
1
vote
1answer
22 views

Growing multiples of variable combinations

I need to find growing combinations of variables a, b, c etc. I don't know names of math things in English well, so my description of the problem will be in pseudocode. This is for a programming ...
0
votes
1answer
173 views

Number of 2-3 trees of depth 4

I have a task to find a number of 2-3 trees... I don't quite know what it means, I'm asked to: find the number of 2-3 trees of depth $4$? Is there a specific way to find number of 2-3 trees of depth $...
3
votes
1answer
27 views

Polynomial Computation of the probability of a number of independent events

Suppose to have $n$ independent events $E_1, E_2,..., E_n$, where the probability of occurrence of event $E_i$ is $p_i$ (i.e., each event has its own probability of occurrence). We can easily define ...
1
vote
2answers
120 views

Non-trivial bin-packing instance with 5 objects

Bin packing problem is a problem, where one has to find the minimum number of bins of size $v$ required to store $n$ objects of sizes $s_1, \ldots, s_n$. Object sizes are never greater than $v$. For ...
6
votes
1answer
249 views

Combinatorics: how many ways can we mark nodes in a DAG as black or white, if every node downstream of a black node is also black?

We are assigning the colours white/black to the vertices of a DAG, under the condition that if $V$ is black and there is a path $V \to W$ for some vertex $W$, then $W$ is black. Examples: In the ...
1
vote
0answers
51 views

Hat Distribution Problem

I had a question for my paper last week and i tried solving but failed. Given n people, any two are either friends or enemies, and friendship and enmity are mutual. I want to distribute hats to them, ...
3
votes
1answer
189 views

Counting Colorings of a Grid

Given a $n \times m$ grid, define a valid coloring as mapping from the grid cells to a set of $k$ available colors such that no two adjacent cells have the same color. Cells are considered as adjacent ...
0
votes
1answer
31 views

What do you call a lower/upper bound that is the best one?

I have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it ...
1
vote
2answers
350 views

Proving a factor 2 performance guarantee for a greedy minimum cardinality vertex cover algorithm (Exercise)

Exercise 1.3 from Vijay Vazirani - 'Approximation Algorithms' asks: Consider the following factor $2$ approximation algorithm for the cardinality vertex cover problem. Find a depth first search tree ...
1
vote
0answers
23 views

Set cover such that every vertex appears in at most k sets

Given a set $\{x_1,x_2,\dots, x_n\}$ and sets $\mathcal(F)=\{f_1,f_2,\dots, f_m\}$. Is there any hardness result or approximation algorithm to find a set cover with this extra condition. For every ...
2
votes
0answers
94 views

Efficient algorithm for “group-sum-min” problem

Given two finite sets $A, B \subseteq \mathbb{C} \times \mathbb{R}$, each stored as an array, define $$ S = \{ (z_1 + z_2, x + y, z_1, z_2, x, y) : (z_1, x) \in A, (z_2, y) \in B \} $$ and $$ f(s) = \...
1
vote
3answers
149 views

Is there a way to make chess an absolutely fair game? [closed]

Chess is usually considered a mostly "fair game" between White and Black because the opening position of pieces has mirror symmetry (between players). In practice it also appears to be a fair game ...
2
votes
1answer
46 views

Minimum number of nucleotides to force duplicate substring

There are 4 DNA nucleotides, each represented by one of the letters A, C, G, or T. Assume that they can be arranged in a string e.g. "GATTACA...". I want to figure out the minimum number of ...