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.

Filter by
Sorted by
Tagged with
4
votes
3answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
7answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
6answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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 ...