All Questions
Tagged with combinatorics algorithms
117
questions
6
votes
2
answers
2k
views
How can I reduce a number?
I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
- 419
5
votes
2
answers
3k
views
On counting and generating all $k$-permutations of a multiset
Let $A$ be a finite set, and $\mu:A \to \mathbb{N}_{>0}$. Let $M$ be the multiset having $A$ as its "underlying set of elements" and $\mu$ as its "multiplicity function". (Hence $M$ is finite.)
...
- 14.5k
4
votes
1
answer
515
views
Collection of subset generating every pairs of elements
I'm looking forward to a construction with the following property:
Given a set S of n elements, find a small/the smallest collection of subsets of S of size k such that for every pair of elements a, ...
- 51
4
votes
1
answer
2k
views
Expected value when die is rolled $N$ times
Suppose we have a die with $K$ faces with numbers from 1 to $K$ written on it, and integers $L$ and $F$ ($0 < L \leq K$). We roll it $N$ times. Let $a_i$ be the number of times (out of the $N$ ...
- 235
3
votes
2
answers
3k
views
Sum of multiplication of all combination of m element from an array of n elements
Suppose I have an array {1, 2, 3, 4} and m = 3.
I need to find:
...
- 31
3
votes
2
answers
754
views
How to calculate the number of possible multiset partitions into N disjoint sets?
I have made a Ruby program, which enumerates the possible multiset partitions, into a given number of disjoint sets (N), also called bins. The bins are indistinguishable. They can be sorted in any ...
- 155
1
vote
1
answer
2k
views
Making all row sums and column sums non-negative by a sequence of moves
Real numbers are written on an $m\times n$ board. At each step, you are allowed to change the sign of every number of a row or of a column. Prove that by a sequence of such steps, you can always make ...
- 3,914
1
vote
1
answer
283
views
Showing there exists a sequence that majorizes another
The exact quantity of gas needed for a car to complete a single loop around a track is distrubuted among $n$ containers placed along the track. Show that there exists a point from which the car can ...
- 1,418
11
votes
5
answers
12k
views
Secret santa problem
We decided to do secret Santa in our office. And this brought up a whole heap of problems that nobody could think of solutions for - bear with me here.. this is an important problem.
We have 4 people ...
- 221
8
votes
2
answers
2k
views
Minimum transactions to settle debts among friends
You are given $n$ integers $x_1,x_2,\dots,x_n$ satisfying $\sum_{i=1}^n x_i=0$. A legal move is to choose an integer $a$ and two indices $i,j$, and to increase $x_i$ by $a$ and decrease $x_j$ by $a$. ...
- 98
7
votes
4
answers
4k
views
What is the number of full binary trees of height less than $h$
Given a integer $h$
What is $N(h)$ the number of full binary trees of height less than $h$?
For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't find ...
- 13.8k
6
votes
5
answers
2k
views
Least wasteful use of stamps to achieve a given postage
You have sheets of $42$-cent stamps and
$29$-cent stamps, but you need at least
$\$3.20$ to mail a package. What is the
least amount you can make with the $42$-
and $29$-cent stamps that is ...
- 36.6k
5
votes
3
answers
5k
views
How many ways to reach $Nth$ number from starting point using any number steps between $1$ to $6$
In a board game, dice can roll either $1, 2, 3, 4, 5$ or $6$. The board has $N$ number of space. Every time of dice roll randomly, pawn moves forward exactly to dice rolled a number. Now the problem ...
- 63
5
votes
2
answers
2k
views
Generating a Eulerian circuit of a complete graph with constant memory
(this question is about trying to use some combinatorics to simplify an algorithm and save memory)
Let $K_{2n+1}$ be a complete undirected graph on $2n+1$ vertices.
I would like to generate a Eulerian ...
- 3,315
4
votes
0
answers
2k
views
