# Questions tagged [enumerative-combinatorics]

The tag has no usage guidance.

260 questions
Filter by
Sorted by
Tagged with
86 views

### Sizes of connected components from a random choice in a grid

This is inspired by the illustration in this recently updated question. So we take a (fairly big) $n$ and an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares. ...
171 views

### Induction step in Bóna and Ehrenborg's proof that the generating function of the alternating runs has -1 as a root of a certain multiplicity

This is a crosspost of a question I asked on Mathematics SE four months ago. Periodically bumping it and placing a bounty on it to attract more attention were to no avail. There are some comments ...
25 views

### Enumerating all directed 3-cycle covers

It is fairly easy to enumerate the directed Hamilton cycles of a complete directed graph by fixing one of the vertices and enumerating the permutations of the others via one of the next-permutation ...
120 views

### Enumerating antichains modulo permutation

I encountered the following combinatorics problem in my research, and I'd like to know if there is a reference or an easy solution for such a problem. Given a partially ordered set $\mathscr P$, an ...
184 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 ...
20 views

### Standard terminology for these “coarsening” and “refining” operations for compositions and ordered set partitions?

Let $[M]:=\{1,2,\dots, M\}$. (Part of the twelvefold way) as we all know, there is a bijection between surjective functions $[N] \to [B]$ and ordered set partitions of $[N]$ into $[B]$ blocks (of ...
196 views

300 views

### Refined reverse plane partition generating function

I have a simple question about the generating function for reverse plane partitions: $$\sum_{\pi \in RPP(\lambda)} z^{|\pi|}= \prod_{s \in \lambda} \frac{1}{1-z^{h_{\lambda}(s)}}$$ There's a ...
118 views

### Reference for Dedekind's problem

Dedekind's problem is about enumerating antichains in the Boolean lattice. Is there an explicit reference where Dedekind stated this problem? Is there a good motivation to study this problem except ...
395 views

### Request for an exact formula related to a partition in number theory

The Frobenius equation is the Diophantine equation $$a_1 x_1+\dots+a_n x_n=b,$$ where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$ must consist of non-...
67 views

### On the proportion of simplicial $d$-polytopes on $n$-vertices

I have a question regarding estimates for the proportion of simplicial $d$-polytopes on $n$-vertices. Let $c_s(n,d)$ denote the number of combinatorial types of simplicial $d$-polytopes on $n$ ...
142 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$ ...
170 views

47 views

### Seeking bijective proof of a recurrence for generalized Narayana numbers

Consider lattice paths in $d$ dimensions with the steps $X_1\mathrel{:=}(1,0,\dotsc,0)$, $X_2\mathrel{:=} (0,1,\dotsc,0)$,…, $X_d\mathrel{:=} (0,0,\dotsc,1)$. Let $\mathcal C(d, n)$ denote the set of ...
90 views

### Calculating the values of a generalization of binomials to permutations

let $$\Pi\binom{n}{k}:=\mathrm{card}\left( \left\lbrace \lbrace \Pi_1^n\,\cdots\,\Pi_k^n\rbrace\,|\,0\leq \pi_{r,c}\in\sum_{i=1}^k\Pi_i^n\ni\pi_{r,c}\leq 1\right\rbrace\right)$$ be the number of sets ...
300 views

115 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 ...
280 views

### Graph isomorphism by invariants

Graph isomorphism is known to be a difficult computational problem. The problem get even worst if we want to find non-isomorphic graphs in a large family of graphs. Let us call a (numerical) ...
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$ ...
### Sum of: k permutations of n $\times e^x$
Simplify the following: \begin{equation} \sum\limits_{\ell =1}^n P(n,\ell) (e^x -1)^\ell \end{equation} to something like $n!n^n$. I got curious about this expression after going through this ...