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

795 questions

**23**

votes

**3**answers

2k views

### How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...

**21**

votes

**8**answers

2k views

### Can we disallow finite choice?

When people work with infinite sets, there are some who (with good reason) don't like to use the Axiom of Choice. This is defensible, since the axiom is independent of the other axioms of ZF set ...

**18**

votes

**4**answers

1k views

### What is the minimum N for which there exist N points in the plane that cannot be covered by any number of non-overlapping closed unit discs?

This problem was posed in March 2010 at G4G9 in a talk by the Japanese mathematician Hirokazu "Iwahiro" Iwasawa. He claims there is a simple proof that N > 10, though he did not share it with the ...

**16**

votes

**4**answers

8k views

### Exact formulas for the partition function?

I am curious, what kind of exact formulas exist for the partition function $p(n)$?
I seem to remember an exact formula along the lines $p(n) = \sum_k f(n, k)$, where $f(n, k)$ was some extremely ...

**16**

votes

**1**answer

889 views

### A natural refinement of the $A_n$ arrangement is to consider all $2^n-1$ hyperplanes given by the sums of the coordinate functions. Have you seen this arrangement? Is it completely intractable?

The short version
Here is an extremely natural hyperplane arrangement in $\mathbb{R}^n$, which I will call $R_n$ for resonance arrangement.
Let $x_i$ be the standard coordinates on $\mathbb{R}^n$. ...

**11**

votes

**2**answers

1k views

### Is the Steiner ratio Gilbert–Pollak conjecture still open?

Gilbert-Pollak conjecture on the Steiner ratio: Consider a set $P$ of $n$ points on the euclidean plane. A shortest
network interconnecting $P$ must be a tree, which is called a Steiner minimum ...

**7**

votes

**3**answers

441 views

### Combinatorial interpretation of series reversion coefficients

In a recent paper studying some generalizations of Stirling numbers, my coauthors and I needed the following result:
If $f(x)=\sum_{n \geq 1} a_n x^n/n!$ is a power series with $a_1 \neq 0$, and $g(x)...

**16**

votes

**3**answers

747 views

### $\prod_k(x\pm k)$ in binomial basis?

Let $x$ be an indeterminate and $n$ a non-negative integer.
Question. The following seems to be true. Is it?
$$x\prod_{k=1}^n(k^2-x^2)=\frac1{4^n}\sum_{m=0}^n\binom{n-x}m\binom{n+x}{n-m}(x+2m-n)^...

**16**

votes

**1**answer

727 views

### When is $(q^k-1)/(q-1)$ a perfect square?

Let $q$ be a prime power and $k>1$ a positive integer. For what values of $k$ and $q$ is the number $(q^k-1)/(q-1)$ a perfect square, that is the square of another integer? Is the number of such ...

**16**

votes

**5**answers

656 views

### The smallest disk containing all sides of an $n$-gon

Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect.
What is the radius ...

**13**

votes

**2**answers

594 views

### in search of a transformation between determinants

