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.
10,515
questions
6
votes
0
answers
364
views
Is this just a numerical accident or what?
In a complementary proof for a matrix determinant of $a_{i,j}=\binom{n-1+i}j$, raised by BillyJoe, I showed the more general evaluation
$$\det\left(\binom{i+p}{j+k-1}\right)_{1\leq i,j\leq m}
=\prod_{...
6
votes
0
answers
242
views
Recursive runoff voting schemes
Background: I will below describe a generalization of the following voting systems (what is meant by “voting system” will be defined formally below) which are occasionally used in the real world:
“...
6
votes
0
answers
94
views
q-binomial-like series with exponentials defining probability distribution
Recently I encountered the series
$$f(d) = \frac{1}{(t;t)_\infty} \sum_{k=0}^\infty \frac{(-1)^k t^{\binom{k}{2}}}{(t;t)_k} e^{-t^{d-k}}$$
where $(t;t)_n = \prod_{i=1}^n (1-t^i)$, and $0 < t < 1$...
6
votes
0
answers
213
views
Lindström-Gessel-Viennot from properties of the $Alt^k$ functor?
Let $A$ be the directed adjacency matrix of an acyclic directed graph, with variables as its nonzero entries (one for each edge). The $(a,b)$ entry of the matrix $(I-A)^{-1}$ is the sum over all paths ...
6
votes
0
answers
206
views
Reference request: maximal determinant of matrices with pairwise orthogonal rows and entries in $\{1, 0, -1\}$
We know that "Hadamard maximal determinant problem" concerns the largest determinant of a matrix of oder $n$ with entries in $\{-1,1\}$ or $\{0, 1\}$. For $n=4k$, it is the Hadamard ...
6
votes
0
answers
274
views
Power law correction factor in tree enumeration via naïve division
It is a theorem of Otter, building on fundamental work of Pólya, that the number of unlabeled trees on $n$ vertices is $\approx C \alpha^{n} n^{-5/2}$, where $C = 0.534\ldots$ and $\alpha = 2.955\...
6
votes
0
answers
491
views
At most two elements give 1 to n
Fix a positive integer $m$. Let $n$ ( $= n(m)$) be the largest positive integer for which there exists some subset $\{a_1,\ldots,a_m\} \subseteq \{1,2,\ldots,n\}$ of $m$ positive integers between $1$ ...
6
votes
0
answers
236
views
What do Macdonald polynomials hint about $\operatorname{Rep}(S_\infty)$?
$\DeclareMathOperator\Rep{Rep}$It is well-known that the Macdonald "$P$" polynomials deform the
Jack "$J$" polynomials [1]. The latter have profound relations with
representation ...
6
votes
0
answers
254
views
A density result for arithmetic progressions
Note: By upper/lower density, we shall mean the upper/lower asymptotic density as given here.
Question:
For any subset $S \subset \mathbb N$ with positive upper density, does there exists a $\...
6
votes
0
answers
171
views
The Kostka-Foulkes polynomial in terms of the weak-order on standard tableaux
J. Nzeutchap offers an interesting interpretation of the Kostka numbers in his paper "On the Young-Fibonacci Insertion Algorithm" (see the link https://arxiv.org/abs/0704.1969), namely:
If $...
6
votes
0
answers
165
views
Eigenvalues of symmetric matrices associated to posets
For a finite connected poset $P$ define the Cartan matrix $C$ as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in P$.
Define the Frobenius-Cartan matrix of $P$ as $...
6
votes
0
answers
222
views
Gaussian coefficients identity
I am having difficulty showing the equivalence between (11) and (15) of Delsarte - Association schemes and $t$-designs in regular semilattices. It is somehow an application of Möbius inversion, but I ...
6
votes
0
answers
312
views
Reference request: colored Motzkin path interpretation of Catalan numbers
Recall that a Dyck path of length $2n$ is a lattice path in $\mathbb{Z}^2$ from $(0,0)$ to $(2n,0)$ consisting of $n$ up steps $U=(1,1)$ and $n$ down steps $D=(1,-1)$ which never goes below the $x$-...
6
votes
0
answers
155
views
Expanding the zonal polynomial $Z_\lambda(x/(1-x))$
Schur polynomials $s_\lambda(x)$ have a determinantal expression. Using that, I know how to write the polynomial $s_\lambda(\frac{x}{1-x})=s_\lambda(\frac{x_1}{1-x_1},\frac{x_2}{1-x_2},...)$ as an ...
6
votes
0
answers
113
views
Distribution of peaks in permutations, after a sorting operation
Let $S_n$ be the set of permutations on $\{1,2,\dotsc,n\}$.
A peak-value of $\pi$ is some $\pi_i$ such that $\pi_{i-1} < \pi_i > \pi_{i+1}$, where $1<i<n$. Let $PV(\pi)$ denote the set of ...
6
votes
0
answers
84
views
Can a spherical simplicial complex have more than one "central" inversion?
Let $\Delta$ be a finite connected simplicial complex. Call a simplicial map $\phi:\Delta\to\Delta$ an inversion if
$\phi$ is an involution, that is $\phi\circ\phi=\mathrm{id}$, and
$\phi$ is not ...
6
votes
0
answers
146
views
Distribution of iid hypergeometric random variables conditioned on the sum
Let $X_1,X_2,\ldots,X_n$ be iid random variables with hypergeometric distribution. To be specific,
$$ \mathrm{Prob}(X_1=i) = \frac{\binom{N}{i}\binom{M-N}{m-i}}{\binom{M}{m}}.$$
Let $S=X_1+\cdots+X_n$....
6
votes
0
answers
404
views
This sum over partitions has unexpectedly nice denominators
Fix an integer $n\geq0$, a power series $\gamma \in \mathbb Q[[X]]$ with valuation 1, and a symmetric function $f$ (with coefficients in $\mathbb Q$). Now, consider the series
$$
S_n = \sum_{\Lambda\...
6
votes
0
answers
204
views
Parameter independence of Stanley's "content formula". Why?
For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
R. Stanley remarked following ...
6
votes
0
answers
325
views
What do the circuits of this matroid look like?
Given any hypergraph $H=(V,E)$ we call a family of sets $I\subseteq E$ "indifferent" iff there exists a map $\phi:I\to V$ such that: $\forall X\in I(\phi(X)\in X)$ and $\forall X,Y\in I(X\...
6
votes
0
answers
306
views
extensions of the Nekrasov-Okounkov formula
This post is related to the issues addressed in
A q,t-extension of Plancherel Measure thru Yang-Mills Theory ?
however the generalization/interpolation which John Mangual asks for looks different ...
6
votes
0
answers
187
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 ...
6
votes
0
answers
125
views
Minimum of sums over degree products in a directed acyclic graph
My problem is the following: we have a graph $ G=(V,E)$. Having a total ordering $ \eta $ of the nodes, we give a direction to the edges such that $ (u,v) $ is directed from $u$ to $v$ iif $ \eta(u) &...
6
votes
0
answers
98
views
Zero-area-free embedding of points on the grid
Given $n$, I am looking for the smallest $m$ such that there is an $n$ element subset $S$ of the $m\times m$ grid (i.e., $n$ points with integer coordinates in $[0,m]^2$) such that no matter how one ...
6
votes
0
answers
185
views
Word/Loop in $L(\Lambda)$
Let $\mathfrak{g}$ be a symmetrizable Kac-Moody algebra, with Chevalley generators $e_i,f_i$ ($i=1,...,n$).
Let $L(\Lambda)$ denote the irreducible module with highest weight $\Lambda$. Let $v$ denote ...
6
votes
0
answers
152
views
When are Hamming codes cyclic?
I've asked this question on math.stackexchange before, but it has not been solved.
The following statement appears to be true:
The $q$-ary Hamming code of codimension $r$ over $\mathbb{F}_q$ is ...
6
votes
0
answers
229
views
Derivations for symmetric functions
A symmetric function is a formal power series in infinitely many variables $x_1,x_2,\dots$ invariant under the permutation of variables (as opposed to a polynomial). Let $\Lambda$ denote the algebra ...
6
votes
0
answers
321
views
Irreducibility of a palindromic polynomial
I have strong reasons to believe that the palindromic polynomial $p_n(x)$ defined by
$$p_n(x) = x^{2n}+2x^{2n-1}+3x^{2n-2}+ \cdots+ nx^{n+1}+(n+3)x^{n}+nx^{n-1}+\cdots+2x+1$$
is irreducible in $\...
6
votes
0
answers
282
views
Arrangement of subspaces over finite fields
I'm trying to find out what is already known about the following setup.
Let $V$ be an $n$-dimensional vector space over a finite field $F_q$ (I'm mostly interested in the case where $q$ is prime), and ...
6
votes
0
answers
166
views
Characteristic polynomials of Cartan matrices of Lie algebras
Let $L$ be a simple Lie algebra over $\mathbb{C}$ with Cartan matrix $C_L$ (as in https://de.wikipedia.org/wiki/Cartan-Matrix )
Question 1: Is is true that the characteristic polynomial $f$ of $C_L$ ...
6
votes
0
answers
316
views
An inequality related to the numbers of faces of polytopes with d+2 facets
I would like to prove an inequality related to the number of $k$-faces of two $d$-polytopes with $d+2$ facets; see (1) below.
Let $r>0$, $s>0$, $t\ge 0$, and $d\ge 2$ be such that $d=r+s+t$. We ...
6
votes
0
answers
299
views
Eigenvectors of a symmetric sum of tensor products
Let $A$ and $B$ be two (finite-dimensional) Hermitian matrices and $n$ be a positive integer. We define the matrix
$$
L_i = A\otimes \dots\otimes A\otimes B\otimes A\otimes \dots\otimes A~,
$$
where ...
6
votes
0
answers
126
views
Any comparison between the category of cubes and its opposite?
To model topological spaces combinatorially, one can use simplicial sets -- or cubical sets. Simplicial sets are defined as presheaves on the simplex category $\Delta$, the category of non-empty ...
6
votes
0
answers
88
views
Maximal number of commuting functions of a finite set
Let $S$ be a finite set with $n$ elements and let $F_S$ denote the set of functions from $S$ to $S$. I wonder whether anything is known about the maximal cardinality of a commuting subset of $F_S$? A ...
6
votes
0
answers
242
views
An extension of Erdos' distinct distances problem based on circles of various radii
Consider a collection $C_1,C_2, \dots, C_n$ of circles in the plane and suppose that the center of $C_i$ is $o_i$ and the radius of $C_i$ is $r_i$. We will define the relative distance between the ...
6
votes
0
answers
184
views
A class of symmetric functions
When attacking a symmetric problem via an asymmetric method, I encountered the following function: $$U_2(n, m) = \sum_{a = 0}^n\binom na (2^a + 2^{n - a})^m.$$
It is easy to see that this function is ...
6
votes
0
answers
212
views
Two conjectural congruences for Franel numbers
Recall that the Franel numbers are given by
$$f_n:=\sum_{k=0}^n \binom{n}{k}^3\ \ \ (n=0,1,\ldots).$$
Question. How to prove my following conjecture?
Conjecture. For each odd prime $p$, we have
$$\...
6
votes
0
answers
123
views
Squared squares and partitions of $K_{nn}$
This is inspired by a recent question.
Define a square square sum (SSS) of order $n$ to be any partition $$n^2=\sum_1^tc_ii^2 \tag{*}$$ of $n^2$ into square summands. Call it perfect if all $c_i \leq ...
6
votes
0
answers
99
views
Number of Dyck paths up to stable equivalence
Acyclic (connected) Nakayama algebras can be identified with Dyck paths via their top boundary Auslander-Reiten quivers.
Now two Nakayama algebras $A$ and $B$ should be stable equivalent in case ...
6
votes
0
answers
173
views
Generalized graph-minor theorem?
Consider the following generalized graph-minor theorem:
GM($κ,λ$): Given any collection $S$ of $κ$ simple undirected graphs each with less than $λ$ vertices, there are distinct graphs $G,H$ in $S$ ...
6
votes
0
answers
181
views
A question about dominating circuits in cubic graphs
Let $G$ be a 3-connected cubic graph with a dominating circuit $C$, that is, a circuit such that all edges in $G$ have at least one endvertex in $C$. Let $D$ be another circuit and let the symmetric ...
6
votes
0
answers
128
views
Q-analogue of an inequality
Pick integers $b\geq a \geq 0$ and $k\geq j\geq 0$.
It is not super-difficult to prove the inequality
$$
\binom{kb}{ka}^j \geq \binom{jb}{ja}^k.
$$
This is actually quite a nice inequality that was ...
6
votes
0
answers
190
views
A curious $q$-identity
Let $[x]_{q}=\frac{1-q^x}{1-q}$ and $\binom{x}{n}_{q}$ denote a $q$-binomial coefficient.
Let $A_n(x,q)$ be the $n\times n $ matrix with entries $$q^\binom{i-j}{2}\binom{i+j+x}{i-j+1}_{q},$$ $0 \le i,...
6
votes
0
answers
131
views
On a certain $(-1)$-Eulerian polynomials of type $B$
Let $(q)_n=(1-q)(1-q^2)\cdots(1-q^n)$ with $(q)_0:=1$. Define a $q$-exponential by
$$e_q(z)=\sum_{n\geq0}\frac{z^n}{(q)_n}.$$
There is a notion of $q$-Eulerian polynomials of type $A$, see the ...
6
votes
0
answers
475
views
Darkness in the lamplighter group
Consider paths through the lamplighter group $\mathbb{Z}_n\wr\mathbb{Z}$ with steps consisting of moving left, moving right, and toggling the lamp at the current position. How many paths of length $m$ ...
6
votes
1
answer
867
views
Does the likelihood of these tables exist?
Probably it does, and may be a number near $e^{-3/2}$ for 2-deficient tables. First some background.
Early on in my studies of universal algebra, I encountered a result of Vadim Murskii, with the ...
6
votes
0
answers
576
views
Is there a theory behind these puzzles? (communicating by modifying data)
Consider the following puzzles:
Problem 1: Alice is given two data by Zora: a binary string $w$ of length $2^r$, and a position $p$ in the string (which we can view as an integer $0\leq p<2^r$). ...
6
votes
0
answers
225
views
A challenging problem on disjoint cosets
Motivated by my negative solutions (see this paper published in Chinese Ann. Math. 13A(1992)) to two open problems on disjoint residue calsses posed by A. P. Huhn and L. Megyesi [Discrete Math. 41(...
6
votes
0
answers
123
views
Sets $X,Y$ of natural numbers such that any natural $n$ writes uniquely $n=x+y$ [duplicate]
There are many pairs $X, Y$ of infinite subsets of $\mathbb{N}:=\{0,1,2\dots\}$ such that any $n\in\mathbb{N}$ writes uniquely as $n=x+y$, with $x\in X$ and $y\in Y$. An example of such a pair is $(X,...
6
votes
0
answers
88
views
Numbers where there is a unique group with integral character table
Call a number $n$ special in case there is a unique group of order n whose character table consists of only integers. This should be equivalent to the condition that the number of conjugacy classes ...