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

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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
3answers
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
2answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
4answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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 $\...