# 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,206
questions

0
votes

0
answers

15
views

### How many possible combinations [closed]

How many possible combinations ?
Hi,
I have provided a picture to explain.
Each Lettered card can be true or false.
So an Example if A,C,F are enabled there will be less combinations than if A,B,C,E ...

-2
votes

0
answers

37
views

### Sum-product estimate: Let A ⊂ Z/qZ be any set not containing zero with |A| > √ 2q 5/8 . Show that (A + A) · (A + A) + A · A + A · A = Z/qZ [closed]

https://gshakan.files.wordpress.com/2016/04/discretefouriertransform1.pdf
Is there any idea to prove exercise 1.11? I tried to use above techniques but it seems quite hard.

3
votes

1
answer

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

5
votes

0
answers

86
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

49
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)\...

6
votes

0
answers

77
views

### Alon-Füredi for special 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

535
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

110
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

92
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

127
views

### Why are these Littlewood-Richardson coefficients congruent to 1 mod 8?

Let $n\in{\mathbb N}$ and write $n=q_1+q_2+\dots+q_t$, where $q_1>q_2>\dots>q_t$ are powers of $2$. Let $\lambda_n$ be the partition with Frobenius symbol $(q_1-1,q_2-1,\dots,q_t-1;q_t,q_{t-1}...

3
votes

0
answers

128
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

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

-1
votes

0
answers

34
views

### How many combinations of strings of length m consisting of n digit types are there? [closed]

I'm looking to find a formula for the number of combinations there are given a string of a fixed length and a certain number of available digits.
Example: A string of length 6 containing 3 Xs and 3 Os ...

0
votes

0
answers

52
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

147
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

117
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

208
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

112
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

95
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

220
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

64
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

72
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

204
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

85
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

263
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

412
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

192
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

74
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 \...

4
votes

2
answers

94
views

### $O(n^{2-\epsilon})$ bound on choosing $n$ points on the hypersphere to maximize $\pm 1$ weighted sum of their $\binom{n}{2}$ inner products

Given $n,d\in\mathbb{N}, n\gg d$, I'm looking for a bound on the maximum (or minimum) expected value of the following game:
Draw a vector $\epsilon\in\{\pm 1\}^{\binom{n}{2}}$, uniformly at random. ...

0
votes

0
answers

64
views

### Optimal covering trails in 3 and 4 dimensions

A couple of years ago, I constructively solved (inside the $AABB$ $[0,3]$ X $[0,3]$ X ... X $[0,3]$) the $k$-dimensional generalization of the infamous Nine-Dot Problem by S. Loyd (see Cyclopedia of ...

0
votes

0
answers

72
views

### Inverse limit in category of graphs

Let $... \leftarrow G_i \leftarrow G_{i+1} \leftarrow ...$ be an inverse system of graphs (which might not be locally finite), morphisms are symplicial maps (we allow collapsing of edges to vertices)....

2
votes

0
answers

77
views

### A minimal size of a set of tuples for an upper bound of a distance between any pair of elements

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....

5
votes

1
answer

526
views

### Much weaker condition for Kakeya sets over finite fields

What is the minimum size of a subset $S \subseteq \mathbb{F}_p^n$ such that for all directions $a \in \mathbb{F}_p^n$, there is a line in direction $a$ that intersects $S$ in at least $C$ points?
If $...

6
votes

0
answers

113
views

### Number of tautologies of a given size?

Fix some complete set of $L$ logical connectives such as $\{ \wedge, \neg \}, \{\Rightarrow, \neg \}, \{\ \vee, \wedge, \neg \}, \{ \uparrow\}, \{\wedge, \vee, \neg, \Rightarrow \}$ - I'll assume all ...

1
vote

0
answers

84
views

### Are there standard short notations for ascending and descending cyclic permutations?

In a paper I am currently writing I use cyclic permutations of the form
$$
(k,k+1,\dots,\ell)
$$
and
$$
(\ell,\ell-1,\dots,k)
$$
of consecutive elements quite a lot (I added the commas to avoid ...

15
votes

1
answer

370
views

### Make $n$ numbers equal using pairwise averages

Given $n$ rational numbers. Every time you can delete $2$ numbers, and add 2 numbers which are equal to $\frac{a+b}{2}$ (assume the number you delete is $a$ and $b$). How to judge whether it is ...

22
votes

1
answer

3k
views

### Can an odd number of marbles jump to infinity?

Loosely inspired by the game Abalone, I've encountered the following simple problem I cannot solve.
Suppose that we are given a finite set of marbles on an infinite chessboard.
One move consists of ...

2
votes

0
answers

77
views

### Reference request on Plancherel measure for partitions whose parts differing by more than $1$

Given an (unrestricted) integer partition $\lambda$ of $n$, let $f_{\lambda}$ denote the number of standard Young tableaux (SYT) of shape the Young diagram $Y(\lambda)$ of $\lambda$. Then,
$$\sum_{\...

4
votes

1
answer

177
views

### A combinatorial question about certain sequences

Consider the sequence defined by the following algorithm:
Make a stack of tickets numbered from 1 to $n,n>1 \in N$ and arranged in reverse order with the ticket numbered 1 at the bottom and that ...

0
votes

0
answers

61
views

### Expectation of edge weights on the complete graph, Part 2

This question concerns the same basic set-up as my previous question: Expectation of edge weights on the complete graph
In that question an answer was given which shows that the expected value is as ...

3
votes

1
answer

143
views

### Total number of plane partitions for $4$ or more dimensions

According to MacMahon formula the total number $P_3(r, s, t)$ of plane partitions that fit in the $r \times s \times t$ box $\mathcal{B}(r,s,t)$ is equal to the following product formula:
$$
P_3(r,s,t)...

1
vote

1
answer

132
views

### Expectation of edge weights on the complete graph

Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random ...

7
votes

1
answer

221
views

### Harmonic flow on the Young lattice

Let me begin with some preliminary concepts: A positive real-valued function $\varphi: P \rightarrow \Bbb{R}_{>0}$ on a locally finite, ranked poset $(P, \trianglelefteq)$ is harmonic if
$\varphi(\...

3
votes

1
answer

137
views

### Existence of wild regular abstract polytopes

Is it possible for an edge to connect two non-adjacent vertices of a polygonal face in a regular abstract polytope? Here “adjacent” means that the two vertices are connected by an edge that is a facet ...

0
votes

0
answers

53
views

### Determining the total number of nonzero expansion terms in a (0,1)-matrix

Let $A=(a_{ij})_{n\times n}$ be a $(0,1)$-matrix such that it contains equal number of $1$s in each row and column. Is there any general method to count the total number of the nonzero terms $\prod_{i=...

1
vote

0
answers

87
views

### $r(M)$-subsets of a 3-connected matroid $M$

It is proved in Lowrance, Oxley, Semple, and Welsh - On properties of almost all matroids that almost all matroids are 3-connected asymptotically. Also, it is conjectured that almost all matroids are ...

4
votes

1
answer

232
views

### Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?

Update: In light of Fedor Petrov's answer, I added an additional requirement that all strings in $A$ and $B$ have Hamming weight exactly $n/2$, which hopefully makes the question more interesting.
...

2
votes

0
answers

47
views

### Does periodic pattern arise in syndetic pattern

We wonder for two "large" sets $I,J\subseteq \omega$, if $(J-J)\cap I=\emptyset$, then it must be due to certain periodic pattern.
We say $I\subseteq \omega$ is $t$-syndetic iff for every $n\...

0
votes

0
answers

56
views

### Shattering of a set of binary classifiers

Let $S$ be a set, and let $\mathcal{F}_{S}=\{f:S\to\{-1,+1\}\}$ be a set of different label assignments. Show that $\mathcal{F}_{S}$ shatters at least $|\mathcal{F}_{S}|$ subsets of $S$.
Here is what ...