All Questions
Tagged with combinatorics or co.combinatorics
11,024 questions
11
votes
0
answers
387
views
Inequality for symmetric polynomial functions of log concave variables
Let $(x_i)_{i \ge 1}$ be a log-concave (resp. log-convex) sequence of non-negative real variables. In other words, for $i \ge 2$, we have $x_i^2 \ge x_{i-1}x_{i+1}$ (resp. $x_i^2 \le x_{i-1}x_{i+1}$).
...
- 505
1
vote
0
answers
105
views
Simpler recursion for the A358612
Let $T(n,k)$ be an integer coefficients (A358612) such that
$$
T(2n+1, k) = kT(n, k) + T(n, k-1), \\
T(2n, k) = kT(n, k) + T(n, k-1) - \frac{T(2n, k-1) + T(n, k-1)}{k-1}, \\
T(n, 1) = T(0, 2) = 1
$$
...
- 175
2
votes
1
answer
219
views
Existence of a special ordering of the elements of a finite group (II)
Let $G$ be a finite non-abelian group of order $n$. Given $g\in G$ we denote its order by $\mathrm{ord}(g)$.
Consider the group algebra $\mathbb{F}[G]$ for some field $\mathbb{F}$.
Given an ordering $...
- 12.9k
3
votes
1
answer
140
views
$R$-recursion for unsigned Genocchi numbers (of first kind) of even index
Let $G_n$ be A036968 (i.e., Genocchi numbers). Here
$$
\frac{2t}{1+e^t}=\sum\limits_{n=0}^{\infty}G_n\frac{t^n}{n!}.
$$
Also
$$
t\tan\left(\frac{t}{2}\right)=\sum\limits_{n=1}^{\infty}(-1)^n G_{2n}\...
- 175
8
votes
2
answers
367
views
Existence of a special ordering of the elements of a finite group
Let $G$ be a finite non-abelian group of order $n$. Given $g\in G$ we denote its order by $\mathrm{ord}(g)$.
Consider the group algebra $\mathbb{F}[G]$ for some field $\mathbb{F}$.
Given an ordering $...
- 1,338
6
votes
1
answer
282
views
Integer sequences with a periodic pattern
Let $A$ and $B$ be two different integers. Let $S$ be a finite integer sequence with exactly $n_A$ $A$s and $n_B$ $B$s. By repeating $S$ infinitely many times we obtain an infinite integer sequence $P$...
- 39.7k
8
votes
0
answers
260
views
Efficient listing of ASMs
Famously, the alternating sign matrix theorem gives a product formula for the number $a(n)$ of ASMs of size $n$. There are multiple proofs of this formula, all somewhat involved. My question is ...
- 17k
2
votes
1
answer
194
views
Find bivariate generating function for two-dimensional sequence
How to find generating function for triangle of squares of elements in this sequence? I. e. for
$1 + (1 + 4x)y + (1 + 9x + 16x^2)y^2 + ...$ ? It seems that ordinary approach with arithmetic ...
- 34.3k
4
votes
1
answer
378
views
Counting permutations with a fixed number of descents and an extra condition
I am computing the volumes of certain polytopes and it turns out that knowing a "closed formula" for the following number would help a lot.
Determine the number of permutations $\sigma\in \...
- 34.3k
6
votes
1
answer
218
views
Maximizing the mutual Hamming distance in $\big[{\cal P}([n])\big]^n$
If $X$ is a set and $A,B\subseteq X$ we let the Hamming distance of $A,B$ be defined as $d_H(A,B) = \big|(A\setminus B)\cup(B\setminus A)\big|$. If $\newcommand{\S}{{\cal S}}\S\subseteq {\cal P}(X)$, ...
- 800
5
votes
0
answers
112
views
A strengthening of an inequality for posets by Chan-Pak
Suppose that $P$ is a poset, $x$ and $y$ are two minimal elements of $P$, and that $e(P)$ denotes the number of linear extensions of $P$. Chan and Pak use their recent combinatorial atlas technology ...
- 85.6k
3
votes
0
answers
165
views
Elegant algorithm for A140717
Let $T(n, k)$ be A140717 (i.e., triangle read by rows: $T(n,k)$ is the number of Dyck paths $d$ of semilength $n$ such that sum of peakheights of $d$ - number of peaks of $d$ equals $k$ ($n \geqslant ...
- 4,938
2
votes
0
answers
48
views
Maximum coverage of an orthogonal polygon using $k$ rectangles
I have an orthogonal polygon (all edges are horizontal or vertical) which is convex (no holes in any row of column of the polygon).
I would like to cover as much as possible of this orthogonal polygon ...
- 6,367
4
votes
1
answer
234
views
What's known about the matroid induced by the Plücker coordinates of the representation of a matroid?
Let $M$ be a linear matroid with ground set $E$ and independent subsets $\mathcal I$, represented by $\rho: E \rightarrow V$.
This induces a map
$$
\hat\rho: \mathcal I \rightarrow \mathbf P(\Lambda V)...
- 1,046
2
votes
1
answer
262
views
Randomly fixing elements and transcendence degree
Given $f_1,\ldots,f_n \in \mathbb{F}_q[x_1,\ldots,x_m]$ such that $\deg(f_i) \leq d < q$. Suppose we have for some $1 \leq j \leq m$
$$ \operatorname{trdeg}_{\mathbb{F}(x_1,\ldots,x_j)}\{f_1,\ldots,...
- 341
19
votes
2
answers
1k
views
Explicit invariant of tensors nonvanishing on the diagonal
The group $SL_n \times SL_n \times SL_n$ acts naturally on the vector space $\mathbb C^n \otimes \mathbb C^n \otimes \mathbb C^n$ and has a rather large ring of polynomial invariants. The element $$\...
2
votes
1
answer
135
views
Number of permutations that map fixed number of elements between boxes
I would like to count the number of permutations with the following restriction:
I have $N$ objects distributed over $d$ boxes. The boxes are labelled by $a=1,..,d$ and I know the number $n_a$ of ...
6
votes
1
answer
199
views
Combinatorial type construction of the free operad
$\DeclareMathOperator\RT{RT}$I am reading the book "Algebraic operads" by J. L. Loday and B. Vallete. The authors have given a combinatorial construction of the free operad over an $\mathbb{...
- 63.9k
0
votes
0
answers
95
views
Nested Set Permutations and their Enumeration
Let $(S_i)_{i \in \mathbb{N}}$ be a sequence of sets defined recursively as follows:
$S_1 = \{1\}$
$S_{i+1} = S_i \cup \{S_i, i+1\} \quad \forall i \in \mathbb{N}$
A permutation $\sigma$ of $S_i$ is ...
- 34.3k
2
votes
0
answers
64
views
On a $\sum\limits_{n=0}^{\infty}c_n x^n=\sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n+1}(1-f(k)x^k)$ (slightly different question)
Please note that this question differs from one of the previous questions of mine.
Let $f(n)$ be an arbitrary function with integer values.
Let $c_n$ be an arbitrary integer sequence.
Let $a(n)$ be ...
- 4,938
0
votes
1
answer
98
views
Chromatic tiling complexity and the chromatic number conjecture
Let $T$ be a finite set of tiles in $\mathbb{R}^d$. A tiling of $\mathbb{R}^d$ by $T$ is a collection of disjoint translates of tiles in $T$ whose union is $\mathbb{R}^d$. A tiling is $k$-chromatic if ...
- 18.8k
4
votes
1
answer
406
views
Inverse relationship between Stirling numbers of the first and second kind via generating functions
In combinatorics, a well-known result is that the matrix formed by the Stirling numbers of the second kind $\left(S(n,k)\right)_{n,k\geq 0}$ and the matrix of the signed Stirling numbers of the first ...
- 34.3k
1
vote
0
answers
32
views
On a A347205 and related row polynomials
Let $a(n)$ be A347205. Here
$$
a(2^m(2k+1)) = \sum\limits_{j=0}^{m}a(2^j k), \\
a(0) = 1.
$$
Let $\nu_2(n)$ be A007814 (i.e., number of trailing zeros in the binary expansion of $n$). Here
$$
\nu_2(2n+...
- 4,938
5
votes
0
answers
145
views
Are there convex polyhedrons that can be cut into mutually congruent connected pieces only if pieces are non-convex?
This is the 3D (and higher D) version of A claim on partitioning a convex planar region into congruent pieces
Is there a 3D convex polyhedral solid that can be cut into 2 mutually congruent non-...
- 5,979
9
votes
2
answers
582
views
Solving a second-order recurrence relation / Series expansion of a confluent Heun equation
I would like to know whether it is possible to solve (in "closed form") either one of the following two second-order recurrence relations, which are closely related to each other. The first ...
- 176
4
votes
1
answer
85
views
Why does the Athansiadis-Linusson bijection encode floors?
The Athanasiadis-Linusson bijection is a correspondence between dominant regions of the $k$-Shi arrangement (in type A) and $k$-parking functions. I'll take $k=1$ here for convenience here.
Let $V$ be ...
- 525
11
votes
1
answer
990
views
Choosing a relative large density subsequence from a low density sequence
My question is somewhere in the interface of combinatorics, probability, and measure theory. It is quite ad-hoc, and I wonder if there is a counter example.
Consider for example the unit interval $[0,...
- 114k
0
votes
0
answers
73
views
General solution of partial difference equation that generates Eulerian numbers
I have a question on the partial difference equation
$$f(n+1, k) = (k+1) f(n,k) + (n+1-k)f(n,k-1)$$
where $(k, n) \in \mathbb{Z}^2$.
It is well known, that under some boundary conditions this equation ...
- 63.9k
1
vote
1
answer
200
views
Description of the generalized permutahedron
According to Postnikov, we know that the generalized permutahedron are describe as "polytopes obtained by moving vertices of the usual permutohedron so that directions of all edges are preserved&...
- 24.2k
5
votes
1
answer
168
views
On a generating function and vector $\nu$ of length $n$
Let $f(n)$ be an arbitrary function with integer values.
Let $a(n)$ be an integer sequence such that
$$
\frac{1}{1-x}=\sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n+1}(1-f(k)x)
$$
Start with ...
- 109k
1
vote
0
answers
54
views
Finding a path of given length with maximal relative weight
Let $G$ be a directed graph with vertices $V$ and edges $E \subset V\times V$. A path of length $n \geq 2$ in $G$ is a sequence of vertices $(i_{0},i_{1},\ldots,i_{n-1})$ such that $(i_{k},i_{k+1}) \...
- 798
4
votes
1
answer
98
views
Clique number for hypergraphs
Does anybody know any link/source where I can find examples of hypergraphs with their clique numbers? I need a few examples to test an algorithm and do not want to go for randomly generated hypergraph....
- 109
3
votes
1
answer
380
views
Generating all possible subsets in order of sum
Given a set of positive integers, I am looking for method to algorithmically generate all possible subsets in order of their sum. Because the the count of possible subsets is exponential ($2^n$), it ...
- 12.9k
1
vote
1
answer
361
views
A sequence and majorization
For two positive vectors $a,b$ such that $a\prec b$, we know that there is an $m$ sequence of vectors $c^{(i)}$ such that $$a\prec c^{(1)}\prec \ldots \prec c^{(m)}\prec b$$ where each vector in the ...
CommunityBot
- 1
2
votes
1
answer
142
views
Bounds for ground set of Steiner system (inverse EKR style problem)
Imagine we have $r$ subsets of a ground set $S$, each of size $k$, such that each set of size $l$ is contained in at most one of the $r$ sets. What can we say about the minimum value of $|S|$? I am ...
- 5,409
1
vote
0
answers
44
views
Constrained random sampling from partitioned sets with quotas
Let $D$ be a finite set, $\mathcal{P} = \{D_{i,j}\}_{(i,j) \in I \times J}$ a partition of $D$, $N: J \to \mathbb{N}$ a quota function, and $k \in \mathbb{N}^+$. A subset $F \subseteq D$ is considered ...
- 63.9k
2
votes
1
answer
110
views
Asymptotic behavior in a modular color-cycling problem
Consider the following problem: We have $k$ rooms, each equipped with a light that cycles through three colors – red, green, and blue – in a cyclic order. Initially, all lights are set to red. Each of ...
2
votes
0
answers
43
views
Idempotent suplattice endomorphisms which commute
Let $X$ be a suplattice and let $f, g$ be suplattice endomorphisms of $X$. Suppose $$f \circ f = f$$
$$g \circ g = g$$
$$f \circ g = g \circ f$$
What can we say about $f, g$?
- 591
0
votes
0
answers
120
views
Is there an existing problem related to inferring a hidden node in a graph from its neighbors
My original question was a bit too ambiguous, so I updated it as follows:
Consider a graph $G=(V,E)$. A vertex in $G$ is chosen uniformly at random; then a neighbor $x$ of $v$ is chosen uniformly at ...
- 109
1
vote
1
answer
59
views
Bounding the number of fully connected vertex subsets of a graph
I have a graph $G$ on $n$ vertices with edge density $p$. I am most interested in $p=O(1)$ but I would also appreciate ideas for the sparse case. My goal is to bound the number of subsets $A,B\...
- 11
1
vote
1
answer
102
views
Multiplicities and double and triple tensor products of simple $\frak{g}$-modules
Given a complex simple Lie algebra $\frak{g}$ and a simple module $V_{\lambda}$ for some dominant weight $\lambda$. Consider the tensor product decomposition
$$
V_{\lambda} \otimes V_{\lambda} \simeq ...
- 3,054
0
votes
0
answers
35
views
How many colors can an almost-unique subcube cover of a boolean cube have?
Consider a boolean cube $\{0,1\}^n$ and a collection of colored subcubes $\{(C_a, \ell_a)\}_{a \in [N]}$, where $C_a \in \{0,1,*\}^n$ is a subcube and $\ell_a \in \mathbb{N}$ is a color. I will ...
- 231
1
vote
0
answers
63
views
On a A162326 and vector $\nu$ of length $n$
Let $a(n)$ be A162326. Here
$$
a(n) = \frac{1}{n}(2(5n-7)a(n-1) - 9(n-2)a(n-2)), \\
a(0) = a(1) = 1.
$$
Also ordinary generating function is
$$
\frac{5 - \sqrt{\frac{1-9x}{1-x}}}{4}.
$$
Let $b(n)$ be $...
- 4,938
9
votes
1
answer
339
views
What is the formula for $\mathcal P_{n}^{k} (a_{1}, a_{2}, ...)$, defined by Peter Luschny?
Recently, I was reading a blog post called The P-transform by Peter Luschny, where the following formulas are given:
\begin{align*}
(-1)^k\frac{n!}{k!}\mathcal P^k_n\left(1, \frac1 2, \frac2 3, \dotsc\...
- 93
9
votes
2
answers
383
views
Action of Weyl group on regions of Shi arrangement
This is an elaboration of a question which was aked on MO several years ago, which was unanswered but deleted by the question-asker. I hope it is okay to elaborate on a deleted question like this; for ...
- 525
2
votes
0
answers
187
views
Matrix with elementary symmetric polynomials as entries
Let $n\geq 1$, and for each $j=1,\ldots, n+1$ let $\mathbf{X}_{j}=(X_{j1},\ldots, X_{jn})$ be $n$ variables. Let $M$ be the $(n+1)\times (n+1)$ matrix whose $(i,j)$-th entry is $$M_{ij}=(-1)^i e_{i-1}(...
2
votes
0
answers
124
views
Symmetric matching in special graphs
Let $G$ be a bipartite graph, $L$ ($R$) be the set of vertices in the left (right) part.
Consider a graph $T$ with the set of vertices $R \times L$ ( $L \times R$ ) in the left (right) part. For any $...
- 5,429
4
votes
1
answer
182
views
Permutations of the natural numbers with a common conditionally convergent series
Let $S\subset S_{\infty}$ be a set of permutations of $\mathbb{N}$. A real series $\sum_{n\geq0}u_{n}$ will be called $S$-conditionally convergent if it is absolutely divergent and if, for all $\sigma\...
- 18.5k
1
vote
0
answers
41
views
Unexpected non-uniformity of results from some implementations of Jacobson-Matthews seem to show a strange sensitivity to isotopy class
Questions
Why do some Jacobson-Matthews (J-M) implementations for generating random latin squares exhibit frequencies inconsistent with an underlying uniform distribution?
Further investigation ...
- 41
6
votes
0
answers
250
views
On the $p$-adic valuation of the sum of the first $n$ factorials
This is more a curiosity than anything useful. Consider $n>3$ and define $A(n)= 1!+2!+\cdots+n!$
It seems that if $p$ is the largest prime divisor of $A(n)$, then the $p$-adic valuation of $A(n)$ ...
CommunityBot
- 1