Questions tagged [enumerative-combinatorics]

Filter by
Sorted by
Tagged with
11
votes
2answers
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
2answers
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
5answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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 ...

1
2 3 4 5 6