# 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,419
questions

**4**

votes

**2**answers

240 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

132 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

306 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

171 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

120 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

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

**1**

vote

**1**answer

38 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

394 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

206 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

69 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

69 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

108 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

276 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

631 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

42 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

262 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

165 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

91 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

83 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

81 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

133 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

105 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

219 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

223 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

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

**0**

votes

**0**answers

43 views

### maximum radius for a $k$-set of vertices in a graph

this is a cross-post from mse here.
Let $G$ be a connected graph and $S$ a subset of its vertices. Given a vertex $v$ of $G$ we define the $S$-eccentricity of $v$ as the largest distance between $v$ ...

**1**

vote

**1**answer

47 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

63 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

113 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

122 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

413 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

242 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

51 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

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

**5**

votes

**2**answers

190 views

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

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)$ associate a sequence $\text{seq}(f))$ defined recursively by
...

**7**

votes

**2**answers

401 views

### Chip-firing clocks

Let $G$ be some outdegree-regular directed graph with $n$ vertices and let $H$ be the Laplacian of $G$, so that the rows of $H$ correspond to chip-firing moves. I’m interested in linear functions $f$ ...

**2**

votes

**1**answer

177 views

### Find a collection of values of polynomial

Given a polynomial $f(x)\in \mathbb C[x]$ where $\deg f(x)=n-1.$ Assume that we need to find a collection of values of this polynomial corresponding to the following set of $x$-values: $\{ e^{ik} \}$ ...

**2**

votes

**0**answers

49 views

### Tail asymptotics of Durfee square identity

This post is related to the problem Asymptotics of a combinatorial series
According to the Durfee square identity:
$$\sum_{k \ge 0} \frac{q^{k^2}}{(q;q)_k^2} (q;q)_{\infty} = 1,$$
where $(q;q)_k$ is ...

**1**

vote

**0**answers

34 views

### Problem concerning cutting of 2n*2n square into 2 equal area connected figures using various cuts without self crossings

We have a square 2n*2n, where n belongs to N. The main problem is to find how many different equal area connected figures could be produced by cuttings without self-crossings. The orientability of the ...

**11**

votes

**2**answers

531 views

### Alternating sum of hook lengths: Part I

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$.
Is there a closed formula or a generating function for the ...

**1**

vote

**0**answers

40 views

### Higher order Leibniz rule and ordered multiindex notation

Although I think this is probably known, I am making here a short exposition on the multiindex notations I am using to make this question self-contained. I note that there is at least two different ...

**2**

votes

**1**answer

113 views

### Directed version of this lemma

On a paper by Shoham Letzter, available Here, there's a lemma that says as follows:
Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...

**0**

votes

**1**answer

80 views

### Number of linear inequalities describing a polyhedron with prescribed number of vertices

If a polytope has $d$ vertices in $k$ dimensions how many linear inequalities is required to describe it?

**7**

votes

**1**answer

426 views

### Packing equal-size disks in a unit disk

Inspired by the delicious buns and Siu Mai in bamboo steamers I saw tonight in a food show about Cantonese Dim Sum, here is a natural question. It probably has been well studied in the literature, but ...

**0**

votes

**0**answers

243 views

### Is there a permutation $\tau\in S_n$ with $\tau(1)^{\tau(2)}+\cdots+\tau(n-1)^{\tau(n)}+\tau(n)^{\tau(1)}$ a square?

Let $n>1$ be an integer, and let $S_n$ be the symmetric group of all the permutatins of $\{1,\ldots,n\}$.
I'm curious whether there is a permutation $\tau\in S_n$ such that
$$\tau(1)^{\tau(2)}+\...

**2**

votes

**1**answer

69 views

### Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$

What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...