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.
- 1
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 ...
- 326
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)\...
- 1,587
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 ...
- 21.3k
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 ...
- 138k
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?
...
- 23
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 ...
- 695
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}...
- 991
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,...
- 1,587
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 ...
- 21
-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\...
- 39.4k
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 $\{...
- 39.4k
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)...
- 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 ...
- 5,009
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)^{...
- 1,400
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., ...
- 577
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 $\...
- 12.9k
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,...
- 25.3k
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 ...
- 343
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 ...
- 31
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 ...
- 15.2k
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 ...
- 347
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 - ...
- 37.8k
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$$
...
- 25.3k
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 ...
- 339
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 \...
- 39.4k
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. ...
- 41
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 ...
- 1
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)....
- 1
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)....
- 695
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 $...
- 101
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 ...
- 383
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 ...
- 5,661
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 ...
- 151
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 ...
- 17.1k
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_{\...
- 37.8k
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 ...
- 532
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 ...
- 21.3k
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)...
- 326
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 ...
- 21.3k
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(\...
- 1,475
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 ...
- 1,552
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=...
- 133
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 ...
- 359
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.
...
- 43
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\...
- 909
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 ...
- 101