# Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

510 questions
Filter by
Sorted by
Tagged with
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, ...
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 ...
167 views

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

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 ...
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 ...
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 ...
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$-...
52 views