Tagged Questions
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
0
votes
0answers
6 views
A divisibility of q-binomial coefficients combinatorially
Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient ${a+b \choose a}$. I know how to prove this combinatorially - for example after choosing an ordered set ...
0
votes
0answers
3 views
A divisibility of q-binomial coefficients combinatorially
Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient ${a+b \choose a}$. I know how to prove this combinatorially - for example after choosing an ordered set ...
1
vote
0answers
21 views
Bijective operations on finite simple graphs
Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An ...
10
votes
0answers
38 views
The set of polytopes with given $f$-vector
Let $f=(f_0,\ldots f_n)$ be a vector in $\Bbb N^{n+1}$. Let $X$ be the set of all (ordered) $f_0$-tuples in $\Bbb R^n$ whose convex hull has $f$ as its $f$-vector. Assume that $X$ is non-empty. Is ...
2
votes
2answers
47 views
Spectral decomposition of a combinatorial matrix/Random walks on $s$-sets
$\newcommand{\Z}{\mathbb{Z}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\la}{\lambda}
\newcommand{\1}{\mathbf{1}}
\newcommand{\R}{\mathbb{R}}$
Take any $n\in[3;\infty]$. Here and in what follows, $[k;\...
3
votes
0answers
114 views
Matrix rescaling increases lowest eigenvalue?
Consider the set $\mathbf{N}:=\left\{1,2,....,N \right\}$ and let $$\mathbf M:=\left\{ M_i; M_i \subset \mathbf N \text{ such that } \left\lvert M_i \right\rvert=2 \text{ or }\left\lvert M_i \right\...
0
votes
0answers
29 views
How many possible choices are there to make a ternary tree equal height by inserting nodes?
Suppose $T$ is a ternary tree with $s$ nodes. Here, a tree is ternary if every node in the tree is either a leaf node (with no child) or a non-leaf node with exactly three child. See below for a ...
6
votes
1answer
157 views
Is this bound uniform in $N$?
I encountered this small combinatorial problem and do not quite know how to solve it:
Consider a set $\mathbf N:=\left\{1,2,....,N \right\}.$ This set has $\binom{N}{2}$ many subsets of cardinality $...
4
votes
0answers
134 views
Random walk on $\mathbb{R}$ with “sticky” origin
Let $P_i$, $N_i$, and $Z_i$, $i\in\mathbb{N}$ be r.v.'s with the $P_i$, $N_i$, and $Z_i$ being identically distributed with known pdf's $f_P$, $f_N$, and $f_Z$, respectively; and with no dependence ...
2
votes
1answer
137 views
The largest number $y$ such that $(x!)^{x+y}|(x^2)!$
Since the multiplication of $n$ consecutive integers is divided by $n!$, then $(n!)^n|(n^2)!$ with $n$ is a positive integer.
Are there any formula of the function $y=f(x)$ that shows the largest ...
-3
votes
0answers
51 views
Higher Derivative of Rational function [on hold]
As is well known, every rational function $R(x)$ has a partial fraction decomposition. i.e.$$ R(x) = \frac{p(x)}{q(x)} = P(x) + \sum_{i=1}^m\sum_{r=1}^{j_i} \frac{A_{ir}}{(x-a_i)^r} + \sum_{i=1}^n\...
9
votes
0answers
235 views
Why does Loday call the permutohedra “zylchgons”?
Today I was reading Jean-Louis Loday's classic paper, "Realization of the Stasheff polytope", in which he produces a simple and very pretty realization of the associahedra as convex polytopes. He ...
2
votes
1answer
60 views
On submatrices: size bound
Let $M$ be a generic $2n\times 2n$ matrix and fix $k\leq n$.
Suppose $\mathcal{F}$ is a family of submatrices under the conditions that $A\in\mathcal{F}$ provided
(a) $A$ is a $k\times k$ ...
2
votes
1answer
118 views
Decide if a system of arithmetic sequences is an $m$-cover of $\mathbb{N}$
Let $A = \{ a_i + b_i \mathbb{N} \}_{i=1}^{k}$, where $a_1, \ldots, a_k \in \mathbb{N} \cup \{0\}$ and $b_1, \ldots, b_k \in \mathbb{N}$ be a system of arithmetic sequences.
For a positive integer $m$...
1
vote
1answer
117 views
Reference request: Catalan number of type B
Are there some generalized Catalan number of type $B$ such that the sequence of the numbers is $3,9,29,97,333$ for $n=2,3,4,5,6$?
As discussed in this previous question, there are at least two types ...
10
votes
2answers
343 views
Seeking a more symmetric realization of a configuration of 10 planes, 25 lines and 15 points in projective space
I've got ten (projective) planes in projective 3-space:
\begin{align}
&x=0\\
&z=0\\
&t=0\\
&x+y=0\\
&x-y=0\\
&z+t=0\\
&x-y-z=0\\
&x+y+z=0\\
&x-y+t=0\\
&x+y-t=0
...
1
vote
1answer
63 views
$k$-substrings of a binary string
Let $k > 1,$ and $a=a_1a_2...a_{2k-1}$ be a binary string, i.e. $a_i\in \{0,1\}$. Consider contiguous substrings of $a$ of length $k (k-$substrings$): b_i := a_ia_{i+1}...a_{i+k-1}, 1\leq i\leq k$. ...
2
votes
2answers
229 views
how to calculate the following integral related to Chebyshev polynomials
Chebyshev polynomials of the second kind $V_n(x)$ can be defined as
$$V_n(x)=\frac{\sin(n+1)\theta}{\sin\theta}, x=2\cos\theta$$
or through the recurrence relation
$$V_{n+1}=xV_n-V_{n-1}, V_0=1, V_1=...
7
votes
1answer
295 views
A combinatorial property of uncountable groups, II
Problem 1. Is it true that each uncountable group $G$ contains two subsets $A,B\subset G$ such that
1) for any $x,y\in G$ the intersection $xA\cap yB$ is finite and
2) for any function $\...
4
votes
1answer
86 views
+50
Component properties in Euclidean graphs with distance threshold
In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...
0
votes
1answer
57 views
Graphs represented by a subset of a metric space
Let $(X,d)$ be a metric space, and suppose $S\subseteq X$ is a finite subset in which all pairwise distances are distinct (formal definition here).
If $x\in S$ and $k$ is a non-negative integer with $...
3
votes
2answers
241 views
Number of self avoiding paths on a grid graph?
Let $G$ be an $n \times n$ grid graph. Is there anything known about the asymptotic growth rate of the number of self avoiding paths from $(0,0)$ to $(n,b)$ (from the lower left corner to some ...
10
votes
3answers
302 views
Cardinality of families of subsets of $\mathbb{N}$ whose intersections are finite
Does there exist an uncountable $P \subset \mathcal{P}(\mathbb{N}) $ with the property that for any distinct $x,y \in P$, $|x \cap y|$ is prime?
A more general, but likely harder, question: is it ...
5
votes
0answers
143 views
$X$-rays of permutations
Consider the set of permutations $\mathfrak{S}_n$, on $\{1,2,\dots,n\}$, and identify each element $\pi\in\mathfrak{S}_n$ with the corresponding permutation matrix.
There has been some study (e.g. ...
0
votes
0answers
161 views
On the connection between Faulhaber's formula and identity $n^{2m+1}=\sum_{k=0}^{n-1}\sum_{j=0}^m A_{m,j}k^j(n-k)^j$
This question is part of series of the questions, as follows:
Coefficients in the sum $\sum_{k=0}^{n-1}\sum_{j=0}^{m}A_{j,m}(n-k)^jk^j=n^{2m+1}$,
Coefficients $U_m(n,k)$ in the identity $n^{2m+1}=\...
3
votes
1answer
189 views
Generating function for 3 -core partitions: Part II
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$.
We call $\lambda$ a $t$-core partition if none of ...
4
votes
0answers
81 views
Number of hereditary modules of a hereditary algebra
Let $Q$ always denote a Dynkin quiver.
Given a connected path algebra $A=kQ$ and a module $M$, is there a useful criterion on $M$ when $End_A(M)$ is again a connected quiver algebra?
Call a module ...
4
votes
4answers
190 views
partial alternating sum involving binomial coefficients
I came across the following alternating sum
$$
\sum_{k=0}^n (-1)^k \binom{2n}{k} (n-k)^r,\quad 1\leq r < n.
$$
It seems that when $r$ is an even integer the sum is $0$ and when $r$ is an odd ...
4
votes
1answer
107 views
Generating function for $3$-core partitions
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$.
We call $\lambda$ a $t$-core partition if none of ...
4
votes
0answers
71 views
equidistributed parameters on graphs
Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I wonder whether there are any 'interesting' combinatorial parameters $a,b: \mathcal G_n\to \mathbb ...
4
votes
0answers
152 views
Two congruence conjectures modulo prime p
How to prove the following two congruences?
Question1: Let $p\equiv 1 \pmod 3$ be a prime, then
$$\sum_{k=0\atop k\neq(p-1)/3}^{(p-1)/2}\frac{\binom{2k}k}{3k+1}\equiv 0 \pmod p.$$
...
36
votes
3answers
1k views
+100
A curious process with positive integers
Let $k > 1$ be an integer, and $A$ be a multiset initially containing all positive integers. We perform the following operation repeatedly: extract the $k$ smallest elements of $A$ and add their ...
7
votes
2answers
167 views
A link between hooks and contents: Part II
This is a question in the spirit of an earlier problem.
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$.
Recall also the notation for the content of a cell $...
3
votes
1answer
105 views
On decomposition of finite Abelian groups
It is easy to see that for any finite Abelian group $G$ and any numbers $a,b$ with $|G|=ab$ there exist a subgroup $A\subset G$ and a subset $B\subset G$ such that $|A|=a$, $|B|=b$ and $G=A+B$, where $...
6
votes
2answers
122 views
A link between hooks, contents and parts of a partition
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Denote its conjugate partition by $\lambda'$. For example, if $\lambda=(4,3,1)$ then $\lambda'=(3,2,2,1)$.
...
7
votes
3answers
596 views
Counting configurations on a 2xn board under restrictions [closed]
Find the number of ways of selecting k cells from a $(2\times n)$-board such that no two selected cells share a side (non-adjacent).
For $n=3$ and $k=2$, the answer is $8$; for $n=5$ and $k=3$, the ...
5
votes
1answer
90 views
SYT and contents of a partition
Let $\lambda$ be an integer partition, denote the number of Standard Young Tableaux of shape $\lambda$ by $f_{\lambda}$. This number is computed by the formula
$$f_{\lambda}=\frac{n!}{\prod_{u\in\...
2
votes
0answers
22 views
condition on rational polyhedral cone to guarantee dual cone is homogeneous
Let $\sigma\subseteq \Bbb R^d$ be a full-dimensional rational polyhedral cone which is strongly convex (i.e. $\sigma\cap-\sigma=0$).
Definition. The cone $\sigma$ is homogeneous if there are ...
1
vote
0answers
73 views
Axiomatization of the shuffle decomposition
I am trying to figure out an axiomatization for Reedy categories such that the product of representables admits a shuffle decomposition. Cisinski suggested imposing a condition, which we will state ...
6
votes
0answers
151 views
A binomial determinant formula: a new variant
In a previous MO question, the OP asks a proof for $\det_{1\leq i,j\leq n}\left(\binom{i}{2j}+\binom{-i}{2j}\right)=1$. Subsequently, Gjergji Zaimi generalized the problem to
$$\det_{1\le i,j\le n}\...
4
votes
0answers
59 views
Sum of all projective dimensions of simple modules
Let $X_{n,t}$ be the set of all finite dimensional algebras (we can assume they are given by a connected quiver and admissible relations) that have global dimension equal to $n$ and $t$ simple modules....
4
votes
1answer
192 views
Understanding proof about chromatic number
Consider an undirected graph $K(n,k,i)$, with the all $k$-element subsets of $\{1,\dots,n\}$ as vertices, and two vertices connected by an edge if their sets intersect in less than $i$ elements.
...
3
votes
1answer
60 views
$|V|$ and $|E|$ in hypergraphs with a separation property
Let $H=(V,E)$ be a hypergraph. We call it $T_0$ if for all $x\neq y \in V$ there is $e\in E$ with $\{x,y\}\not\subseteq E$ and $\{x,y\}\cap e\neq \emptyset$ (i.e., $e$ contains exactly one of $x,y$).
...
9
votes
1answer
189 views
Orientations of Planar Graphs
Let $G$ be a $2$-edge-connected graph drawn in the plane (such that the edges intersect only at the endpoints). I want to orient
the edges of $G$ such that for each vertex $v$, there are no
three ...
4
votes
0answers
103 views
On the parity of $|\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ \ j(j+1)\ \text{mod}\ p\,>\,k(k+1)\ \text{mod}\ p\}|$ with $p$ prime
Let $p=2n+1$ be an odd prime, and let $a_1<\ldots<a_{n}$ be all the quadratic residues mod $p$ among $1,\ldots,p-1$. For $a\in\mathbb Z$ let $\{a\}_p$ be the least nonnegative residue of $a$ ...
3
votes
1answer
134 views
Partitions and $q$-integers
Denote an integer partition of $n$ by $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq\lambda_k)$ where $\lambda_k>0$. Also recall the $q$-analogues of integer $n$ given by $[n]_q=\frac{1-q^n}{1-q}$. ...
0
votes
1answer
116 views
Number of compositions of n into k parts (where 0 and 1 are not allowed as parts) [closed]
I know that there is a formula where even 0 is treated as significant, but is there a formula where 1 and 0 cannot be parts?
Edit:The formula that I was referencing was (Excuse the presentation) $\...
19
votes
3answers
774 views
Does the hypergraph of subgroups determine a group?
A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...
1
vote
0answers
52 views
Number of intersections formed by chords connecting all N evenly spaced nodes on a circle [migrated]
Non-mathematician here, sorry if terminology is wrong.
For a circle with N evenly spaced nodes on the perimeter;
With chords connecting every node to every other node;
What is the total number of ...
5
votes
0answers
103 views
A nowhere-zero point in a linear mapping conjecture
I found a very interesting problem in the Open Problem Garden, which I am surprised is not as well-known as I would think it would be:
Prove that If $p>3$ is prime and $A$ is an invertible $n \...
