# 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.

6,443 questions

**28**

votes

**5**answers

1k views

### What's the motivation of entropy as a combinatorical tool? What problems is it able to solve?

I am interested in using Shannon's entropy in combinatorics. It is often presented with a motivation of how much information can be passed, but assume I am not interested in that, I want to understand ...

**28**

votes

**1**answer

8k 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 ...

**28**

votes

**1**answer

778 views

### Vanishing line on Conway's game of life

If the initial state of Conway's game of life is a line of $n \in [0,100]$ alive cells, then it vanishes completely after some steps iff $n \in \{0,1,2,6,14,15,18,19,23,24 \}$. See below for $n=24$.
...

**27**

votes

**9**answers

3k views

### Is the empty graph a tree?

This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed.
The ...

**27**

votes

**8**answers

4k views

### Applications of infinite graph theory

Finite graph theory abounds with applications inside mathematics itself, in computer science, and engineering. Therefore, I find it naturally to do research in graph theory and I also clearly see the ...

**27**

votes

**4**answers

2k views

### In what rigorous sense are Sperner's Lemma and the Brouwer Fixed Point Theorem equivalent?

I understand that one can give a proof of each of these propositions assuming the truth of the other. But this seems a bit squishy to me, since there is a trivial sense in which any two true theorems ...

**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 ...

**27**

votes

**5**answers

2k 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 (...

**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 ...

**27**

votes

**2**answers

1k 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 ...

**27**

votes

**2**answers

2k 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 ...

**27**

votes

**1**answer

1k 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 ...

**27**

votes

**5**answers

4k views

### How many binary operations are associative?

Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each
be ...

**27**

votes

**2**answers

1k views

### A bijection between sets of Young tableaux of two kinds

Assuming that the problem of exhibiting a bijection is not considerd a frivolous pursuit, allow me to ask a question troubling me for some time now.
Let $\lambda \vdash n$ denote the fact that $\...

**27**

votes

**1**answer

1k 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 ...

**27**

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 ...

**27**

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 ...

**27**

votes

**2**answers

975 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 ...

**26**

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(...

**26**

votes

**3**answers

4k views

### Is the sum $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0?$

I am trying to prove $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$. This inequality has been verified by computer for $k\le40$.
Some clues that might work (kindly provided by ...

**26**

votes

**3**answers

2k 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$ ...

**26**

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 ...

**26**

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 ...

**26**

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 ...

**26**

votes

**3**answers

6k 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 ...

**26**

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 ...

**26**

votes

**5**answers

1k 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, ...

**26**

votes

**3**answers

1k views

### A double grading of catalan numbers

This is something I found in trying to work on Vince Vatter's excellent question. I have no solution, but a much more precise conjecture.
Recall that a rooted planar tree is a rooted tree where, for ...

**26**

votes

**1**answer

651 views

### Why do the adjoint representations of three exceptional groups have the same first eight moments?

For a representation of a compact Lie group, the $n$th moment of the trace of that representation against the Haar measure is the dimension of the invariant subspace of the $n$th tensor power. The ...

**26**

votes

**2**answers

1k views

### Some binomial coefficient determinants

It is well known that for $n>0$
$$d(n)=\det\left(\binom{2i+2j+1}{i+j}\right)_{i,j=0}^{n-1}=1.$$
Computer experiments suggest that more generally
$$d(n,k)=\det\left(\binom{2i+2j+2k+1}{i+j}\right)_{i,...

**26**

votes

**2**answers

1k views

### Slick proof related to choosing points from an interval in order

Choose a point anywhere in the unit interval $[0, 1]$. Now choose a second point from the same interval so that there is one point in each half, $[0, \frac12]$ and $[\frac12, 1]$. Now choose a third ...

**26**

votes

**3**answers

984 views

### What is the probability two random maps on n symbols commute?

It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...

**26**

votes

**2**answers

666 views

### What is the right notion of self-dual (two-dimensional) percolation in R^4?

For a lattice in $\mathbb{R}^2$, if we include each edge independently with probability $p$ (i.e. bond percolation), it is well known that there is a critical probability $0 < p_c < 1$ depending ...

**26**

votes

**2**answers

2k views

### Is there a combinatorial interpretation of the identity $\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m} =4^{-m} \binom{4m+1}{2m}$?

I came across the following combinatorial identity in a paper by Victor H. Moll and Dante V. Manna 'a remarkable sequence of integers'.
$$\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m}
=4^{-m} \...

**26**

votes

**2**answers

462 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**25**

votes

**5**answers

1k 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 ...

**25**

votes

**19**answers

19k 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 ...

**25**

votes

**6**answers

1k views

### For which $n$ is there a permutation such that the sum of any two adjacent elements is a prime?

For which $n$ is it possible to find a permutation of the numbers from $1$ to $n$ such that the sum of any two adjacent elements of the permutation is a prime?
For example: For $n=4$ the permutation $...

**25**

votes

**5**answers

5k 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 ...

**25**

votes

**3**answers

9k views

### Cutting a rectangle into an odd number of congruent pieces

We are interested in tiling a rectangle with copies of single tile (rotations and reflexions are allowed). This is very easy to do, by cutting the rectangle into smaller rectangles.
What happens when ...

**25**

votes

**4**answers

2k views

### $\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$ is a convex function on $[0,+\infty)$?

Let $f(x)=\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$, where $u\in\mathbb{Z}^+$ and $\binom{x}{l}=\frac{x(x-1)\dots(x-l+1)}{l!}$ for all $l\in\mathbb{Z}^+$.
Then can we prove $f(x)$ is a convex ...

**25**

votes

**2**answers

1k 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-...

**25**

votes

**2**answers

601 views

### Convex hull of total orders

Let $n$ be a positive integer and $\prec$ an arbitray total order on $\{1,\dots,n\}$. I associate to this order a vector $v$ with one coordinate for every pair $(i,j)$ s.t. $1\leq i\neq j \leq n$, by ...

**25**

votes

**3**answers

1k views

### A game of plates and olives

This question has its origin in Morse theory (see this paper) but it can be given an entirely elementary and amusing formulation.
The game of plates and olives starts with an empty table and ...

**25**

votes

**1**answer

766 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 $...

**25**

votes

**3**answers

2k views

### How thick is the reciprocal of the squares

There is a unique nonempty set $B$ of nonnegative integers such that
every positive integer can be written in the form
$$b + s^2, b\in B, s\ge0$$
in an even number of ways.
$B = \{0, 1, 2, 3, 5, 7, 8,...

**25**

votes

**3**answers

711 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,...

**25**

votes

**2**answers

947 views

### Is $\varphi(n)/n$ the maximal portion of $n$-cycles in a degree $n$ group?

Let $G$ be a degree $n$ group, i.e., a subgroup of the symmetric group $S_n$. Let $p(G)$ be the number of $n$-cycles in $G$ divided by the size of $G$.
Examples:
If $G$ is a cyclic transitive ...

**25**

votes

**1**answer

1k 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$. ...

**25**

votes

**1**answer

1k views

### Combinatorics of K(Z,2)?

Anybody knows a semi-simplicial model for $K(Z,2)$ having finite number of simplexes in any dimension? With some regular description? I have heard about big activity on triangulating $CP^n$ but this ...