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