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

1,586 questions

**0**

votes

**2**answers

605 views

### Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by
$$\frac{k}{2n-k}{2n-k \choose n}.$$
The number of Dyck paths from the ...

**48**

votes

**1**answer

3k views

### (Approximately) bijective proof of $\zeta(2)=\pi^2/6$ ?

Given $A,B\in {\Bbb Z}^2$, write $A \leftrightarrows B$ if the
interior of the line segment AB misses
${\Bbb Z}^2$.
For $r>0$, define
$S_r:=\{ \{A, B\} | A,B\in {\Bbb Z}^2,||A||<r,||B||<r, |...

**15**

votes

**1**answer

475 views

### To find a longer path with fixed endvertices in a graph satisfies the following property

Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where
$$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$
I found that if the path $P$ satisfies:
...

**13**

votes

**1**answer

965 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**9**

votes

**1**answer

928 views

### Hobbled rook tour - Hamiltonian cycle on square grid

Consider square grid of even sides ($2n \times 2n$). It is easy to see that there must exist Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balance if the number of vertical ...

**7**

votes

**1**answer

374 views

### Homomesy in perfect matchings

Assume $n \geq 2$. Let $\mathcal{M}_n$ denote the set of perfect matchings on $[2n] := \{1,\ldots,2n\}$, i.e., the set of partitions of $[2n]$ into pairs. For $M \in \mathcal{M}_n$, and $p = \{a,b\}$,$...

**7**

votes

**1**answer

784 views

### Best possible sieves for the jacobsthal problem, linear programming, and the prime 2

Background/Motivation
Gerhard Paseman asked a question about bounds on the Jacobsthal function a while ago, which made me curious about whether the known bounds are best possible. Briefly, the ...

**6**

votes

**1**answer

186 views

### Problem with the vertices of a convex quadrilateral on integer lattice

I made the following observation and I am wondering if it is always true.
Let $x_1$, $x_2$, $x_3$ and $x_4$ be four positive integer points in the plane ($x_i\in\mathbb{Z^2_{\geq 0}}$) forming a ...

**6**

votes

**1**answer

171 views

### Triangulations of convex surfaces

Let $M$ be a smooth closed positively curved surface in Euclidean 3-space, $T$ be a geodesic triangulation of $M$, and $E$ be the edge graph of the convex hull of vertices of $T$.
It is easy to see ...

**6**

votes

**1**answer

611 views

### Regular unimodular triangulation for a certain simplex

Consider an $n$-simplex with vertices given by
$(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers,
and $i=0,1,\dots,n+1$.
Does this simplex admit a regular, ...

**5**

votes

**1**answer

496 views

### What is the six positive real number for a dice producing a highest chance?

Say there is a dice with six faces, each face has a positive real number different from others. There is a chessman on the origin of the number axis. In each trial, the dice rolls infinite times. ...

**5**

votes

**1**answer

233 views

### Finding a semi-sparse vertex in a grid

Let $H$ be a $r \times r$ grid. Suppose that at most $r/10^5$ vertices of this grid are colored red. For every vertex $v \in V(H)$, let $B_i(v)$ be the ball of radius $i$ centered at $v$. (Or for ...

**4**

votes

**1**answer

185 views

### Distribution of longest run locations in a random string

Let x be a random n-bit string, and let $I ={i_1,i_2,...,i_n}$ be the starting indexes of the longest 0-runs of x, sorted in decreasing order (so $i_1$ is the starting index of the longest (~$\log n$) ...

**4**

votes

**1**answer

397 views

### Combinatorial optimization problem for bipartite graphs

Let $G(V_1\cup V_2, E)$ be a simple bipartite graph having $n$ vertices and $m$ edges, such that $|V_1|=|V_2|$ (which implies that $n$ is an even number). Given any node $i \in V_1\cup V_2$, we denote ...

**4**

votes

**1**answer

479 views

### Birthday Inequality for non uniform distribution with specific collision entropy

Let $D$ be a distribution with collision-entropy $k$, i.e., $H_2(D) = k$.
Let $n$ samples are chosen independently according to the distribution $D$. Let $E_n$ be the event that there is no ...

**3**

votes

**1**answer

207 views

### Which 3-regular graphs are Schreier coset graphs

Given a group $G$ and a subgroup $H$ the Schreier coset graph (w.r.t. some set $S$ of $G$) is the directed (and labelled) graph whose vertices are the cosets of $H$ (i.e. the set $G/H$) and $x \sim y$ ...

**3**

votes

**1**answer

312 views

### Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...

**2**

votes

**1**answer

139 views

### Does the likelihood of these tables exist?

Probably it does, and may be a number near $e^{-3/2}$ for 2-deficient tables. First some background.
Early on in my studies of universal algebra, I encountered a result of Vadim Murskii, with the ...

**2**

votes

**1**answer

236 views

### H-generalized join graph

The $A$-join of a set of graphs $\{ G_a \}_{a \in A}$ as
the graph $H$ with vertex and edge sets
\begin{eqnarray*}
V(H) &=& \{(x,y) \ | \ x \in V(A) \ \& \ y \in V(G_x) \},\\
...

**1**

vote

**1**answer

78 views

### Evaluation of a complete homogeneous symmetric polynomial related to Stirling number of 2nd kind

It is well known that the complete homogeneous symmetric polynomial $h_{n-k}(1,\,2,\,3, ...,\,k-1,\,k)$ equals $S(n,\,k)$ the Stirling number of the second kind. [Wikipedia]
During a research project ...

**1**

vote

**1**answer

61 views

### Asymptotic upper bound for partial binomial-like sum

I want to upper bound the quantity $$\sum_{i\le \alpha n} \binom{n}{i}\lambda^i$$, where ${\lambda>1}$, $0<\alpha<1$. It is not the same as partial sum of binomial coefficients. An asymptotic ...

**1**

vote

**1**answer

67 views

### Random Optimization on Graphs: Minimum Cut

Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...

**1**

vote

**1**answer

143 views

### Coefficients of the monomials appearing in a Schubert polynomial

It is known that the coefficients of the monomials appearing in a Schubert polynomial are always positive. My question is: Is it always true that at least one such coefficient must be $1$? If that is ...

**1**

vote

**1**answer

179 views

### Bounds on degrees of minors obtained by edge contractions of regular graphs

Given a connected $d$-regular graph $G=(V,E)$, generate a sequence of minors by performing only edge contractions and loop deletions (as, e.g., in Karger's algorithm) until the graph collapses to a ...

**0**

votes

**1**answer

84 views

### Finding $P$ points among $N$ to approximate a probability density function?

Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ ...

**0**

votes

**1**answer

97 views

### Description of Linear Time Algorithm for TSP in Halin Graphs

I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in
"G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...

**0**

votes

**1**answer

385 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**-1**

votes

**1**answer

265 views

### Odd & even permutations and unit fractions

One more motivated by recent questions of Zhi-Wei Sun.
Let $S_n$ be the group of permutations of $\{1,2,\ldots, n\}$.
Is it true that, for every $n \ge 8$, there is at least one even permutation $\...

**-1**

votes

**1**answer

63 views

### Transforming random variables for having good property?

For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that
\begin{align}
\Omega&\triangleq \{(x,y): A(x,y)=1\},\\
\Lambda&\triangleq \{x: B(x)=1\}.
\end{...

**-1**

votes

**1**answer

91 views

### What type of graph is this? (Edges that are valid / invalid depending on route to node)

I'm trying to model a questionnaire where the flow between questions depends on the answers given in previous questions.
Example. (Node represent questions, edges represent answers).
As you can see ...

**-1**

votes

**1**answer

229 views

### Bins and colored balls

Consider $n$ color balls. We throw them as follows. For a given ball $i$, randomly choose $k$ bins; create $k$ 'copies' of the ball (i.e., of the same color of the ball $i$); throw a 'copy ball' into ...

**-1**

votes

**1**answer

192 views

### Collecting terms of a linear expression with nested sums and combinatorics in coefficients

I need to collect the $\Pr(\cdot)$ terms of the following expression:
$\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left(
1-\theta \right) }\right) ^{m}}\left[ \sum_{j=2}^{m-1}...

**-1**

votes

**0**answers

44 views

### Multiplicities of ordered pairs in pairing of two multisets

This is a repost from a question on math.stackexchange.
Problem: I have two multisets, $X$ and $Y$. Each is a $k$-combination with repetition of a set $N=\{1,2,3,\dots,n\}$, where $n$ can be greater, ...

**-1**

votes

**0**answers

53 views

### Is there any relationship between the Hungarian Algorithm and the Hesse Diagram method for ranking and sorting?

The Hungarian algorithm is used for the assignment problem. I would like to know whether the Hesse diagram method can be used to rank and sort as the Hungarian algorithm can.

**-1**

votes

**0**answers

41 views

### Max+Min of a specific data set

Let $r\geq 6$ and $3\leq f \leq 2r-3$ be integers. Suppose we have $f$ data points $x_0,x_1,\ldots, x_{f-1}$ such that
for each i, $1\leq x_i \leq r-4$ is an positive integer.
for each i in $\mathbb ...

**-1**

votes

**0**answers

140 views

### What is known about Carmichael function distribution and growth?

Let $\lambda(n)$ be the Carmichael Lambda Function of $n$.
We know that for every $m$ there is the largest $n_m\in\Bbb N$ such that for every $n>n_m$ we have $\lambda(n)\neq m$ and $\lambda(n_m)=m$...