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

**1**

vote

**0**answers

47 views

### Existence of a “generic enough” lattice point interior to a lattice triangle

Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a ...

**-4**

votes

**0**answers

92 views

### On $\det\big[x+\big(\frac{i^2-\frac{p-1}2!\,j}p\big)\big]_{1\le i,j\le(p-1)/2}$ for primes $p\equiv 3\pmod 4$

Motivated by Question 302323 and Question 317509, I have formulated the followng conjecture on the basis of my computation.
Conjecture. For any prime $p\equiv3\pmod4$, there is a positive integer $...

**1**

vote

**0**answers

59 views

### A computing shortcut to $Dedekind Number(n)$?

OEIS A132581 gives a functional extension of Dedekind numbers.
$F(n)$ is the number of antichains in the first $n$ elements
of "the infinite boolean lattice".
And $\operatorname{DedekindNumber}(e) =...

**1**

vote

**0**answers

51 views

### Calculating coefficients in a general product

Is there a formula for the coefficient of $\prod_{i=1}^{n}a_{i}^{n_i}\prod_{j=1}^{m}b_{i}^{m_i}$ in the product
$$\prod_{i=1}^{n}\prod_{j=1}^{m}\left(a_{i}+b_{j}\right).$$
Is there a simple way to ...

**0**

votes

**0**answers

58 views

### On $\det[x+(\frac{i\pm j}p)]_{1\le i,j\le(p-1)/2}$ for primes $p\equiv 3\pmod 4$

I have made the followng conjecture on the basis of my computation.
Conjecture. For any prime $p\equiv3\pmod4$ with $p>3$, we have
$$\det\left[x+\left(\frac{i+j}p\right)\right]_{1\le i,j\le(p-1)/2}...

**1**

vote

**1**answer

97 views

### Equality $F(n,3)=F(2n,2)$ for Dedekind numbers on $x-valued$ logic lattices?

F(n) = Number of antichains in the first n elements of the infinite boolean lattice. (OEIS A132581).
$\text{DedekindNumber}(e)=F(2^e)$.
Rename F(n) to F(n,2). Boolean =2.
First Question.
Equality ...

**5**

votes

**2**answers

182 views

### Formula for a sum of product of binomials

We know that equation $$s_1+s_2+s_3=n-1 \quad \mbox{$s_1,s_2,s_3$}\geq 1$$
has $\binom{n-2}{2}$ solution.
I want to find any good formulae for the following form :
$$\sum_{(s_1,s_2,s_3)}\prod_{i=1}^...

**0**

votes

**0**answers

41 views

### number of $k$ element subset of $[n]$ with non-empty intersection

Let $[n] = \{1,2,\dots,n\}$ and for $1 \le k \le n$, how to find the cardinality of the maximal collection of, $k$ element subsets of $[n]$ that are pairwise intersecting.
Any hint or reference will ...

**1**

vote

**1**answer

155 views

### Largest cardinality $n$ of a subset $A$ of $\{1,2,\ldots,M\}$ such that $(A+A) \cap A$ is empty

