All Questions
Tagged with combinatorics algorithms
117
questions
9
votes
3
answers
9k
views
How can I (algorithmically) count the number of ways n m-sided dice can add up to a given number?
I am trying to identify the general case algorithm for counting the different ways dice can add to a given number. For instance, there are six ways to roll a seven with two 6-dice.
I've spent quite ...
- 557
2
votes
3
answers
1k
views
Counting subsets containing three consecutive elements (previously Summation over large values of nCr)
Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$.
...
- 242
12
votes
2
answers
13k
views
Efficient computation of the minimum distance of a binary linear code
I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix.
How can I find parameter $d$ efficiently?
I know the method that compute all the codewords and take ...
- 303
27
votes
2
answers
3k
views
Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$
More precisely,
$$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$
This is Theorem 4 ...
- 1,727
19
votes
4
answers
9k
views
Algorithm wanted: Enumerate all subsets of a set in order of increasing sums
I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time.
Given a set of ...
- 293
3
votes
4
answers
2k
views
Generate all de Bruijn sequences
There are several methods to generate a de Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length $n$...
- 10.9k
1
vote
2
answers
2k
views
Algorithms for mutually orthogonal latin squares - a correct one?
I am very interested in using mutually orthogonal latin squares (MOLS) to reduce the number of test cases but I struggle to find a way how to implement the algorithm. In an article published in a ...
- 141
24
votes
8
answers
42k
views
How do I compute binomial coefficients efficiently?
I'm trying to reproduce Excel's COMBIN function in C#. The number of combinations is as follows, where number = n and number_chosen = k:
$${n \choose k} = \frac{n!}{k! (n-k)!}.$$
I can't use this ...
- 495
7
votes
2
answers
7k
views
Lights Out Variant: Flipping the whole row and column.
So I found this puzzle similar to Lights Out, if any of you have ever played that. Basically the puzzle works in a grid of lights like so:
1 0 0 00 0 0 00 1 0 0 0 0 1 0
When you selected a light (...
- 194
0
votes
1
answer
159
views
Generate some number of lists of pairs given a list of people
Given a list of people:
[
1,
2,
3,
4,
5,
6
]
The goal is to generate some number of lists of pairs.
...
20
votes
3
answers
1k
views
Finding the Robot [closed]
There are five boxes in a row. There is robot in any one of these five boxes. Every morning I can open and check a box (one only). In the night, the robot moves to an adjacent box. It is compulsory ...
- 827
18
votes
4
answers
7k
views
Looking to understand the rationale for money denomination
Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:
$$
s = \sum_{i=1}^k n_i d_i\quad\text{...
- 484
17
votes
3
answers
11k
views
Generate Random Latin Squares
I'm looking for algorithms to generate randomized instances of Latin squares.
I found only one paper:
M. T. Jacobson and P. Matthews, Generating uniformly distributed random Latin squares, J. ...
user14947
15
votes
5
answers
14k
views
Algorithm for generating integer partitions up to a certain maximum length
I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...
- 757
14
votes
2
answers
8k
views
Complexity of counting the number of triangles of a graph
The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle.
This procedure ...
- 5,032
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
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
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
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
4
votes
1
answer
380
views
What is the minimum number of squares to be drawn on a paper in order to obtain an 8x8 table divided into 64 unit squares? [closed]
What is the minimum number of squares to be drawn on a paper in order to obtain an $8\times8$ table divided into $64$ unit squares.
Notes:
-The squares to be drawn can be of any size.
-There ...
- 63
4
votes
1
answer
826
views
All nonisomorphic trees of order $n$
I have two questions regarding spanning trees:
Q$1$. Is there any formula for the number of distinct trees of order $n$? I don't mean labelled trees, just distinct trees. For example: for $n=3$ there'...
- 251
3
votes
1
answer
309
views
Algorithm to partition a multiset into $K$ equal sized multisets
How can I partition a multiset of integers, $A$, of size $N=MK$, into $K$ equal-sized multisets, $G_1,G_2,\ldots,G_K$, such that $\sum_i \mathrm{\lvert \min(G_i)\rvert}$ is maximized? Here, $\min(G)$ ...
- 53
3
votes
1
answer
514
views
Finding algorithm among 3 color balls
You have $5$ white, $5$ black, and $5$ red balls. There is exactly $1$ radioactive ball among each group. There is a device, which says if there is at least one radioactive ball among some group of ...
- 127
2
votes
2
answers
687
views
Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version
I am coordinating cookie-baking events with kindergarten kids. This turns out to be a challenging problem, and I could use a little help:
We would like a general way of creating 'fair' cookie-baking ...
- 123
2
votes
1
answer
406
views
Mathematically representing combinations with integers uniquely?
Say I want to pick up $k$ amongst $n$ with respect to order. I am thinking about splitting it into two separate problems.
...
- 26.1k
2
votes
1
answer
105
views
determine the least number of rounds that needs to be played so that every child is satisfied
A group of N children, who are numbered 1, 2, . . . , N, want to play hide and seek. In a single round of hide and seek, there will one seeker, and N −1 hiders. Children like to hide and not seek and ...
- 49
1
vote
1
answer
172
views
Number of binary numbers given constraints on consecutive elements
I've been trying to solve this question for quite a while, given to us by our discrete maths professor. I've been having a hard time in general with it, so I thought I tried looking it up online but ...
- 27
1
vote
0
answers
123
views
What is the best way to solve discrete divide and conquer recurrences?
Note: I have converted my announcement
into a question
and supplied an answer.
What is the best way to solve discrete divide and conquer recurrences?
The "Master Theorem" is one way.
What other ...
- 108k
0
votes
0
answers
46
views
Computing the cardinality of a combinatorial set
Define two sets: $S_1$ and $S_2$ where we have that $a$ is an odd natural number and $b\in \mathbb{N}$,
$S_1 = \Big\{ \frac{2}{a},\frac{2}{a-2},\frac{2}{a-4},...,\frac{2}{a-(a-1)},$
$\frac{2+4}{a+2},\...
user830143
0
votes
3
answers
1k
views
For a set with N members, what is the number of set partitions in which each subset is either of size 1 or 2? [duplicate]
I have a set with $N$ members $\{1,2, \dots, N\}$. I would like to know number of set partitions in which each subset is either of size $1$ or $2$, i.e., cardinality of each subset in the partition is ...
- 327
38
votes
1
answer
3k
views
Is War necessarily finite?
War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules.
A ...
- 27.2k
17
votes
3
answers
5k
views
In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?
Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard?
For example:
$M = 2, N = 2$, ans $= 6$
$M = 3, ...
- 251
15
votes
2
answers
1k
views
Domination problem with sets
Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
of $M$, satisfying:
(1) $|S_i|\leq 3,i=1,2,...,k$
(2) Any element of $M$ is an element of at least $4$ sets among
$S_1,....,...
- 90.7k
15
votes
3
answers
946
views
Partition 100 people, 4 from each country into 4 groups with conditions
This is a problem from the $2005$ All-Russian Olympiad. Problem is as follows:
$100$ people from $25$ countries, four from each country, sit in a circle.
Prove that one may partition them onto $4$ ...
- 381
14
votes
2
answers
5k
views
For what coinage systems does a greedy algorithm not work in providing change?
For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins.
However, for a coinage system with 12 cent coins, a greedy ...
- 3,445
13
votes
3
answers
2k
views
Deducing correct answers from multiple choice exams
I am looking for an algorithmic way to solve the following problem.
Problem
Say we are given a multiple choice test with 100 questions, 4 answers per question (exactly one of those four being ...
- 346
9
votes
2
answers
6k
views
Numbering edges of a cube from 1 to 12 such that sum of edges on any face is equal
Assign one number from 1 to 12 to each edge of a cube (without repetition) such that the sum of the numbers assigned to the edges of any face of the cube is the same.
I tried a bunch of equations but ...
- 193
9
votes
1
answer
5k
views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
user7055
9
votes
2
answers
738
views
Connect $n$ white and $n$ black points
$n$ black and $n$ white points are drawn on plane, so that no three of them lay on one line. How to prove that we can connect each white point to some black point by straight segment so that no two ...
- 4,793