# Questions tagged [enumerative-combinatorics]

The enumerative-combinatorics tag has no usage guidance.

447
questions

8
votes

1
answer

217
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 \} \}$, $\{...

2
votes

1
answer

163
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

172
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

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

0
votes

0
answers

65
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

348
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

389
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

204
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

62
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

165
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

373
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

1
answer

119
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

31
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

36
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

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

1
vote

0
answers

97
views

### Partitions of a multiset and Möbius function

Consider the partial order set of all partitions of the multiset $\{1,1,\dots,n,n \}$. What is the value of $\mu(\hat 0, \hat 1)$, where $\hat 0$ and $\hat 1$ are respectively partitions of the ...

0
votes

2
answers

116
views

### Integer solutions of system of inequalities

I am trying to solve a problem in combinatorics and I came up with the following system of inequalities:
$0\leq x<y<z\leq n$ and $x+y<n$ and I am trying to count the number of integer ...

3
votes

2
answers

208
views

### Proof of an asymptotic formula by Tricomi

Firs of all I ask my question, then I explain how this question arises in my mind and lastly what I tried to solve it.
QUESTION:
Let $P_{n,N}(k)$ be the number of composition of an integer $k$ in $n$ ...

3
votes

2
answers

369
views

### An "incomplete" tiling?

Given an $m\times n$ chess board, we place $p$ $2\times 1$ dominoes on the board so that they don't overlap. How many ways can we place them?
When each square of the board is covered by a domino this ...

8
votes

2
answers

495
views

### Number of matrices with unit determinant and fixed sum of elements

Question. Let $\mathcal{M}_3$ be the set of $3\times 3$ matrices with non-negative integer entries and unit determinant. What is the number of $M\in \mathcal{M}_3$ with fixed sum of entries? What is ...

15
votes

2
answers

948
views

### A combinatorial interpretation for $n$-ary trees for negative $n$

The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation
$$
T_n=1+xT_n^n.
$$
This is usually defined for $n\ge 0$, but the functional equation can be ...

7
votes

2
answers

366
views

### Decomposition of a natural number as sum of positive integers

Let $n \in \mathbb{N}$ be a positive natural number and denote by $f(n)$ the number of decompositions of $n$ of the form $n = a+b+c+d$ where $a,b,c,d > 0$ are also positive natural numbers such ...

20
votes

1
answer

594
views

### Combinatorial proof of a certain binomial identity

Let $n$, $p$, $q$ be non-negative integers. Then
$$
\sum_{k=0}^n{2k+2p\choose k+p,k,p}{2(n-k)+2q\choose n-k+q,n-k,q}=4^n{2p\choose p}{2q\choose q}{n+p+q\choose n}.\tag{$\heartsuit$}\label{heart}
$$
In ...

4
votes

0
answers

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

0
votes

0
answers

33
views

### Large sum of determinants of Hadamard products

We have $n$ by $n$ matrices $A$, $C$ and $S$ over a finite field $\mathbb{F}_q$. The $C$ is invertible of order $m$ as an element of $GL(\mathbb{F}_q,n)$.
Is there an algorithm, polynomial in $n$, ...

0
votes

0
answers

41
views

### Existence of full-weight codeword in a linear q-ary code

I'm new to coding theory but would like to ask the following question:
Let $C$ be a linear $q$-ary code over $\mathbb{F}_q$ of length $n$ and dimension $k$ where $\mathbb{F}_q$ is a finite field with $...

1
vote

1
answer

152
views

### hook length formula for plane partitions

The hook length formula give a simple product expression for the number of standard Young tableaux of a given shape $\lambda$, where $\lambda$ is an integer partition, or equivalently, the number of ...

0
votes

0
answers

82
views

### Connectivity constant for lattices

A celebrated result due to Duminil-Copin and Smirnov states that the connectivity constant for the honeycomb lattice is equal to $\sqrt{2+\sqrt{2}}$.
My question is the following: apart from the ...

8
votes

0
answers

134
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_{\...

2
votes

0
answers

169
views

### Existence of fully supported element in a finite-dimensional vector space over $\mathbb{F}_p$ (and in finite abelian groups)

Let $V$ be an $n$-dimensional vector space over $\mathbb{F} = \mathbb{Z} / (p)$, the field of $p$ elements, $p$ a prime, with $\{v_1, \dotsc, v_n \}$ a basis for $V$. An element $x \in V$ is called &...

4
votes

2
answers

248
views

### Is this a known symmetry of lattice paths?

I recently came across the fact that NE lattice paths from $(0,0)$ to $(m,n)$ in aggregate pass through each row and column an equal number of times (which also has a corresponding binomial identity); ...

2
votes

0
answers

171
views

### Which combinatorial class do noncrossing partitions belong to?

Let $n$ be a nonnegative integer. The set $\lbrace 1,2,\ldots, n\rbrace$ is partitioned into blocks, with $p\left(n\right)$ possibilities (e.g., for permutations $p\left(n\right)=n!).$ For each block ...

11
votes

1
answer

875
views

### And, yet, another evaluation to Catalan numbers

Construct the $n$-tuple Cartesian product of the ternary set $X_n=\{0,1,2\}\times\cdots\times\{0,1,2\}=\{0,1,2\}^n$. Define its subset $W_n$ according to the rule (here $y=(y_1,\dots,y_n)$ is made use ...

2
votes

0
answers

44
views

### Removing convex sets that are unions of other convex sets from a large combinatorial enumeration

An addition chain for $n$ is a sequence of integers $1=a_0<a_1<...<a_r=n$ with $a_i=a_j+a_k,i>j\ge k\ge 0$. We say $r$ is the addition chain length. We define the length of the smallest ...

0
votes

0
answers

60
views

### Bounds on these numbers

Let $[n]$ be the set of natural numbers $1,2,3 \cdots n$ and $k$ be a natural number. Define $S(n,k) = \# \{ A \subset [n] \mid \displaystyle\sum_{i \in A} i =k \}$. My question is; Are there any ...

1
vote

1
answer

130
views

### Explicit formula for Fibonacci numbers; compositions of $n$

A Fibonacci-type sequence is a sequence with two seed-values, $F_1$ and $F_2$, and which, for all $n>2$, abides by the recurrence relation $F_n = F_{n-1} + F_{n-2}$. If $F_1 = F_2 = s$, then the $n$...

7
votes

2
answers

366
views

### A sequence of polynomials related to Catalan numbers

The sequence of polynomials
$$P_n=\sum_{k=0}^{\lfloor(2n-1)/3\rfloor}
\frac{(2n-2k-1)!(2n-2k-2)!}{k!(n-k)!(n-k-1)!(2n-3k-1)!}x^k$$
satisfies apparently the identities
$$0=\sum_{j=0}^nP_{n-j}(P_j-(-x)^...

3
votes

0
answers

153
views

### Transitive action on domino tilings

Fix a $n \times m$ rectangle and consider the set $S_{n,m}$ of all its dominos tilings.
Here are examples with $n=m=8$.
The set $S_{n,m}$ is empty if and only if $nm$ is odd, and for small $nm$, its ...

5
votes

0
answers

50
views

### An atlas for the enumeration of planar maps

The theory of planar map enumeration was started by Tutte and iniciated the theory of map enumeration when trying to solve the 4-colour theorem by enumerative arguments. Nowadays a wide diversity of ...

0
votes

0
answers

55
views

### Asymptotics for enumerating graphs

Let $K>k$ be positive integers. Now assume that $G$ is a $K$-connected graph with $n$ vertices and $m$ edges.
I would like to ask:
QUESTION. Is there an asymptotic for the number of $k$-connected ...

15
votes

2
answers

301
views

### Convergency radius of the generating series for A93637

Sequence A93637 of the OEIS (https://oeis.org/A093637) starting as $1,1,2,4,9,20,49,117,297,746,1947,\ldots$ is defined by
the coefficients $a_0,a_1,\ldots$ of the unique formal power series
defined ...

0
votes

1
answer

100
views

### Upper bound of the number of oscillatory sequences

Let $$A_n=\{(x_1,x_2,x_3,\cdots,x_n):x_i \in [q] \text{ for } i \in [n], x_1 < x_2, x_2 > x_3, x_3 < x_4, \cdots , (-1)^{n}x_{n-1} < (-1)^{n} x_n\}.$$ What is the cardinality of $A_n$?
I ...

3
votes

0
answers

112
views

### Counting monomials modulo prime numbers

The present quest emanates from this study by R. Stanley, including his recent MO question. Define the product (polynomials after full expansion)
$$I_n(x)=\prod_{i=1}^n(1+x^{F_{i+1}})$$
based on the ...

2
votes

0
answers

78
views

### Inequality on polynomials

Recall $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ and the Gaussian polynomial $\binom{a}{b}_q=\frac{[a]!_q}{[b]!_q[a-b]!_q}$ with $[0]!_q:=1$.
Given two polynomials $U(q)=\sum_k\alpha_kq^...

3
votes

1
answer

136
views

### Random covering of a set

Let $A$ be a set of $n$ elements. Let $S_1,\dots,S_n$ be independent $k$-element random subsets of $A$. What is the probability that $S_1,\dots, S_n$ evenly cover $A$, i.e. each element of $A$ belongs ...

1
vote

0
answers

61
views

### Counting pieces when an object is cut n ways

I was reading a passage from an old essay by Martin Gardner on the calculus of finite differences, and it seems to me that there is more that can and should be said about seemingly anomalous values of ...

4
votes

0
answers

148
views

### How many choices for $(f,g)$ such that $f \circ g = h$?

For $a,b,c \in \mathbb{N}$ let $[a] := \{1,...,a\}$ and suppose a map $h: [a] \rightarrow [c]$ is given. How many choices $(f,g)$ for maps $f: [a] \rightarrow [b]$ and $g: [b] \rightarrow [c]$ are ...

4
votes

0
answers

182
views

### Non-crossing and crossing bijection in higher genus

This is a follow-up question of my SO post I'll briefly mention it here.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the monotonic 2 -tuples, of the form $(a,b)(c,d)$, monotonicity in on the ...

12
votes

0
answers

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

0
votes

1
answer

57
views

### Enumerating (i.e. generating one by one) matrices of given rank over a finite field

Let be given positive integers $m,n,r$, with $r \leq \min(m, n)$, and a finite field of $q$ elements $\mathbb{F}_q$.
I'm looking for an efficient algorithm to enumerate (i.e., generate one by one) all ...