Questions tagged [combinatorics]

For questions about the study of finite or countable discrete structures, especially how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

Filter by
Sorted by
Tagged with
216
votes
4answers
9k views

How many fours are needed to represent numbers up to $N$?

The goal of the four fours puzzle is to represent each natural number using four copies of the digit $4$ and common mathematical symbols. For example, $165=\left(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}...
207
votes
17answers
35k views

Do men or women have more brothers?

Do men or women have more brothers? I think women have more as no man can be his own brother. But how one can prove it rigorously? I am going to suggest some reasonable background assumptions: ...
186
votes
4answers
57k views

Why can a Venn diagram for 4+ sets not be constructed using circles?

This page gives a few examples of Venn diagrams for 4 sets. Some examples: Thinking about it for a little, it is impossible to partition the plane into the $16$ segments required for a complete $4$-...
152
votes
9answers
17k views

There are apparently $3072$ ways to draw this flower. But why?

This picture was in my friend's math book: Below the picture it says: There are $3072$ ways to draw this flower, starting from the center of the petals, without lifting the pen. I know it'...
119
votes
14answers
65k views

Taking Seats on a Plane

This is a neat little problem that I was discussing today with my lab group out at lunch. Not particularly difficult but interesting implications nonetheless Imagine there are a 100 people in line to ...
118
votes
2answers
6k views

Making Friends around a Circular Table

I have $n$ people seated around a circular table, initially in arbitrary order. At each step, I choose two people and switch their seats. What is the minimum number of steps required such that every ...
112
votes
1answer
3k views

Is there a characterization of groups with the property $\forall N\unlhd G,\:\exists H\leq G\text{ s.t. }H\cong G/N$?

A common mistake for beginning group theory students is the belief that a quotient of a group $G$ is necessarily isomorphic to a subgroup of $G$. Is there a characterization of the groups in which ...
89
votes
2answers
4k views

Help me put these enormous numbers in order: googol, googol-plex-bang, googol-stack and so on

Popular mathematics folklore provides some simple tools enabling us compactly to describe some truly enormous numbers. For example, the number $10^{100}$ is commonly known as a googol, and a googol ...
88
votes
5answers
5k views

Cutting sticks puzzle

