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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
3answers
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
1answer
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
0answers
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
1answer
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
2answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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, ...
