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

7,207
questions

**4**

votes

**3**answers

191 views

### Sum of multi-index factorials

Fix $d\in\mathbb{N}\setminus\{0\}$. For $j\in\mathbb{N}\setminus\{0\}$, let
\begin{align*}
[j] = \Big\{\alpha\in \mathbb{N}^d: \sum^d_{i=1}\alpha_i=j\Big\}.
\end{align*}
For $\alpha\in[j]$, define ...

**1**

vote

**1**answer

97 views

### Number of sequences satisfying termination conditions

This question was originally posed on math.SE but seems to require research-level mathematics expertise:
Two players play each other in a match of games of chess where the match winner is the first ...

**2**

votes

**0**answers

71 views

### Getzler's stable graphs for modular operads

In The semi-classical approximation for modular operads, Getzler displays a table at the bottom of page two enumerating certain stable graphs. (This is related to the MO-Q "Stable graphs: Feynman ...

**7**

votes

**0**answers

135 views

### A diagonal generating function for Fibonacci: Part II

In my earlier MO question, I mentioned although we have for the Fibonacci numbers that
$$F_n=[x^n]\left(\frac1{1-x-x^2}\right),$$
is there a function $F(x)$ such that $F_n=[x^n]\left(F(x)\right)^n$?
...

**0**

votes

**0**answers

105 views

### Number of spanning trees in third power of cycle

The following page
https://oeis.org/A005822
gives the number of spanning trees in third power of cycle, for example,
$1, 1, 2, 4, 11, 16, 49, 72, 214, 319, 947, 1408,\ldots $.
It is unclear for ...

**4**

votes

**0**answers

99 views

### Bijections of Littlewood-Richardson coefficients

Let $c^{\lambda}_{\mu\nu}$ be the Littlewood-Richardson coefficients, where $\lambda,\mu,\nu$ are partitions. We know that $c^{\lambda}_{\mu\nu}= c^{\lambda}_{\nu\mu}$. Up to now, what are the ...

**3**

votes

**1**answer

69 views

### Affine equivalence of Coxeter permutahedra?

Suppose that $W=\langle s_1,\ldots, s_d\mid (s_is_j)^{m_{ij}}=e\rangle$ is a finite reflection group and consider its standard $d$-dimensional geometric realization (i.e., the Tits representation) $\...

**5**

votes

**1**answer

185 views

### Tiling rectangle with trominoes - an invariant

There are two types of trominoes, straight shapes and L-shaped. Suppose a rectangle $R$ admits at least one tiling using trominoes, with an even number of L-trominoes.
EDIT: we do not admit ALL ...

**1**

vote

**1**answer

64 views

### Concentration of maxima of a random polynomial with Rademacher coefficients

Let $X_1,\ldots, X_n$ be independent Rademacher random variables (i.e. $\mathbb{P}(X_i=\pm 1)=1/2$). Consider the random polynomial $$P_{n}(t)=c+X_{1}t+X_2t^2+\cdots+X_{n}t^n.$$
Is it well known how ...

**-1**

votes

**1**answer

226 views

### Isomorphism classes of split extensions [closed]

Let $p$ be a prime number and $n$ an integer such that $p\geq n$. Let $P(n)$ denotes the number of partitions of $n$. Can we conclude from Theorem 1.1 and Theorem 1.3 in the reference FINITE_p-...

**2**

votes

**0**answers

48 views

### double shuffle lie algebra

I have a question about the definition of the double shuffle lie algebra discussed in section 1.3 of Sarah Carr's thesis (see https://www.imj-prg.fr/theses/pdf/sarah_carr.pdf)
Recall the definition ...

**14**

votes

**7**answers

2k views

### A special type of generating function for Fibonacci

Notation. Let $[x^n]G(x)$ be the coefficient of $x^n$ in the Taylor series of $G(x)$.
Consider the sequence of central binomial coefficients $\binom{2n}n$. Then there two ways to recover them:
$$\...

**2**

votes

**0**answers

75 views

### Small set in partition-large class

A collection $\mathcal{A}\subseteq \mathcal{P}(X)$
is $k$-large in $X$
if for every $k$-partition
of $X$ namely
$X_1,\cdots,X_k$, there exists an $i\leq k$ such that $X_i\in \mathcal{A}$;
$\mathcal{...

**1**

vote

**0**answers

69 views

### Packing almost-subgroups into a group

We consider a group finite $G$. We say a set $A\subset G$ injects a set $B$ if $|A+B| = |A||B|$, and let $I(B) = \max \{|A| :A\text{ injects } B\}$.
For a subgroup $H$, it is well-known that $I(H) = ...

**1**

vote

**1**answer

61 views

### 2-quotient of integer partition

This question is mostly about understanding the notation used in the following article:
Alex Eskin, Andrei Okounkov, Pillowcases and quasimodular forms, in: Victor Ginzburg (ed.), Algebraic Geometry ...

**1**

vote

**0**answers

161 views

### Combinatorial bijection on monotone sequences

Let $(n),\mu$ be the partition of $n$ define $H_g^{m}((n);\mu)$ count's the number of tuples $(\tau_1,\ldots,\tau_r)$ of transposition in symmetric group $S_n$ with the following conditions
$$ (1,2,\...

**3**

votes

**0**answers

92 views

### Tableaux switching

I'm reading the article Tableau Switching: Algorithms and Applications by Benkart, Sottile, and Stroomer. Do you know if there are any articles or books that talk more about the properties of tableau ...

**1**

vote

**1**answer

236 views

### Closed submonoid of $(\mathbb{C}^*)^n$

The answer of this question might be known but I was not able to find any answer. Let $n\geq 1$ and $S$ be a closed submonoid of $(\mathbb{C}^*)^n$, that is, a closed and stable by product subset of $(...

**1**

vote

**0**answers

55 views

### What is the minimal $m$ for which the independence graph is $n$-universal?

Suppose, an $m$ sided die is rolled. Let's define the independence graph $I_m$ as a graph with the set of all possible events as vertices, and edges between two events iff they are independent.
...

**7**

votes

**0**answers

149 views

### Recognizing reflection subgroups of Coxeter groups

Given a Coxeter system $(W,S)$ with reflections $T$, and any subset $A \subseteq T$, it is known that the reflection subgroup $W_A$ generated by $A$ has a canonical choice $S_A$ of generators so that $...

**1**

vote

**1**answer

63 views

### Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph, what is the smallest number of “curves”?

Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph $G$, what is the smallest number of "curves" in the plane drawn from $u$ to $v$ such that no $u$--$v$ path in $G$ ...

**2**

votes

**0**answers

165 views

### For human proofs of two novel combinatorial identities

For $n=0,1,2,\ldots$, let us define the polynomial
$$S_n(x):=\sum_{k=0}^n\binom{x/2}k\binom{(x-1)/2}k\binom{-(x+1)/2}{n-k}\binom{-(x+2)/2}{n-k}.$$
Such polynomials occur in some series for $1/\pi$ ...

**3**

votes

**1**answer

51 views

### Finding a not too slim triangulation with prescribed vertices on $\mathbb R^2$

Let us fix a constant $r>1$. Let $d(x,y)$ denote the distance between points $x,y\in \mathbb R^2$. Suppose we have a discreet subset $X\subset \mathbb R^2$ such that
1) For any two points $x,x'\...

**1**

vote

**1**answer

125 views

### Explicit upper bound on the number of simple rooted directed graphs on 𝑛 vertices?

Harary mentioned this problem in "The number of linear, directed, rooted, and connected graphs" on p. 455, l. 3–5, but a short and crisp upper bound is missing. I believe that someone must have ...

**1**

vote

**1**answer

215 views

### Sum from combinatorics on nonnegative integer numbers

Let $n_1,n_2,\ldots,n_k\in\{0,1,2,\ldots\}$. Can you calculate the sum
$$
\sum_{n_1,n_2,\ldots,n_k\geqslant0}\mathbb{1}_\left\{n_1+\frac{n_2}{2}+\ldots+\frac{n_k}{k}<1\right\}?
$$
If it's helpful, ...

**4**

votes

**1**answer

75 views

### Upper bound for an expression for distributive lattices

Let $L$ be a finite distributive lattice with minimum $0$ and Maximum $1$ and join-irreducible elements $j_1,...,j_l$ and meet irreducible elements $m_1,...,m_l$.
Let $J_L:= \sum\limits_{i=1}^{l}{| [...

**1**

vote

**1**answer

89 views

### How to generating all flats of the cycle matroid of a graph?

If $M$ is a matroid, I can use M.flats(k) in SageMath to list all the flats of rank $k$. But I hope that there is an algorithm or program to list all flats of the cycle matroid of a graph. And do not ...

**1**

vote

**0**answers

107 views

### Sidon sets in finite groups

Suppose $G$ is a group, $S \subset G$. Let’s call $S$ a Sidon subset iff $\forall$ quadruples $(a, b, c, d)$ of distinct elements of $S$ we have $ab \neq cd$ (named after Simon Sidon who studied such ...

**5**

votes

**0**answers

116 views

### Determinantal formula for plane partitions of shifted shape

For $\lambda = (\lambda_1,\ldots,\lambda_{\ell})$ a partition, a (weak) plane partition of shape $\lambda$ is a filling of the Young diagram of $\lambda$ with nonnegative integers such that entries ...

**0**

votes

**0**answers

33 views

### Proof: shortest paths on a $m \times n$ sliding puzzles exist if number of blocks is smaller than m and n

Let a sliding puzzle of size $m \times n$ be given. Let there be only p occupied positions on that puzzle and let $(x,y)$ and $(x′,y′)$ be arbitrary positions inside the puzzle. What conditions have ...

**2**

votes

**1**answer

116 views

### Tight sublinear estimates for a triple partial binomial summation

Is there tight estimates for the following logarithmic summation ($\gamma,\gamma'\in(0,1)$ and $\mu,\mu'>0$)
$$\log_2\Bigg(\sum_{t=\frac{n^{}}2-n^\gamma\sqrt{\mu\ln n}}^{\frac{n^{}}2+n^\gamma\sqrt{...

**1**

vote

**1**answer

95 views

### Tight estimates for binomial summation

Is there tight estimates for the following logarithmic summation ($\gamma\in(0,1)$)
$$\ln\Bigg(\sum_{t=\frac{n^{}}2-\gamma n^\gamma}^{\frac{n^{}}2+\gamma n^\gamma}\sum_{\ell=\frac{n^{}}2-\gamma n^\...

**1**

vote

**0**answers

62 views

### Sliding puzzle related path finding

Let a sliding puzzle of size $m\times n$, with $p$ empty positions be given. Further, let $(x,y)$ and $(x',y')$ be two arbitrary positions inside the puzzle. What conditions have to be fulfilled s.t. ...

**2**

votes

**2**answers

94 views

### Generalization of independence complex of graphs

Let $G$ be an undirected graph with no multiple edges or loops. Recall that the independece system $\mathcal{I}(G)$ consists of all those subsets $A$ of the vertex set such that the induced subgraph $...

**1**

vote

**1**answer

82 views

### Cliques in overlap graphs for words

Let $\Sigma$ be a finite alphabet, and consider the free monoid $\Sigma^*$. Given $w, w' \in \Sigma^*$ we say that $w$ overlaps $w'$ if there exist non-empty words $u, v, u'$ such that $w = uv$ and $w'...

**0**

votes

**1**answer

147 views

### A combinatorics question: $\lim\limits_{n \to \infty} \frac1{2^{2n}} \sum\limits_{k=1}^n \sum\limits_{i=0}^{k-1} \binom nk \binom ni = \frac12$ [closed]

Am trying to show that $\lim_{n \rightarrow \infty} \frac{1}{2^{2n}} \sum_{k=1}^n \sum_{i=0}^{k-1} \binom{n}{k} \binom{n}{i} =0.5.$
I think that the above result is true but am not sure how to prove ...

**0**

votes

**1**answer

124 views

### On the permanent dominance conjecture for symmetric group

The Lieb's permanent dominance conjecture states that the expression $$\frac{d_{\chi}^HA}{\chi(e)}\le per(A)$$ holds for all positive semidefinite matrices $A$, where $d_{\chi}^HA=\sum_\limits{\sigma\...

**5**

votes

**0**answers

92 views

### submodules of the exterior algebra

Let $A_{n,q}$ be the exterior algebra of a vector space of dimension $n$ over the finite field $F_q$.
Let $a_{n,q}$ be the number of submodules of $A_{n,q}$ (meaning submodules of the $A_{n,q}$-...

**2**

votes

**0**answers

52 views

### Counting binary vectors that satisfy given distance constraints

Let's start with a warm up problem.
Suppose I am given two binary vectors $x, y \in \{0, 1\}^n$ of length $n$ that differ in exactly $r$ places, i.e. $||x-y||_0=r$, i.e. their hamming distance is $r$...

**9**

votes

**0**answers

177 views

### How to describe the power operation on Lie groups?

Let $\mathfrak{g}$ be a semisimple Lie algebra over $\mathbb{C}$, or its compact form over $\mathbb{R}$. Recall that the automorphism group $\operatorname{Aut}(\mathfrak{g})$ is of the form $G^{\...

**1**

vote

**1**answer

53 views

### Finding a cycle of a specific length in an edge-weighted graph

I'm looking for some suggestions on how we might calculate cycles of a specific length in an edge-weighted graph.
For example, imagine my phone tells me that I need to walk three miles today. It ...

**25**

votes

**6**answers

2k views

### Why are we interested in permutahedra, associahedra, cyclohedra, …?

The following families of polytopes have received a lot of attention:
permutahedra,
associahedra,
cyclohedra,
...
My question is simple: Why?
As I understand, at least the latter two were ...

**5**

votes

**0**answers

238 views

### The expressiveness of functions computable on trees

Motivation:
Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...

**0**

votes

**0**answers

31 views

### Matroids with controlled closure growth

Let $\delta > 0$ be some rational constant, and let $r \in \mathbb{N}$ be an integer. I'm looking for an infinite familiy of Matroids of rank $r$ so that
$$ |cl(A)| = C(1+\delta)^{rank(A)}.$$
Here ...

**0**

votes

**0**answers

18 views

### Criteria for whether a CC-System is realizable

Donald Knuth's CC-systems generalize points on the plane. (Their axioms are listed in Wikipedia.)
Are there any simple criteria for testing whether a CC-system is realizable as points on the plane?
...

**9**

votes

**1**answer

194 views

### When does a graph have a circular orientation? Or equivalently can anyone help me characterize this particular class of $3$-colorable perfect graphs?

Call an oriented digraph $D=(V,A)$ circular when for all $\small x,y,z\in V$ if $(x,y)\in A$ and $(y,z)\in A$ then $(z,x)\in A$ or equivalently if $D$ is any oriented digraph whose arc set is a ...

**4**

votes

**1**answer

68 views

### How do I check if two linear binary codes are equivalent?

Suppose I have a list of generator matrices $G_i$, $i=1,\ldots N$, of the same size (each defines an $n$-bit linear binary code encoding $k$ logical bits).
I consider two codes to be equivalent if ...

**6**

votes

**1**answer

200 views

### Limits (growth rates) of power series coefficients

Take two positive integers $m$ and $n$ and consider the rational function
$$G_{m,n}(x,t)=\frac{d}{dx}\left(\frac1{(1-x^m)(1-tx^n)}\right)$$
and the corresponding Taylor expansion as
$$G_{m,n}(x,t)=u_0(...

**1**

vote

**1**answer

137 views

### A balancing property of infinite subsets of $\mathbb{N}$

Let $\omega$ denote the set of non-negative integers and let $[\omega]^\omega$ be the collection of infinite subsets of $\omega$.
If $S\in [\omega]^\omega$ and $A\subseteq \omega$ we say that $A$ is ...

**2**

votes

**1**answer

33 views

### maximum weighted matching with weights being sets

Given a set $S$ and a bipartite graph $G$, each edge $v\in E(G)$ covers a subset $S_v$ of $S$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $V$ the set of ...