# Questions tagged [enumerative-combinatorics]

The enumerative-combinatorics tag has no usage guidance.

260
questions

**8**

votes

**1**answer

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. ...

**7**

votes

**1**answer

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 ...

**0**

votes

**0**answers

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 ...

**4**

votes

**1**answer

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 ...

**8**

votes

**0**answers

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 ...

**1**

vote

**0**answers

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 ...

**2**

votes

**1**answer

196 views

### Number of non-crossing sets of intervals

Consider the integers $[1,n]=\{1,\dots,n\}$ and call subsets of the type $[a,b]=\{a,\dots,b\}$ with $1\le a < b\le n$ intervals. We say that two intervals $[a,b],[c,d]$ are crossing if either $a<...

**2**

votes

**0**answers

19 views

### On the number of connected functional digraphs recoverable from the preimage set size structure

I am studying the list of inverse images (preimage sets) of some function $f$ at a given inverse depth $j$ -- for each element $x_i$ of a finite domain $X$.
For example,
$P_j=\left[f^{-j}(...

**5**

votes

**1**answer

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 ...

**3**

votes

**1**answer

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 ...

**5**

votes

**4**answers

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-...

**3**

votes

**0**answers

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$ ...

**5**

votes

**0**answers

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$ ...

**1**

vote

**0**answers

170 views

### Combinatorial bijection on monotone sequences

Let $(n),\mu$ be the partition of $n$ define $H_g^{m}((n);\mu)$ count's the number of tuples $(\tau_1,\ldots,\tau_r)$ of transposition in symmetric group $S_n$ with the following conditions
$$ (1,2,\...

**0**

votes

**1**answer

58 views

### Ordered $m$-tuples with fixed number of changes

Given $1\leq k\leq m$, $2\leq d\leq c i\ln i$ and $2\leq i\leq c'\ln(mi\ln i)$ at some $c,c'>0$ how many sequences (lower and upper bounds) are of form $$z_1,\dots,z_m$$ on the condition that
$$0\...

**2**

votes

**0**answers

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 ...

**1**

vote

**1**answer

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 ...

**7**

votes

**2**answers

300 views

### Counting nilpotent self-maps of $\{1,\dots,n\}$ with image of a given cardinal

Let $\mathcal{C}_n$ be the monoid of self-maps $\alpha$ of $\{1\dots,n\}$ that are order-preserving ($\forall x,y$, $x\le y$ $\Rightarrow$ $\alpha(x)\le\alpha(y)$ and decreasing ($\forall x$, $\alpha(...

**0**

votes

**1**answer

82 views

### Number of positive integer solutions with a lower bound

If $0\leq\gamma<\alpha<1$ and $t=\lceil n^\gamma\rceil$ hold then how many positive solutions to the linear diophantine equation
$$x_1+\dots+x_t=\lceil n^\alpha\rceil$$
have the property
$$n^\...

**4**

votes

**2**answers

175 views

### Number of nonequivalent weight functions on a set of $n$ elements

For a finite set $S$ of $n$ elements, say a weight function is a function $f \colon S \to \mathbb{R}$. For any subset $T \subseteq S$, define $f(T) = \sum _{x \in T} f(x)$. Define two weight functions ...

**1**

vote

**1**answer

87 views

### mapping integers to k-ary trees

Is there an algorithmic way to map the natural numbers to unique k-ary trees?
I am familiar with the work of Tychonievich who created a mapping from integers to binary trees. https://www.cs.virginia....

**3**

votes

**1**answer

393 views

### Sum of all products of k distinct integers in [1,n] [duplicate]

Let $S=\{1,2,3,...,n\}$ be the set of integers up to $n$ and $p_k(a_1,...,a_k)=a_1\cdots a_k$ the product of $k$ distinct integers $a_1,...,a_k \in S$. There are $\binom{n}{k}$ possibilities to ...

**2**

votes

**0**answers

84 views

### Number of permutations with precedence constraints : DP case [closed]

I have two sets of balls (blacks and whites), each set is numbered from $1$ to $n$, and all are put in a jar. My precedence constraint is expressed as following : to pick a black ball with index $i$, ...

**0**

votes

**0**answers

61 views

### Paths in graphs as a vector space or matroid

If I have a simple graph $G$, and what to count the number of simple paths between two distinct vertices, can the paths be seen as independent sets of a vector space, or even somehow, a matroid? I ...

**4**

votes

**1**answer

287 views

### Enumerating all permutations that are “square roots” of derangements

Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement?
Other information about those kind ...

**4**

votes

**1**answer

92 views

### What is the probability of an empty convex $k$-gon among many given points?

Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points.
For a big number $n$ of randomly distributed ...

**0**

votes

**0**answers

21 views

### Iterated Inverse structures: polynomial representation of integer partitioning of preimages in Sigma Matrices (reference request)

I am studying iterated preimage structures of functions on a finite set.
The main structure of interest to me, the Sigma Matrix, is derived from a matrix listing the element-wise preimage sets at ...

**2**

votes

**2**answers

125 views

### enumerate line partitions of points in the plane

Let $S$ be a nonempty subset of $\mathbb{R}^2$ and $l$ a line in $\mathbb{R}^2$ disjoint from $S$. Then $l$ partitions $S$ into two disjoint sets $S = S_1 \cup S_2$ in the obvious way. Note that, at ...

**12**

votes

**1**answer

461 views

### Dividing a chocolate bar into any proportions

Suppose I have a chocolate bar of integer length $L$, and there are $m\leq L$ people that are going to share it. We do not know ahead of time how much each person should receive, all we know is that ...

**1**

vote

**1**answer

52 views

### Rank and edges in a combinatorial graph?

Fix a $d\in\mathbb N$ and consider the matrix $M\in\{0,1\}^{2^d\times d}$ of all $0/1$ vectors of length $d$. Consider the matrix $G\in\{0,1\}^{n\times n}$ whose $ij$ the entry is $0$ if inner product ...

**1**

vote

**2**answers

395 views

### Constant row-column sum matrices?

Given an integer $T$ how many $n\times n$ matrices in $\mathbb Z_{\geq0}^{n\times n}$ we have such that every row and column sum to same $T$?
Do the set of constant row and column sum matrices form ...

**2**

votes

**0**answers

56 views

### Annihilator of the of the generating function not holonomic

The following is a generating function in $x,h$ with infinite parameters
$q_1,q_2\ldots,$ and $w_1, w_2,\ldots$.
$$\Psi(x, h)= \sum_{d=0}^{\infty} s_{(d)} (q_1, q_2, \ldots) \exp \bigg( \sum_{r=1}^{\...

**1**

vote

**2**answers

211 views

### Fair partitioning of a set - Weighted sums of Bernoullis

For $n$ an integer, let $a_n$ be the number of ways in which one may partition the set $\{1, \ldots, 2n \}$ in two parts with:
the same number of elements: $n$
and the same sum: $2n(2n+1)/4$.
...

**2**

votes

**1**answer

180 views

### Filling $1..mn$ into a $m×n$ rectangle such that every number $<mn$ is dominated

This is a problem from my professor, who claimed that it's open:
Combinatorial problem.
Fill $1,2,...,mn$ into a rectangle of size $m\times n$, such that for every number other than $mn$, ...

**3**

votes

**0**answers

59 views

### Using Kac-Rice formula to count average number of sub-regions carved out by $n$ random hyper-planes

Context. This is the first in a set of tiny pieces of a problem I've formulated to help me measure the "complexity" of certain piecewise linear functions. Thanks in advance for your help and patience.
...

**7**

votes

**2**answers

190 views

### Estimating the number of functions which are at most $c$-to-$1$ for some constant $c \ge 2$

Notation: $[m] := \{1, 2, \dots, m \}$.
How many functions are there $f: [a] \to [b]$? The answer is easily seen to be $b^a$.
How many $1$-to-$1$ functions are there $f: [a] \to [b]$? Again the ...

**0**

votes

**0**answers

74 views

### Generating uniformly distributed trees

I'm looking for closed (possibly approximate) formulae for the following problem.
I am trying to generate (uniformly distributed) random trees of a given size n. The "size" is the number of symbols ...

**1**

vote

**1**answer

79 views

### Circular (bracelets) permutations with alike things(reflections are equivalent) using polya enumeration

Circular permutations of N objects of n1 are identical of one type, n2 are identical of another type and so on, such that n1+n2+n3+..... = N?
A similar question exists but it doesn't address the case ...

**5**

votes

**1**answer

174 views

### Intuition for the expected number of returns of a Dyck path

It is known that the expected number of returns of a Dyck path of semilength $n$ to the $x$-axis is $3n/(n+2)$, so it tends to 3 as $n\to\infty$. (This was proved in the Dyck path context by Deutsch ...

**13**

votes

**1**answer

463 views

### Coincidences between average Catalan tableaux

There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices:
$$
P_n \, := \, \frac{1}{C_n} \, \...

**4**

votes

**0**answers

258 views

### What arithmetic would you do in parallel?

This is a post asking for references, and soliciting problems and people interested in accelerated computing. I will add the big-list tag and make it community-wiki. If this interests you strongly, ...

**0**

votes

**1**answer

71 views

### Primage structures: induced domain partitioning by itterated inverse (reference request)

I am studying the list of inverse images (preimage sets) of some function $f$ at a given inverse depth $j$ -- for each element $x_i$ of a finite domain $X$.
For example, the j-th such preimage list ...

**5**

votes

**2**answers

207 views

### Eigenvalues of the Laplacian of the directed De Bruijn graph

We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ ...

**4**

votes

**0**answers

110 views

### Count necklaces with fixed substring

I consider k-ary strings of the form $a_1 \cdots a_n$ where $a_i \in \{0,\ldots,k-1\}$ for $1\le i \le n$. A necklace is the lexicographically smallest representative of an equivalence class where two ...

**1**

vote

**0**answers

23 views

### Extension of definition of Holonomic closure

My question is about finding the annihilator of a series. Let me begin with what is known and then ask my question. Let $s_d(\frac{q_1}{h},\ldots )$ denote schur function for partition $\lambda =[d]$ ...

**6**

votes

**1**answer

155 views

### Sufficient conditions for the coefficients of a generating function to dominate those of its square

Let $f(z)$ be a generating function (so in particular, its power series coefficients are nonnegative). I am interested in conditions which would ensure that for every $n$, the coefficient of $z^n$ in $...

**5**

votes

**0**answers

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 ...

**3**

votes

**1**answer

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) ...

**5**

votes

**0**answers

446 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$ ...

**-2**

votes

**1**answer

100 views

### 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 ...