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

**0**

votes

**0**answers

43 views

### Length of walking on a graph

Given a finite directed connected graph $G$,
let $P_{circle}$ be the set of finitely long circle paths on $G$
(a circle path is a path with identical starting and ending vertex).
It is well known that ...

**6**

votes

**0**answers

131 views

### How many non-isomorphic abelian subgroups of the permutation group $S_n$?

I am interested in how many (pairwise non-isomorphic) subgroups of the permutation group $S_n$ are abelian. ($n \in \mathbb{N}$ arbitrary and possibly big)
Are you aware of any references which treat ...

**0**

votes

**0**answers

14 views

### Low-discrepancy submatrices in any matrix

First we define what is discrepancy. Discrepancy measure the bias of matrix $M$ and its submatrices. Given a matrix $M$ with entries in $\{0,1\}$, for any combinatorial rectangle R we define $\text{...

**8**

votes

**3**answers

271 views

### Expected number of compositions needed to get constant function

This is somewhat inspired by Factoring a function from a finite set to itself.
Fix natural number $n$ and let $[n] := \{1,2,\ldots,n\}$. Set $g_0 \colon [n]\to [n]$ to be the identity, and for $i \geq ...

**0**

votes

**1**answer

40 views

### Limit of the Schröder numbers ratio

I have been playing around with interesting integer sequences and came across Schröder number which defines the number of lattice paths of n x n grid.
The recurrence formula to calculate these numbers ...

**2**

votes

**0**answers

62 views

### Another generalization of parity of Catalan numbers

Recently, a question by T. Amdeberhan gathered up many enjoyable proofs that a Catalan number $C_n$ is odd if and only if $n=2^r-1$.
Noam D. Elkies' answer considered $F=\sum_{n=0}^\infty C_n x^{n+1}$....

**1**

vote

**0**answers

31 views

### A variant of node-disjoint path problem

Given a graph $G$, I want to find $2$ (or $k$) node-disjoint paths with minimum total cost (or minimum maximum cost). The problem is a classical problem, but I have the following non-trivial setting. ...

**0**

votes

**1**answer

162 views

### Nested sums as a single sum [closed]

Is there a nice way to write the following repeated sum
$$
\sum_{a_1=1}^{i+(2-k)} \sum_{a_2=1}^{i-(a_1-(3-k))}\sum_{a_3=1}^{i-(a_1+a_2-(4-k))}\sum_{a_4=1}^{i-(a_1+a_2+a_3-(5-k))}\dotsb\sum_{a_k=1}^{i-(...

**1**

vote

**1**answer

347 views

### On 'Improved Bounds for the Sunflower Lemma' [Alweiss, Lovett, Wu, Zhang]

I have been reading the paper 'Improved Bounds for the Sunflower Lemma' (Ann. of Math., Vol. 194(3), pp. 795-815), and have not managed to understand the following:
I would like a formalization for ...

**2**

votes

**0**answers

186 views

### Two conjectures about generalised A329369

Let $m \geqslant 2$ be a fixed integer.
Let
$$\operatorname{wt}(n,m)=\operatorname{wt}\left(\left\lfloor\frac{n}{m}\right\rfloor,m\right)+n\bmod m, \operatorname{wt}(0,m)=0$$
Then we have an integer ...

**11**

votes

**1**answer

248 views

### Bijective proof of recurrence for rooted unlabeled trees

Would've been a better question for Christmas than Thanksgiving, but alas...
Let $t_n$ denote the number of rooted, unlabeled trees on $n$ vertices (OEIS A000081). These are the isomorphism classes of ...

**3**

votes

**1**answer

153 views

### Conjecture on some combinatorial constant

In the process of computing Shapley values, I observed an interesting combinatorial constant. I am not exactly sure where such behavior comes. And here is the conjecture.
Notations
For any finite non-...

**2**

votes

**1**answer

79 views

### Modulo $2$ binomial transform of A243499 applied $k$ times

Let $m \geqslant 1$ be a fixed integer.
Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.
...

**0**

votes

**0**answers

50 views

### Modulo $2$ binomial transform of A124758

Let $f(n)$ be A153733, remove all trailing ones in binary representation of $n$. Here
\begin{align}
f(2n)& = 2n\\
f(2n+1)& = f(n)\\
\end{align}
Then we have an integer sequence given by
\begin{...

**1**

vote

**0**answers

47 views

### Inverse modulo $2$ binomial transform of generalised A284005

Let $m \geqslant 1$ be a fixed integer.
Let $\operatorname{wt}(n)$ be A000120, $1$'s-counting sequence: number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).
Let $f(n)$ be A007814, ...

**1**

vote

**0**answers

280 views

### Combinatorial proof of a matrix equation

I'm looking for combinatorial proofs (using, e.g., trees) of the following particular matrix equation $(I)$ and also combinatoric operational analogs of its solution via matrix inversion and/or Cramer'...

**0**

votes

**0**answers

41 views

### An inequality for twisted sums of counting functions

Suppose that $\mathbb{Z}_p^2$ is a 2-dimensional vector space over finite field $\mathbb{Z}_p,$ where $p\equiv 3 \pmod 4$. Define a "distance" as follows: for $x,y\in \mathbb{Z}_p^2$ let $\...

**9**

votes

**1**answer

148 views

### An integral indexed by two partitions that mysteriously vanishes

Let $\alpha,\beta\vdash n$ and define the polynomial
$$f_{\alpha,\beta}(x)=\sum_{\lambda \vdash n}\chi_\lambda(n)\chi_\lambda(\alpha)\chi_\lambda(\beta)x^{\ell(\lambda)-1},$$
where $\chi_\lambda$ are ...

**5**

votes

**3**answers

294 views

### Generating function of product of binomial coefficients

Let $m, n\in \mathbb{N}$ and $|x| < 1$. I look for hints to derive an analytic formula for
$$f_{m,n}(x) = \sum_{k \in \mathbb{N}} {n + k \choose k} {m + k \choose k} x^{k}. $$

**2**

votes

**0**answers

25 views

### Max flow with minimum number of edges

A max-flow problem may have multiple solutions. Among these max-flows, I seek the one with the minimum number of positive flow edges (by positive flow edges I mean the edges carrying positive flow). ...

**-2**

votes

**0**answers

121 views

### Was the computational Diffie-Hellman really broken in a key exchange?

Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X,Y$ be positive integer and $P_X=P_0^X A_0 P_0^{-X}$
and $P_Y=P_0^Y A_0 P_0^{-Y}$ and $...

**6**

votes

**3**answers

925 views

### Graphs from the point of view of Riemann surfaces

I was listening to the lecture "Graphs from the point of view of
Riemann surfaces" by Prof. Alexander Mednykh. I am looking for references for the basics of this topic. Any kind of ...

**11**

votes

**0**answers

285 views

### List of problems that Erdős offered money for?

Is there a list somewhere of all the problems that Erdős offered cash awards for, including both solved and unsolved problems? One would think that the answer is yes, but so far I have had no luck ...

**5**

votes

**1**answer

202 views

### Combinatorics and symmetry in matrices under row and column swaps

Suppose we have a $m\times n$ matrix and a sequence of numbers with which to fill the matrix, $\{c_1,c_2 \dots c_k \}$. I like to think of the numbers as colors, hence the notation. How many unique ...

**2**

votes

**0**answers

98 views

### Can the absolute value of fixed sized minors be arbitrarily ordered?

In an $m \times n$ matrix $X$, there are exactly $\binom{m}{r}\binom{n}{r}$ minors of size $r \times r$. Is it always possible to construct a real matrix $X$ such that the absolute value of the ...

**0**

votes

**0**answers

85 views

### Subsequence which is identical to A122778

Let $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).
Let $a(n)$ be A284005,
\begin{align}
a(0)& = 1\\
a(n)& = (1+\operatorname{wt}(n)...

**3**

votes

**2**answers

272 views

### Relation graph isomorphism to discrete logarithm

$\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$.
Q1 ...

**2**

votes

**0**answers

42 views

### Compact expression for triples of subsets with total sum zero

I am looking whether there is any compact way to write the following: Suppose we have an abelian group $G$. For a subset $A\subset G$ let $S_A$ be the sum of its elements. I want to find the number of ...

**11**

votes

**0**answers

173 views

### 3-manifolds with stacked links

Stacked spheres
A triangulation of a 2-dimensional sphere is called a stacked sphere if it is obtained inductively from the boundary of a 3-simplex by deleting a 2-face (triangle) $T$ adding a new ...

**14**

votes

**4**answers

2k views

### Collecting alternative proofs for the oddity of Catalan

Consider the ubiquitous Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$. In this post, I am looking for your help in my attempt to collect alternative proofs of the following fact: $C_n$ is odd if and ...

**0**

votes

**0**answers

130 views

### Open tours by a biased rook (proof verification)

Related questions:
Number of open tours by a biased rook on a specific $f(n)\times 1$ board which end on a $k$-th cell from the right
Sum with products turned into subsequences
Combinatorial ...

**3**

votes

**2**answers

168 views

### Ask for a reference or a proof of a combinatorial identity $\sum_{k=0}^n\binom{2n+1}{2k}\binom {k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m}$

Could you please recommend a reference to or supply a proof of the following identity \eqref{combin-ID-Maclaurin}, or \eqref{first-equiv-form}, or \eqref{combin-ID-Mac-Equiv}, or \eqref{combin-ID-Mac-...

**21**

votes

**2**answers

740 views

### The chromatic number of the union of two graphs

Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus,...

**0**

votes

**0**answers

62 views

### Objects equinumerous with $3$-ary partitions?

There is a concept of the so-called RP-compositions of an integer discussed by K. Q. Ji and H. S. Wilf in Extreme palindromes. They proved the following result too:
Theorem. The number of RP-...

**4**

votes

**0**answers

43 views

### Amalgamation problem for the 11-cell and 57-cell

Are there any finite regular abstract 5-polytopes whose facets are 11-cells and whose vertex figures are 57-cells?

**2**

votes

**2**answers

136 views

### Modulo $2$ binomial transform of $m^n$

Let $m \in \mathbb{R}$.
Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.
Let $g(n)$ be ...

**1**

vote

**0**answers

98 views

### Polynomial interpolation of binary vectors

Let $\mathbb{F}$ be a finite field and let $\boldsymbol{x} = (x_1, x_2, \dots, x_n)$ be $n$
pairwise distinct points in $\mathbb{F}$.
Given the vector $\boldsymbol{y} = (y_1, y_2, \dots, y_n)$, with $...

**1**

vote

**1**answer

149 views

### Ubiquity of simplices in subsets of $\mathbb{F}_q^d$

I was reading Hart and Iosevich - Ubiquity of simplices in subsets of vector spaces over finite fields about some quantitative results on simplices in subsets of vector spaces over finite fields. I ...

**4**

votes

**0**answers

52 views

### Chromatic index of hypergraphs

A proper $k$-edge-coloring of a hypergraph $H$ is a mapping from $E(H)$ to a set of $k$ colors so that every pair of adjacent edges receives different colors. We say $H$ is $k$-edge-colorable if
$H$ ...

**2**

votes

**1**answer

65 views

### Connection between bijective maps and subsets of product sets in a multi-variable problem

Let $X$ be a finite set. A bijective map $f: X\to X$ can be represented by a subset $A$ of $X\times X$, such that for every element $a\in X$ there is only one element $b$ so that $(a,b)\in A$, and ...

**3**

votes

**1**answer

39 views

### Simplicial polytope with regular cones

Let $P$ be a convex simplicial polytope in $\mathbb{R}^n$. Can we find a convex simplicial polytope $P_0$ in $\mathbb{R}^n$ combinatorially equivalent to $P$, satisfying the following condition: The ...

**1**

vote

**0**answers

74 views

### Number of intersections that must occur in any partition of a given size

Let $\mathcal{S}$ be the set of all $n$-element subsets of $[2n]:=\{1,\dots,2n\}$.
Consider a partition $\mathcal{P}$ of $\mathcal{S}$ into $m$ blocks $P_1,\dots,P_m$, where all except at most one of ...

**10**

votes

**1**answer

161 views

### Reversals of autonomous subsets in right-angled Coxeter groups

This question has to do with some experimental phenomenon in groups generated by involutions that I cannot explain.
Let $G$ be a finite, undirected graph, and let $W$ be the corresponding right-angled ...

**2**

votes

**0**answers

118 views

### Combinatorial interpretation of inverse modulo $2$ binomial transform of A284005

My question is related to the following:
Sum with products turned into subsequences
We have an identity
$$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\...

**5**

votes

**1**answer

153 views

### Does every $4$-connected nonplanar graph contain a $K_5$-minor?

By Kuratowski's theorem, every nonplanar graph contains a (topological) minor of $K_5$ or $K_{3,3}$.
But I observed that every time I construct a $4$-connected nonplanar graph, it always contains not ...

**2**

votes

**1**answer

144 views

### On the sum $\sum_{i=1}^{m}\binom{m}{i}\frac{(-1)^{i+1}}{2^i-1}$

I want to find out the result of the following summation if some (maybe big) positive integer $m$ is given.
$$
\sum_{i=1}^{m}\binom{m}{i}\frac{(-1)^{i+1}}{2^i-1}
$$
It doesn't seem much possible to ...

**2**

votes

**0**answers

136 views

### Sum with products turned into subsequences

Let $p, q \in \mathbb{Z}$.
Let $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$) and
$$n=2^{t_1}(1+2^{t_2+1}(1+\dots(1+2^{t_{wt(n)}+1}))\dots)$...

**0**

votes

**1**answer

158 views

### Controlling iterated sum sets of "most" of $A+B$

I am reading Tao-Vu book on Additive combinatorics and came across the following lemma. I know that it is better to ask this question on MathStack but I asked few questions before and no one answered ...

**3**

votes

**0**answers

137 views

### Combinatorial interpretation of a determinant

This is a continuation of Worpitzky-like identities?.
Let $ r_k(x)=\prod_{j=1}^k {(\frac{x+j}{j}})^{\min(j,k-j)}.$
As Sam Hopkins has remarked $r_k(x)$ is the number of plane partitions in a $ \...

**1**

vote

**1**answer

62 views

### A sufficient condition for a subcuic graph having a 2-distance vertex 4-coloring

Let $G$ be a subcubic graph with only vertices of degree 1 or degree 3.
Suppose that $G$ has an edge coloring $\varphi$ using colors from $\{1,2,3,4,5\}$ such that
each edge is colored with a set of ...