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.
9,275
questions
3
votes
0
answers
203
views
Inequalities for Motzkin polynomials
Let us denote by $M_{n}(t)$ the $n$-th Motzkin polynomial. It is defined by $M_1(t) = M_2(t) = 1$ and
$$ M_{n}(t) = \sum_{i=0}^{\lfloor n/2\rfloor } \frac{1}{n-1-i} \binom{n-1-i}{i} \binom{n-1}{i+1} t^...
6
votes
0
answers
112
views
Exact classifications of numerical sequences in combinatorics
Recently there has been tremendous progress in showing that certain sequences of numbers $(a_0,a_1,\ldots,a_n)$ attached to a combinatorial object (such as the coefficients of the characteristic ...
5
votes
1
answer
320
views
Is this function rational?
Let
$$
F=\sum_{i\ge0}\frac1{(T+2)^i}\left(\frac T{T+1}\right)^{3^i}\in\mathbb F_3\left(\!\!\left(\frac1T\right)\!\!\right).$$
Does $F$ belong to $\mathbb F_3(T)$?
Here, truncations of the series do ...
9
votes
1
answer
696
views
How hard is it to compute the Davenport constant?
The Davenport constant $D(G)$ of a finite abelian group $(G,+)$ is the least positive integer $k$ such that every sequence in $G$ of length $k$ has a zero-sum (nonempty) subsequence.
It seems that the ...
4
votes
1
answer
176
views
Can one find an elementary function $f(t)$ such that ${}_2F_1\bigl(\frac{1}{2},\frac{1}{2};2;t\bigr)=f(t)$?
For $\alpha,\beta\in\mathbb{C}$ and $\gamma\in\mathbb{C}\setminus\{0,-1,-2,\dotsc\}$, Gauss' hypergeometric function ${}_2F_1(\alpha,\beta;\gamma;z)$ can be defined by the series
\begin{equation}\...
1
vote
0
answers
68
views
Intersection of lattice polytopes
Is there a way to characterise when the intersection of two or more lattice polytopes is again a lattice polytope? For instance, can you read that property from their Ehrhart polynomials? If it makes ...
2
votes
0
answers
95
views
Almost subgroups of $\mathbb S^1$
Suppose $X\subset \mathbb S^1$ is a finite subset of the group $\mathbb S^1$ such that $|X+X|<(1+c )|X|$ for a sufficiently small $c\in(0,1)$. I believe that in such case there exists a subgroup $G=...
1
vote
0
answers
111
views
Volume of a polytope as its degenerates to be lower dimensional
Consider a polytope $P$ defined by the usual inequalities $A\mathbf{x}\leq \mathbf{b}$; let me assume that $P$ is not contained in a proper subspace. A result which I believe to true, but am not ...
1
vote
0
answers
174
views
Closed form for partial sums of A103318
Let $a(n)$ be A103318, number of solutions $i$ in range $[0,n-1]$ to $i \equiv 0 \pmod {2^{n-i}}$: the sequence begins with
$$1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 1, 2, 2, 2, 1, 2, 2, 3, 2$$
Also let's ...
5
votes
1
answer
167
views
On a proof involving Young symmetrizers acting on tensor spaces
I hope this is not too elementary for this site, but I already asked something similar on MSE which has not received any attention whatsoever. I am extremely unfamiliar with the algebraic/...
0
votes
1
answer
84
views
$a(16n+k)=b(16n+k)-c(16n)$ for $n\geqslant0$, $0 < k < 16$ where $c(n)=b(n)-a(n)$
Let $a(n)$ be A339970 = A329697$($A019565$(2n))$: the sequence begins with
$$0, 1, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 5, 6, 2, 3, 3, 4, 4$$
Also let's consider
$$\ell(n)=\left\lfloor\log_{2}(n)\right\...
4
votes
1
answer
122
views
How to find an optimal sequence of merging operations?
Given a set of items, each characterized by a quality $q_i\in(0,1)$. We can merge two items of quality $q_i$ and $q_j$ to a single item $k$ of quality $q_k=f(q_i,q_j)$, where $f$ is increasing in $q_i$...
1
vote
0
answers
115
views
Steiner tree subject to non-trivial constraint
Given a edge-weighted transportation network modeled as a graph. A source node $s$ needs to send an object to a set of $k$ destination nodes $t_i$, $1\le i\le k$. For the transportation, $s$ needs to ...
3
votes
1
answer
124
views
Number of "half symmetries" of a finite subset of $\mathbb S^1$
Suppose $X\subset \mathbb S^1$ is a finite subset of the group $\mathbb S^1=\mathbb R/\mathbb Z$. We say that $t\in \mathbb S^1$ is a half symmetry of $X$ if $|(X+t)\cap X|>|X|/2$.
Question. Can ...
6
votes
0
answers
129
views
Polynomial count varieties and affine paving (e.g., determinantal varieties)
Let $X$ be a variety defined over $\mathbb{Z}$, $X_{\mathbb{F}}$ be the base change $X\times_{\mathrm{Spec}(\mathbb{Z})} \mathrm{Spec}(\mathbb{F})$. We say $X$ is of polynomial count if there is a ...
6
votes
0
answers
339
views
Is this just a numerical accident or what?
In a complementary proof for a matrix determinant of $a_{i,j}=\binom{n-1+i}j$, raised by BillyJoe, I showed the more general evaluation
$$\det\left(\binom{i+p}{j+k-1}\right)_{1\leq i,j\leq m}
=\prod_{...
1
vote
0
answers
117
views
$\mathfrak{sl}_2$-action on Young diagrams
Let $\mathcal{Y}$ be a vector $\mathbb{Q}$-space of all Young diagrams. Denote by $\delta_\lambda$ the Young diagram of the partition $\lambda$ and $c(\square)$ be
the content of the square $\...
5
votes
3
answers
793
views
Series involving power of the index
How to prove the following identity
$$ \sum_{n=1}^{\infty} \frac{n^{n-1} e^{-n}}{n!} = 1$$
analytically (which can be confirmed with $Mathematica$)? The standard trick for geometrical series does not ...
4
votes
0
answers
138
views
An identity for Schur polynomials
Given a partition $\lambda$, the Schur polynomials can be defined, among many other ways, as
$$S_{\lambda}(\xi_1,\dots,\xi_a)=\frac{\det\left(\xi_i^{\lambda_j+a-j}\right)_{i,j=1}^a}{\det\left(\xi_i^{a-...
1
vote
2
answers
84
views
Name for the weight function defined as the integer sum of coordinate entries from ${\mathbf F}_p$
In ${\mathbb F}_p^n$, $p$ prime one may define a weight function on vectors in various ways such as Hamming, or Lee weight. (These two weights correspond nicely to the respective distances from $\bar ...
1
vote
1
answer
148
views
Words representations of elements of a symmetric group
Let $S=\{(1,2),(1,2,\ldots,n),(1,n,,n-1,\ldots,2)\}$ be a subset of the symmetric group $S_n$. Let $a=(1,2),b=(1,2,\ldots,n),c=(1,n,n-1\ldots,2)$ be the elements of $S$. My question is, since $S$ is a ...
3
votes
0
answers
95
views
The Grassmann twist-map, an associated semi-group action, and RSK
Let me begin by setting some notation: Let $\mathrm{Mat}_{k,n}(\Bbb{R})$ denote the vector space of all $k \times n$
real-valued matrices. Given $g \in \mathrm{Mat}_{k,n}(\Bbb{R})$ and two (ordered) ...
4
votes
1
answer
155
views
Reference for a definition of Catalan numbers
The $l$-th Catalan number ${2l\choose l}\frac{1}{l+1}$ is equal
to the number of sequences $s_0,\ldots,s_{l+1}$ of length $l+2$ with the following
properties:
(1) $s_0=s_{l+1}=1$ and $s_1,\ldots,s_l$ ...
0
votes
1
answer
67
views
How many unique orders of length n are there where the index number is different from the number itself? [closed]
Suppose you pick a random order of consecutive numbers from 1 to $n$.
The order for a series of $n$ numbers would then be:
$$
x_1, x_2, ... x_{n-1} , x_n
$$
The amount of unique combinations is of ...
0
votes
0
answers
97
views
An exercise about sum-product estimate
I am struggling with 1.11 exercise from the George Shakan "Discrete Fourier Transform".
Let $A \subset \mathbb{Z}/q\mathbb{Z}$ be any set not containing zero with $|A|>\sqrt2q^{5/8}$. ...
16
votes
2
answers
640
views
Has the following problem, resembling the lonely runner conjecture, been studied?
Given $n$, what is the smallest value $\delta_n$ satisfying the following:
For any group of $n$ runners with constant but distinct speeds,
starting from the same point and running clockwise along the ...
7
votes
2
answers
282
views
Determinant of matrix with Stirling numbers as elements
After noticing that the determinant of an $n \times n$ matrix $A_n$ with elements $a_{i,j}=i^j$, $1 \le i \le n$, $1 \le j \le n$, is the superfactorial (product of the first $n$ factorials), I wanted ...
2
votes
0
answers
55
views
Odious twin locations related to the sequence based on $d(n) = n-d(d(n-1))-d(d(n-2))$
Let $\operatorname{wt}(n)$ be A000120, i.e. the number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).
Let $a(n)$ be the sequence of numbers $k$ such that $\operatorname{wt}(k)\...
9
votes
2
answers
202
views
Alon-Füredi for homogeneous polynomials
A theorem of Alon and Füredi says that if $A$ and $B$ are finite, nonempty subsets of the field $\mathbb F$, and if a polynomial $P(x,y)\in\mathbb F[x,y]$ vanishes on all, but exactly one point of the ...
15
votes
2
answers
588
views
Indecomposable contracting maps on the integers
$\def\ZZ{\mathbb{Z}}$Call a function $f : \ZZ \to \ZZ$ "contracting" if
$$|f(j) - f(i)| \leq |j-i|$$
for all $i$, $j \in \ZZ$. The contracting functions form a monoid under composition; call ...
2
votes
1
answer
121
views
Can connectivity be less than min cut/degree?
Suppose we have a graph with min-cut $\lambda$ and minimum degree $> \lambda$.
Is it possible for there to be a vertex that is at most $\lambda$-connected to every other vertex in the graph?
...
3
votes
3
answers
99
views
An efficient generalized algorithm to obtain an arbitrary element of a lexicographically ordered tuple of all balanced $l$-bit binary sequences
Assuming that $l>1$ is even, an $l$-bit binary sequence $b$ is balanced if and only if the number of zeroes in $b$ is equal to $l/2$.
Let $T_l$ denote a lexicographically ordered tuple of all ...
4
votes
0
answers
136
views
Binary iterations, Fibonacci numbers and permutation of natural numbers
Let $\operatorname{wt}(n)$ be A000120, i.e. the number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).
Also let's consider
$$\ell(n)=\left\lfloor\log_{2} n\right\rfloor$$
and
$$T(n,...
2
votes
1
answer
53
views
fills a given polygon with a few types of given primitives
Given one large 2D polygon, and K types of small polygons (the primitives). For each type of small polygon, it can be rotated, and has an infinite number of pieces. For such a Jigsaw puzzle
game, is ...
0
votes
0
answers
61
views
Cutsets and disjoint edge sets in graphs
If $H=(V,E)$ is a hypergraph then we say that $C\subseteq V$ is a cutset if $C\cap e \neq \emptyset$ for all $e\in E$. We set
$$\text{cut}(H) = \min\{|C|: C \text{ is a cutset of }H\}.$$ A subset $D\...
1
vote
1
answer
150
views
"Lamp-switch set-up number" of $n$ [closed]
Motivation. The following has a real-life (!) inspiration from a discussion about how to connect lamps and switches in an efficient way.
Question. Let $n\in\mathbb{N}$ be a positive integer and let $\{...
4
votes
1
answer
121
views
Strongly minimal covers for clique hypergraphs of graphs
$\DeclareMathOperator\Cliq{Cliq}$A hypergraph $H$ is a pair consisting of a set $V$ of vertices and a family of subsets of $V$ called edges.
One class of examples is obtained by taking a graph $G=(V,E)...
2
votes
0
answers
88
views
A closure property of a set partition
Let $A$ be a finite set, $k\in\mathbb N$, $\tilde A\subset A^k$ and $\phi: \tilde A\to A$ be a map.
Consider the following property a set partition $P$ of $A$ might have:
$$
\forall B_1,\dotsc,B_k\in ...
7
votes
1
answer
232
views
A curious $q$-series identity on a truncated Euler function
Recall that a $q$-Pochhammer symbol is defined as
$$
(x)_n = (x;q)_n := \prod_{l=0}^{n-1}(1-q^l x).
$$
I found the following curious $q$-series identity that seems to hold for any $n\geq 0$:
$$
(-1)^{...
4
votes
1
answer
118
views
Find all 2-planar drawings of $K_6$ and $K_7$
A $k$-planar graph is a graph which can be embedded with at most $k$ crossings per
edge.
It is proved that a complete graph $K_n$ is 2-planar if and only if $n\le 7$.
Angelini P., Bekos M. A., ...
1
vote
0
answers
99
views
On probability of coprimality of a list of numbers
We know $r$ randomly chosen integers are coprime with probability $\frac1{\zeta(r)}$.
Pick a bound $N$ and pick $k\lceil N^{\alpha}\rceil$ uniformly random integers in $[0,N^{\alpha+\beta}]$ where $\...
4
votes
1
answer
228
views
Explicit expression for recursive sums - II
A twist on just unfolded recursive summation formula. Let polynomials in nonnegative integer variables $t_1,t_2,\dots$ be defined by the recurrence:
\begin{split}
g_0 &= 1, \\
g_k(t_1,t_2,\dots,...
2
votes
1
answer
69
views
Counting Euler circuits through labelled trees where $v_1$ and $v_2$ have distance two
Let $T_n$ be the set of all labelled trees with $n$ vertices. For any $T \in T_n$ let $D(T)$ be the 'doubled tree', where each edge of $T$ is replaced by one directed edge in each direction. $D(T)$ is ...
0
votes
0
answers
77
views
Has the mixture of forward and backward finite difference existed?
Given a function $ f(x) $, there are forward and backward finite differencs, whose definitions are given in the following. By forward one, we mean $ \Delta f(x) = f(x+d)- f(x) $, $(d>0)$; and by ...
9
votes
0
answers
215
views
Hives for other root systems? [duplicate]
Littlewood-Richardson coefficients $c^\lambda_{\mu\nu}$ have numerous combinatorial interpretations, including the hive model by Knutson and Tao, see here. For other root systems, there are also ...
4
votes
0
answers
91
views
Almost acyclicity of the complex of configuration spaces of noncollinear points in projective plane over finite fields
Let $F$ be a finite field with many elements, say more than 7 for example, and $X$ be the corresponding projective plane $\mathbb{P}^2(F)$.
For a set of points in $X$, if any three of them are ...
2
votes
1
answer
277
views
Prove positivity of rational functions
We say a rational function $F(z)$ is positive if the coefficients of its Maclaurin expansion, in the variable $z$, are non-negative.
In this context, let
$$F_r(z):=\frac{1 - 2z + z^r - (1 - z)^r}{(1 - ...
10
votes
2
answers
432
views
Explicit expression for recursive sums
Let $t_1,t_2,\dots,t_k$ be non-negative integers. Can the following sum
$$f_k(t_1,t_2,\dots,t_k):=\sum_{j_1=0}^{t_1} \sum_{j_2=0}^{t_2+j_1} \sum_{j_3=0}^{t_2+j_2} \dots \sum_{j_k=0}^{t_k+j_{k-1}} 1$$
...
7
votes
2
answers
205
views
On permanent of a square of a doubly stochastic matrix
Let $A = (a_{i,j})$ be a double stochastic matrix with positive entries. That is, all entries are positive real numbers, and each row and column sums to one. A permanent of a matrix $A = (a_{i,j})$ is ...
0
votes
0
answers
75
views
Efficiency of covers
Let $X\neq \emptyset$ be a set. We say $C \subseteq {\cal P}(X)$ is a cover of $X$ if $\bigcup C = X$. For covers $C, D$ of $X$ we say that $C$ is more efficient than $D$ if $|C\setminus D| < |D \...