Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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