# Questions tagged [enumerative-combinatorics]

The enumerative-combinatorics tag has no usage guidance.

478
questions

4
votes

2
answers

231
views

### Applying $\sum_i \partial_{x_i}$, $\sum_i x_i \partial_{x_i}$ and $\sum_i x_i^2 \partial_{x_i}$ to Schur polynomials

The operators $L_k=\sum_i x_i^k\frac{\partial}{\partial x_i}$, with integer $k$, take symmetric polynomials into symmetric polynomials.
Is it known how to write the result of the application of $L_0$, ...

0
votes

0
answers

55
views

### How many rigid 4-regular graphs are there?

I am interested in any formulas for the number of globally rigid 4-regular graphs, or Laman graphs of degree at most 4, on $n$ vertices. The bound can be for graphs with labeled or unlabeled vertices.

6
votes

0
answers

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

2
votes

0
answers

55
views

### Combining (generalized) Polya enumeration with invariant properties

Let's say we want to enumerate maps $f$ between two finite sets $X$ and $Y$ modulo the action of groups $G$ on $X$ and $H$ on $Y$. Additionally we want $f$ to satisfy a certain property $P$ that is ...

5
votes

0
answers

140
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, $\...

1
vote

0
answers

62
views

### Ordered combinatorial classes and partitions

Let $\mathcal{C}$ be a combinatorial class and let $\leq$ be a partial order on $\mathcal{C}$. We say that $(\mathcal{C},\leq)$ is an ordered combinatorial class if for all $x,y\in\mathcal{C}$, $$x&...

1
vote

2
answers

229
views

### Estimation of a combinatoric formula

