# Questions tagged [enumerative-combinatorics]

The enumerative-combinatorics tag has no usage guidance.

299
questions

**11**

votes

**2**answers

404 views

### The verbs in combinatorics: Enumerating, counting, listing and all that

Two closely related, but different tasks in combinatorics are
determining the number of elements in some set $A$, and
presenting all its elements one by one.
Question: What are some works in ...

**2**

votes

**2**answers

70 views

### Calculating number of vertex-pairs with separate common ancestor

Given a tree-graph with one of the vertices designated as the root, what is the complexity of calculating the number of vertex-pairs $\lbrace u,v \rbrace$ of which $v$ is not nearer to the root than $...

**2**

votes

**0**answers

91 views

### Enumeration and encoding of simplicial complexes

I'd like to know how to enumerate and encode all (abstract) simplicial complexes of a given kind.
To start as simple as possible, consider the familiy $\mathcal{S}_n^{d}$ of simplicial complexes which ...

**3**

votes

**0**answers

63 views

### Ehrhart-Macdonald reciprocity with multiplicities

Let $P$ be a convex lattice polytope in $\mathbb{R}^n$. The function $L(t, P) = |\mathbb{Z}^n \cap t\cdot P|$ is a polynomial, and we have an equality
$$L(-t, P) = (-1)^nL(t, P^{int}),$$
where $P^{int}...

**3**

votes

**0**answers

120 views

### Partitions of n into k distinct parts which are multiples of given numbers

Is there anything known about the number of partitions of an integer $n$ into $k$ distinct parts in the following way?
Let $a_1,\dotsc,a_k\geqslant1$ be given integers. In how many ways can we write $...

**11**

votes

**2**answers

782 views

### How many finitely-generated-by-elements-of-finite-order-groups are there?

I do not know where this question is on the trivial to intractable spectrum.
Consider the set of isomorphism classes of groups finitely generated by elements of finite order. What is the cardinality ...

**1**

vote

**0**answers

79 views

### Dimension of a certain space of symmetric functions: Part II

This is the second installment of my earlier MO question.
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. Denote the set of all partitions with distinct parts by $\...

**5**

votes

**0**answers

183 views

### Dimension of a certain space of symmetric functions: Part I

Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. A partition $\lambda$ is called a $t$-core if none of its hook lengths are multiples of $t$.
QUESTION. Consider the ...

**4**

votes

**1**answer

186 views

### Identity involving binomial coefficients and partitions

