Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

Filter by
Sorted by
Tagged with
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 ...
Richard's user avatar
  • 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 ...
Sergei Ivanov's user avatar
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 ...
Michael Hardy's user avatar
30 votes
1 answer
981 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 ...
Simon Mauras's user avatar
30 votes
1 answer
935 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&...
Fedor Petrov's user avatar
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 ...
Per Alexandersson's user avatar
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 ...
Fedor Petrov's user avatar
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 ...
Anthony Labarre's user avatar
29 votes
7 answers
3k views

Why are we interested in permutahedra, associahedra, cyclohedra, ...?

The following families of polytopes have received a lot of attention: permutahedra, associahedra, cyclohedra, ... My question is simple: Why? As I understand, at least the latter two were ...
M. Winter's user avatar
  • 12.5k
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+...
Roland Bacher's user avatar
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 $...
Fedor Petrov's user avatar
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 ...
Denis Serre's user avatar
  • 51.5k
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 ...
Liviu Nicolaescu's user avatar
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 ...
Nicholas Proudfoot's user avatar
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 ...
Christian Gaetz's user avatar
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 ...
Gary Kennedy's user avatar
29 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 ...
Debanjan Chanda's user avatar
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 ...
Gil Kalai's user avatar
  • 24.2k
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 ...
T. Amdeberhan's user avatar
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
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 ...
DoubleJay's user avatar
  • 2,353
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?
Pratik Poddar's user avatar
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(...
T. Amdeberhan's user avatar
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 ...
Mostafa's user avatar
  • 4,454
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....
Izar Urdin's user avatar
28 votes
11 answers
2k views

Combinatorial databases

At one point, I remember being excited by seeing the website Encyclopedia of Combinatorial Structures as an extension of Sloane's Online Integer Sequence Database site. Unfortunately, the site (ECS) ...
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 ...
Clark Lyons's user avatar
28 votes
6 answers
12k 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 ...
Emile Okada's user avatar
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 ...
john mangual's user avatar
  • 22.6k
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 ...
Timothy Chow's user avatar
  • 78.1k
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 ...
John Watrous's user avatar
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 ...
Seva's user avatar
  • 22.8k
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
2 answers
3k views

Is there a "finitary" solution to the Basel problem?

Gabor Toth's Glimpses of Algebra and Geometry contains the following beautiful proof (perhaps I should say "interpretation") of the formula $\displaystyle \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} ...
Qiaochu Yuan's user avatar
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 ...
Mare's user avatar
  • 25.8k
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 ...
Will Sawin's user avatar
  • 135k
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 $...
Igor Pak's user avatar
  • 16.3k
28 votes
3 answers
872 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,...
Ian Wanless's user avatar
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 ...
Harry Altman's user avatar
  • 2,535
27 votes
5 answers
8k 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 ...
Alex R.'s user avatar
  • 4,902
27 votes
19 answers
25k 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 ...
27 votes
2 answers
2k views

Is there a name for a family of finite sequences that block all infinite sequences?

Let ${\bf N}^\omega = \bigcup_{m=1}^\infty {\bf N}^m$ denote the space of all finite sequences $(N_1,\ldots,N_m)$ of natural numbers. For want of a better name, let me call a family ${\mathcal T} \...
Terry Tao's user avatar
  • 108k
27 votes
4 answers
3k views

Alice and Bob playing on a circle

I want to solve this problem: Let there be $n \ge 2$ points around a circle. Alice and Bob play a game on the circle. They take moves in turn with Alice beginning. At each move: Alice takes one ...
F.Joh's user avatar
  • 379
27 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)...
Adi Ostrov's user avatar
27 votes
5 answers
7k views

Probability of a Random Walk crossing a straight line

Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the ...
TMM's user avatar
  • 713
27 votes
5 answers
2k views

What (if anything) happened to Viennot's theory of Heaps of pieces?

In 1986 G.X. Viennot published "Heaps of pieces, I : Basic definitions and combinatorial lemmas" where he developed the theory of heaps of pieces, from the abstract: a geometric interpretation of ...
Gjergji Zaimi's user avatar
27 votes
1 answer
1k views

What is the name of this combinatorial object and place to read about it?

The title is admittedly noninformative but I could not figure out how to squeeze into it the description of the object I am interested in. Judge by yourself. I have an alphabet on $d$ symbols. I want ...
მამუკა ჯიბლაძე's user avatar
27 votes
4 answers
3k views

Genealogy of the Lagrange inversion theorem

A wonderful piece of classic mathematics, well-known especially to combinatorialists and to complex analysis people, and that, in my opinion, deserves more popularity even in elementary mathematics, ...
Pietro Majer's user avatar
  • 56.5k
27 votes
1 answer
2k views

Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...
user19906's user avatar
  • 419
27 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 ...
Frieder Ladisch's user avatar

1
3 4
5
6 7
211