Permutations, combinations, bijective proofs, generating functions
143
votes
1answer
6k 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=(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}) ...
71
votes
3answers
6k 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-set ...
69
votes
5answers
3k 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 ...
53
votes
10answers
4k 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 ...
48
votes
2answers
4k views
More than 99% of groups of order less than 2000 are of order 1024?
In Algebra: Chapter 0, the author made a remark (footnote on page 82), saying that more than 99% of groups of order less than 2000 are of order 1024.
Is this for real? How can one deduce this result? ...
45
votes
2answers
2k 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 ...
44
votes
0answers
794 views
+50
Is there a characterization of groups with the property $\exists N \unlhd G : \not \exists H \leq G \,\,\,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 for groups for which this ...
42
votes
2answers
1k 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
...
42
votes
1answer
2k 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} ...
41
votes
3answers
736 views
Alice and Bob matrix problem.
Alice and Bob play the following game with an $n*n$ matrix, where $n$ is odd.
Alice fills in one of the entries of the matrix with a real number. then Bob fills one. Then Alice and so on so forth ...
39
votes
2answers
1k 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 ...
39
votes
4answers
823 views
Combinatorics Problem: Box Riddle
A huge group of people live a bizarre box based existence. Every day, everyone changes the box that they're in, and every day they share their box with exactly one person, and never share a box with ...
36
votes
4answers
2k 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 ...
36
votes
7answers
783 views
Problems regarding $\{x_n \}$ defined by $x_1=1$; $x_n$ is the smallest distinct natural number such that $x_1+…+x_n$ is divisible by $n$.
Let me denote a sequence of distinct natural numbers by $x_n$ whose terms are determined as follows:
$x_1$ is $1$ and $x_2$ is the smallest distinct natural number $n$ such that $x_1+x_2$ is divisible ...
36
votes
5answers
1k views
Solutions to $\binom{n}{5} = 2 \binom{m}{5}$
In Finite Mathematics by Lial et al. (10th ed.), problem 8.3.34 says:
On National Public Radio, the Weekend Edition program posed the
following probability problem: Given a certain number of ...
34
votes
2answers
499 views
Counting trails in a triangular grid
A triangular grid has $N$ vertices, labeled from 1 to $N$. Two vertices $i$ and $j$ are adjacent if and only if $|i-j|=1$ or $|i-j|=2$. See the figure below for the case $N = 7$.
How many trails ...
34
votes
3answers
839 views
Putting many disks in the unit square
Consider a square of side equal to $1$. Prove that we can place inside the square a finite number of disjoint circles, with different radii of the form $1/k$ with $k$ a positive integer, such that ...
32
votes
4answers
695 views
Strange Patience Game
I read about this game as a kid, but my maths was never up to solving it:
The score starts at zero. Take a shuffled pack of cards and keep dealing face up until you reach the first Ace, at which the ...
31
votes
3answers
1k views
What is the shortest string that contains all permutations of an alphabet?
What is the shortest string $S$ over an alphabet of size $n$, such that every permutation of the alphabet is a substring of $S$?
I thought of this problem while reading a open problem on shortest ...
30
votes
4answers
2k views
The 9 Billion Names of God
TLDR; I go on a math adventure and get overwhelmed :)
Some background:
My maths isn't great (I can't read notation) but I'm a competent programmer and reasonable problem solver. I've done the first ...
30
votes
1answer
1k 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 ...
29
votes
2answers
1k views
Identity for convolution of central binomial coefficients
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 ...
29
votes
5answers
1k 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 ...
28
votes
2answers
835 views
Is there a clever solution to this elementary probability/combinatorics problem?
My friend was asked the following problem in an interview a while back, and it has a nice answer, leading me to believe that there is an equally nice solution.
Suppose that there are 42 bags, ...
28
votes
3answers
404 views
Guessing a subset of $\{1,…,N\}$
I pick a random subset $S$ of $\{1,\ldots,N\}$, and you have to guess what it is. After each guess $G$, I tell you the number of elements in $G \cap S$. How many guesses do you need?
27
votes
3answers
843 views
A combinatorial proof of $n^n(n+2)^{n+1}>(n+1)^{2n+1}$?
The statement is, of course, simply that the sequence $\left(1+\frac{1}{n}\right)^n$ is increasing.
Since the numbers $n^m$ have quite natural combinatorial interpretations, it makes me wonder if a ...
27
votes
2answers
1k 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 ...
25
votes
1answer
831 views
Dividing a square into equal-area rectangles
How many ways are there to tile an $n\times n$ square with exactly $n$ rectangles, each of which has integer sides and area $n$?
The sequence $C(n)$ begins 1, 2, 2, 9, 2, 46, 2, 250, 37. Clearly ...
24
votes
2answers
346 views
Can a collection of points be recovered from its multiset of distances?
Consider $n$ distinct points $x_1,\dots,x_n$ on $\mathbb{R}$. Associated to these points is the multiset of all distances $d(x_i,x_j)$ between two points. Suppose one is only handed this multiset (you ...
24
votes
1answer
501 views
Expiring coupon collector's problem
The well-studied coupon collector's problem asks, given $N$ different coupons from which coupons are being drawn with equal probability and with replacement:
How many coupons do you expect to need ...
23
votes
4answers
1k 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$, ...
23
votes
5answers
287 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)}}$$
23
votes
6answers
7k views
How many triangles are there?
The question is how many triangles are there in the following picture?
I have thought to solve it by creating a formula based on the angles of the lines starting from the bottom of each side. I ...
22
votes
3answers
418 views
Find the number of pairs of positive integers $(a, b)$ such that $a!+b! = a^b$
How many pairs of positive integers $(a, b)$ such that $a!+b! = a^b$?
A straight forward brute-force reveals that $(2,2)$ and $(2,3)$ are solutions and this seems to be the only possible solutions, I ...
22
votes
1answer
429 views
Six Frogs - Puzzle
I had come across a puzzle:
The six educated frogs in the illustration are trained to reverse their order, so that their numbers shall read 6, 5, 4, 3, 2, 1, with the blank square in its ...
22
votes
2answers
2k views
How do I count the subsets of a set whose number of elements is divisible by 3? 4?
Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that
$\displaystyle \sum_{k=0}^{n} {n ...
22
votes
2answers
416 views
Is the Maclaurin series expansion of $\sin x$ related to the inclusion-exclusion principle?
When I see the alternating signs in the infinite series expansion of $\sin x$, I'm reminded of the inclusion-exclusion principle. Could there be any way to visualize it in such a way?
Also, is there ...
21
votes
15answers
2k 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 ...
21
votes
2answers
606 views
How to prove that the number 1!+2!+3!+…+n! is never square?
How to prove that the number 1!+2!+3!+...+n! is never square?
I was told to count permutations but I cannot figure out what we are permuting.... Thanks!
21
votes
6answers
947 views
Proofs of $\lim\limits_{n \to \infty} \left(H_n - 2^{-n} \sum\limits_{k=1}^n \binom{n}{k} H_k\right) = \log 2$
Let $H_n$ denote the $n$th harmonic number; i.e., $H_n = \sum\limits_{i=1}^n \frac{1}{i}$. I've got a couple of proofs of the following limiting expression, which I don't think is that well-known: ...
21
votes
3answers
901 views
Guaranteed Checkmate with Rooks in High-Dimensional Chess
Given an infinite (in all directions), $n$-dimensional chess board $\mathbb{Z^n}$, and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite ...
21
votes
1answer
573 views
Purely combinatorial proof that$ (e^x)' = e^x$
At the beginning of Week 300 of John Baez's blog,
Baez gives a proof that the "number" of finite sets (more specifically, the cardinality of the groupoid of all finite sets, where an object in the ...
21
votes
3answers
366 views
Permutations with restriction
We have $n$ types of objects, and the number of objects of type $i$ is $a_i$, $1\leq i\leq n$.
What is the number of permutation of the $\sum_{i=1}^n a_i$ objects, if no two objects of the same type ...
20
votes
8answers
922 views
why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$
why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$?
I know this is well-known. But how to prove it rigorously? Even mathematical induction does not seem so straight-forward.
...
20
votes
6answers
628 views
How are we able to calculate specific numbers in the Fibonacci Sequence?
I was reading up on the Fibonacci Sequence when I've noticed some were able to calculate specific numbers. So far I've only figured out creating an array and counting to the value, which is incredibly ...
20
votes
6answers
1k 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 ...
20
votes
3answers
810 views
An example of a real-world map that is not 4-colourable?
The four-colour mapping theorem states that all maps can be four-coloured (adjacent regions receive distinct colours, and four different colours are used in total). However, the technical definition ...
20
votes
2answers
932 views
Proving $\prod_{j=1}^n \left(4-\frac2{j}\right)$ is an integer
How do I show that the product $$\biggl(4 - \frac21\biggr) \cdot \biggl(4 - \frac22\biggr) \cdot \biggl(4 - \frac23\biggr) \cdots \biggl(4 - \frac2{n}\biggr)$$ is an integer for any $n \in ...
20
votes
2answers
552 views
a problem from 1977 all Soviet Union Mathematical Olympiad
Seven dwarfs are sitting at a round table. Each has a cup, and some cups contain milk. Each dwarf in turn pours all his milk into the other six cups, dividing it equally among them. After the seventh ...
19
votes
6answers
1k views
Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$
Let $m,n\ge 1$ be two integers. Prove that
$$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$
where $\delta_{mn}$ stands for the Kronecker's delta.
Note: I put the tag "linear ...