Motivated by this MO question. Consider the two matrices $A_n$ and $B_n$ with entries $\binom{2j}i$ and $\binom{n+1}{2j-i}$, respectively; for $1\leq i, \,j\leq n$.
I can show $\det A_n=\det B_n=2^{\...

**19**

votes

**1**answer

976 views

### Symmetric polynomial from graphs

Let $g$ be a directed, connected multigraph, on $n$ vertices, without loops.
Define
$$P_g(x_1,\dots,x_n) := Sym\left[ \prod_{(i,j) \in g} (x_i-x_j) \right]$$
where $(i,j)$ is the directed edge ...

**12**

votes

**1**answer

536 views

### Asymptotic growth of antichains in divisibility posets

The following question is inspired by a problem that Erdős used to ask epsilons. It asks to prove that if one chooses a subset of $\lbrace 1,\dots,n\rbrace$ with more than $\lfloor\frac{n+1}{2}\rfloor$...

**11**

votes

**5**answers

2k views

### Simple/efficient representation of Stirling numbers of the first kind

Stirling numbers of the second kind can be expressed by means of a simple hypergeometric (considering $n$ fixed) sum
$$S_2(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n. \qquad (1)$$
...

**10**

votes

**3**answers

1k views

### A problem on a specific integer partition

Let $n$ be a positive integer, we consider partitions of the following form :
$$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that :
$d_{i}\vert n$
$1=d_{1}<d_{2} \le d_{3} \le ... \le d_{r}$...

**9**

votes

**2**answers

1k views

### How to find counterfeit coins by weighing

In one variant of the classic counterfeit coins problem you are given a bag of $n$ numbered but otherwise identical looking coins and a scale and your job is to find which coins are counterfeit. ...

**23**

votes

**2**answers

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

**22**

votes

**8**answers

1k views

### Examples of sequences whose asymptotics can't be described by elementary functions

It is somewhat miraculous to me that even very complicated sequences $a_n$ which arise in various areas of mathematics have the property that there exists an elementary function $f(n)$ such that $a_n =...

**14**

votes

**0**answers

348 views

### The rank of a “triangle-free” matrix

This is a version of the question I asked recently, but the assumptions got now strengthened substantially.
Suppose that $A=(a_{ij})_{1\le i,j\le n}$ is a square matrix with all elements in $\{0,\...

**12**

votes

**0**answers

567 views

### Pointwise (Hadamard) matrix product and the rank

$\DeclareMathOperator{\rk}{rk}$
Suppose that $A$ is a square matrix of order $n$. If, for any polynomials $P$ and $Q$ with $\deg P+\deg Q\le 2$, we have
$$ P(A)\circ Q(A^t) = P(1)Q(1)\, I_n \tag{$\...

**12**

votes

**0**answers

320 views

### On some special spanning trees of grid graphs

I would like to know if there are existing results on the following objects:
spanning trees of a grid graph, with no corridor
where a corridor is a vertex having exactly two neighbors, on opposite ...

**11**

votes

**2**answers

926 views

### Highbrow interpretations of Stirling number reciprocity

The number ${n \choose k}$ of $k$-element subsets of an $n$-element set and the number $\left( {n \choose k} \right)$ of $k$-element multisets of an $n$-element set satisfy the reciprocity formula
$\...

**9**

votes

**1**answer

1k views

### maximum size of intersecting set families

Suppose $n$ is a big number and $k\geq 2$. How many sets $S_1,\dots,S_m\subset [n]$ can we find such that
(1) $|S_i| = k$ for all $i$,
(2) $|S_i\cap S_j| \leq 1$ for all $i\ne j$.
What's the maximum ...

**8**

votes

**0**answers

319 views

### Inversion, Koszul duality, combinatorics and geometry

According to this MO answer Koszul duality is related to operations on generating series;
1) multiplicative inversion for quadratic algebras,
2) compositional inversion for quadratic operads,
3) ...

**7**

votes

**1**answer

193 views

### Partition of 4-tuples

Some $4$-tuples of positive real numbers $(a_1,b_1,c_1,d_1),\dots,(a_n,b_n,c_n,d_n)$ are given, with all $a_i,b_i,c_i,d_i\leq 1$. Can we always partition $\{1,2,\dots,n\}$ into two subsets $X,Y$ so ...

**6**

votes

**3**answers

232 views

### Spectrum of orthogonality graph (2)

The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent.
I am only interested when $4|n$, since otherwise $\Omega(n)$ is ...

**5**

votes

**1**answer

1k views

### What is the largest number of k-element subsets of a given n-element set S such that…

Given a set S of n elements. What is the largest number of k-element subsets of S such that every pair of these subsets has at most one common element?

**23**

votes

**3**answers

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

**21**

votes

**7**answers

30k views

### Notation for the all-ones vector [closed]

What's the most common way of writing the all-ones vector, that is, the vector, when projected onto each standard basis vector of a given vector space, having length one? The zero vector is frequently ...

**9**

votes

**6**answers

3k views

### Status of the Hadamard Circulant conjecture

The following feels like a community wiki question, so I do it here:
Recently we have heard of a new proof of the Circulant Hadamard conjecture of Ryser
(a long standing difficult conjecture):
...

**9**

votes

**2**answers

558 views

### Graphs with many edges avoided by Hamiltonian cycles

Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...

**8**

votes

**1**answer

385 views

### A Schur positivity conjecture related to row and column permutations

The problem Counting cycles after permuting within rows and columns reminds me of the
following unpublished conjecture of mine. Let $D$ be any finite
planar diagram (in the sense of Young diagram, ...

**8**

votes

**1**answer

430 views

### Primes arising from permutations

Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $n$ there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k+\pi_n(k)$ is prime for every $k=1,\ldots,n$ (cf. ...

**7**

votes

**1**answer

252 views

### Counting some binary trees with lots of extra stucture

While working on some computations on Hilbert schemes, I came across the following combinatorial problem.
Let $D(k,n)$ be the weighted number of binary trees (children are left/right) with $n$ ...

**7**

votes

**1**answer

180 views

### Eigenvectors of a matrix with entries involving combinatorics

In the question Eigenvalues of a matrix with entries involving combinatorics No_way asked about eigenvectors of $n\times n$ matrix $M$ with entries \begin{eqnarray*}
M_{ij}=(-1)^{i+j}F(n, l, i, j),
\...

**7**

votes

**1**answer

480 views

### Grassmann-Plücker relations for permanents

Let $K$ be a field, $1 \leq d \leq n$ integers and $V$ an $n$-dimensional vector space. The Grassmann-Plücker relations are quadratic forms on $\wedge^d V$ whose zero set is exactly the set of ...

**5**

votes

**1**answer

586 views

### Known decomposition of $\bigwedge^k Sym^d \mathbb C^n$ in special cases?

Let $V = \mathbb C^n$. Consider the plethysm $\bigwedge^k Sym^d V$ as a representation of $GL(V)$. In what special cases (e.g., for what $k$, $d$, and $n$) is this representation's decomposition into ...

**5**

votes

**1**answer

535 views

### Eulerian ordering of the integers modulo n

Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$.
An Eulerian ordering of $C_n$ is an ordering $r_1, \dots, r_n$ of its elements such that:
$$\forall i \le n \ \forall j&...

**4**

votes

**1**answer

218 views

### A discrete operator begets even/odd polynomials

Given a function $f(x)$ define the forward shift operator by $Ef(x)=f(x+1)$ and the discrete derivative $\delta f(x)=(E-1)f(x)=f(x+1)-f(x)$.
Given a partition $\lambda=(\lambda_1,\lambda_2,\dots,\...

**3**

votes

**2**answers

361 views

### Birthday inequality for non-uniform distributions for fixed collision probability (random allocation, collision probability)

Question: Consider a distribution $D$, and $n$ i.i.d. random variables $X_i$, all distributed according to $D$. Let $p^D_2:=\Pr[X_1=X_2]$. What is a lower bound for $p^D_n:=\Pr[\exists i\neq j. X_i=...

**19**

votes

**3**answers

811 views

### Does the hypergraph of subgroups determine a group?

A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...

**14**

votes

**1**answer

398 views

### divisibility independence

The following is a standard combinatorics question:
Any set of $n+1$ numbers from $1, \dotsc, 2n$ contains a pair of
numbers $a, b$ where $a \left| b \right.$
The argument is by pigeonhole ...

**12**

votes

**1**answer

437 views

### Number of trivializations of a trivial word in the free group

Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ ...

**11**

votes

**1**answer

660 views

### Uniquely hamiltonian graphs with minimum degree 4

A graph is uniquely hamiltonian if it has exactly one Hamilton cycle.
As every edge in a cubic graph lies in an even number of Hamilton cycles, a cubic graph cannot be uniquely hamiltonian, and a ...

**9**

votes

**2**answers

378 views

### Cubic graphs whose 2-factors all have the same cycle type

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...

**9**

votes

**1**answer

207 views

### Eigenvalues of a matrix with binomial entries

I am trying to determine the eigenvalues and eigenvectors of the following matrix:
$$M_{ij} = 4^{-j}\binom{2j}{i}$$
where it is understood that the binomial coefficient $\binom{m}{k}$ is zero if $k&...

**8**

votes

**1**answer

319 views

### Transitive closure of balanced mass transport in Z (move to close)

Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...

**7**

votes

**2**answers

1k views

### Duality of eta product identities: a new idea?

Looking at the collection of Eta Function Product Identities by Michael Somos, it seems like generally those identities come in pairs:
let's call two eta product identities $\sum\limits_{i=1}^r ...

**7**

votes

**2**answers

355 views

### Limit associated with complementary sequences

Define $A=(a_n)$ and $B=(b_n)$ as follows: $a_0=1$, $a_1=2$, $b_0=3$, $b_1=4$, and $$a_n=a_0b_{n-1}+a_1b_{n-2}$$ for $n \geq 2$, where $A$ and $B$ are increasing and every positive integer occurs ...

**6**

votes

**1**answer

228 views

### map from 6-vertex model to domino tiling

I am trying to find a correspondence between 6-vertex model and an Aztec Diamond tiling. Here are the building blocks of the 8-vertex model:
There seems to be more than one correspondence. I found ...