Assume $n\ge m$, what is the estimation of
$$\sum_{k_1+\dots +k_m\,=\,n,\\ k_1\ge 1,\,\dots,\,k_m\ge 1} C_n^{k_1,\dots,k_m} \left(\frac{1}{k_1}+\frac{1}{k_2}+\dots +\frac{1}{k_m} \right)$$
where $C_n^{...

3
votes

0
answers

158
views

### Factorization of symmetric polynomials

Let $\Lambda_n$ be the algebra of all symmetric polynomials in $n$ variables, which we also consider as an infinite-dimensional vector $\mathbb{Q}$-space, whose basis is the Schur polynomials.
The ...

2
votes

0
answers

186
views

### Distribution of peaks in Dyck paths

A Dyck word is a sequence of open and closed brackets such that the brackets come in correctly matched pairs. For example $(()(()))()$ is a Dyck word, while $())(()$ is not. A Dyck path is a visual ...

9
votes

0
answers

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

0
votes

0
answers

61
views

### Interpretate a condition on Signed graph

In my research I came up with a condition on signed complete graph as follows:
Consider adjacency matrix of signed complete graph, i.e. symmetric, diagonal-free matrix with elements $A_{ij}=-1$ or $+1$...

2
votes

1
answer

294
views

### Can you confirm the positivity of a quantity involving the Stirling numbers of the first kind

Let $s(m,n)$ denote the Stirling numbers of the first kind. For $m,n\in\mathbb{N}$, define
\begin{equation}
\mathcal{Q}(m,n)=(-1)^n\sum_{\ell=0}^{2n} \binom{m+\ell-1}{m-1} s(m+2n-1,m+\ell-1)\biggl(\...

7
votes

1
answer

473
views

### Combinatorial consequences of de Branges's Theorem?

I'm usually not a proponent of the mentality “here is a tool, what results can we prove with it?” (as I prefer to start at the other end with a well-motivated problem), but this famously entertaining ...

3
votes

3
answers

710
views

### Ordinary partitions vs partitions into odd parts

Let $\mathcal{P}(n)$ be the set of all unrestricted partitions of $n$ while $\mathcal{O}(n)$ stand for the set of all partitions of $n$ into odd parts. We adopt the power notation for partitions $\...

5
votes

2
answers

263
views

### Enumerating all inequivalent planar embeddings of a planar graph

Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ ...

3
votes

0
answers

207
views

### Number of partitions of set restricted by sum of square of part size

Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\...

14
votes

2
answers

870
views

### Sequences that don't count algebraic structures on finite sets

People count $n$-element groups, $n$-element monoids, $n$-element commutative monoids, etcetera - always up to isomorphism. The algebraic structures I've listed, and many more, are studied ...

3
votes

0
answers

113
views

### Divide Euclidean space by surfaces

It is well known that $n$ hyperplanes in $\mathbb{R}^k$ can divide $\mathbb{R}^k$ into at most $p$ regions where $p$ is
\begin{equation}
1 + n + C^2_n + \cdots + C^k_n
\end{equation}
Is there similar ...

0
votes

0
answers

163
views

### Sum of square of parts, and sum of binomials over integer partition

Let $n$ be positive integer. Consider its integer partitions denoting as $(m_1,\cdots,m_k)$, where $m_1+\cdots+m_k=n$ and the order does not matter. We ignore the case of $(m_1,\cdots,m_k)=n$.
I am ...

6
votes

2
answers

275
views

### The number of boolean function with given Fourier degree

How many boolean functions $\{-1,1\}^n \to \{-1,1\}$ with Fourier degree at most $d$?
By Fourier degree I mean the maximal cardinality of $S$ such that the Fourier coefficient $\hat{f}(S)$ is not ...

1
vote

0
answers

97
views

### The number of boolean functions with given decision tree complexity

How many boolean function with $n$ variables with decision tree complexity $k$?
By decision tree complexity of a function $f$ I mean the smallest depth among all deterministic decision trees that ...

3
votes

1
answer

260
views

### Enumerating possible number of satisfied linear equations

Consider a system of linear equations of variable $x=(x_1,\cdots,x_n)$ where each $x_i\in\{ 0,1,\cdots,L-1 \}$. Clearly, there are $\frac{n(n-1)}{2}$ number of equations in the system.
$$x_i-x_j=0, \ \...

0
votes

1
answer

342
views

### A combinatorial proof: where art thou?

Start by introducing the finite sums
$$A_n:=\sum_{m=1}^nq^m\prod_{j=1}^{m-1}(1-q^j) \qquad \text{and} \qquad
B_n:=\sum_{m=1}^nq^m\prod_{j=m+1}^n(1-q^j).$$
An algebraic proof is facile: Clearly, $A_1=...

4
votes

0
answers

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

14
votes

3
answers

1k
views

### On the finite sum of reciprocal Fibonacci sequences

I want to check if $$\left\lfloor \left( \sum_{k=n}^{2n}{\frac{1}{F_{2k}}} \right)^{-1} \right\rfloor =F_{2n-1}~~(n\ge 3) \tag{$*$}$$ where $\lfloor x \rfloor$ is th floor function.
The Fibonacci ...

4
votes

2
answers

294
views

### Number of partitions of $n$ and number of different integers in 1-avoiding partitions

Consider the number of integer partitions of $n$, usually denoted by $p(n)$ and generated by
$$\sum_{n\geq0}p(n)x^n=\prod_{k\geq1}\frac1{1-x^k}.$$
I have encountered an interesting enumeration.
Take ...

6
votes

0
answers

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

4
votes

1
answer

180
views

### On a double sum involving binomial coefficients

For natural $n$, let
\begin{equation}
p_n:=2^{1-n}\sum_{v=1}^l \binom l{(v+l)/2}1(v\equiv l)
\sum_{u=1-v}^{v-1}\binom k{(u+k)/2}1(u\equiv k), \tag{1}\label{1}
\end{equation}
where $k:=\lfloor(n+1)/...

1
vote

1
answer

252
views

### Counting $n$-edge directed graphs

I would like to count the $n$-edge directed graphs. The graphs might contain self-loops (edges connecting a vertex to itself) and multiple edges (multiple edges connecting the same pair of vertices). ...

2
votes

0
answers

74
views

### Skewed plane partition with only row fillings reversed

The number of plane partitions in a bounded box is well-studied and dates back to MacMahon, at the start of this paper by Sam Hopkins and Tri Lai, p9, they summarized current results on the ...

4
votes

0
answers

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

1
vote

0
answers

72
views

### Distribution of colour pairs from a random matching

Given $a$ many red balls and $b$ many blue balls, with $a+b$ even, suppose we chose a random matching between the $a+b$ balls. What is the distribution of the number of red-red and red-blue (and blue-...

3
votes

0
answers

88
views

### Number of planar bipartite graphs

How many planar bipartite graphs are there with $m$ vertices of one color and $n$ vertices of the other color?
How many non-isomorphic classes exist?

6
votes

1
answer

236
views

### Intuitive explanations of the Carlitz-Scoville-Vaughan theorem

Crossposted from MSE:
I recently came across Ira Gessel's slides on a theorem he says should "be considered one of the fundamental theorems of enumerative combinatorics."
The Carlitz-...

2
votes

0
answers

158
views

### Lattice paths avoiding holes

Consider lattice paths from $(0,0)$ to $(2n,2n)$ with steps $N=(0,1)$ and $E=(1,0)$ avoiding the points $(2i-1,2i-1)$ for all $1\leq i\leq n$. There are Catalan many $C_{2n}=\frac1{2n+1}\binom{4n}{2n}$...

8
votes

1
answer

286
views

### What is the Möbius function for the lattice of partial partitions?

Let $n$ be a positive integer. Let $P$ be the set of partitions of subsets of
$\{ 1, 2, \dotsc, n \}$ (so, for example, when $n=2$, the set $P$ contains $\emptyset$, $\{ \{1 \} \}$, $\{ \{2 \} \}$, $\{...

3
votes

1
answer

212
views

### Seeking for a combinatorial argument for partition identities

Given an integer partition $\lambda$, introduce the following quantities:
\begin{align*}
c(\lambda)&=\sum_{i\geq1}\left\lceil\frac{\lambda_i}2\right\rceil, \qquad c_o(\lambda)=\sum_{i\geq1}\left\...

4
votes

0
answers

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

2
votes

1
answer

201
views

### Catalan and path pairs in polynomials

Define $\mathbf{K}_n$ to be the set of all $(2n+1)$-tuple sequences $\mathbf{a}=(a_0,a_1,\dots,a_{2n})\in\{-1,1\}^{n+1}$ satisfying: (a) there are $n$ occurrences of $-1$ and $n+1$ of $+1$; (b) all ...

1
vote

0
answers

91
views

### Super Catalan (super ballot) numbers

We refer to this article by Ira Gessel. In section 6, page 10, equation (28), the Super Catalan numbers are defined as
$$S(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}.$$
On page 12, equation (31), there goes ...

3
votes

1
answer

382
views

### A combinatorial identity involving binomial coefficients

When I was reading an article by CHUN-GANG JI (A SIMPLE PROOF OF A CURIOUS CONGRUENCE BY ZHAO), he mentioned in the acknowledgement
the following identity
$$\sum_{i+j+k=p,\text{ } i,j,k\gt 0}{p\choose ...

6
votes

2
answers

424
views

### Plane partitions as sums of determinants

Consider the Vandermonde's determinant computed by
$$V(x_1,\dots,x_m):=\det(x_j^{i-1})_{i,j=1}^m=\prod_{1\leq i<j\leq m}(x_i-x_j).$$
The number of plane partitions in an $n\times m\times m$ box (...

2
votes

1
answer

226
views

### Proof of a binomial identity

Computations with Maple suggest the following binomial identity
\begin{equation*}
\forall{p,j}: \sum_{k=j+1}^{p+1} (-1)^j \dfrac{1}{k}\binom{k-1}{j} =
\sum_{k=j+1}^{p+1} (-1)^{k-1} \dfrac{1}{...

1
vote

1
answer

90
views

### Existence of some lattice path connecting all given lattice paths

My daily work concerns analysis on metric spaces and some time ago it turned out that the problem I am dealing with boils down to a certain combinatorial problem. I've checked a lot of examples and it ...

4
votes

0
answers

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

5
votes

1
answer

389
views

### Catalan sequences vs composition sequences

In the paper, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Pitman and Stanley studied the $n$-dimensional polytope
$$\Pi_n(\mathbf x)=\{y\in\...

0
votes

2
answers

173
views

### Asymptotic approximation of a convolution of binomial coefficients

I would like to find the following limit which is somewhat similar to the usual Vandermonde's convolution for binomial coefficients. Define $L$ as follows.
$$ L \triangleq \lim_{N\to\infty} \frac{1}{2^...

0
votes

0
answers

39
views

### Enumerating directed cacti by the number of vertices and edges

Let's say that a directed cactus is a labeled directed graph, such that each vertex belongs to at most one simple cycle. In other words, it is a directed graph such that all its strongly connected ...

1
vote

0
answers

38
views

### Probability of generating the same DAG after picking a topological ordering 3 times in a row

Consider the following process:
Choose a random permutation $p$ of $\{1, 2, \dots, n\}$ out of $n!$ options.
Choose a random directed acyclic graph $G$ that has $p$ as a topological ordering out of $...

7
votes

0
answers

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