All Questions
Tagged with combinatorics or co.combinatorics
11,023 questions
6
votes
0
answers
158
views
Binary sequences avoiding structures
I'm interested in estimating the number of binary strings $(a_1, a_2, \dots, a_n)$ that avoid a specific type of structure. A specific example is the following: for any $k$, $(a_{k-3}, a_{k-2}, a_k, ...
- 63.9k
4
votes
0
answers
207
views
Who first considered "Pascal Triangle"? [closed]
Arnold was used saying in his talks,
"Pascal’s triangle, so called, because it was by Chinese discovered"!
How much is he right?
- 869
2
votes
0
answers
70
views
Property of a family of simple polynomials related to the A329369
Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\dotsc,m\}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \...
- 12.9k
2
votes
1
answer
513
views
Prove ${^{b}a} \equiv {^{b+1}} a \pmod {10^{\lfloor{\log_{10} (^{b}a) }\rfloor + 1}} \Rightarrow a=5$ as $a$ and $b$ are two integers greater than $1$
$\DeclareMathOperator\len{len}$Let $a, b \in \mathbb{N} -\{ 0, 1 \}$ and define ${^{b}a}$ to be $a^a$ if $b = 2$ and $a^{\left(^{b-1}a \right)}$ if $b \geq 3$ (e.g., ${^{3}5} = 5^{\left( 5^5 \right)} =...
- 1,028
39
votes
3
answers
2k
views
Chromatic number of the hyperbolic plane
A notorious problem in combinatorics is the following:
If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required?
This ...
- 4,713
7
votes
1
answer
413
views
Has Plummer's open problem on the cyclic connectivity of planar graphs been solved?
$\DeclareMathOperator\cl{cl}$The cyclic edge connectivity $\cl(G)$ is the size of a smallest cyclic edge cut, i.e., a smallest edge cut $F$ such that $G-F$ has two connected components, each of which ...
- 1
2
votes
0
answers
51
views
Convex polygons that can be cut into sets of m mutually congruent convex pieces in exactly n ways
General question: Given two integers m and n, to find a convex polygonal region that can be cut into sets of m mutually congruent convex pieces in exactly n ways - the shape of pieces in each set ...
- 5,979
3
votes
0
answers
112
views
Ruzsa embedding lemma in $\mathbb{F}_p^N$
Below, you will find the lemma known as the Ruzsa embedding lemma in $\mathbb{F}_p^N$. I understood the idea of the proof quite well, but one technical detail is bothering me. I've pondered it for a ...
- 330
4
votes
1
answer
148
views
Closed form for the A110501 (unsigned Genocchi numbers (of first kind) of even index)
Let $a(n)$ be A110501 (i.e., unsigned Genocchi numbers (of first kind) of even index). Here
$$
a(n) = \sum\limits_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2i}a(n-i)(-1)^{i-1}, \\
a(1) = 1
...
- 17k
0
votes
0
answers
92
views
Algorithm that can solve or approximate the solution to a combination problem
I have a computational problem on my hands and I would like your help.
Here is my problem (simplified)
Let $X = \{x_1, x_2, \ldots, x_n\}$ represent a set of $n$ values.
Each value $x_i$ has a ...
- 869
3
votes
0
answers
89
views
Young symmetrizers-like projections to the center of group algebra
Let $A:=\mathbb{C}S_n$ be the symmetric group aglebra.
Let $T$ be a standard Young tableaux of shape $\lambda$. Denote $R(T)$ and $C(T)$ as row and column stabilizers of $T$. For a set $S \subseteq ...
- 31
3
votes
0
answers
128
views
Fast and simple algorithm for the A329369
Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\cdots,m\}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \...
- 4,938
2
votes
0
answers
62
views
On convex polygons that can be cut into convex and mutually congruent pieces in exactly one way
Observations: any thin isosceles triangle has exactly 1 partition into 2 congruent pieces - only 1 line, bisector of its apex, does it.
By attaching a right triangle with base 1 and altitude 2 to an ...
- 5,979
8
votes
3
answers
779
views
Computer program for counting graph homomorphisms
I would like to ask is there a computer program for counting graph homomorphisms?
- 75
12
votes
1
answer
684
views
Graphs $G$ with $G \cong \text{Aut}(G)$
Let $G=(V,E)$ be a simple, undirected graph. By $\newcommand{\Aut}{\text{Aut}}\Aut(G)$ we denote the collection of graph isomorphisms $\varphi:G\to G$. We let $$E(\Aut(G)) =\big\{\{\varphi, \psi\}:\...
- 1,543
3
votes
0
answers
97
views
What algebras generate polynomial count varieties as their representations spaces ? Is it preserved by the Koszul duality, Manin's endomorphisms?
Consider for example commutative polynomial algebra $C[x,y]: xy=yx$, look on $F_p$-matrices satisfying that relation - the number over $F_p$ will be given by polynomial in $p$ (classical result due to ...
- 24.9k
1
vote
1
answer
199
views
Gluing $n$ $2(n-1)$-simplices
It should be true that $n$ $2(n-1)$-simplices can be glued together, such that $k$ of them intersect in a common $(2n -k -1)$-cell and the resulting object is a "convex $2(n-1)$-disc" whose ...
- 869
7
votes
1
answer
296
views
Is this known? As $p,q\to\infty$, most elements of the power set of $\{1,\dots,p\}\times\{1,\dots,q\}$ are in free $\Sigma_p\times\Sigma_q$-orbits
Let $p,q$ be nonnegative integers. The product of symmetric groups $\Sigma_p\times\Sigma_q$ acts on the power set $P(\{1, \dots ,p\}\times\{1, \dots ,q\})$ in the evident way. You can ask what ...
- 12.9k
10
votes
1
answer
604
views
Is the action of the Laplacian on the Schur polynomials known?
Since the Laplace operator
$$
\Delta=\frac{\partial^2}{\partial x_1^2}+\cdots+\frac{\partial^2}{\partial x_n^2}
$$
preserves symmetric polynomials in $n$ variables, its action on the Schur polynomial $...
- 50.8k
3
votes
1
answer
272
views
An inequality about factorial function
Let $d,s,k$ be integers such that $d<s+2$, $s=o(k)$. For sufficiently large integer $k$, is the following inequality right?
$$\frac{(k-2d+1)^{k+s-d}}{(k-d)!\cdot (k-2)_s} \ge 1$$
We write $(k)_s = ...
- 128k
6
votes
0
answers
245
views
Searching for a proof of the pattern and identification of integer coefficients for the A329369
Please see the update given below. Everything you need to know from the old version of the question are the functions $a(n), \ell(n), s(n), t(n), r(n)$.
Let $a(n)$ be A329369 (i.e, number of ...
- 4,938
3
votes
1
answer
406
views
Electricity division and bin packing
In the electricity division problem, there is a powerhouse that supplies $s$ kilowatt of electricity. There are $n$ households. The connection size of household $i$ is $d_i$.
The problem is that $s &...
- 5,409
1
vote
0
answers
73
views
Alternating sum of integer coefficients of the triangles related to Eulerian numbers and binomial transforms
Let $W(n, k, m)$ be an integer coefficients defined for $n > 0, 1 \leqslant k \leqslant n, m > 0$ with $W(n,k,m)=0$ for $n \leqslant 0$ or $k \leqslant 0$ such that
$$
W(n, k, m) = (k+m-1)W(n-1,...
- 4,938
5
votes
0
answers
307
views
On $s$-additive sequences
For a non-negative integer $s$, a strictly increasing sequence of positive integers $\{a_n\}$ is called $s$-additive if for $n>2s$, $a_n$ is the least integer exceeding $a_{n-1}$ which has ...
- 791
3
votes
1
answer
115
views
Lower bound for sets couples such that $A \subset B$ or $B \subset A$ in some union-closed families
Consider a union-closed family of sets $\mathcal{F}$, with $n = \vert\mathcal{F}\vert$ and thus $n \choose 2$ unordered couples of distinct sets $\{A, B\}$, $A,B \in \mathcal{F}$.
In general, the ...
- 13.4k
1
vote
0
answers
93
views
Inside-out dissections of a cube
Ref:
Inside-out polygonal dissections
Inside-out dissections of solids
Definitions: A polygon P has an inside-out dissection into another polygon P' if P′ is congruent to P, and the perimeter of P ...
- 5,979
5
votes
1
answer
226
views
A polynomial identity involving Wick ordering of a complex power
The problem is related to the paper 1509.02093 by Oh and Thomann, where the authors considered the 2D Wick ordered NLS.
Let $g=a+ib$ be a complex number. Then it is claimed (see (2.7) in the paper and ...
- 7,226
0
votes
0
answers
36
views
Sufficient conditions for a polynomial function to have the same critical points as its symmetrized version
Are there any sufficient conditions known for a polynomial function (of many variables) to have the same critical points as its symmetrized version (with respect to all variables)?
This question has ...
- 765
1
vote
0
answers
111
views
On finding optimal convex planar shapes to cover a given convex planar shape
Covering a specific convex shape S with n copies of another specified convex shape S' (which may be different from S) is well studied - for example, https://erich-friedman.github.io/packing/index.html....
- 5,979
9
votes
1
answer
1k
views
Newman's Lemma or Diamond Lemma
I'd like to learn the Newman's Lemma or Diamond Lemma (the one used in abstract rewriting system), can someone recommend me some books where I can read it? I'd appreciate self-contained books with ...
- 33.8k
22
votes
8
answers
13k
views
Lower bound for sum of binomial coefficients?
Hi! I'm new here. It would be awesome if someone knows a good answer.
Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case $\...
6
votes
1
answer
339
views
Number of ways a positive integer n can be expressed as a sum of k natural numbers under a certain ordering condition
I have a question that I can't solve for the moment. Suppose we have a fixed positive integer $k$, now consider $k$
natural numbers $x_1,x_2,\dots,x_k$
such that they satisfy the following condition:
$...
- 4,589
18
votes
2
answers
876
views
Groupoid cardinality of the class of abelian p-groups
$\DeclareMathOperator\Aut{Aut}\newcommand\card[1]{\lvert#1\rvert}$So, after going over the classification of finite abelian groups in a class I was teaching this winter, I got curious about whether it ...
- 5,382
11
votes
1
answer
1k
views
Order of the "children's card shuffle"
Motivation. My eldest son thinks the following procedure is a "perfect shuffle" for a deck of cards: Take the first card, put the second on top of it, put the 3rd below cards 2 and 1, put ...
- 48.9k
5
votes
2
answers
190
views
Number of Hamiltonian cycles on 24-cell graph
I asked Wolfram Alpha for the number of Hamiltonian cycles on the 24-cell graph.
https://www.wolframalpha.com/input?i=number+of+hamiltonian+cycles+on+24-cell+graph
It answers 114.9 billion but doesn't ...
- 4,713
1
vote
2
answers
164
views
General and translational Birkhoff lattices. Equational classes
By lattice I'll mean Birkhoff lattice.
The two classical equational classes of lattices are modular lattices and distributive lattices. The old problem used to be:
Is there an equational class ...
- 14.6k
6
votes
0
answers
111
views
What is the largest subgraph of the Kneser graph which has a small chromatic number?
While trying to characterize constraint satisfaction problems which can be solved by the Linear Programming relaxation, I've run into a few perplexing puzzles related to the existence of certain ...
- 8,688
3
votes
4
answers
1k
views
Apply doubly stochastic matrix M to a probability vector, then entropy increases?
Consider a vector $p =(p_1,\dots,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 ...
5
votes
1
answer
231
views
Reference request: Gessel interview's generating function identities
In this interview, Ira Gessel mentions the following results:
Result 1: Let $B_n$ denote the $n^{\text{th}}$ Bernoulli number.
Define the series
$$B(x) = \sum_{n=2}^{\infty} \frac{B_nx^{n-1}}{n(n-1)}.$...
- 17k
5
votes
0
answers
83
views
Nonnegativity of the coefficients of the commuting difference operators of Fomin, Gelfand, and Postnikov evaluated on quantum Schubert polynomials
This post is about quantum Schubert polynomials. Fomin, Gelfand, and Postnikov defined operators in the nil-Hecke ring with coefficients in $\mathbb{Z}[x,q]$ denoted by $\chi_k$ for $1\leq k\leq n$ ...
- 2,168
9
votes
2
answers
625
views
Number of longest decreasing subsequences and RSK
It is well known via the RSK-correspondence that the length of the longest decreasing subsequence in a permutation $\pi \in S_n$ is the length of the longest column of the insertion tableau of $\pi$. (...
- 3,738
6
votes
3
answers
531
views
Enumerating all inequivalent planar embeddings of a planar graph
Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ ...
- 37.7k
4
votes
2
answers
559
views
Conjecture about union-closed families of sets - attempt 3
Version 2 of the conjecture was disproved. In this version 3 of the conjecture I am adding a further requirement to obtain from $\mathcal{H}$ a "minimal" family $\mathcal{G}$.
I have already ...
- 1,000
1
vote
1
answer
114
views
Removing a face from 4-connected planar graph
After removing a face (vertices along with edges) of a 4-connected planar graph, is the remaining graph 4-connected? Alternatively under what conditions is this true?
- 4,219
2
votes
1
answer
124
views
Proof of dynamic programming calculation of Levenshtein distance
Let s1 and s2 are 2 arbitrary strings with lengths l1 and ...
- 981
8
votes
0
answers
82
views
$2$-for-$2$ asymmetric Hex
This is a crosspost from Math stackexchange as I left the question open a while and bountied it but received no answers.
If the game of Hex is played on an asymmetric board (where the hexes are ...
- 181
2
votes
0
answers
54
views
Transform connecting powers of integration and differentiation operators
Just by a chance, I found the following power series identity, which holds for any analytic function $F(\cdot)$, nonnegative integer $m$, and constants $u,v$ not depending on indeterminates $z,t$:
$$\...
- 34.3k
0
votes
0
answers
79
views
Are there triangles that can be cut into 7 mutually congruent connected polygons?
First question below had appeared in a note at Triangles that can be cut into mutually congruent and non-convex polygons
Following the results of Beeson quoted in the answer at Subdivision of ...
- 5,979
4
votes
1
answer
443
views
Conjecture about union-closed families of sets - attempt 2
[Update: this one has been disproved, but I have started conjecture attempt 3]
My previous question had an error, I am sorry for that. The limit $\lceil n/2 \rceil$ must be replaced with $\lceil (n+1)/...
- 1,000
3
votes
0
answers
190
views
Stirling number, Delannoy number, and binomial coefficients in a sum
I want to compute/prove that the following sum is positive:
$$ \sum_{i = 0}^n \left[\frac{D(n - i, i)}{d} \sum_{j = m}^d s(d, j) \binom{j}{m} (d - i)^{j - m}\right] > 0
$$
where $s(d, j)$ is the ...
- 51