All Questions
Tagged with combinatorics or co.combinatorics
11,024 questions
31
votes
1
answer
2k
views
Navigating $\mathbb{Z}/p\mathbb{Z}$
$\newcommand{\Z}{\mathbb{Z}}$Let's consider a silly-looking question first. Consider $\Z/p\Z$. Say I am allowed the two operations $x\mapsto x+1$ and $x\mapsto 2x$. Then, starting from $0$, I can ...
- 20.2k
30
votes
2
answers
2k
views
When does doubling the size of a set multiply the number of subsets by an integer?
For natural numbers $m, r$, consider the ratio of the number of subsets of size $m$ taken from a set of size $2(m+r)$ to the number of subsets of the same size taken from a set of size $m+r$:
$$R(m,r)...
- 2,902
30
votes
8
answers
3k
views
Cryptomorphisms
I am curious to collect examples of equivalent axiomatizations of mathematical structures. The two examples that I have in mind are
Topological Spaces. These can be defined in terms of open sets, ...
30
votes
2
answers
1k
views
Minimum number of $|\cdot|$ operations necessary to express $\max$
For two variables, their maximum
$\max\{x_1,x_2\}$ can be expressed using one $|\cdot|$ operation:
$$
\max\{x_1,x_2\} = \frac12(x_1+x_2+|x_1-x_2|).
$$
For $3$ variables, it seems fairly clear that ...
- 6,541
30
votes
3
answers
8k
views
Status of the 196 conjecture?
A palindrome is a number which remains the same when reversing it, for instance 34143. Now pick an arbitrary number, say 26: then 26+62=88 is a palindrome. If the number was 57, then 57+75=132 is not ...
- 1,363
30
votes
2
answers
3k
views
An unfair marriage lemma
I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:
Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
- 32.4k
30
votes
1
answer
1k
views
Rearrangements that never change the value of a sum
I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...
30
votes
1
answer
10k
views
Reconstructing the argument that yields Graham's number
Graham's number achieved a kind of cult status, thanks to Martin Gardner, as the largest finite number appearing in a mathematical proof. (It may no longer hold that record, but that is not my concern ...
- 82.7k
30
votes
1
answer
2k
views
Is there an accessible exposition of Gelfand-Tsetlin theory?
I'm hoping to start an undergraduate on a project that involves understanding a bit of Gelfand-Tsetlin theory, and have been tearing my hair out looking for a good reference for them to look at. ...
- 44.7k
30
votes
1
answer
3k
views
There are $n$ horses. At a time only $k$ horses can run in a single race. What is the minimum number of races required to find the $m$ fastest horses?
The following question was asked and not (yet) answered at Math Stack Exchange.
There are $n$ horses. At a time only $k$ horses can run in the single race. What is the minimum number of races ...
- 309
30
votes
1
answer
1k
views
Sum over 0-1 matrices
I stumbled across the following formula when working on a research problem in theoretical computer science. I am looking for a simple proof of it, or any idea which might prove useful.
I checked its ...
- 303
30
votes
1
answer
942
views
partition of infinite word onto permitted words
Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, $0<c&...
- 109k
30
votes
1
answer
1k
views
Mysterious symmetry - in search for a bijection
I have a mysterious symmetry that I have not managed to prove.
First some definitions (see picture below)
Fix a partition that fit in a staircase shape with $n$ rows.
There are $Catalan(n)$ such ...
- 15.8k
30
votes
4
answers
1k
views
Resolution of multiple edges
Given $k$ girls, they are given $kn$ balls so that each girl has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each colour. Two girls may exchange the balls (1 ball for ...
- 109k
30
votes
1
answer
3k
views
An edge partitioning problem on cubic graphs
Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
- 1,164
29
votes
7
answers
8k
views
Solving NP problems in (usually) Polynomial time?
Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
- 2,383
29
votes
1
answer
2k
views
Reason for breakdown of a nice binomial identity
One has the nice identities
$${xy\choose 1}={x\choose 1}{y\choose 1},$$
$${xy+1\choose 2}={x+1\choose 2}{y+1\choose 2}+{x\choose 2}{y\choose 2}$$
and
$${xy+2\choose 3}={x+2\choose 3}{y+2\choose 3}+4{x+...
- 17.9k
29
votes
3
answers
4k
views
Roots of permutations
Consider the equation $x^2=x_0$ in the symmetric group $S_n$, where $x_0\in S_n$ is fixed. Is it true that for each integer $n\geq 0$, the maximal number of solutions (the number of square roots of $...
- 109k
29
votes
6
answers
14k
views
Algorithms for calculating R(5,5) and R(6,6)
Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said:
Suppose aliens invade the earth and threaten to obliterate it in a year's time unless ...
- 393
29
votes
6
answers
2k
views
Combinatorial Morse functions and random permutations
This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function ...
- 34.7k
29
votes
6
answers
7k
views
Integers in a triangle, and differences
I read about the following puzzle thirty-five years ago or so, and I still do not know the answer.
One gives an integer $n\ge1$ and asks to place the integers $1,2,\ldots,N=\frac{n(n+1)}{2}$ in a ...
- 52.3k
29
votes
2
answers
2k
views
Have you seen my matroid?
Let $M(n,k)$ be the matroid on the ground set $\{\pm 1,\ldots,\pm n\}$ for which a set is independent if and only if it contains at most $k$ pairs $\pm i$. Note that the signed permutation group (the ...
- 2,537
29
votes
2
answers
1k
views
Determining if a rational function has a subtraction-free expression
This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class.
Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
- 2,753
29
votes
3
answers
1k
views
Stirling number identity via homology?
This is a question about the well-known formula involving both types of Stirling numbers:
$\sum_{k=1}^{\infty}(-1)^{k}S(n,k)c(k,m)=0$,
where $S(n,k)$ is the number of partitions of an $n$-element set ...
- 533
29
votes
1
answer
2k
views
High-Dimensional Analogs of Polygon Spaces
[Edit: I had a mistake in the numerology (took d=6,5 instead of d=5,4). Edit: I mistakenly identified my mistake, it is 6,5 but I got the indices shifted by one.]
Background: Polygon spaces
Given a ...
- 24.7k
29
votes
0
answers
665
views
A conjecture about inclusion–exclusion
$\newcommand\calF{\mathcal{F}}
\def\cupdot {\stackrel{\bullet}{\cup}}
\def\minusdot {\stackrel{\bullet}{\setminus}}$This post presents a conjecture that we have with some colleagues. It is about ...
- 391
29
votes
0
answers
1k
views
Linking formulas by Euler, Pólya, Nekrasov-Okounkov
Consider the formal product
$$F(t,x,z):=\prod_{j=0}^{\infty}(1-tx^j)^{z-1}.$$
(a) If $z=2$ then on the one hand we get Euler's
$$F(t,x,2)=\sum_{n\geq0}\frac{(-1)^nx^{\binom{n}2}}{(x;x)_n}t^n,$$
on the ...
- 43.2k
29
votes
0
answers
3k
views
Why do polytopes pop up in Lagrange inversion?
I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
28
votes
5
answers
9k
views
Erdos Conjecture on arithmetic progressions
Introduction:
Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.
Question:
I ...
- 4,952
28
votes
4
answers
9k
views
Is 8 the largest cube in the Fibonacci sequence?
Can you prove that 8 is the largest cube in the Fibonacci sequence?
- 431
28
votes
3
answers
3k
views
Sum over permutations is 1
This might be easy, but let's see.
Question 1. If $\mathfrak{S}_n$ is the group of permutations on $[n]$, then is the following true?
$$\sum_{\pi\in\mathfrak{S}_n}\prod_{j=1}^n\frac{j}{\pi(1)+\pi(...
- 43.2k
28
votes
5
answers
2k
views
Visibility of vertices in polyhedra
Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ is an interior point of $P$. Is it true that $X$ can see at least one vertex of $P$? More ...
- 4,484
28
votes
1
answer
2k
views
How can I improve my formal definitions?
I am a Software Architect and not very familiarized with standard notation in mathematics. Nonetheless, I would like to write a paper explaining a normalization of a computing model for expert systems....
- 401
28
votes
6
answers
1k
views
Are there always more conjugacy classes in the kernel of a morphism to $Z_2$ than not?
Let $G$ be a finite group and let $\phi:G\to Z_2$ be a homomorphism to the group with two elements. Is it always the case that there are more conjugacy classes in the kernel of $\phi$ than conjugacy ...
- 513
28
votes
6
answers
2k
views
Random Alternating Permutations
An alternating permutation of {1, ..., n} is one were π(1) > π(2) < π(3) > π(4) < ... For example: (24153) is an alternating permutation of length 5.
If $E_n$ is the number of alternating ...
- 22.8k
28
votes
3
answers
2k
views
Is every positive integer the permanent of some 0-1 matrix?
In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely:
Is it true that for every positive integer $k$ there exists a balanced ...
- 82.7k
28
votes
6
answers
2k
views
How fast are a ruler and compass?
This may be more of a recreational mathematics question than a research question, but I have wondered about it for a while. I hope it is not inappropriate for MO.
Consider the standard assumptions ...
- 513
28
votes
1
answer
2k
views
Multiplying all the elements in a group
Let $G = \{ g_i | i = 1, ...,n \}$ be a finite group and denote by $G!$ the multiset consisting of all the products of all different elements of $G$ in any order, that is
$$ G! = [ \prod_i g_{\sigma(i)...
- 943
28
votes
2
answers
3k
views
Erdős-Szekeres for first differences
The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$
real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however,
that we want to find a subsequence which is not ...
- 23k
28
votes
6
answers
2k
views
Multiplying by irrational numbers in combinatorial problems
This is getting no attention on stackexchange.
Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$.
It had escaped my attention until last week, ...
28
votes
1
answer
1k
views
Number of irreducible representations of a finite group over a field of characteristic 0
Let $G$ be a finite group and $K$ a field with $\mathbb{Q} \subseteq K \subseteq \mathbb{C}$.
For $K=\mathbb{C}$ the number of irreducible representations of $KG$ is equal to the number of conjugacy ...
- 26.5k
28
votes
4
answers
2k
views
Matrices: characterizing pairs $(AB, BA)$
Let $A$ be an $m\times n$-matrix and $B$ an $n \times m$-matrix over the same field. Consider the matrices $C=AB$ and $D=BA$. It is probably well known (and not difficult to show) that the only ...
- 6,919
28
votes
1
answer
2k
views
How many polynomial Morse functions on the sphere?
Let $f$ be a homogeneous polynomial of degree $d$ in $n$ variables. Restricted to the unit sphere $S^{n-1}$, it might or might not be a Morse function.
If $f$ is a Morse function of degree $1$, you ...
- 148k
28
votes
3
answers
2k
views
When does a graph underlie the Hasse diagram of a poset?
For any finite poset $P=(X,\leq)$ there is a graph $G$ underlying its Hasse diagram $H=(X,\lessdot)$, so that $V(G)=X$ and $E(G)=\{\{u,v\}:u\lessdot v\}$. With that said, is it possible to ...
- 2,506
28
votes
3
answers
1k
views
Inequality for hook numbers in Young diagrams
Consider a Young diagram $\lambda = (\lambda_1,\ldots,\lambda_\ell)$. For a square $(i,j) \in \lambda$, define hook numbers $h_{ij} = \lambda_i + \lambda_j' -i - j +1$ and complementary hook numbers $...
- 17k
28
votes
3
answers
969
views
Ordering subsets of the cyclic group to give distinct partial sums
Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums $a_1,...
- 281
28
votes
1
answer
1k
views
Are Minkowski sums of upward closed "convex" sets in $\mathbb{N}^k$ still "convex"? (WAS: Comparing mana costs in Magic: The Gathering)
This was originally a question about comparing mana costs in Magic: The Gathering, but it's turned into a question about Minkowski sums of upward-closed convex sets in $\mathbb{N}^k$. The original ...
- 2,585
28
votes
2
answers
1k
views
Is this graph polynomial known? Can it be efficiently computed?
I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...
- 281
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
27
votes
19
answers
26k
views
Good combinatorics textbooks for teaching undergraduates?
Hello, can anyone recommend good combinatorics textbooks for undergraduates? I will be teaching a 10-week course on the subject at Stanford, and I assume that the students will be strong and motivated ...