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.

Filter by
Sorted by
Tagged with
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^...
user avatar
  • 1,756
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 ...
user avatar
  • 18.9k
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 ...
user avatar
  • 3,079
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 ...
user avatar
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}\...
user avatar
  • 430
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 ...
user avatar
  • 131
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=...
user avatar
  • 13.3k
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 ...
user avatar
  • 41.5k
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 ...
user avatar
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/...
user avatar
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\...
user avatar
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$...
user avatar
  • 503
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 ...
user avatar
  • 503
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 ...
user avatar
  • 13.3k
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 ...
user avatar
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_{...
user avatar
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 $\...
user avatar
  • 516
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 ...
user avatar
  • 67
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-...
user avatar
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 ...
user avatar
  • 11
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 ...
user avatar
  • 1,723
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) ...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 11
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}$. ...
user avatar
  • 1
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 ...
user avatar
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 ...
user avatar
  • 348
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)\...
user avatar
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 ...
user avatar
  • 21.4k
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 ...
user avatar
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? ...
user avatar
  • 23
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 ...
user avatar
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,...
user avatar
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 ...
user avatar
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\...
user avatar
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 $\{...
user avatar
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)...
user avatar
  • 1,064
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 ...
user avatar
  • 5,019
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)^{...
user avatar
  • 1,400
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., ...
user avatar
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 $\...
user avatar
  • 13k
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,...
user avatar
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 ...
user avatar
  • 343
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 ...
user avatar
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 ...
user avatar
  • 15.3k
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 ...
user avatar
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 - ...
user avatar
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$$ ...
user avatar
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 ...
user avatar
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 \...
user avatar