Working on a problem in the symmetric group I have stumbled upon the following equation:
$$\sum_{\substack{\pi=(1^{c_1},2^{c_2},\ldots,n^{c_n})\\\textrm{partition of }n}}(-1)^{n-\sum_{i=1}^nc_i}\frac{...

**1**

vote

**0**answers

67 views

### Number of extremal $\{0,1\}$ matrices having permanent $1$ property

Is there a function which describes the number of $\{0,1\}^{n\times n}\cap\mathbb Z^{n\times n}$ matrices having permanent $1$?
I think it might be $\mathsf{poly}(n!)$ bounded.
Is there a function ...

**3**

votes

**0**answers

122 views

### Does every finite lattice embed into a finite Eulerian lattice?

A finite Boolean lattice is a lattice isomorphic to the subset lattice of a finite set. Every Boolean lattice is Eulerian, namely, a graded lattice $L$ such that $\mu(a,b) = (-1)^{|b|-|a|}$ for all $a,...

**5**

votes

**1**answer

352 views

### Typo in Stanley, Enumerative combinatorics II, Cor. 7.23.9?

In Stanley, EC2, we have the following statement:
I think there is a typo in the first sum after "generating function",
and that $[n]_q!$ should be replaced by $(1-q)(1-q^2)\dotsb (1-q^n)$,
...

**0**

votes

**0**answers

114 views

### Question on rank of matrices over $\mathbb F_2$

$A$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $k\leq n-1$.
$B$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $n$.
$T$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $1$...

**1**

vote

**0**answers

109 views

### Polynomial systems and algebraic functions

An algebraic function $y(x)$ is defined as the solution of a polynomial equation of the form $p(x,y)=0$, that is one making the identity $p(x,y(x))=0$ true --- in either analytical or formal power ...

**3**

votes

**1**answer

122 views

### Maximum number of subsets in which people co-exist with their friends

Let $P = \{1,\dots,p\}$ be a set of people. Consider partitioning $P$ into two disjoint sets, $A$ (of cardinality $a$) and $A^c = P-A$. Let us index $A$ as $A = \{A_1,\dots,A_a\}$. Each person in $A$ ...

**6**

votes

**1**answer

211 views

### What is the direct proof of the recurrence relation about lattice path enumeration given by Bizley?

Let $k$ be a nonnegative integer and let $m,n$ be coprime positive integers. Let $\phi_k$ be the number of lattice paths from $(0,0)$ to $(km,kn)$ with steps $(0,1)$ and $(1,0)$ that are never rising ...

**0**

votes

**0**answers

121 views

### Binomial coefficient in a binomial coefficient

I am doing some research in combinatorics, and I found that I have to consider the following binomial coefficient :
$$ \binom{\binom{i}{j}}{k} $$
(In fact, I have to take the product for fixed $i,k$ ...

**2**

votes

**2**answers

90 views

### Efficiently generating all regular/bidegreed graphs

There is a related question on how to generate all regular graphs; however, the procedure is random and repeats the generated graphs. Plus, there is no stop condition, unless recording the total ...

**5**

votes

**1**answer

199 views

### Toroidal alternating sign matrices

Consider $n\times k$ matrices with entries from $\{0,1,-1\}$ such that the sum in each row and each column is 0 and the non-zero numbers in each row/column alternate in sign (so, they alternate if we ...

**17**

votes

**2**answers

879 views

### A conjecture harmonic numbers

I will outlay a few observations applying to the harmonic numbers that may be interesting to prove (if it hasn't already been proven).
From the Online Encyclopedia of Positive Integers we have:
$a(n)$ ...

**9**

votes

**0**answers

88 views

### Smallest counterexample to Stein's conjecture?

An equi-$n$-square is an $n$ by $n$ array of cells filled with the symbols $1,2,\dots,n$ so that each symbol occurs exactly $n$ times.
(Every Latin square of order $n$ is an equi-$n$-square, but the ...

**2**

votes

**1**answer

107 views

### Enumeration of connected, bridgeless, trivalent graphs

Is it known how many connected, bridgeless, trivalent graphs there are on $2n$ vertices?
I am allowing the graph to have multiple edges, but no self edges (though I think the fact that the graph is ...

**2**

votes

**0**answers

59 views

### How to compute the number of combinations with r allowed repetitions [closed]

Assume we have set $A$ with $n$ elements and we want to choose $k$ items with the maximal number of repetitions $r$.
If $r = 1$ then repetitions are not allowed. Then this number can be computed as $n ...

**9**

votes

**5**answers

789 views

### The number of ways to merge a permutation with itself

Let $\sigma$ be a permutation of $[k]=\{1,2, \dots , k\}$. Consider all the ordered triples $(\pi, s_{1},s_{2})$, such that $\pi$ is a permutation of length $2k-1$ that is a union of its two ...

**6**

votes

**1**answer

381 views

### Reciprocity for fans of bounded Dyck paths

This is a continuation of some questions asked by Johann Cigler: Number of bounded Dyck paths with "negative length" and Number of bounded Dyck paths with negative length as Hankel ...

**2**

votes

**2**answers

250 views

### Number of bounded Dyck paths with negative length as Hankel determinants

This is a continuation of my post Number of bounded Dyck paths with "negative length".
Let $C_{n}^{(2k+1)}$ be the number of Dyck paths of semilength $n$ bounded by $2k+1.$ They satisfy a ...

**5**

votes

**1**answer

266 views

### Two remarkable weighted sums over binary words

This question builds off of the previous MO question Number of collinear ways to fill a grid.
Let $A(m,n)$ denote the set of binary words $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$ consisting ...

**8**

votes

**1**answer

352 views

### Number of bounded Dyck paths with “negative length”

Let $c(n,k)$ denote the number of Dyck paths of semilength $n$ which are contained in the strip $0 \leq y \leq 2k + 1.$
They satisfy the recursion $\sum_{j=0}^{k+1}(-1)^j \binom{2k+2-j}{j}c(n-j,k)=0$ ...

**0**

votes

**1**answer

94 views

### Number of duplicate pairs in multiple samplings

My universe has M different items. I run m=10 independent samplings over M. In each sampling, n elements are picked without replacement (n<<M). What is the expected number of pair duplicates we ...

**2**

votes

**0**answers

43 views

### Counting the number of simple labelled bipartite graphs 𝐺𝑛,𝑚 with 𝑘 edges such that 𝑑1 vertices have degree 1

I have tried to count the number of simple labelled bipartite graphs $G_{n,m}$ with $k$ edges such that $d_1$ vertices have degree 1.
Has this problem been studied?
So far the only related paper I ...

**2**

votes

**0**answers

69 views

### Bijections between binary sequences and primitive elements in a finite field [duplicate]

Let $n>1$ be a natural number. We call a binary sequence $(b_1,\ldots, b_n)\in \{0,1\}^n$ $rigid$ if it is not a proper power of a sequence of shorter length. So for example $(0,1,0,1) = (0,1)^2$ ...

**4**

votes

**0**answers

63 views

### Asymptotics of the number of minimal strongly connected digraphs

Is anything known about the number of minimal strongly connected digraphs on $n$ labeled nodes? (``Minimal’’ meaning that on the deletion of any arc, strong connectivity is lost.) Some values are ...

**4**

votes

**1**answer

168 views

### Number of paths in the Bruhat order in the symmetric group

Let $\mathbb{S}_m$ the symmetric group on $m$ letters. Let $v\in\mathbb{S}_m$, and consider paths in the Bruhat order like this: $1\lessdot v_1\lessdot\cdots\lessdot v$, where $\lessdot$ means the ...

**6**

votes

**1**answer

265 views

### How does the number of trees on $n$ vertices *up to isomorphism* grow as $n \to \infty$?

It is well known that the number of labelled trees on $n$ vertices is equal to $n^{n-2}$.
We do not expect any such exact formula for the number of isomorphism types of trees on $n$ vertices. But ...

**1**

vote

**0**answers

80 views

### Counting unions of unlabelled connected graphs

My question can be stated as follows: let $X$ be a hereditary family of unlabelled graphs closed under disjoint unions. Suppose we know, for each $n$, the number $c_n$ of connected graphs in X on $n$ ...

**0**

votes

**0**answers

34 views

### Integer partitions and compositions into restricted parts with a difference condition

Given a linear diophantine equation $$x_1+\dots+x_n=m\leq nn'$$ how many solutions does it have with each $x_i\in[0,n']\cap\mathbb Z$ if $x_{max}-x_{min}=m'\leq m$? Looking for asymptotics that ...

**0**

votes

**0**answers

64 views

### Group analogue of polynomial zero-patterns

In
On the number of zero-patterns of a sequence of polynomials,
Rónyai, Babai, and Ganapathy bound the number of zero-patterns for sequences of polynomials. I am interested in an analogous problem for ...

**0**

votes

**1**answer

70 views

### Relationship between cycle length, number of chords, and number of induced $P_{4}$ subgraphs of the cycle

I was wondering if there was a known relationship between the length of cycle, the number of chords of the cycle, and the number of induced $P_{4}$ subgraphs of the cycle.
Here, I am referring to ...

**1**

vote

**1**answer

223 views

### Integer partitions into restricted parts

Given a linear diophantine equation $$x_1+\dots+x_n=m\leq nn'$$ how many solutions does it have with each $x_i\in[0,n']\cap\mathbb Z$? Looking for asymptotics that parametrizes well with both $n$ and $...

**1**

vote

**0**answers

85 views

### Balls and bins, with cardinality constraints

Suppose I have $n$ sets of $k$ balls each, with each one of the $nk$ balls distributed uniformly at random among $m$ bins. Further suppose that I have a probability vector $p=(p_1,\dots,p_m)$. I am ...

**2**

votes

**0**answers

131 views

### A combinatorics identity

Let $G$ be a finite group, for any positive integer $n$ we have a wreath product $G\wr \Sigma_{n}$. It is well know that the conjugacy classes of $G\wr \Sigma_{n}$ is classified by sequences $\{m_{r}(...

**8**

votes

**1**answer

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

**8**

votes

**1**answer

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

**5**

votes

**1**answer

143 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

241 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

29 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

208 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

25 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

369 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

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