Questions tagged [enumerative-combinatorics]

Filter by
Sorted by
Tagged with
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$, ...
thedude's user avatar
  • 1,397
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.
domotorp's user avatar
  • 18.2k
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\...
M. Winter's user avatar
  • 12.2k
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 ...
Max Alekseyev's user avatar
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, $\...
Sam Hopkins's user avatar
  • 22.4k
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&...
smoneh's user avatar
  • 11
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^{...
Hao Yu's user avatar
  • 177
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 ...
Leox's user avatar
  • 546
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 ...
Tardis's user avatar
  • 1,015
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 ...
ho boon suan's user avatar
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$...
tony's user avatar
  • 335
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(\...
qifeng618's user avatar
  • 828
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 ...
Erik Lundberg's user avatar
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 $\...
T. Amdeberhan's user avatar
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$ ...
L.C. Zhang's user avatar
  • 1,593
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,\...
tony's user avatar
  • 335
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 ...
John Baez's user avatar
  • 21.1k
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 ...
Hao Yu's user avatar
  • 177
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 ...
tony's user avatar
  • 335
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 ...
Alexey Milovanov's user avatar
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 ...
Alexey Milovanov's user avatar
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, \ \...
tony's user avatar
  • 335
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=...
T. Amdeberhan's user avatar
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 ...
Dreamer's user avatar
  • 261
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 ...
fusheng's user avatar
  • 65
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 ...
T. Amdeberhan's user avatar
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}...
T. Amdeberhan's user avatar
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)/...
Iosif Pinelis's user avatar
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). ...
tim guo's user avatar
  • 11
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 ...
Zhi Wang's user avatar
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 ...
T. Amdeberhan's user avatar
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-...
Lewwwer's user avatar
  • 129
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?
Turbo's user avatar
  • 13.6k
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-...
KJL's user avatar
  • 113
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}$...
T. Amdeberhan's user avatar
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 \} \}$, $\{...
Naysh's user avatar
  • 455
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\...
T. Amdeberhan's user avatar
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{...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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 ...
wkmath's user avatar
  • 33
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 (...
T. Amdeberhan's user avatar
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}{...
MathCrawler's user avatar
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 ...
elsnar's user avatar
  • 127
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 $\...
T. Amdeberhan's user avatar
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\...
T. Amdeberhan's user avatar
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^...
shortfatboy's user avatar
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 ...
Oleksandr  Kulkov's user avatar
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 $...
Oleksandr  Kulkov's user avatar
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$ ...
Pluviophile's user avatar
  • 1,394

1
2 3 4 5
10