All Questions
Tagged with combinatorics or co.combinatorics
11,024 questions
41
votes
0
answers
1k
views
Is there anything to the obvious analogy between Joyal's combinatorial species and Goodwillie calculus?
Combinatorial species and calculus of functors both take the viewpoint that many interesting functors can be expanded in a kind of Taylor series. Many operations familiar from actual calculus can be ...
- 63.9k
40
votes
7
answers
18k
views
How many surjections are there from a set of size n?
It is well-known that the number of surjections from a set of size n to a set of size m is quite a bit harder to calculate than the number of functions or the number of injections. (Of course, for ...
- 29k
40
votes
9
answers
255k
views
The factorials of -1, -2, -3, … [closed]
Well, $n!$ is for integer $n < 0$ not defined — as yet.
So the question is:
How could a sensible generalization of the factorial for negative integers look like?
Clearly a good generalization ...
- 1,054
40
votes
5
answers
3k
views
Reference on Persistent Homology
I will be teaching a course on algebraic topology for MSc students and this semester, unlike previous ones where I used to begin with the fundamental group, I would like to start with ideas of ...
- 3,173
40
votes
9
answers
8k
views
What proportion of chess positions that one can set up on the board, using a legal collection of pieces, can actually arise in a legal chess game?
Many chess positions that one may easily set up on a chess board
are impossible to achieve in a game of legal moves. For example,
among the impossible situations would be:
A position in which both ...
- 236k
40
votes
1
answer
2k
views
Orders of products of permutations
Let $p$ be a prime, $n\gg p$ not divisible by $p$ (say, $n>2^{2^p}$). Are there two permutations $a, b$ of the set $\{1,...,n\}$ which together act transitively on $\{1,2,...,n\}$ and such that all ...
user6976
40
votes
1
answer
1k
views
Do runs of every length occur in this sequence?
This is a repost from user r.e.s's unsolved Math Stack Exchange question: Do runs of every length occur in this string? That question was derived from my original question on the subject: Does this ...
- 391
40
votes
1
answer
2k
views
Curious $q$-analogues
Consider the Fibonacci polynomials
$$F_n (x) = \sum_{j = 0}^{\left\lfloor {n/2} \right\rfloor }\binom{n-j}{j} x^{n - 2j} $$
and the Lucas polynomials
$$L_n (x) = \sum_{j = 0}^{\left\lfloor {n/2} \...
- 5,622
39
votes
2
answers
2k
views
Random sequence of integers in $\{1, 2, \dots, n \}$ which is "everywhere probably increasing" - how long can it be?
Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$.
Fix $r \...
- 1,927
39
votes
3
answers
3k
views
Is there a finite family of functions such that the max of any two functions can be dominated by a third?
Is it true that for every $t$ there is an $n$ and there exists a finite function
family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different
values) and for any $f_1, \ldots, ...
- 18.9k
39
votes
5
answers
3k
views
Does there exist a comprehensive compilation of Erdos's open problems?
Fan Chung and Ron Graham's book Erdos on Graphs: His Legacy of Unsolved Problems (A. K. Peters, 1998) collects together all of Erdos's open problems in graph theory that they could find into a single ...
- 82.7k
39
votes
9
answers
3k
views
The shortest path in first passage percolation
Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)
Consider a square planar grid. (The vertices are pair of ...
- 24.7k
39
votes
5
answers
2k
views
Is every path with this property shorter than another path with the same endpoints?
Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where
$$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$
I found that if the path $P$ satisfies:
...
- 1,997
39
votes
3
answers
2k
views
Chromatic number of the hyperbolic plane
A notorious problem in combinatorics is the following:
If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required?
This ...
- 7,857
39
votes
5
answers
6k
views
Factorials in Pascal's triangle
I asked this question of Keith Conrad, and he suggested that I try posting here. One of my students observed that the only instances of factorials in the interior of Pascal's triangle are $\binom{4}{...
- 391
39
votes
2
answers
1k
views
How close can one get to the missing finite projective planes?
This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ ...
- 85.6k
38
votes
6
answers
3k
views
Show that this ratio of factorials is always an integer
show the formula always gives an integer
$$\frac{(2m)!(2n)!}{m!n!(m+n)!}$$
I don't remember where I read this problem, but it said this can be proved using a simple counting argument (like observing ...
- 383
38
votes
6
answers
4k
views
Number of real roots of 0,1 polynomial
$0,1$ polynomial has coefficients from $\{0,1\}$.
I investigate the number of roots in such polynomials.
We are talking about real roots, and multiples are counted only once.
It was found numerically ...
- 512
38
votes
2
answers
5k
views
Is the set of primes "translation-finite"?
The definition in the title probably needs explaining. I should say that the question itself was an idea I had for someone else's undergraduate research project, but we decided early on it would be ...
- 25.8k
38
votes
1
answer
4k
views
Updates to Stanley's 1999 survey of positivity problems in algebraic combinatorics?
In 1999, Richard Stanley wrote a very nice survey on open problems in algebraic combinatorics, with a specific focus on positivity, called "Positivity problems and conjectures in algebraic ...
38
votes
4
answers
2k
views
A family of words counted by the Catalan numbers
In recent work with Michael Albert and Nik Ruškuc, a family of words has arisen which is counted by the Catalan numbers. I've looked at Richard Stanley's Catalan exercises in EC2 and his Catalan ...
- 2,339
38
votes
3
answers
4k
views
finding the parity of a permutation in little space
Suppose we have a permutation $\pi$ on $1,2,\ldots,n$ and want to determine the parity (odd or even) of $\pi$.
The standard method is find the cycles of $\pi$ and recall that the parity of $\pi$ ...
- 37.7k
37
votes
2
answers
3k
views
A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself
Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
- 1,730
37
votes
2
answers
4k
views
How to find Erdős' treasure trove?
The renowned mathematician, Paul Erdős, has published more than 1500 papers in various branches of mathematics including discrete mathematics, graph theory, number theory, mathematical analysis, ...
37
votes
2
answers
4k
views
Is there any superstable configuration in the game of life?
This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration.
There are numerous configurations in the game of life that are known to be stable-...
- 236k
37
votes
4
answers
2k
views
"Circular" domination in ${\mathbb R}^4$
The following problem is related to (and motivated by) the first open case of this MO question. It is difficult to believe that this is a hard problem; and yet, I do not have a solution.
For two ...
- 23k
37
votes
2
answers
3k
views
Rooks in three dimensions
Given is an infinite 3-dim chess board and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite number of moves?
(In 3-dimensional chess rooks ...
- 541
37
votes
2
answers
2k
views
A group-theoretic perspective on Frankl's union closed problem
Here is a group theoretic phrasing of a special case of the union closed conjecture:
Question: Given a finite group $G$, is there an element of prime power order which is contained in at most half ...
- 85.6k
37
votes
3
answers
2k
views
How to prove the identity $L(2,(\frac{\cdot}3))=\frac2{15}\sum\limits_{k=1}^\infty\frac{48^k}{k(2k-1)\binom{4k}{2k}\binom{2k}k}$?
For the Dirichlet character $\chi(a)=(\frac a3)$ (which is the Legendre symbol), we have
$$L(2,\chi)=\sum_{n=1}^\infty\frac{(\frac n3)}{n^2}=0.781302412896486296867187429624\ldots.$$
Note that this ...
- 15.6k
37
votes
1
answer
1k
views
Errata for Fulton's "Young tableaux"
Fulton's Young tableaux is one of the best texts on the subject, one which I
often recommend and cite for reference. Unlike Fulton/Lang and
Fulton/Harris,
it is neither an early-dawn draft nor a ...
36
votes
21
answers
6k
views
Generalizations of Planar Graphs
This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...
- 24.7k
36
votes
7
answers
7k
views
Help with a double sum, please
Here is a double series I have been having trouble evaluating:
$$S=\sum_{k=0}^{m}\sum_{j=0}^{k+m-1}(-1)^{k}{m \choose k}\frac{[2(k+m)]!}{(k+m)!^{2}}\frac{(k-j+m)!^{2}}{(k-j+m)[2(k-j+m)]!}\frac{1}{2^{k+...
- 825
36
votes
3
answers
4k
views
the following inequality is true，but I can't prove it
The inequality is
\begin{equation*}
\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)
\end{equation*}
for all integer $d\geq 1$. I use computer to verify ...
- 363
36
votes
8
answers
3k
views
Examples of errors in computational combinatorics results
I would like to collect examples of errors in published numerical results in computational combinatorics: where a result (typically a counting of some objects, or an extremal quantity within some ...
36
votes
2
answers
13k
views
Mean minimum distance for N random points on a one-dimensional line
Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. I was wondering if there was a simple/straightforward method (not involving long ...
- 811
36
votes
2
answers
3k
views
The coupon collector's earworm
[EDITED mostly to report on the answer by Kevin Costello
(and to improve the gp code at the end)]
I thank Nicolas Dupont for the following question
(and for permission to disseminate it further):
...
- 79.9k
36
votes
4
answers
10k
views
Do actual Sudoku puzzles have a unique rational solution?
Here is a question in the intersection of mathematics and sociology. There is a standard way to encode a Sudoku puzzle as an integer programming problem. The problem has a 0-1-valued variable $a_{i,...
- 56.6k
36
votes
1
answer
3k
views
Collatz conjecture for numbers of th form $2^n +1$
Everybody has heard of the Collatz conjecture and it is a nice programming exercise to write a function, that calculates for a given number $n$ the number of iterations it takes until one reaches $1$. ...
- 11.1k
36
votes
2
answers
1k
views
Is there a combinatorial reason that the (-1)st Catalan number is -1/2?
The $n$th Catalan number can be written in terms of factorials as
$$ C_n = {(2n)! \over (n+1)! n!}. $$
We can rewrite this in terms of gamma functions to define the Catalan numbers for complex $z$:
$$...
- 14k
36
votes
2
answers
1k
views
Is there an analog of Sperner's lemma for the Hopf invariant?
Recall that Sperner's lemma is essentially a combinatorial version of the topological statement "A map from $S^n$ to $S^n$ with degree one cannot be nullhomotopic."
My question is, does there exist ...
- 8,493
36
votes
0
answers
2k
views
3-colorings of the unit distance graph of $\Bbb R^3$
Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$.
Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\alpha,...
- 17k
35
votes
12
answers
4k
views
Open questions about posets
Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
35
votes
3
answers
3k
views
Does the hypergraph structure of the set of subgroups of a finite group characterize isomorphism type?
Question
Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ ...
- 483
35
votes
4
answers
2k
views
Graph containing all trees?
Consider graphs on $n$ nodes. I am trying to find a graph $G$ that contains all $n$-node trees as sub-graphs but contains as few edges as possible. The complete graph $K_n$ suffices, but can we get ...
- 3,979
35
votes
5
answers
3k
views
Small simplicial complexes with torsion in their homology?
Fix a prime $p$. What is the smallest integer $n$ so that there is a simplicial complex on $n$ vertices with $p$-torsion in its homology?
For example, when $p=2$, there is a complex with 6 vertices (...
- 4,254
35
votes
1
answer
3k
views
"The Two Sheriffs" puzzle
This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler.
Two sheriffs in neighboring towns are on the track of a killer, in a
case involving eight ...
- 12.3k
35
votes
3
answers
6k
views
Is there a good argument for why you can't place 4 queens which cover a chessboard?
It has been known since the 1850's (or even much earlier) that 5 queens could be placed on an 8*8
chessboard so that every square on the board lies in the same row, column, or diagonal as at least ...
- 6,215
35
votes
4
answers
4k
views
How does this relationship between the Catalan numbers and SU(2) generalize?
This is a question, or really more like a cloud of questions, I wanted to ask awhile ago based on this SBS post and this post I wrote inspired by it, except that Math Overflow didn't exist then.
As ...
- 118k
35
votes
6
answers
2k
views
Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime
This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...
- 353
35
votes
5
answers
4k
views
Cliques, Paley graphs and quadratic residues
A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...
- 703