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 \} \}$, $\{...
- 397
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\...
- 40.2k
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{...
- 40.2k
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 ...
- 40.2k
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 ...
- 40.2k
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 ...
- 33
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 (...
- 40.2k
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}{...
- 950
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 ...
- 117
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 $\...
- 40.2k
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\...
- 40.2k
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^...
- 155
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 ...
- 857
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 $...
- 857
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,253
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 ...
- 1,253
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 ...
- 1
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$ ...
- 177
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 ...
- 329
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 ...
- 485
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 ...
- 1,078
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 ...
- 215
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 ...
- 94.9k
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 ...
- 61
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$, ...
- 3,011
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 $...
- 181
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 ...
- 528
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 ...
- 1,463
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,064
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 &...
- 181
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); ...
- 43
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 ...
- 297
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 ...
- 40.2k
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 ...
- 87
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 ...
- 281
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$...
- 13
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)^...
- 16k
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 ...
- 24.7k
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 ...
- 1,463
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 ...
- 40.2k
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 ...
- 16k
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 ...
- 15
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 ...
- 40.2k
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^...
- 40.2k
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,253
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 ...
- 18.8k
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 ...
- 511
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 ...
- 675
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 \...
- 5,474
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 ...
- 43