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

**8**

votes

**0**answers

124 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

127 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

69 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

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

**0**

votes

**1**answer

38 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

117 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

31 views

### How to sit n couples around a table with distinct seats [closed]

How many ways are there to sit $n$ couples ($2n$ people) in a round table, with numbered chairs, so that no couples sit together?

**0**

votes

**0**answers

51 views

### Optimal numbering of a bipartite graph [closed]

We have a complete bipartite graph $K_{m,n}$. That is, the set of vertices is divided at one vertex $m$, in another $n$. Any two vertices from different parts are connected by an edge. There are no ...

**4**

votes

**0**answers

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

**3**

votes

**1**answer

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

**25**

votes

**0**answers

886 views

### Can the fugitive escape?

A fugitive is surrounded by $N$ police officers, with the nearest one at distance $1$ away. The fugitive and the officers move alternatively.
In a fugitive move, the fugitive can travel no more than ...

**8**

votes

**2**answers

201 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

95 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

41 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

44 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

55 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

103 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

216 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}$ (...

**2**

votes

**1**answer

118 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

75 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

205 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

383 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

231 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

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

**6**

votes

**1**answer

166 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

174 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

394 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

152 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

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

**-2**

votes

**0**answers

190 views

### $$\sum_{i=\lceil nx \rceil}^n\frac{\lceil nx \rceil (n-\lceil nx \rceil)! p^{i-\lceil nx \rceil} (1-p)^{n-i}}{i (i-\lceil nx \rceil)! (n-i)!}$$

I am planning to study a variant of the secretary problem and need the following auxiliary result.
How to prove the following uniform convergence on [0,1]?
Let
$$ f_n(x):= \sum_{i=\lceil n x \rceil}^...

**1**

vote

**0**answers

33 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

519 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

36 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

109 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

60 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

415 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

239 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

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

**1**

vote

**0**answers

122 views

### Finding a tree with adjacency matrix near a given matrix

For defining a distance between trees, one can code them into $\mathbb{R}^n$ and use norms in $\mathbb{R}^n$ as distance. (For example we can use adjacency matrices as a tool for this coding) After ...

**1**

vote

**1**answer

82 views

### Almost-parallel corners of the hypercube in high dimensions

Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...

**3**

votes

**0**answers

81 views

### A connection between the Bell numbers and Bell polynomial

Let $B(n,x) = \sum_{k=0}^n {n\brace k}x^k$ be the Bell polynomials and $B_n = B(n,1)$ be the Bell numbers.
I recently proved a nice relation between the two:
$$
B(n,x)^{1/n}/x \ge B_{n/x}^{x/n},
$$
...

**3**

votes

**0**answers

78 views

### When is it possible to extend several linear orders defined “locally” into a single linear order defined “globally”?

This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...

**1**

vote

**1**answer

54 views

### “Circuit rank” but for vertices

A graph's circuit rank is the minimum number of edges that have to be removed for the graph to become a tree or forest. Is there a term that represents the minimum number of vertices that we must ...

**2**

votes

**1**answer

138 views

### Expansion in hypergraphs

Is there a useful concept of expansion in hypergraphs, generalizing the concept for graphs (see: expander graphs)?
Of course, expander graphs can be characterized in several qualitatively equivalent ...

**2**

votes

**2**answers

124 views

### growth of the permanent of some band matrix

Consider such special band matrix of dimension $n$. It is a $0-1$ matrix, and only the first few diagonals are nonzero. Specifically,
$$ H_{ij} = 1 $$
if and only if $|i-j| \leq 2$.
How does the ...

**7**

votes

**1**answer

409 views

### Hurwitz numbers and $t$-cores

For integers $k \geq 0$ and $d \geq 1$ let $H(k,d)$
be the Hurwitz number which, for the purposes
of this posting, will be defined by:
\begin{equation}
H(k,d)
\, := \ d! \, \sum_{\lambda \, \vdash d}...

**2**

votes

**0**answers

118 views

### Square root of a function on a finite set

Let $S$ be a finite set and $f \colon S \to S$ be an arbitrary function. How can we find all functions $g \colon S \to S$ with $f = g \circ g$?
If $f$ and $g$ are both required to be invertible, the ...

**3**

votes

**0**answers

97 views

### Asymptotics of a combinatorial series

I am interested in the exact asymptotics of the following combinatorial series (which arises from the study of a Markov chain):
$$F(q):=\sum_{k \ge 1} \frac{q^{k^2}}{(q;q)_k^2}\quad \mbox{as } q \to 1^...

**2**

votes

**1**answer

63 views

### Min-sum and min-max node-disjoint path problems

Given an undirected weighted graph, we seek a pair of node-disjoint path between $2$ nodes $s$ and $t$: if the objective is to minimize the total path cost, the Suurballe algorithm can be applied; now ...

**2**

votes

**2**answers

235 views

### sum of odious numbers to the power of k

In number theory, an odious number is a positive integer that has an odd number of $1$s in its binary expansion.
The first odious numbers are:
$1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, ...