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.
8,478
questions
8
votes
0answers
280 views
A bijective proof for the odd companion to Shapiro's Catalan convolution
Shapiro's Catalan convolution is the following formula (where $C_n$ is the $n$th Catalan number):
$$
\sum_{k=0}^{n}{C_{2k}C_{2(n-k)}}=4^nC_n.
$$
In other words, letting $C(z)=\sum_{n=0}^{\infty}{C_nz^...
1
vote
1answer
181 views
Partitioning a convex $n$-polygon
Let $P$ be a convex polygon with $n\ge3$ vertices. Let $\mathcal{Z}_K(P)$ be a partition of the polygon into $K$ polygonal (but not necessarily convex) parts whose interiors are pairwise disjoint,
$$
\...
1
vote
0answers
131 views
For any $n-1$ elements of $\mathbb Z/n\mathbb Z$, we can make $0$ using $\{-,+,\times\}$ without parentheses
MSE: Just using $+$ ,$-$, $\times$ using any given n-1 integers, can we make a number divisible by n? (no brackets allowed)
Is there any hope in proving the following? (Cross-posted here after a ...
3
votes
0answers
60 views
On a connectivity property of set systems
Let $X\neq \emptyset$ be a set and let ${\cal A}\subseteq {\cal P}(X)$ with $\bigcup {\cal A}=X$. We say that $S\subseteq X$ is indivisible if for all $T\subseteq S$ with $\emptyset \neq T \neq S$ ...
14
votes
2answers
1k views
How many category structures are possible on two sets?
For two sets $O$ and $A$, we will call a category structure a collection of functions ${\sf dom}:A\to O,\ {\sf cod}:A\to O,\ {\sf 1}:O\to A,\ \circ:A\times_OA\to A$ satisfying the usual axioms for a ...
6
votes
2answers
187 views
A convolution-type identity for the “major index”
For a permutation $\pi\in\frak{S}_n$, define the number of descents of $\pi$ as $$\text{des}(\pi)=\vert\{i: \pi(i)>\pi(i+1)\}\vert.$$
The following is a well-known (and interesting) identity:
$$\...
2
votes
0answers
92 views
Enumeration and encoding of simplicial complexes
I'd like to know how to enumerate and encode all (abstract) simplicial complexes of a given kind.
To start as simple as possible, consider the familiy $\mathcal{S}_n^{d}$ of simplicial complexes which ...
2
votes
0answers
51 views
Inverting “codimension matrix” for polytopes?
Let $P$ be an abstract polytope. Let's construct its square matrix $A$ as follows. Its lines and columns are labelled by all faces of $P$, of all dimensions. Put $A(F_1,F_2)=t^m$ if $F_1$ is a subface ...
9
votes
0answers
306 views
A robust version of Harper's theorem
Let $S$ be subset of $\{0,1\}^n$ with cardinality $k$.
Denote by $\Gamma_r(S)$ the union of all Hamming balls with centers in $S$ and radius $r$.
Harpers's theorem states that $\Gamma_d(S)$ is minimal ...
0
votes
0answers
35 views
The linear embedding complexity of subsets of $0/1$ cube
We say $\pi$ is a subset of the $0/1$ integer points in $t$ dimensions represented by coordinates $(x_1,\dots,x_t)$ of complexity $\log^ct$ if there is an $A$ of $2^{\log^ct}\times2^{\log^ct}$ ...
0
votes
0answers
34 views
Travelling salesman problem with variable weights
Take a fully connected graph with $v$ vertices. We assign weights to edges using an arbitrary function $f_{ij}(x)$ for pairs of vertices $0 < i, j \le v$, then starting at $c_{0}=0$, traverse the ...
1
vote
0answers
187 views
Solution to system of linear equations
Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...
3
votes
0answers
84 views
Ehrhart-Macdonald reciprocity with multiplicities
Let $P$ be a convex lattice polytope in $\mathbb{R}^n$. The function $L(t, P) = |\mathbb{Z}^n \cap t\cdot P|$ is a polynomial, and we have an equality
$$L(-t, P) = (-1)^nL(t, P^{int}),$$
where $P^{int}...
4
votes
2answers
249 views
High degree differences in bipartite graphs
Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us define the quantity:
$$\mathcal{I}_k(G) := \sum_{1\le i,j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v_i)-\...
5
votes
1answer
135 views
Signs in Chevalley systems for reductive groups
Let $G$ be a pinned split reductive group. There exists a Chevalley system:
For each root $b$ in its root system there are parametrisations $x_b: \mathbb{G}_a \rightarrow U_b$ of the corresponding ...
7
votes
1answer
309 views
Independent vectors in the permuting coordinates action of $S_n$ on $\mathbb{R}^n$
Let $V$ be the hyperplane in $\mathbb{R}^n$ with equation $\sum_i x_i=0$. The symmetric group $S_n$ acts on $V$ by $s\cdot (v_1,\ldots,v_n)=(v_{s^{-1}(1)},\ldots,v_{s^{-1}(n)})$. Consider those $v\in ...
3
votes
1answer
185 views
Difference set of difference set
I am a hobby computer scientist and searching for an algorithm to construct a set of n numbers (integers) with certain properties.
Property 1 / Step 1
All pairwise differences of the elements should ...
3
votes
0answers
122 views
Partitions of n into k distinct parts which are multiples of given numbers
Is there anything known about the number of partitions of an integer $n$ into $k$ distinct parts in the following way?
Let $a_1,\dotsc,a_k\geqslant1$ be given integers. In how many ways can we write $...
2
votes
0answers
105 views
Magic squares as sums of permutation matrices
A magic square of size $n$ and sum $k$ is a $n\times n$ matrix with non-negative integer elements, whose rows and columns all sum to $k$. A permutation matrix is a magic square of sum $1$. Every magic ...
2
votes
1answer
52 views
Minimal volume of fundamental domains of lattices
Consider a full rank integer lattice in $\mathbb{R}^n$. Let $v_1$ be the shortest non-zero vector in the lattice, $v_2$ be the shortest one among those not parallel to $v_1$, $v_3$ be the shortest one ...
11
votes
1answer
416 views
“Drinking number” of a graph
Motivation. A while ago I attended a party and I only knew some, but not all, of the attendees. There were 2 kinds of drinks: beer and soda. I noticed that amongst my acquaintances, more than half ...
8
votes
1answer
208 views
Find all Non-isomorphic good drawings of $K_{3,3}$？
Sometimes I look at all non-isomorphic good drawings of graphs on a plane or sphere.
Good drawing means that no edge crosses itself, no two edges cross more than once, and no two edges incident with ...
1
vote
1answer
74 views
Knapsack problem with capacity constraint
The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...
5
votes
0answers
71 views
Permutations in a Bruhat interval with a fixed point
Let $[e,\sigma_0]$ be the Bruhat interval of the permutations $\sigma\leq \sigma_0$ for the (strong) Bruhat order. I am interested in the following set, for fixed $i,j$:
$$[e,\sigma_0]_i^j:=\{ \sigma \...
1
vote
1answer
114 views
Partity of partitions with distinct parts of parts $>1$
This question is motivated by my earlier (unanswered) MO post.
The number of partitions into distinct parts is generated by $\sum_{n\geq0}Q(n)x^n=\prod_{k\geq1}(1+x^k)$. Focusing on parity of ...
0
votes
0answers
44 views
Sufficient criterion for unit distance graphs
There are many necessary criteria for a graph to be a unit distance graph. For example, it must not have $K_4$ as a subgraph etc. Can we find some sufficient criterion for a graph to be a unit ...
2
votes
1answer
285 views
Is the number of words finite, when you don't know how to count?
This question is inspired by this one:
Can you do math without knowing how to count?
Let $M_2$ be the set of words constructed by concatenation of the letters $a_1$ and $a_2$, with :
(*) : for any $x$ ...
15
votes
2answers
638 views
n sets, each is large, the intersection of every three is small, what is the size of the union?
Let $A_1, A_2, \ldots, A_n$ be $n$ sets such that:
(1) for each $i\in [n]$, $\frac{n}{3}\leq |A_i|\leq n$;
(2) for any $1\leq i<j<k\leq n$, $|A_i\cap A_j\cap A_k|\leq a$, where $a$ is a constant ...
2
votes
0answers
43 views
Coloring finite subsets of a fixed size with a single modular function
Let $k$ and $N$ be positive integers so that $k\mid N$. Let $M=(k/N){N\choose k}$. A function $f:[N]^k\rightarrow M$ is a coloring function if $f(s_1) = f(s_2)$ implies that $s_1=s_2$ or $s_1 \cap ...
9
votes
0answers
278 views
Being even or odd in the product expansion $\prod(1+x^k+x^{k+1})$
Consider the generating function of "partitions with distinct parts"
$$\sum_nQ(n)x^n=\prod_k(1+x^k).$$
It's known that
$$\left[\prod_k(1+x^k)\right] \mod 2=\prod_m(1-x^m)=\sum_{j\in\mathbb{Z}...
1
vote
1answer
212 views
What is the inverse Laplace transform of $\frac{(1/s)_{n}}{s} $?
Introduction
So far, I have found (p. 5) the following generating functions of the unsigned Stirling numbers of the first kind:
\begin{equation} \tag{1} \label{1} \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)...
2
votes
0answers
93 views
Number of sets of distinct pairs which doesn't share difference
Inspired by This question by Vidyarthi I tried to find the value of $T(2m)$ where, $T(2m)$ is the number of sets of distinct pairings (so, the sets have $m$ elements) of the numbers $1,2,3....,2m$ ...
2
votes
0answers
85 views
Partitioning a set of consecutive nonnegative integers into distinct pairs
Let us have a set of $k$ consecutive natural numbers $2,3,\ldots, k+1$, $k$ even. In addition, we are given a set of $m=\frac{k}{2}$ 'differences' from one among the $k$ numbers $1,2,\ldots, k$.
My ...
1
vote
1answer
87 views
Knapsack problem with value range constraint
The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...
1
vote
0answers
135 views
Is this graph theory paper in German translated into English?
I recently read such a paper and want to understand the proof idea of this article. However since it is in German and I have not studied German before, I'd like to ask whether this paper has an ...
4
votes
0answers
109 views
Positivity conjecture for Somos sequences
Let $\{s_n\}$ be the Somos-$4$ sequence, which is defined by $$s_{n+4}s_n=\alpha s_{n+3}s_{n+1}+\beta s_n^2.$$ It is known that $s_n$ is a Laurent polynomial: $s_n\in\mathbb{Z}[s_1^{\pm1}, \ldots, s_4^...
5
votes
1answer
223 views
Positioning ice-cream stands on a street
We want to position $n$ ice-cream stands on a street. Assume that the population on the street is modeled by a nonnegative integrable function $f$, and everyone goes to the nearest ice-cream stand. ...
8
votes
2answers
234 views
Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$
Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$.
Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...
7
votes
0answers
106 views
On the number of Reed–Muller codewords with no consecutive ones
$\DeclareMathOperator\RM{RM}\DeclareMathOperator\Eval{Eval}$Consider the polynomial ring $\mathbb{F}_2[x_1,x_2,\dotsc,x_m]$ and let $f\in \mathbb{F}_2[x_1,x_2,\dotsc,x_m]$. Let us now fix a Gray ...
1
vote
1answer
48 views
Expectation of the sum of the squares of the cardinal of an inverse function
I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as:
$$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$
where $\oplus$ is the bitwise XOR.
...
1
vote
0answers
64 views
Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph
A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
3
votes
1answer
115 views
A ratio of two probabilities
I am concerned about the monotonicity of the following ratio
$
f(\eta)=\frac{\sum_{x=K}^{N}\left(\begin{array}{c}
N\\
x
\end{array}\right)\left(q_{G}\eta\right)^{x}\left(1-q_{G}\eta\right)^{N-x}}{\...
0
votes
0answers
217 views
Equality of the products involving (prime powers - 1)
Let $q_1,q_2,\dots,q_m$ be a collection of prime powers such that $q_i = p_i^{k_i}$. I have the following questions.
When the products $\prod_{i=1}^m(q_i-1)^{r_i}$ and $\prod_{j=1}^m(q_j-1)^{s_j}$ (...
1
vote
1answer
123 views
Expectation of maximum of all period lengths of functions $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$
This is based on an older question.
For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ and ''starting value'' $...
1
vote
0answers
79 views
When are the 3-colorings of vertex subsets uncorrelated?
Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.
For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct ...
-1
votes
1answer
209 views
Given the index of two permutations, Is there a direct way to compute the index of their composition? [closed]
Suppose you are given two indexed permutations, (7 followed by 4, for instance)
What is the best way to go about finding their composition, given the indices themselves? I'd imagine that the answer ...
9
votes
3answers
416 views
Pairs of vertices with high degree difference
Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us also fix an integer $k> n/2$. What are we able to say about the following quantity:
$$\mathcal{I}_k(G) :=...
2
votes
1answer
253 views
Alternating sum of hook lengths: Part II
This is a follow up on my earlier MO post.
Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$. Let
$$f_n=\sum_{\...
0
votes
0answers
52 views
Multiplication on a group of given cardinal and random permutations
Let $n$ be an integer, that we assume to be large (the order of magnitude for the motivation about the question is about 2^100).
For the purpose of random automatic program certification, I need to be ...
7
votes
1answer
179 views
Constructing permutations avoiding a pattern
See here for some theory.
It is fairly easy to explicitly generate all permutations of $n$ elements that have a pattern (just begin with the pattern and add the rest in all possible positions), but ...
