Skip to main content

Questions tagged [enumerative-combinatorics]

166 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
18 votes
0 answers
987 views

"Special" meanders

One of the open problems in combinatorics is enumeration of meanders. Here on MO I only could find them under the heading not-especially-famous-long-open-problems-which-anyone-can-understand. Since my ...
მამუკა ჯიბლაძე's user avatar
14 votes
0 answers
270 views

A symmetry of lattice paths

The number of $n$-step NSEW lattice paths from $(0,0)$ to $(a,b)$ that intersect the line $y=k$ precisely $t$ times is independent of $k$, for $0\leq k\leq b$, where we assume $b\geq0$ for simplicity. ...
Robin Houston's user avatar
13 votes
0 answers
323 views

Reference request: exponential growth rates of subword-closed languages are integers

For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters (...
Vince Vatter's user avatar
  • 2,339
12 votes
0 answers
629 views

$q$-analogue of the multinomial theorem?

The $q$-binomial theorem states that $$ \prod_{k=0}^{n-1}(1+q^kt) = \sum_{k=0}^n q^{\binom k2}{n\brack k}_q t^k. $$ This identity is a $q$-analogue of the binomial theorem $$ (1+t)^n = \sum_{k=0}^n \...
Amritanshu Prasad's user avatar
12 votes
0 answers
330 views

The number of labeled pairs of edge disjoint trees and related questions

I wonder what is known on the following: 1) What is the number $T_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ with $n$ labelled vertices? 2) (harder, it seems) What ...
Gil Kalai's user avatar
  • 24.7k
12 votes
0 answers
642 views

Wilf's conjecture: complementary Bell numbers

The complementary Bell numbers or Uppuluri–Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by $$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$ Definition. Fix an integer $m\geq0$....
T. Amdeberhan's user avatar
12 votes
0 answers
270 views

Number of updown sequences of $1,1,2,2,\cdots,n,n$

I would like to count the updown sequences of the set $\{1,1,2,2, \cdots, n,n \}.$ Sequence $a_1, a_2, a_3, \ldots$ is an updown sequence if the sequence satisfies the following: $ a_1 \lt a_2 \gt a_3 ...
hkju's user avatar
  • 121
10 votes
0 answers
429 views

321-avoiding and parity-alternating permutations

It is classical that 321-avoiding permutations are enumerated by the Catalan numbers. A permutation is parity-alternating if it sends even integers to even integers, and odd integers to odd. I am ...
Per Alexandersson's user avatar
10 votes
0 answers
141 views

Smallest counterexample to Stein's conjecture?