Assume that the set $A$ does not have simple structures (such as the case that when all elements are odd numbers in $[1,M/2]$ then all sums are even thus there are no solutions, as pointed out by @...

**0**

votes

**0**answers

54 views

### Clustering on tree

I am looking for a method that would identify clusters in a tree-like structure. In the figure below you can see a very simple example where one can visually identify distinct branches with a lot of ...

**10**

votes

**3**answers

192 views

### Mean maximum distance for N random points on a unit square

Following up on Mean minimum distance for N random points on a one-dimensional line and Mean minimum distance for N random points on a unit square (plane), I have the following questions.
Given N ...

**-2**

votes

**2**answers

82 views

### Is every graph an incompatibility graph?

Let $G=(V,E)$ be a simple, undirected graph. Is there a partial ordering $\leq\subseteq (V\times V)$ with the following property? $$\{v,w\} \in E \text{ if and only if } v||y$$
(We write $v||w$ in ...

**1**

vote

**0**answers

30 views

### Spherical code for interesection of $k$-sparse vectors and unit sphere

Let us assume $X\in\mathbb{R}^{n\times d}, rank(X)=d$, integer $k\in\mathbb{N},k\ll d$, positive constant $0<\epsilon<1$, and $\mathcal{S}\subset \mathbb{R}^d$ denotes the unit sphere. We also ...

**0**

votes

**0**answers

30 views

### k-ary necklaces with conserved/fixed indexes

I asked a question in a previous post about enumerating all possible k-ary bracelets with certain positions fixed to a specific bead/character. I asked a few mathematicians, and it seems its quite ...

**1**

vote

**0**answers

125 views

### Two versions of the Möbius inversion formula

Consider the following versions of Möbius inversion:
Let $(A,+)$ be an abelian group, and let $f$ and $g$ be functions $\mathbb N\rightarrow A$. Then $$\left((\forall n )\;g(n)=\sum_{d|n}f(d)\right)\;...

**10**

votes

**1**answer

138 views

### Connected incomparability graph

Let $X$ be a finite set equipped with a partial order. (Not a preorder: $a < b$ implies $b \not< a$.) The corresponding incomparability graph has vertex set $X$ with an edge between two points ...

**0**

votes

**1**answer

80 views

### 3 dice combination [on hold]

It there any formula for the calculating dice combinations. For example for hex-dice, when I roll one dice it is possible $6$ results. If I do the same with $2$ disces there are $21$ results instead ...

**0**

votes

**1**answer

67 views

### Finding $P$ points among $N$ to approximate a probability density function?

Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ ...

**2**

votes

**0**answers

85 views

### Inequalities about tripling and doubling sumsets

Let $A$ be a set of vectors in $\mathbb Z^d$ who $\mathbb R$-span is the whole $\mathbb R^d$. Let $s_i(A)$ denote the size of $A+A+\dots A$ ($i$ times). I am interested in the following:
Question 1:...

**13**

votes

**1**answer

436 views

### Holes in double-tileable polynominoes

This question was communicated to me by Evgeniy Romanov.
Consider a connected polyomino $P$ that can be completely tiled in two different ways: with disjoint $2 \times 2$ square tetraminoes, and with ...

**17**

votes

**2**answers

2k views

### A Putnam problem with a twist

This question is motivated by one of the problem set from this year's Putnam Examination. That is,
Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some ...

**6**

votes

**2**answers

230 views

### Domination problem with sets

For nearly two years, I have been struggling with the next task I have already published on MSE, but unfortunately with no respond.
Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
...

**2**

votes

**0**answers

24 views

### Generating complete sets of representatives for the strong contentedness equivalency on the tensor product of strongly connected digraphs

Given any $n\geq 2$ strongly connected digraphs $\small D_1,D_2,\ldots D_n$, if we let $\small T=D_1\otimes D_2\otimes\cdots\otimes D_n$ be their tensor product then by definition we can write $T=(X,R)...

**9**

votes

**0**answers

144 views

### Fundamental circuit characterization of matroid independence complexes

I have the following characterization of independence complexes of matroids, which I think is standard but I can't find a reference. Here it goes:
A pure simplicial complex $\Delta$ is the ...

**1**

vote

**1**answer

62 views

### How many graphs of order n, maximum degree k, and maximum diameter d exist?

The total number of simple undirected graphs of order $n$ is
$\sum\limits_{i = 0}^{\frac{n(n-1)}{2}}{\binom{\frac{n(n-1)}{2}}{i}} = 2^{\frac{n(n-1)}{2}}$.
What is the number of simple undirected ...

**1**

vote

**1**answer

75 views

### Basis of cone lattice

I only want to know whether a construction that I use appears in literature and maybe has a name already.
Let $V$ be a $\mathbb Q$ vector space of dimension $d\in\mathbb N$.
A subset $C\subset V$ is ...

**3**

votes

**1**answer

136 views

### Minimum planar bipartite graph to cover all perfect matching count

Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...

**4**

votes

**0**answers

134 views

### Counting “motifs” with the same “energy”

This question is motivated by physics --- trying to understanding the so-called 'accidental' (i.e. non representation-theoretic) degeneracies that occur in the spectrum of the Haldane--Shastry spin ...

**7**

votes

**1**answer

258 views

### Products of Catalan numbers

Let $c(n)=\frac{1}{n+1}\binom{2n}{n}$ be the Catalan number. It seems that a product $\prod_{n\in I} c(n)$, where $I\subset\mathbb N_{>1}$, is never a Catalan number. Is this a (known) fact?

**3**

votes

**0**answers

210 views

### A new combinatorial problem for finite groups

In a recent preprint arXiv:1811.10503, I proved that if $a_1,\ldots,a_n$ are distinct elements of a torsion-free additive abelian group $G$, then there is a permutation $\pi\in S_n$ such that all ...

**0**

votes

**1**answer

95 views

### A problem related to the comparison of two integer-valued random variables

Consider an urn containing red, blue and green balls (the situation is the same illustrated in this post).
Let $X$ be the non-negative, integer-valued random variable defined as the number of trials (...

**3**

votes

**0**answers

164 views

### Is there a theory behind these puzzles? (communicating by modifying data)

Consider the following puzzles:
Problem 1: Alice is given two data by Zora: a binary string $w$ of length $2^r$, and a position $p$ in the string (which we can view as an integer $0\leq p<2^r$). ...

**0**

votes

**1**answer

353 views

### “Mathematics is the science of the infinite” [closed]

The title is the first sentence of Hermann Weyl's 1930 essay,
"Levels of Infinity."
He focuses on
"the distinction between actuality and potentiality, between
Being and Possibility."
He opines
...

**6**

votes

**0**answers

167 views

### A challenging problem on disjoint cosets

Motivated by my negative solutions (see this paper published in Chinese Ann. Math. 13A(1992)) to two open problems on disjoint residue calsses posed by A. P. Huhn and L. Megyesi [Discrete Math. 41(...

**0**

votes

**2**answers

185 views

### Permutations of squares and finite fields

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$, and let
$$S(n)=\bigg\{\sum_{k=1}^nk^2\pi(k)^2:\ \pi\in S_n\}.$$
Motivated by Question 316142 of mine, here I ask the following ...

**1**

vote

**4**answers

206 views

### Apply doubly stochastic matrix M to a probability vector, then entropy increases?

Consider a vector $p =(p_1,...p_n)$, $p_i>0$, $\sum p_i = 1$
and a matrix $M_{ij}$, which is doubly stochastic: $\sum_i M_{ij} = 1, \sum_j M_{ij} = 1, M_{ij} > 0$.
Question 1 Just apply ...

**4**

votes

**1**answer

92 views

### What is the lower bound for the number of facets that a general convex $d$-polytope with $n$ vertices can have?

I am familiar with Barnette's Lower Bound Theorem on the number of facets a $d$-dimensional simplicial convex polytope with $n$ vertices can have. Is there a similar result for a general (i.e. not ...

**1**

vote

**1**answer

104 views

### Matrices with distinct columns

Let $M$ be an $n \times m$ matrix over $\mathbb{F}_2$ with no repeated columns, and suppose that $m \leq 2^{n-1}$: i.e., it is possible to have a matrix with fewer rows that still has $m$ unique ...

**5**

votes

**1**answer

279 views

### van der Waerden's theorem in Reverse Mathematics

What is known about weak systems of axiomata that allow one to prove van der Waerden's theorem ?
van der Waerden's theorem can be used to show that there are infinitely many primes (see below). Is ...

**6**

votes

**1**answer

185 views

### Covering the finite plane with lines

This is, essentially, a geometrically rendered version of the question I asked a week ago, with the emphases slightly shifted; it seems more natural and appealing (to me, at least) in this form.
Let ...

**7**

votes

**2**answers

288 views

### linear recurrence relation for square of sequence given recursively

If $a_n$ satisfies the linear recurrence relation $a_n = \sum_{i=1}^k c_i a_{n-i}$ for some constants $c_i$, then is there an easy way to find a linear recurrence relation for $b_n = a_n^2$ ?
For ...

**-1**

votes

**1**answer

83 views

### Discrepancy in non-homogeneous arithmetic progressions

I have a doubt, Roth's discrepancy theorem [1] says that there is a subset of arithmetic progressions $A \in [n]$ where any function $f:N\rightarrow \left \{ -1,1 \right \} $ implies
$ \left | \...

**4**

votes

**1**answer

58 views

### Optimal pseudotransversals

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...

**0**

votes

**1**answer

144 views

### Is it true that $\sum_{k=m}^n\frac{\sigma(k)}k\not\in\mathbb Z$ for all derangements $\sigma\in S_n$ and $1\le m\le n$?

Let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
Recall that a permutation $\sigma\in S_n$ is called a derangemnt if $\sigma(k)\not=k$ for all $k=1,\ldots,n$.
Motivated ...

**2**

votes

**0**answers

56 views

### Bivariate power series as rational function

Suppose we have a bivariate power series of the form
$$\sum_{i}\sum_j a_{i,j} t^i s^j,$$
where for every fixed value of $i$ the corresponding univariate power series in $s$ is a rational function. Are ...

**1**

vote

**1**answer

42 views

### Asymptotic upper bound for partial binomial-like sum

I want to upper bound the quantity $$\sum_{i\le \alpha n} \binom{n}{i}\lambda^i$$, where ${\lambda>1}$, $0<\alpha<1$. It is not the same as partial sum of binomial coefficients. An asymptotic ...

**0**

votes

**1**answer

90 views

### Expected values of two non-negative, integer-valued random variables related to an urn problem

Consider an urn containing $c$ distinguishable balls, $\alpha$ of which are red, $\beta$ of which are blue, and $\gamma$ of which are green, and $\alpha+\beta+\gamma=c$. We assume $\alpha,\beta,\gamma&...

**-1**

votes

**0**answers

145 views

### Permutations $\pi\in S_n$ with $\sum_{0<k<n}\pi(k)\pi(k+1)-1$ a power of two

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is my following conjecture true?
Conjecture. (i) For any integer $n>1$, there is a permutation $\pi\in S_n$ ...

**4**

votes

**0**answers

122 views

### Is there a permutation $\pi\in S_n$ with $\sum\limits_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0$ for each $n>7$?

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each $n=8,9,\ldots$ we have
$$\sum_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0\tag{$*$}$$
for ...

**0**

votes

**1**answer

238 views

### Odd & even permutations and unit fractions

One more motivated by recent questions of Zhi-Wei Sun.
Let $S_n$ be the group of permutations of $\{1,2,\ldots, n\}$.
Is it true that, for every $n \ge 8$, there is at least one even permutation $\...