All Questions
Tagged with combinatorics or co.combinatorics
11,024 questions
69
votes
7
answers
17k
views
What is a chess piece mathematically?
Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained ...
- 1,451
4
votes
1
answer
170
views
About $CW(512,16^2)$
Definitions: A weighing matrix $W = W(n,k)$ with weight $k$ is a square matrix of order $n$ and entries $w_{ij}$ in $\{0, \pm 1\}$ such that $WW^T=kI$,
where $I$ is the identity matrix. A circulant ...
- 1,021
2
votes
1
answer
217
views
Number of distinct higher dimensional integer partitions
By a distinct partition, I mean a partition into distinct parts, i.e., $10 = 5+4+1$ is one, but $10=6+2+2$ is not. The number of distinct partitions of $k$ all whose parts are at most $n$ is given by ...
- 4,589
15
votes
3
answers
1k
views
Classification of Platonic solids
My question is very basic: where can I find a complete (and hopefully self-contained) proof of the classification of Platonic solids? In all the references that I found, they use Euler's formula $v-e+...
- 4,713
4
votes
1
answer
173
views
Approximating a partition
Let $X = \{1,\ldots,2 \cdot n\}$ be a set of numbers. For this question, an equal partition $Y_1,Y_2$ of $X$ is a partition of $X$ to two equal sizes. Let $\varepsilon \in (0,1)$ be an error parameter....
- 109k
1
vote
0
answers
99
views
Minimum of the maximum element frequency given the family size and the universe size
[Crossposted at math.stackexchange].
Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$.
I have written and solved ...
- 1,000
3
votes
1
answer
237
views
Find the number of triangles in plane
Let $S$ be a set of $n$ points in the plane in general position. Each 3 points of S span a triangle. Total number of triangles spanned by S:
$$\binom{n}{3}=\frac{n(n-1)(n-2)}{6}=\frac{1}{6} n^3-O(n^2 )...
- 109k
26
votes
0
answers
708
views
Coloring a Ferrers diagram
I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed.
Say that a coloring of the dots of a Ferrers diagram ...
- 82.7k
2
votes
1
answer
174
views
Constrained triangulation of a convex polytope
I am looking for an algorithm that can do a constrained triangulation of a convex polytope ($n$-dimensional). The constraint is that it should contain certain $(n-1)$-dimensional simplices. Can ...
- 63.9k
0
votes
1
answer
170
views
Summation of binomial coefficients with alternating signs
For a fixed $\alpha > 1$ and integer $n$, I want to provide some bounds or scaling results for the following summations
$$S_1(n,\alpha) = \sum_{k = 1}^{n} {n \choose k} (-1)^{k + 1} k / (\alpha k + ...
- 34.3k
1
vote
0
answers
75
views
VC-dimension of intersection
Let $A$ and $B$ be sets of real-valued functions on $X$. Are there any reasonably tight bounds on the VC-dimension of $A\cap B$ in terms of the VC-dimensions of $A$ and $B$?
- 63.9k
5
votes
2
answers
189
views
Bisymmetric Hadamard matrices
Definitions: An $n\times n$ Hadamard matrix is a matrix whose entries are either $1$ or $−1$ and whose rows are mutually orthogonal.
A symmetric matrix is a square matrix that is equal to its own ...
- 696
5
votes
2
answers
792
views
How to calculate an integral over the complex unit sphere
We want to calculate the following integral over the complex unit sphere $S^{2n-1}$:
$$\int_{S^{2n-1}} \frac{1 }{|1 - \langle z, \zeta \rangle|^2} \, d\sigma(\zeta),$$
where $ z $ is a fixed point in ...
3
votes
2
answers
493
views
Why can we not find exact values for sizes of cap sets for $d>6$?
I've been reading about cap sets in $\mathbb{F}_3^d $ over the past couple of days and wondered why we can only find bounds, as opposed to exact values, for (maximum) sizes of cap sets for $d>6$. ...
- 2,370
5
votes
1
answer
355
views
How do you traverse a rectangular grid of points while turning as little as possible?
Suppose I have a lattice grid of $m \times n$ points in the plane, with $m\leq n$. I want to traverse this grid in such a way as to minimize the total amount of turning that occurs. I am pretty sure ...
- 5,103
-1
votes
1
answer
145
views
Bijection $f:\mathbb{N}\to\mathbb{N}$ such that $f(S)\neq S$ for $S\subseteq \mathbb{N}$ infinite and co-infinite [closed]
Is there a bijection $f:\newcommand{\N}{\mathbb{N}}\N\to\N$ such that $f(S)\neq S$ whenever $S\subseteq \N$ is infinite and $\N\setminus S$ is infinite?
- 10.8k
9
votes
0
answers
212
views
Left adjoint functor between categories of polygons?
EDIT: Based on very helpful comments from Alec Rhea and Qiaochu Yuan I am adding some specification on objects and morphisms, hoping that this clarifies the idea behind these categories. I have also ...
- 6,917
7
votes
1
answer
259
views
A name for the Weyl group of $\frak{so_{2n}}$
For the $A$-series the Weyl group is the symmetric group $S_n$. For the $B$ and $C$ series the Weyl group is the hyperoctahedral group $\mathbb Z_2 \wr S_n$.
A) Does the $D$-series Weyl group $S_n \...
- 10.7k
1
vote
1
answer
90
views
$|S\cap f(S)|$ for bijections $f:\omega\to\omega$ and $S\subseteq \omega$
Is there a bijection $f:\omega\to\omega$ with the following property?
Whenever $S\subseteq \omega$ is infinite such that $\omega\setminus S$ is infinite as well, then $S\cap f(S)$ is finite.
- 63.9k
6
votes
1
answer
2k
views
Some mathematician with mental illness who was a friend of Paul Erdős that has some open problems in Combinatorics
I remember a few years ago reading his bio in Wiki page, but I don't remember his name.
I know there's a list of open problems in combinatorics that bear his name. If I remember correctly his problems ...
- 105k
4
votes
1
answer
356
views
Left and right halves of convex curve
Let $S$ be a set of $n$ points in the plane in general position (no 3 on a line), $n$ even.
A halving line is a line through $2$ points of $S$ that partitions $S$ into 2 equal parts ($(n-2)/2$ points ...
- 60.5k
7
votes
0
answers
162
views
A differential equation and recurrence related to P-partitions
I am interested in polynomials $G_n(z)$ defined by the recurrence
$$G_{n+1}(z) - 2G_n(z) + (1-nz)G_{n-1}(z)=0$$
for $n\ge1$ with the initial values $G_0(z) = 1$ and $G_1(z) = 1$.
The next few values ...
- 17k
1
vote
0
answers
90
views
Closed form for the A357990 using A329369 and generalised A373183
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor, \\
\ell(0) = -1
$$
Let
$$
f(n) = \ell(n) - \ell(n-2^{\ell(n)}) - 1
$$
Here $f(n)$ is A290255.
Let $A(n,k)$ be a square array such that
$$
A(n,k)...
- 175
3
votes
0
answers
88
views
Recursion for reversed rows of the A373183 using unsigned Stirling numbers of the first kind
Let $\left[{n \atop k}\right]$ be unsigned Stirling numbers of the first kind. Here
$$
\left[{n \atop k}\right] = (n-1)\left[{n-1 \atop k}\right] + \left[{n-1 \atop k-1}\right], \\
\left[{n \atop 0}\...
- 175
1
vote
0
answers
122
views
Monomial symmetric polynomials evaluation at roots of unity
The monomial symmetric polynomials are defined see Wikipedia.
For an arbitrary partition $\lambda$ with $n$ parts
I'm trying to find the following values:
$$m_{\lambda}(\omega_0,\dotsc,\omega_{n-1})$$
...
- 175
8
votes
0
answers
507
views
Example of graph with strange property
I've also posted this problem in Math Stack Exchange (here).
Note: Whenever I mention a coloring of a graph I'm referring to a proper coloring over its vertices using the least amount of colors.
...
CommunityBot
- 1
0
votes
1
answer
94
views
Do disjunctive sequences eventually get palindromic at some point?
I have a friend who is very interested in math and has been thinking about a problem involving disjunctive sequences. For his birthday, I would like to give him an answer to his question, either by ...
- 54.2k
5
votes
0
answers
167
views
Bounding elementary symmetric polynomials away from zero
Let $2 \leq m \leq n$ be integers and let $\mathbf{x} \in \mathbb{R}^n$ (importantly, I am not assuming that the entries of $\mathbf{x}$ are non-negative). The elementary symmetric polynomials are ...
- 6,351
0
votes
0
answers
135
views
Integer coefficients and continued fractions
Let $a(n,p,q)$ be the family of integer sequences such that ordinary generating functions for it are $\frac{1}{G_1(0,x)}$ where $G_1(0,x)$ are continued fractions such that
$$
G_1(j,x)=1-\cfrac{(qj+1)...
- 4,938
1
vote
0
answers
168
views
Integer coefficients and integrals
Let $a(n,p,q)$ be the family of integer sequences such that exponential generating functions for it satisfy
$$
A_1(x)=\exp\left(x + p\int\int (A_1(x))^q \, dx \, dx\right).
$$
Let $b(n,p,q)$ be the ...
- 4,938
2
votes
1
answer
173
views
Connected partitions of bounded degree graphs with parts of bounded sizes
A connected partition of a graph is a partition of its vertex-set such that the induced subgraph on each part is connected.
Question 1: Are there real numbers $c\ge1$ and $r\ge1$ such that for any ...
- 277
4
votes
1
answer
114
views
Sum of two positive roots which is not a root: uniqueness of heights of the summands
Consider a (finite reduced irreducible crystallographic) root system $\Phi$ and four positive roots $\alpha,\beta,\gamma,\delta$ such that $\{\alpha,\beta\} \neq \{\gamma,\delta\}$ and $\alpha+\beta=\...
- 550
6
votes
0
answers
214
views
Looking for a combinatorial proof for an identity involving $q$-Catalan triangles
Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Following my earlier post on MO, one fine colleague asked me if there is a $q$-analogue of the identity formed by the so-called Shapiro's ...
- 13.4k
5
votes
1
answer
212
views
Image-catching families in $\omega$
Let $[\omega]^\omega$ be the collection of infinite subsets of the set of nonnegative integers $\omega$, and let $\newcommand{\I}{\cal{I}}\I=$ $\{S\in[\omega]^\omega: (\omega\setminus S)\in[\omega]^\...
- 9,902
18
votes
2
answers
1k
views
A combinatorial interpretation for $n$-ary trees for negative $n$
The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation
$$
T_n=1+xT_n^n.
$$
This is usually defined for $n\ge 0$, but the functional equation can be ...
- 10.5k
7
votes
0
answers
191
views
Eulerian posets and order complexes
To every poset $P$ it is possible to associate its order complex $\Delta(P)$. The faces of $\Delta(P)$ correspond to chains of elements in $P$. An Eulerian poset is a graded poset such that all of its ...
- 1,889
2
votes
0
answers
62
views
Maximum distance between consecutive terms in sequence with arbitrarily long APs
Good evening. I am writing a paper on complex analysis, and as a corollary (of my work and others'), I believe that I have managed to deduce the following result.
Proposition: Let $n_1 < n_2 \cdots ...
- 121
2
votes
1
answer
147
views
$R$-recursion for Fibonacci numbers using signed Catalan numbers
Let $F_n$ be A000045 (i.e., Fibonacci numbers). Here
$$
F_n = F_{n-1} + F_{n-2}, \\
F_0 = 0, F_1 = 1.
$$
Let $C_n$ be A000108 (i.e., Catalan numbers). Here
$$
C_n = \frac{1}{n+1}\binom{2n}{n}.
$$
Let
$...
- 4,938
1
vote
1
answer
838
views
Covering a connected bounded-degree bipartite graph with connected subgraphs
Let $G = (L,R,E)$ be a finite connected bipartite graph with maximum degree $\Delta\ge2$. A subgraph $H$ is said to be left-neighbourhood closed (LNC for short) if every $v\in L(H)$ satisfies $\...
- 277
2
votes
1
answer
169
views
Smallest ${\mathbf B}$-function $f:\omega\to( \omega\setminus\{0\})$
Motivation. Every hypergraph $(\omega, E)$ where $E$ is countable and consists of infinite sets has property $\newcommand{\B}{\mathbf{B}}\B$. On the other hand, if the members of $E$ are allowed to be ...
- 13.4k
2
votes
0
answers
105
views
Weighted inclusion-exclusion principle
Let $\mathbb A := \{A_1,\dots,A_n\}$ be a collection of finite sets, and for $J\subseteq[n]$ let $A_J:=\bigcap_{j\in J} A_j$. Inclusion-exclusion principle gives the number of elements belonging to at ...
- 34.3k
1
vote
1
answer
61
views
Simplest way to generate integer coefficients with row sums equal to the terms of an arbitrary given sequence
Let $f(n)$ be an arbitrary function.
Let $\operatorname{wt}(n)$ be A000120 (i.e., number of ones in the binary expansion of $n$). Here
$$
\operatorname{wt}(2n+1) = \operatorname{wt}(n) + 1, \\
\...
- 800
0
votes
1
answer
234
views
Minimum number of elements needed to represent a lattice with a union-closed family of sets
I know that it is possible to represent every finite lattice $L$ with a union-closed family $\mathcal{F}$ containing the empty set: for every $x\in L$, let $S_x=\{y\in L\, :\, y\not\geq x\}$ and $\...
- 1,000
0
votes
0
answers
67
views
Do there exist at least two disjoint sets in a certain union-closed family of sets?
This is a strengthened dual version of this answered question. Here we are adding to that question requirement $3$ below.
Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can ...
- 1,000
0
votes
0
answers
53
views
A question on bounding the size of the polynomial
Suppose we are given the following n polynomials in $\bar{\mathbb{F}}_2[x_1,...,x_n]$:
$f_1 = x_1 + x_n^2$
$f_2 = x_2 + x_1^2$
$\cdot$
$\cdot$
$f_{n-3} = x_{n-3} + x_{n-4}^2$
$f_{n-2} = x_{n-2} + x_{n-...
- 341
4
votes
1
answer
383
views
Point-Hyperplane incidence in finite projective spaces
Let $P$ be a finite projective space of order $q$ and dimension $d$. I am interested in finding the least $k$ such that for any set $S$ of $k$ points of $P$, and for any set $S'$ of $k$ hyperplanes of ...
- 935
6
votes
0
answers
752
views
For all $n\in \mathbb{N}$, How to find $\min\{ m+k\}$ such that $ \binom{m}{k}=n$?
I asked this question on MSE here.
Most numbers in pascal triangle appear only once (excluding the duplicates in the same row of the Pascal's triangle) but certain numbers appear multiple times. ...
- 541
2
votes
0
answers
318
views
What's the number of facets of a $d$-dimensional cyclic polytope?
A face of a convex polytope $P$ is defined as
$P$ itself, or
a subset of $P$ of the form $P\cap h$, where $h$ is a hyperplane such that $P$ is fully contained in one of the closed half-spaces ...
- 53
9
votes
0
answers
177
views
An $m$-positivity conjecture related to bivariate Jacobi-Trudi matrices
This question
by Rellek reminds me of the following problem. Alan Sokal has
conjectured that if we replace the elementary symmetric function $e_k$
in the dual Jacobi-Trudi matrix for $s_\lambda$ (a ...
1
vote
0
answers
48
views
Length of the product of two elements of the subregular two-sided cell in the affine Weyl group of type A
The affine Weyl group of type $A_n$ can be described as follows. It is the group of all permutations $\sigma: \mathbb Z \to \mathbb Z$ such that $\sigma(i+n)=\sigma(i)+n$ and $\sum_{i=1}^n (\sigma(i)-...
- 2,964