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.

Filter by
Sorted by
Tagged with
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_{...
T. Amdeberhan's user avatar
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: “...
Gro-Tsen's user avatar
  • 29.9k
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$...
Roger Van Peski's user avatar
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 ...
Allen Knutson's user avatar
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 ...
Arun 's user avatar
  • 725
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\...
Sam Hopkins's user avatar
  • 22.7k
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$ ...
Andyqian7's user avatar
  • 165
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 ...
Student's user avatar
  • 5,008
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 $\...
Nate River's user avatar
  • 4,822
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 $...
Jeanne Scott's user avatar
  • 1,847
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 $...
Mare's user avatar
  • 25.8k
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 ...
Leon Bankston's user avatar
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$-...
Sam Hopkins's user avatar
  • 22.7k
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 ...
Marcel's user avatar
  • 2,510
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 ...
Per Alexandersson's user avatar
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 ...
M. Winter's user avatar
  • 12.5k
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$....
Brendan McKay's user avatar
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\...
Drew's user avatar
  • 1,469
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 ...
T. Amdeberhan's user avatar
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\...
Ethan Splaver's user avatar
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 ...
Jeanne Scott's user avatar
  • 1,847
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 ...
T. Amdeberhan's user avatar
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) &...
Alt-Tab's user avatar
  • 139
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 ...
domotorp's user avatar
  • 18.3k
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 ...
ArB's user avatar
  • 688
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 ...
azimut's user avatar
  • 253
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 ...
Zach H's user avatar
  • 1,899
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 $\...
Kashyap Rajeevsarathy's user avatar
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 ...
user38495's user avatar
  • 1,042
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$ ...
Mare's user avatar
  • 25.8k
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 ...
Guillermo Pineda-Villavicencio's user avatar
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 ...
Victor G's user avatar
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 ...
Dasha Poliakova's user avatar
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 ...
Anthony Quas's user avatar
  • 22.5k
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 ...
Gil Kalai's user avatar
  • 24.2k
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 ...
WhatsUp's user avatar
  • 3,232
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 $$\...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Aaron Meyerowitz's user avatar
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 ...
Mare's user avatar
  • 25.8k
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$ ...
user21820's user avatar
  • 2,734
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 ...
EGME's user avatar
  • 1,008
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 ...
Per Alexandersson's user avatar
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,...
Johann Cigler's user avatar
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 ...
T. Amdeberhan's user avatar
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$ ...
user76284's user avatar
  • 1,793
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 ...
Gerhard Paseman's user avatar
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$). ...
Gro-Tsen's user avatar
  • 29.9k
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(...
Zhi-Wei Sun's user avatar
  • 14.4k
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,...
Pietro Majer's user avatar
  • 56.5k
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 ...
Mare's user avatar
  • 25.8k

1
71 72
73
74 75
211