This was asked on sci.math ages ago, and never got a satisfactory answer. Given a number of sticks of integral length $ \ge n$ whose lengths add to $n(n+1)/2$. Can these always be broken (by ...
85
votes
19answers
38k views

Good Book On Combinatorics

What is your recommendation for an in-depth introductory combinatoric book? A book that doesn't just tell you about the multiplication principle, but rather shows the whole logic behind the questions ...
79
votes
9answers
9k views

100 Soldiers riddle

One of my friends found this riddle. There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 75 lose a left arm, 70 lose a right arm. What is the minimum number of soldiers losing all ...
78
votes
1answer
2k views

Can a row of five equilateral triangles tile a big equilateral triangle?

Can rotations and translations of this shape perfectly tile some equilateral triangle? I've now also asked this question on mathoverflow. Notes: Obviously I'm ignoring the triangle of side $0$. ...
72
votes
7answers
4k views

Rigorous nature of combinatorics

Context: I'm a high school student, who has only ever had an introductory treatment, if that, on combinatorics. As such, the extent to which I have seen combinatoric applications is limited to ...
71
votes
3answers
11k views

Mathematical research of Pokémon

In competitive Pokémon-play, two players pick a team of six Pokémon out of the 718 available. These are picked independently, that is, player $A$ is unaware of player $B$'s choice of Pokémon. Some ...
70
votes
4answers
7k views

Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$

It's not difficult to show that $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$ On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
69
votes
2answers
6k views

Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even

In my answer here I prove, using generating functions, a statement equivalent to $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even. (Clearly the sum is $...
69
votes
1answer
3k views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
66
votes
7answers
66k views

What is the math behind the game Spot It?

I just purchased the game Spot It. As per this site, the structure of the game is as follows: Game has 55 round playing cards. Each card has eight randomly placed symbols. There are a total of 50 ...
64
votes
2answers
7k views

Can $18$ consecutive integers be separated into two groups,such that their product is equal?

Can $18$ consecutive positive integers be separated into two groups, such that their product is equal? We cannot leave out any number and neither we can take any number more than once. My work: ...
63
votes
8answers
35k views

Probability that random moves in the game 2048 will win

I have recently played the game 2048, created by Gabriele Cirulli, which is fun. I suggest trying if you have not. But my brother posed this question to me about the game: If he were to write a ...
62
votes
3answers
6k views

Optimal strategy for cutting a sausage?

You are a student, assigned to work in the cafeteria today, and it is your duty to divide the available food between all students. The food today is a sausage of 1m length, and you need to cut it into ...
62
votes
6answers
48k views

Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$

I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$. I already know the logical Proof: $${n \choose k}^2 = {...
62
votes
3answers
3k views

In combinatorics, how can one verify that one has counted correctly?

This is a soft question, but I've tried to be specific about my concerns. When studying basic combinatorics, I was struck by the fact that it seems hard to verify if one has counted correctly. It's ...
59
votes
5answers
96k views

Number of ways to write n as a sum of k nonnegative integers

How many ways can I write a positive integer $n$ as a sum of $k$ nonnegative integers up to commutativity? For example, I can write $4$ as $0+0+4$, $0+1+3$, $0+2+2$, and $1+1+2$. I know how to find ...
59
votes
1answer
2k views

Why are asymptotically one half of the integer compositions gap-free?

Question summary The number of gap-free compositions of $n$ can already for quite small $n$ be very well approximated by the total number of compositions of $n$ divided by $2$. This question seeks ...
58
votes
3answers
992 views

Is $\lfloor n!/e\rfloor$ always even for $n\in\mathbb N$?

I checked several thousand natural numbers and observed that $\lfloor n!/e\rfloor$ seems to always be an even number. Is it indeed true for all $n\in\mathbb N$? How can we prove it? Are there any ...
57
votes
1answer
3k views

Quadratic reciprocity via generalized Fibonacci numbers?

This is a pet idea of mine which I thought I'd share. Fix a prime $q$ congruent to $1 \bmod 4$ and define a sequence $F_n$ by $F_0 = 0, F_1 = 1$, and $\displaystyle F_{n+2} = F_{n+1} + \frac{q-1}{4} ...
56
votes
7answers
5k views

How many 7-note musical scales are possible within the 12-note system?

This combinatorial question has a musical motivation, which I provide below using as little musical jargon as I can. But first, I'll present a purely mathematical formulation for those not interested ...
56
votes
5answers
18k views

Probability for the length of the longest run in $n$ Bernoulli trials

Suppose a biased coin (probability of head being $p$) was flipped $n$ times. I would like to find the probability that the length of the longest run of heads, say $\ell_n$, exceeds a given number $m$, ...
55
votes
0answers
1k views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
54
votes
6answers
13k views

Exam with $12$ yes/no questions (half yes, half no) and $8$ correct needed to pass, is it better to answer randomly or answer exactly 6 times yes?

In an exam with $12$ yes/no questions with $8$ correct needed to pass, is it better to answer randomly or answer exactly $6$ times yes and 6 times no, given that the answer 'yes' is correct for ...
54
votes
4answers
6k views

Do circles divide the plane into more regions than lines?

In this post it is mentioned that $n$ straight lines can divide the plane into a maximum number of $(n^{2}+n+2)/2$ different regions. What happens if we use circles instead of lines? That is, what ...
53
votes
11answers
11k views

$7$ fishermen caught exactly 100 fish and no two had caught the same number of fish. Then there are three who have together captured at least 50 fish.

$7$ fishermen caught exactly $100$ fish and no two had caught the same number of fish. Prove that there are three who have captured together at least $50$ fish. Try: Suppose $k$th fisher caught $r_k$ ...
52
votes
3answers
10k views

Is it possible to place 26 points inside a rectangle that is 20 cm by 15 cm so that the distance between every pair of points is greater than 5 cm?

I need help to answer the following question: Is it possible to place 26 points inside a rectangle that is $20\, cm$ by $15\,cm$ so that the distance between every pair of points is greater ...
52
votes
8answers
69k views

What is the proof that the total number of subsets of a set is $2^n$?

What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).
52
votes
5answers
1k views

Time to reach a final state in a random dynamical system (answer known, proof unknown)

Consider a dynamical system with state space $2^n$ represented as a sequence of $n$ black or white characters, such as $BWBB\ldots WB$. At every step, we choose a random pair $(i,j)$ with $i<j$ ...
52
votes
4answers
3k views

A zero sum subset of a sum-full set

I had seen this problem a long time back and wasn't able to solve it. For some reason I was reminded of it and thought it might be interesting to the visitors here. Apparently, this problem is from a ...
52
votes
1answer
1k views

How many values of $2^{2^{2^{.^{.^{.^{2}}}}}}$ depending on parenthesis?

Suppose we have a power tower consisting of $2$ occurring $n$ times: $$\huge2^{2^{2^{.^{.^{.^{2}}}}}}$$ How many values can we generate by placing any number of parenthesis? It is fairly simple for ...
52
votes
0answers
2k views

Mondrian Art Problem Upper Bound for defect

Divide a square of side $n$ into any number of non-congruent rectangles. If all the sides are integers, what is the smallest possible difference in area between the largest and smallest rectangles? ...
51
votes
14answers
14k views

Why is it that if I count years from 2011 to 2014 as intervals I get 3 years, but if I count each year separately I get 4 years?

I'm not a very smart man. I'm trying to count how many years I've been working at my new job. I started in May 2011. If I count the years separately, I get that I've worked 4 years - 2011 (year 1), ...
51
votes
2answers
2k views

How do the Catalan numbers turn up here?

The Catalan numbers have a reputation for turning up everywhere, but the occurrence described below, in the analysis of an (incorrect) algorithm, is still mysterious to me, and I'm curious to find an ...
50
votes
6answers
2k views

What structure does the alternating group preserve?

A common way to define a group is as the group of structure-preserving transformations on some structured set. For example, the symmetric group on a set $X$ preserves no structure: or, in other words,...
49
votes
2answers
1k views

Crazy pattern in the simple continued fraction for $\sum_{k=1}^\infty \frac{1}{(2^k)!}$

The continued fraction of this series exhibits a truly crazy pattern and I found no reference for it so far. We have: $$\sum_{k=1}^\infty \frac{1}{(2^k)!}=0.5416914682540160487415778421$$ But the ...
48
votes
11answers
4k views

What is the total sum of the cardinalities of all subsets of a set?

I'm having a hard time finding the pattern. Let's say we have a set $$S = \{1, 2, 3\}$$ The subsets are: $$P = \{ \{\}, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \}$$ And the ...
48
votes
2answers
33k views

A comprehensive list of binomial identities?

Is there a comprehensive resource listing binomial identities? I am more interested in combinatorial proofs of such identities, but even a list without proofs will do.
47
votes
5answers
1k views

Closed form for $\prod_{n=1}^\infty\sqrt[2^n]{\frac{\Gamma(2^n+\frac{1}{2})}{\Gamma(2^n)}}$

Is there a closed form for the following infinite product? $$\prod_{n=1}^\infty\sqrt[2^n]{\frac{\Gamma(2^n+\frac{1}{2})}{\Gamma(2^n)}}$$
47
votes
2answers
7k views

How to reverse the $n$ choose $k$ formula?

If I want to find how many possible ways there are to choose k out of n elements I know you can use the simple formula below: $$ \binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$ What if I want to go the ...
46
votes
3answers
3k views

Choosing office hours to maximise number of students who can attend at least one time slot

I have the following (real world!) problem which is most easily described using an example. I ask my six students when the best time to hold office hours would be. I give them four options, and say ...
45
votes
7answers
6k views

How many scientists can survive?

Yesterday the aliens took 100 scientists from Earth as prisoners. They want to test how smart the humans are. The aliens made 101 headbands, numbered from 1 to 101. On the contest day, they throw ...
44
votes
7answers
61k views

How many triangles

I saw this question today, it asks how many triangles are in this picture. I don't know how to solve this (without counting directly), though I guess it has something to do with some recurrence. How ...