An equi-$n$-square is an $n$ by $n$ array of cells filled with the symbols $1,2,\dots,n$ so that each symbol occurs exactly $n$ times. (Every Latin square of order $n$ is an equi-$n$-square, but the ...
András Salamon's user avatar
10 votes
0 answers
2k views

Number of rectangles in an n-by-n grid of points

I am seeking a formula for the number of rectangles with vertices belonging to an $n \times n$ square grid of points. This is sequence A085582 in the OEIS. Note that the grid in question has $n^2$ ...
Dave R's user avatar
  • 856
10 votes
0 answers
191 views

What is known about the number of permissible simplicial complexes given the number of k-cells?

Motivation: I am working on a problem that reduces to finding simplicial complexes given some data (details are unnecessary), but all I have managed to wrangle from my input is the number of cells of ...
Ketil Tveiten's user avatar
9 votes
0 answers
144 views

How many simplicial spheres with $n$ vertices and $N$ facets?

Let $s_d(n,N)$ be the number of different $d$-dimensional simplicial spheres on $n$ labelled vertices and $N$ facets (= $d$-simplices). I am in search for the best know upper bounds, especially for $d\...
M. Winter's user avatar
  • 13.6k
9 votes
0 answers
355 views

The $n$ queens problem with no three on a line

The $n$ queens problem asks if we can place $n$ queens on an $n\times n$ chessboard such that no two queens attack one another. For example, when $n=8$, here are two solutions (images taken from ...
ho boon suan's user avatar
9 votes
0 answers
161 views

Number of tautologies of a given size?

Fix some complete set of $L$ logical connectives such as $\{ \wedge, \neg \}, \{\Rightarrow, \neg \}, \{\ \vee, \wedge, \neg \}, \{ \uparrow\}, \{\wedge, \vee, \neg, \Rightarrow \}$ - I'll assume all ...
Sprotte's user avatar
  • 1,075
9 votes
0 answers
409 views

Number of sets $S$ for which number of permutations in $S_n$ with descent set $S$ is odd

The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ is defined by $D(w)=\{ 1\leq i\leq n-1\,:\, a_i>a_{i+1}\}$. Given a set $S$, let $\beta_n(S)$ denote the number of ...
Richard Stanley's user avatar
9 votes
0 answers
327 views

Why does Loday call the permutohedra "zylchgons"?

Today I was reading Jean-Louis Loday's classic paper, "Realization of the Stasheff polytope", in which he produces a simple and very pretty realization of the associahedra as convex polytopes. He ...
Nathaniel Bottman's user avatar
9 votes
0 answers
275 views

pattern-avoiding permutations vs multi-core partitions

Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Given the pattern $\sigma=k(k-1)\cdots321$, let $I_n(\sigma)$ be the number of involutions in $\mathfrak{S}_n$ that avoid the pattern $\sigma$. ...
T. Amdeberhan's user avatar
9 votes
0 answers
188 views

Cycles of length $2^n - 2$ in the De Bruijn graph

It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$. ...
Timothy Chow's user avatar
  • 82.6k
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 ...
Igor Pak's user avatar
  • 17k
8 votes
0 answers
155 views

Partial order on graphs induced by homomorphism counts

For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\...
David Roberson's user avatar
8 votes
0 answers
419 views

Are most semigroups nilpotent of degree 3?

A semigroup is nilpotent of degree 3 if every product of 3 elements gives the same result. In 2012, Andreas Distler and James D. Mitchell wrote that: It is part of the folklore of semigroup theory ...
John Baez's user avatar
  • 22.2k
7 votes
0 answers
220 views

Why are these two determinants equal?

This question is a follow up on Mark Wildon's comment from an earlier MO question. As usual, let $(q)_k=(1-q)(1-q^2)\cdots(1-q^k)$ with $(q)_0:=1$. Also, define the Gaussian polynomials by $$\binom{n}...
T. Amdeberhan's user avatar
7 votes
0 answers
98 views

Pattern avoidance and P-recursiveness

A sequence $\{a_n\}_{n \geq 0}$ is said to be P-recursive if there exist polynomials $p_0(n), p_1(n), \dots , p_k(n)$ such that $$ \sum_{i=0}^k p_i(n) a_{n+i}=0 $$ for all $n \in \mathbb N$. Let $ P$ ...
Pluviophile's user avatar
  • 1,608
7 votes
0 answers
152 views

Inequality of product of discrete cosines

Let $k,a,b,c$ be odd positive integers. Consider the following inequality: $$ \sum_{x,y \in [k]} \cos^a\bigg(\frac{2\pi}{k}\cdot x\bigg) \cdot \cos^b\bigg(\frac{2\pi}{k}\cdot y\bigg) \cdot \cos^c\bigg(...
Tamir Dror's user avatar
7 votes
0 answers
193 views

Factoring a function from a finite set to itself

Let $S$ be a finite set and $f: S \to S$ be a function. Let $k = |f(S)|$ and let $\alpha$ be the partition of $S$ into $f$-fibers, i.e. $\alpha = \{ \alpha_t \}_{t \in f(S)}$ where $\alpha_t = f^{-1}(\...
Sophie M's user avatar
  • 695
7 votes
0 answers
183 views

Explaining $\left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(a^i-1\right)$ by a free $S_n$-action

Here is an olympiad-level problem on elementary number theory: Let $a$ be an integer and $n$ a positive integer. Prove that \begin{align} \left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(...
darij grinberg's user avatar
7 votes
0 answers
692 views

How many solutions $\pm1\pm2\pm3...\pm n=0$

As the title said, I'm very interested how many variants to choose $n$ signs from all $2^n$ variants when expression lead to zero. I tried to get recurrent formula but nothing happened.
Sergey Zaitsev's user avatar
7 votes
0 answers
124 views

in search of intepretations and connections for $k$-central binomials

Fix a positive integer $k$. Then, the sequences $$c(n,k)=\frac{k^n}{n!}\prod_{m=1}^{n-1}(1+km)=[x^n]\left(\frac1{1-k^2x}\right)^{1/k}$$ are referred to as "$k$-central binomial coefficients",...
T. Amdeberhan's user avatar
7 votes
0 answers
355 views

How does the number of self-avoiding paths between two points scale, in a square/cubic lattice?

Consider two different infinite graphs, whose vertices are drawn from $\mathbb Z^2$ or $\mathbb Z^3$. Let $P_d : \mathbb Z^d \times \mathbb N \to \mathbb N$ for $d \in \{2,3\}$ be the function such ...
Niel de Beaudrap's user avatar
6 votes
0 answers
175 views

Combinatorial classes where not almost all objects are asymmetric

Let $\mathcal{C} = \bigcup_{n=0}^{\infty}\mathcal{C}_n$ be a class of finite (labeled) combinatorial objects, where $\mathcal{C}_n$ is the set of objects on $[n] = \{1,2,\dotsc,n\}$. For example, $\...
Sam Hopkins's user avatar
  • 24.2k
6 votes
0 answers
365 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
276 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
  • 24.2k
6 votes
0 answers
479 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
  • 2,203
6 votes
1 answer
940 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
174 views

How to represent the even signed permutations by Young tableaux?

The well-known RSK correspondence established the connection between table pair (P,Q) and the permutations in symmetry group Sn(Coxeter group of type A). Also, there is a similar correspondence for ...
tony su's user avatar
  • 61
6 votes
0 answers
342 views

What is known about the $q$-analogue of the simplex?

I am interested in the field with one element. I am thus interested in combinatorial interpretations of the Gaussian binomial coefficients. Richard Stanley's "Enumerative combinatorics" mentions ...
Andrius Kulikauskas's user avatar
6 votes
0 answers
207 views

When can we determine an $f$-vector or rank-generating function from its unordered list of coefficients?

Let $f_i$ be the number of $i$-dimensional faces in a $d$-dimensional simplicial complex $\Delta $. Recall that the $f$-vector of $\Delta $ is the vector $(f_{-1},f_0,f_1,\dots ,f_d)$ where $f_{-1}=...
Patricia Hersh's user avatar
6 votes
0 answers
256 views

Counting Selections of Entries such having an Extremal Permutation of length n^2+1

Let $S_{n^2+1}$ be permutations of length $n^2+1$. By Erdos-Szekeres Theorem. any $s \in S_{n^2+1}$ would have a monotone subsequence(increasing or decreasing)of length $n+1$. Say a permutation $s$ of ...
WangYao's user avatar
  • 393
5 votes
0 answers
191 views

Do most semigroups have a zero?

It is widely believed in finite semigroup theory that asymptotically almost all finite semigroups $S$, up to isomorphism, are 3-nilpotent, i.e., they satisfy $\#\{abc\,:\,a,b,c\in S\} = 1$. My ...
user513093's user avatar
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 ...
Sayan Dutta's user avatar
5 votes
0 answers
131 views

Identity for classes of plane partitions

There are several classes of plane partitions in the literature. Among these, let's look at the enumeration of three of them: the symmetric (SPP), totally symmetric (TSPP) and totally symmetric and ...
T. Amdeberhan's user avatar
5 votes
0 answers
175 views

A close cousin of involutions?

If $\mathfrak{S}_n$ denotes the permutation group on $n$ letters, then $Inv(n)=\{\pi: \pi^2=1\}\subset\mathfrak{S}_n$ is the set of involutions or self-inverse permutations. The latter is enumerated ...
T. Amdeberhan's user avatar
5 votes
0 answers
249 views

Counting perfect matchings with integrals

Has anyone used the Joni-Rota-Godsil integral formula (see details below) to count perfect matchings of square-grid graphs, Aztec diamond graphs, hexagon-honeycomb graphs, etc.? (Or even just to ...
James Propp's user avatar
  • 19.7k
4 votes
0 answers
104 views

A question about decomposing root system $A_{n}$

Denote $\Phi(n)$ as the root system of Lie algebra $\mathfrak{g}$ of type $A_{n}$. Call a disjoint union $\Phi(n) = \Phi_{1}\sqcup\dotsb\sqcup\Phi_{s}$ a decomposition of $\Phi$ if each $\Phi_{k}$ is ...
Yuanjiu Lyu's user avatar
4 votes
0 answers
124 views

LIS-based permutation property

Let $S_n$ be the set of all permutations of $\{1, \ldots, n\}$, thereafter treated as integer sequences. Let $A_n$ be the set of all such permutations $\sigma \in S_n$ that we can choose two ...
Mikhail Tikhomirov's user avatar
4 votes
0 answers
211 views

Sum $f(n_1,n_2,\ldots,n_k) 1^{n_1} 2^{n_2} \ldots k^{n_k}$ over partitions

Use the notation $(n_1,n_2,\ldots,n_k) \vdash n$ to denote that $(n_1,n_2,\ldots,n_k)$ is a partition of the positive integer $n$, that is, $n_1+n_2+\ldots+n_k = n$ and $n_1 \ge n_2 \ge \ldots \ge n_k ...
Dreamer's user avatar
  • 261
4 votes
0 answers
97 views

"Convolving" a general Catalan with classical Catalan

Consider what is sometimes known as generalized Catalan sequence $$\mathcal{{\color{red}C}}_{a,b}:=\frac{2b+1}{a+b+1}\binom{2a}{a+b}.$$ Observe that $\mathcal{{\color{red}C}}_{n,0}$ reduces to the ...
T. Amdeberhan's user avatar
4 votes
0 answers
181 views

Fuss-Catalan: how does equality of these determinants hold?

There are many ways that the Catalan numbers seemed to have been generalized, one among them is through what Graham-Knuth-Patashnik (in Concrete Mathematics) dubbed as the Fuss-Catalan numbers $\frac1{...
T. Amdeberhan's user avatar
4 votes
0 answers
287 views

How can we prove this combinatorial identity?

This is a follow up on my earlier MO post. Let's recall the sets $$\mathbf{K}_n=\{\mathbf{k}\in\mathbb{Z}^n: k_i\geq0, k_1+\cdots+ k_n=n, k_1+\cdots k_i\leq i, \text{for all $1\leq i\leq n$}\}$$ and $\...
T. Amdeberhan's user avatar
4 votes
0 answers
135 views

Permutations avoiding a family of consecutive patterns

Let $B=\{1324,14325,154326,1654327,\ldots\}$ be the set of permutation patterns of the form $1(m-1)(m-2)\cdots 2m$ for $m\geq 4$. I'm interested in the set $\mathcal P$ of permutations that avoid all ...
Colin Defant's user avatar