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

8,478
questions

**8**

votes

**0**answers

280 views

### A bijective proof for the odd companion to Shapiro's Catalan convolution

Shapiro's Catalan convolution is the following formula (where $C_n$ is the $n$th Catalan number):
$$
\sum_{k=0}^{n}{C_{2k}C_{2(n-k)}}=4^nC_n.
$$
In other words, letting $C(z)=\sum_{n=0}^{\infty}{C_nz^...

**1**

vote

**1**answer

181 views

### Partitioning a convex $n$-polygon

Let $P$ be a convex polygon with $n\ge3$ vertices. Let $\mathcal{Z}_K(P)$ be a partition of the polygon into $K$ polygonal (but not necessarily convex) parts whose interiors are pairwise disjoint,
$$
\...

**1**

vote

**0**answers

131 views

### For any $n-1$ elements of $\mathbb Z/n\mathbb Z$, we can make $0$ using $\{-,+,\times\}$ without parentheses

MSE: Just using $+$ ,$-$, $\times$ using any given n-1 integers, can we make a number divisible by n? (no brackets allowed)
Is there any hope in proving the following? (Cross-posted here after a ...

**3**

votes

**0**answers

60 views

### On a connectivity property of set systems

Let $X\neq \emptyset$ be a set and let ${\cal A}\subseteq {\cal P}(X)$ with $\bigcup {\cal A}=X$. We say that $S\subseteq X$ is indivisible if for all $T\subseteq S$ with $\emptyset \neq T \neq S$ ...

**14**

votes

**2**answers

1k views

### How many category structures are possible on two sets?

For two sets $O$ and $A$, we will call a category structure a collection of functions ${\sf dom}:A\to O,\ {\sf cod}:A\to O,\ {\sf 1}:O\to A,\ \circ:A\times_OA\to A$ satisfying the usual axioms for a ...

**6**

votes

**2**answers

187 views

### A convolution-type identity for the “major index”

For a permutation $\pi\in\frak{S}_n$, define the number of descents of $\pi$ as $$\text{des}(\pi)=\vert\{i: \pi(i)>\pi(i+1)\}\vert.$$
The following is a well-known (and interesting) identity:
$$\...

**2**

votes

**0**answers

92 views

### Enumeration and encoding of simplicial complexes

I'd like to know how to enumerate and encode all (abstract) simplicial complexes of a given kind.
To start as simple as possible, consider the familiy $\mathcal{S}_n^{d}$ of simplicial complexes which ...

**2**

votes

**0**answers

51 views

### Inverting “codimension matrix” for polytopes?

Let $P$ be an abstract polytope. Let's construct its square matrix $A$ as follows. Its lines and columns are labelled by all faces of $P$, of all dimensions. Put $A(F_1,F_2)=t^m$ if $F_1$ is a subface ...

**9**

votes

**0**answers

306 views

### A robust version of Harper's theorem

Let $S$ be subset of $\{0,1\}^n$ with cardinality $k$.
Denote by $\Gamma_r(S)$ the union of all Hamming balls with centers in $S$ and radius $r$.
Harpers's theorem states that $\Gamma_d(S)$ is minimal ...

**0**

votes

**0**answers

35 views

### The linear embedding complexity of subsets of $0/1$ cube

We say $\pi$ is a subset of the $0/1$ integer points in $t$ dimensions represented by coordinates $(x_1,\dots,x_t)$ of complexity $\log^ct$ if there is an $A$ of $2^{\log^ct}\times2^{\log^ct}$ ...

**0**

votes

**0**answers

34 views

### Travelling salesman problem with variable weights

Take a fully connected graph with $v$ vertices. We assign weights to edges using an arbitrary function $f_{ij}(x)$ for pairs of vertices $0 < i, j \le v$, then starting at $c_{0}=0$, traverse the ...

**1**

vote

**0**answers

187 views

### Solution to system of linear equations

Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...

**3**

votes

**0**answers

84 views

### Ehrhart-Macdonald reciprocity with multiplicities

Let $P$ be a convex lattice polytope in $\mathbb{R}^n$. The function $L(t, P) = |\mathbb{Z}^n \cap t\cdot P|$ is a polynomial, and we have an equality
$$L(-t, P) = (-1)^nL(t, P^{int}),$$
where $P^{int}...

**4**

votes

**2**answers

249 views

### High degree differences in bipartite graphs

Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us define the quantity:
$$\mathcal{I}_k(G) := \sum_{1\le i,j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v_i)-\...

**5**

votes

**1**answer

135 views

### Signs in Chevalley systems for reductive groups

Let $G$ be a pinned split reductive group. There exists a Chevalley system:
For each root $b$ in its root system there are parametrisations $x_b: \mathbb{G}_a \rightarrow U_b$ of the corresponding ...

**7**

votes

**1**answer

309 views

### Independent vectors in the permuting coordinates action of $S_n$ on $\mathbb{R}^n$

Let $V$ be the hyperplane in $\mathbb{R}^n$ with equation $\sum_i x_i=0$. The symmetric group $S_n$ acts on $V$ by $s\cdot (v_1,\ldots,v_n)=(v_{s^{-1}(1)},\ldots,v_{s^{-1}(n)})$. Consider those $v\in ...

**3**

votes

**1**answer

185 views

### Difference set of difference set

I am a hobby computer scientist and searching for an algorithm to construct a set of n numbers (integers) with certain properties.
Property 1 / Step 1
All pairwise differences of the elements should ...

**3**

votes

**0**answers

122 views

### Partitions of n into k distinct parts which are multiples of given numbers

Is there anything known about the number of partitions of an integer $n$ into $k$ distinct parts in the following way?
Let $a_1,\dotsc,a_k\geqslant1$ be given integers. In how many ways can we write $...

**2**

votes

**0**answers

105 views

### Magic squares as sums of permutation matrices

A magic square of size $n$ and sum $k$ is a $n\times n$ matrix with non-negative integer elements, whose rows and columns all sum to $k$. A permutation matrix is a magic square of sum $1$. Every magic ...

**2**

votes

**1**answer

52 views

### Minimal volume of fundamental domains of lattices

Consider a full rank integer lattice in $\mathbb{R}^n$. Let $v_1$ be the shortest non-zero vector in the lattice, $v_2$ be the shortest one among those not parallel to $v_1$, $v_3$ be the shortest one ...

**11**

votes

**1**answer

416 views

### “Drinking number” of a graph

Motivation. A while ago I attended a party and I only knew some, but not all, of the attendees. There were 2 kinds of drinks: beer and soda. I noticed that amongst my acquaintances, more than half ...

**8**

votes

**1**answer

208 views

### Find all Non-isomorphic good drawings of $K_{3,3}$？

Sometimes I look at all non-isomorphic good drawings of graphs on a plane or sphere.
Good drawing means that no edge crosses itself, no two edges cross more than once, and no two edges incident with ...

**1**

vote

**1**answer

74 views

### Knapsack problem with capacity constraint

The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...

**5**

votes

**0**answers

71 views

### Permutations in a Bruhat interval with a fixed point

Let $[e,\sigma_0]$ be the Bruhat interval of the permutations $\sigma\leq \sigma_0$ for the (strong) Bruhat order. I am interested in the following set, for fixed $i,j$:
$$[e,\sigma_0]_i^j:=\{ \sigma \...

**1**

vote

**1**answer

114 views

### Partity of partitions with distinct parts of parts $>1$

This question is motivated by my earlier (unanswered) MO post.
The number of partitions into distinct parts is generated by $\sum_{n\geq0}Q(n)x^n=\prod_{k\geq1}(1+x^k)$. Focusing on parity of ...

**0**

votes

**0**answers

44 views

### Sufficient criterion for unit distance graphs

There are many necessary criteria for a graph to be a unit distance graph. For example, it must not have $K_4$ as a subgraph etc. Can we find some sufficient criterion for a graph to be a unit ...

**2**

votes

**1**answer

285 views

### Is the number of words finite, when you don't know how to count?

This question is inspired by this one:
Can you do math without knowing how to count?
Let $M_2$ be the set of words constructed by concatenation of the letters $a_1$ and $a_2$, with :
(*) : for any $x$ ...

**15**

votes

**2**answers

638 views

### n sets, each is large, the intersection of every three is small, what is the size of the union?

Let $A_1, A_2, \ldots, A_n$ be $n$ sets such that:
(1) for each $i\in [n]$, $\frac{n}{3}\leq |A_i|\leq n$;
(2) for any $1\leq i<j<k\leq n$, $|A_i\cap A_j\cap A_k|\leq a$, where $a$ is a constant ...

**2**

votes

**0**answers

43 views

### Coloring finite subsets of a fixed size with a single modular function

Let $k$ and $N$ be positive integers so that $k\mid N$. Let $M=(k/N){N\choose k}$. A function $f:[N]^k\rightarrow M$ is a coloring function if $f(s_1) = f(s_2)$ implies that $s_1=s_2$ or $s_1 \cap ...

**9**

votes

**0**answers

278 views

### Being even or odd in the product expansion $\prod(1+x^k+x^{k+1})$

Consider the generating function of "partitions with distinct parts"
$$\sum_nQ(n)x^n=\prod_k(1+x^k).$$
It's known that
$$\left[\prod_k(1+x^k)\right] \mod 2=\prod_m(1-x^m)=\sum_{j\in\mathbb{Z}...

**1**

vote

**1**answer

212 views

### What is the inverse Laplace transform of $\frac{(1/s)_{n}}{s} $?

Introduction
So far, I have found (p. 5) the following generating functions of the unsigned Stirling numbers of the first kind:
\begin{equation} \tag{1} \label{1} \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)...

**2**

votes

**0**answers

93 views

### Number of sets of distinct pairs which doesn't share difference

Inspired by This question by Vidyarthi I tried to find the value of $T(2m)$ where, $T(2m)$ is the number of sets of distinct pairings (so, the sets have $m$ elements) of the numbers $1,2,3....,2m$ ...

**2**

votes

**0**answers

85 views

### Partitioning a set of consecutive nonnegative integers into distinct pairs

Let us have a set of $k$ consecutive natural numbers $2,3,\ldots, k+1$, $k$ even. In addition, we are given a set of $m=\frac{k}{2}$ 'differences' from one among the $k$ numbers $1,2,\ldots, k$.
My ...

**1**

vote

**1**answer

87 views

### Knapsack problem with value range constraint

The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...

**1**

vote

**0**answers

135 views

### Is this graph theory paper in German translated into English?

I recently read such a paper and want to understand the proof idea of this article. However since it is in German and I have not studied German before, I'd like to ask whether this paper has an ...

**4**

votes

**0**answers

109 views

### Positivity conjecture for Somos sequences

Let $\{s_n\}$ be the Somos-$4$ sequence, which is defined by $$s_{n+4}s_n=\alpha s_{n+3}s_{n+1}+\beta s_n^2.$$ It is known that $s_n$ is a Laurent polynomial: $s_n\in\mathbb{Z}[s_1^{\pm1}, \ldots, s_4^...

**5**

votes

**1**answer

223 views

### Positioning ice-cream stands on a street

We want to position $n$ ice-cream stands on a street. Assume that the population on the street is modeled by a nonnegative integrable function $f$, and everyone goes to the nearest ice-cream stand. ...

**8**

votes

**2**answers

234 views

### Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$

Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$.
Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...

**7**

votes

**0**answers

106 views

### On the number of Reed–Muller codewords with no consecutive ones

$\DeclareMathOperator\RM{RM}\DeclareMathOperator\Eval{Eval}$Consider the polynomial ring $\mathbb{F}_2[x_1,x_2,\dotsc,x_m]$ and let $f\in \mathbb{F}_2[x_1,x_2,\dotsc,x_m]$. Let us now fix a Gray ...

**1**

vote

**1**answer

48 views

### Expectation of the sum of the squares of the cardinal of an inverse function

I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as:
$$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$
where $\oplus$ is the bitwise XOR.
...

**1**

vote

**0**answers

64 views

### Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph

A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...

**3**

votes

**1**answer

115 views

### A ratio of two probabilities

I am concerned about the monotonicity of the following ratio
$
f(\eta)=\frac{\sum_{x=K}^{N}\left(\begin{array}{c}
N\\
x
\end{array}\right)\left(q_{G}\eta\right)^{x}\left(1-q_{G}\eta\right)^{N-x}}{\...

**0**

votes

**0**answers

217 views

### Equality of the products involving (prime powers - 1)

Let $q_1,q_2,\dots,q_m$ be a collection of prime powers such that $q_i = p_i^{k_i}$. I have the following questions.
When the products $\prod_{i=1}^m(q_i-1)^{r_i}$ and $\prod_{j=1}^m(q_j-1)^{s_j}$ (...

**1**

vote

**1**answer

123 views

### Expectation of maximum of all period lengths of functions $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$

This is based on an older question.
For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ and ''starting value'' $...

**1**

vote

**0**answers

79 views

### When are the 3-colorings of vertex subsets uncorrelated?

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.
For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct ...

**-1**

votes

**1**answer

209 views

### Given the index of two permutations, Is there a direct way to compute the index of their composition? [closed]

Suppose you are given two indexed permutations, (7 followed by 4, for instance)
What is the best way to go about finding their composition, given the indices themselves? I'd imagine that the answer ...

**9**

votes

**3**answers

416 views

### Pairs of vertices with high degree difference

Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us also fix an integer $k> n/2$. What are we able to say about the following quantity:
$$\mathcal{I}_k(G) :=...

**2**

votes

**1**answer

253 views

### Alternating sum of hook lengths: Part II

This is a follow up on my earlier MO post.
Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$. Let
$$f_n=\sum_{\...

**0**

votes

**0**answers

52 views

### Multiplication on a group of given cardinal and random permutations

Let $n$ be an integer, that we assume to be large (the order of magnitude for the motivation about the question is about 2^100).
For the purpose of random automatic program certification, I need to be ...

**7**

votes

**1**answer

179 views

### Constructing permutations avoiding a pattern

See here for some theory.
It is fairly easy to explicitly generate all permutations of $n$ elements that have a pattern (just begin with the pattern and add the rest in all possible positions), but ...