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.
10,558
questions
5
votes
1
answer
307
views
Show a sequence of sums involving Catalan Numbers converges
Let $C_n$ be the $n$-th Catalan Number and let $\mathcal{O}_{s,j} = {{2s-j-1}\choose{j}} C_{s-j}^2$. Then we want to consider $\mathcal{E}_s = \sum_{j=0}^{s-1} (-1)^j\mathcal{O}_{s,j}$. We want to ...
- 313
1
vote
0
answers
85
views
An identity in Weyl group
Let $W$ be a Weyl group generated by the simple reflections $s_i$, $i \in I$, where $I$ is the vertex set of the Dynkin diagram of $W$. For $J \subset I$, let $W_J$ be the subgroup of $W$ generated by ...
- 6,121
8
votes
1
answer
204
views
Length of optimal play in Hex as a function of size
Consider Hex on an $n \times n$ board without a swap rule, so that the first player wins. Assume the first player tries to minimize the length of the game, and the second player tries to maximize the ...
- 1,758
0
votes
0
answers
119
views
Maximizing the sum of hook lengths
Given positive integers $a\geq b$, and $n\in\{1,2,\dots,ab\}$ I am looking for a partition of $n$ into at most $b$ parts of size at most $a$ which maximizes the sum of the hook lengths in the ...
- 2,946
7
votes
0
answers
271
views
What are $(m,n)$-pseudoplanes?
An incidence geometry is a set $P$ (the "points"), a set $L$ (the "lines"), and a relation $I\subseteq P\times L$ ("incidence"). Equivalently, a bipartite graph with the halves of the partition ...
- 4,431
1
vote
2
answers
239
views
Is there a standard name for this type of multidigraph?
A digraph (direct graph) consists of a set $V$ of vertices and a set $E$ of directed edges $v\to v'$. A multidigraph is a digraph in which $E$ is a multiset, so edges may appear multiple times in $E$, ...
- 45.7k
8
votes
1
answer
211
views
Categorification of monotone maps via tilting modules?
It is well known that for the algebra of $n \times n$-upper triangular matrices over a field the number of tilting modules is equal to the Catalan number $C_n$. This is just the (hereditary) Nakayama ...
- 26k
1
vote
1
answer
163
views
Modular arithmetic and elementary symmetric functions
Denote the elementary symmetric functions in $n$ variables by $e_k(x_1, x_2,\dots, x_n)$. In the special case $x_j=j$, simply write $e_k(n)$ for $e_k(1, 2, \dots, n)$. Next, define the sequence
$$a_{+}...
- 41.8k
9
votes
1
answer
396
views
Are bipartite Moore graphs Hamiltonian?
This is motivated by a computer-generated conjecture that bipartite distance-regular graphs are hamiltonian. I decided to check the case of Moore graphs first.
The cycles and complete bipartite graphs ...
- 9,421
9
votes
1
answer
277
views
Decomposition of even symmetric polynomials and Euler numbers
Let's denote the even part of a polynomial $p$ by $E[p]$, which means only taking into account the monomials in $p$ which are even in all the arguments. Now let's consider the even part of the ...
- 535
8
votes
1
answer
482
views
Prove that these are polynomials
Define the functions
$$F_n(q)=\frac1{(1-q)^{2n}}\sum_{k=0}^n(-q)^k\frac{2k+1}{n+k+1}\binom{2n}{n-k}
\prod_{j=0,\,j\neq k}^n\frac{1+q^{2j+1}}{1+q}.$$
The numbers $\frac{2k+1}{n+k+1}\binom{2n}{n-k}$ ...
- 41.8k
1
vote
0
answers
42
views
Why are the definitions of i-good nodes of a multipartition equivalent?
Let $e\geq 2$ and $0\leq i\leq e-1$.
For a multipartition $\lambda\vdash_\ell n$ of $n $ one can define the notion of an $i$-good box of the Young diagram of $\lambda$. But there are seemingly ...
6
votes
1
answer
487
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$) ...
- 61
3
votes
1
answer
218
views
Density of a somewhat random set
The density of a set
$X\subseteq\omega$ refers to:
$\limsup\limits_{n\rightarrow\infty}\dfrac{C\cap n}{n}$.
Given a set of positive integers
$F= \{m_0<\cdots<m_{k-1}\}$,
let $C\subseteq \omega$...
- 909
3
votes
0
answers
188
views
Permutation statistics in multiple rows
Usually we study the statistics of a permutation written in one row. Is there any result for the statistics of a permutation written in multiple rows? Let me give an example in order to be more clear: ...
- 535
10
votes
1
answer
526
views
Counting symmetric subgroups of symmetric groups
This question is related to, but much more specific than, this one.
For $k \leq n$, let $a(k,n)$ denote the number of conjugacy classes of subgroups of the symmetric group $S_n$ which are isomorphic ...
- 2,693
8
votes
1
answer
450
views
Real-rootedness of some polynomials
Denote the unsigned Stirling numbers of the first kind by $s(n,j)$.
Question. Is it true that the polynomials
$$P_n(x)=\sum_{j\geq0}s(n,j)\binom{x}j$$
have only real roots?
Note. Obviously, the ...
- 41.8k
4
votes
0
answers
81
views
Number of surjections of a given complexity
Definition:
The complexity of a surjection $\{1,\ldots,n+k\}\rightarrow \{1,\ldots,n\}$ is defined in the following way. First think of this map as the tuple $(f(1),\ldots,f(n+k))$. For two numbers $...
- 10.3k
11
votes
2
answers
402
views
Explicit permutation representation of the Schur double cover of the symmetric group
Main question: How can we describe the double covers $(2\cdot\mathfrak{S}_n)^+$ and $(2\cdot\mathfrak{S}_n)^-$ of the symmetric group $\mathfrak{S}_n$ as permutation groups? (I.e., what sort of set ...
- 30.1k
1
vote
2
answers
56
views
Achieving every possible ranking by rearranging weights
This problem actually arose as a question in the real world (see the paragraph "Origin of the problem" below).
Let $\mathbb{N}$ denote the set of the positive integers and let $n\in\mathbb{N}$. If $...
- 45.4k
3
votes
0
answers
173
views
Refined f- and h-partition polynomials of the associahedra
The f-polynomials, $F_n(x)$ (cf. OEIS A126216, A033282, and A086810), and the h-polynomials, $H_n(x)$ (cf. A001263, the Narayana polynomials), of the family of simple convex polytopes the associahedra ...
- 9,931
7
votes
0
answers
182
views
Positivity of certain polynomial coefficients
Consider the rational functions (in fact, polynomials)
$$F_n(q)=\frac1{(1-q)^{2n}}\sum_{k=0}^n(-q)^k\frac{2k+1}{n+k+1}\binom{2n}{n-k}
\prod_{j=0,\,j\neq k}^n\frac{1+q^{2j+1}}{1+q}.$$
The numbers $\...
- 41.8k
1
vote
1
answer
374
views
References on Power Sums
Consider a recent arXiv preprint 1805.11445. The author of 1805.11445 has done an overview of classical problem of simplifying of power sum
$$\sum_{1\leq k\leq n}k^m, \ (n,m)\geq 0, \ m=\mathrm{const}...
- 167
8
votes
0
answers
169
views
Nonzero subdeterminants conjecture: has anybody seen this anywhere?
I already posted this question on Mathematics StackExchange. A user there suggested that I rather post it on mathoverflow, since it is a research question. So here it is.
Let $m\geq2$, $n\geq1$ be ...
- 291
13
votes
3
answers
1k
views
Cops, Robbers and Cardinals: The Infinite Manhunt
Cops & Robbers is a certain pursuit-evasion game between two players, Alice and Bob. Alice is in charge of the Justice Bureau, which controls one or more law enforcement officers, the cops. Bob ...
2
votes
3
answers
382
views
how to get the coefficient of a special term in the expansion of the graph polynomial?
What is the coefficient $c$ of the term $x_1^2x_2^2x_3^2\cdots x_{12}^2$ in the expansion of the following multivariable polynomial:
$(x_1-x_2)(x_1-x_3)(x_1-x_4)(x_1-x_{10})(x_2-x_3)(x_2-x_5)(x_2-...
- 767
2
votes
0
answers
204
views
Real-rooted polynomials with coefficient constraints
My question is whether there exists $(a_0, a_1, \ldots, a_{2n-1}) \in \mathbb{R}_{+}^{2n}$ such that
(1). $a_{2k} + a_{2k+1} = \binom{3n-1}{3k} + \binom{3n-1}{3k+1} + \binom{3n-1}{3k+2}$ for all $0 \...
- 151
4
votes
1
answer
221
views
A permutation problem for finite subsets of an abelian group
Here I ask the following question in additive combinatorics.
QUESTION: Let $A$ be any finite subset of an additive abelian group $G$ with $|A|=n>3$. Can we write $A$ as $\{a_1,\ldots,a_n\}$ so ...
- 14.5k
1
vote
1
answer
114
views
Probability for a group of stones to live on an infinite Go board
Suppose on an infinite two dimensional Go board the tengen is occupied by a black stone, and every other grid point is occupied by a black stone, or a white stone, or nothing, with probability 1/3 ...
- 5,129
1
vote
1
answer
190
views
A question about a $2^n$-point metric space
For any positive integer $n$, let $X_n$ be the family of all subsets of $\{1,2,\cdots,n\}$.
Let $(X_n,d)$ be the metric space such that
$$d(A,B)=|\,A\triangle B\,|,\ \forall A,B\in X_n$$
where $A\...
- 1,987
0
votes
1
answer
199
views
An interesting series converging to a constant
Let $K>0$ be a constant. Suppose $\{z_n\}_{n=1}^\infty$ is a non-decreasing positive sequence. Then the series
$$\sum_{n=1}^\infty\frac{z_n}{(K+z_1)(K+z_2)\cdots(K+z_n)}K^n=K$$
This is a quite ...
- 21
11
votes
1
answer
800
views
Graphs with only disjoint perfect matchings, with coloring
The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be ...
- 155
0
votes
1
answer
226
views
Funny recurrence
Could someone help me solve the following recurrence?
$$
T(k) \le 1+\sum_{i=1}^{n_k}T(k_i),
$$
where $n_k\le k$, $k_i\le \frac23 k$ $\forall i = 1, \dots n_k$, and $\sum_{i=1}^{n_k}k_i \le k$.
The ...
- 63
3
votes
0
answers
696
views
Puzzle in 3D grid with black and white boxes, related to shelling
Consider a $n$ by $n$ by $n$ grid represented by the set of $3$-uples $S=\{1,2,\dots, n\}^3$.
A line (resp. slice) of $S$ is a subset of cardinal $n$ (resp. $n^2$) where two components (resp. one ...
3
votes
0
answers
56
views
Separating stars and large intersections of cycles
Let $\Gamma$ be a finite simplicial graph. For every $k \geq 0$, let $C_k(\Gamma)$ denote the graph whose vertices are the induced cycles of $\Gamma$ and whose edges link two cycles if their ...
- 7,481
7
votes
0
answers
261
views
Is every integer $n>1$ the sum of two squares and two central binomial coefficients?
Those integers $\binom{2n}n\ (n=0,1,2,\ldots)$ are called central binomial coefficients. By Stirling's formula,
$$\binom{2n}n\sim \frac{4^n}{\sqrt{n\pi}}\ \ \ \ (n\to+\infty).$$
Of course, the ...
- 14.5k
6
votes
0
answers
166
views
How to represent the even signed permutations by Young tableaux?
The well-known RSK correspondence established the connection between table pair (P,Q) and the permutations in symmetry group Sn(Coxeter group of type A). Also, there is a similar correspondence for ...
- 61
4
votes
1
answer
397
views
Bijection between noncrossing matchings on $2b$ points and Standard Young Tableaux of size $2 \times b$
I'm currently reading a review article called Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance by Jessica Striker. In this article, Striker writes that there is a ''nice'' ...
- 95
0
votes
1
answer
115
views
The number of a family of sequences of subsets of $\{1,2,\cdots,n\}$
Given integers $m,n\geq 1$, let $W_{n,m}$ denote the family of all sequences $S_1,S_2,\cdots,S_m$ satisfying
(1) every $S_i$ is a subset of $\{1,2,\cdots,n\}$;
(2) $\mid S_i\cap S_j\mid\geq 3$ for ...
- 1,987
4
votes
1
answer
204
views
Balancing points with lines
$\newcommand{\F}{\mathbb F}$
Suppose that $p$ is a prime, and $k<p/2$ a positive integer.
Consider a system of $k$ distinct directions in the affine plane $\F_p^2$, and the system of $k$ pencils ...
- 22.8k
2
votes
0
answers
49
views
Size of the last non-empty $k$-core of a random graph
Given $n$ and $p$ for $G(n,p)$, how to find the distribution of the size of the non-empty $k$-core with largest $k$?
In particular, what is the probability (for any $n$ and $p$) that only $c$ ...
- 21
6
votes
2
answers
665
views
Is the value of $\sum\limits_{k=1}^{\infty}\frac1{(C_k)^n}$ known?
I posted the question https://math.stackexchange.com/questions/2799068/is-the-value-of-sum-limits-k-1%e2%88%9e-frac1c-kn-known before on mathstackexchange but realised that it might be more ...
- 26k
4
votes
1
answer
148
views
sets of partitions associating any two elements exactly once
There may be a theory that deals with problems like this but I'm not
enough of a mathematician to know what it is. So far I've looked up
braid groups, block design, and the recommended related posts ...
- 41
2
votes
1
answer
268
views
How to recover $k$ lost items in binary data $x_1,x_2,x_3 \dots,x_n$ via only XOR operator?
I asked this question in math.stackexchange (link) and I have had an answer for general case by using Reed-Solomon Code. More information for Reed-Solomon Coding for Fault-Tolerance in RAID-like ...
- 302
3
votes
1
answer
233
views
Nekrasov Partition Function: $F^{inst}(\epsilon_1,\epsilon_2,\mathbf{a},\mathbf{q})$ analytic at $\epsilon_1 = \epsilon_2 = 0$?
Nakajima & Yoshioka [1] showed that
\begin{equation}
F^{inst}(\epsilon_1,\epsilon_2,\mathbf{a},\mathbf{q}) = \sum_{n = 1}^\infty \mathbf{q}^nF^{inst}_n(\epsilon_1,\epsilon_2,\mathbf{a}) := \...
- 415
2
votes
0
answers
40
views
Efficient $H$ representation of matrices with distinct cyclic shift permuted entries
Given points $v_1,\dots,v_n\in\mathbb Z^n$ in codimesion $1$ hyperplane $x_1+\dots+x_n=t$ with $0\leq x_{i}$ and a cyclic shift permutation $\sigma$ where
$v_1,\dots,v_n$ when written as columns of ...
- 13.7k
4
votes
0
answers
92
views
Totally Unimodular matrix edited from ordinary matrix
Given a matrix $M\in\{0,1\}^{m\times n}$ is there an algorithm to tell if we can convert some of $1$s to $-1$s and make $M$ Totally Unimodular and output such a Totally Unimodular in polynomial in $mn$...
- 13.7k
1
vote
1
answer
128
views
Number of distinct points in an n-dimensional tetrahedron
Consider an n-dimensional tetrahedron with $n+1$ vertices $\langle v_0, v_1, \dots,v_n\rangle$. $v_0$ is the origin while $v_i$ lies on $e_i$ (the $i^{th}$ coordinate axis) at a distance $D$ from the ...
1
vote
1
answer
65
views
Existence of dense graph with relatively small codegree?
Let $n$ be some parameter tending to infinity. I am wondering does there exists some kind of graphs $G$ on vertex-set $[n]$ with maximum degree less than $D$, so that
$D\ge n/w_1(n)$,
$e_G$, the ...
- 251
3
votes
1
answer
183
views
Reference request: denominators of lonely runner numbers
The lonely runner conjecture states that for $M=\{m_1,...,m_n\}$ a set of distinct positive integers the quantity
$$
\kappa(M):=\sup_{t \in \mathbb{R}} \min_i ||tm_i||
$$
satisfies $\kappa(M) \geq \...
- 2,693