All Questions
Tagged with combinatorics algorithms
117
questions
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
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
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
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
2
votes
2
answers
688
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
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