Questions tagged [enumerative-combinatorics]

Filter by
Sorted by
Tagged with
8
votes
1answer
86 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. ...
7
votes
1answer
171 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 ...
0
votes
0answers
25 views

Enumerating all directed 3-cycle covers

It is fairly easy to enumerate the directed Hamilton cycles of a complete directed graph by fixing one of the vertices and enumerating the permutations of the others via one of the next-permutation ...
4
votes
1answer
120 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
184 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
20 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
196 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
19 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
300 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
118 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 ...
5
votes
4answers
395 views

Request for an exact formula related to a partition in number theory

The Frobenius equation is the Diophantine equation $$ a_1 x_1+\dots+a_n x_n=b,$$ where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$ must consist of non-...
3
votes
0answers
67 views

On the proportion of simplicial $d$-polytopes on $n$-vertices

I have a question regarding estimates for the proportion of simplicial $d$-polytopes on $n$-vertices. Let $c_s(n,d)$ denote the number of combinatorial types of simplicial $d$-polytopes on $n$ ...
5
votes
0answers
142 views

Number of rectangles in an n-by-n grid of points

I am seeking a formula for the number of rectangles with vertices belonging to an $n \times n$ square grid of points. This is sequence A085582 in the OEIS. Note that the grid in question has $n^2$ ...
1
vote
0answers
170 views

Combinatorial bijection on monotone sequences

Let $(n),\mu$ be the partition of $n$ define $H_g^{m}((n);\mu)$ count's the number of tuples $(\tau_1,\ldots,\tau_r)$ of transposition in symmetric group $S_n$ with the following conditions $$ (1,2,\...
0
votes
1answer
58 views

Ordered $m$-tuples with fixed number of changes

Given $1\leq k\leq m$, $2\leq d\leq c i\ln i$ and $2\leq i\leq c'\ln(mi\ln i)$ at some $c,c'>0$ how many sequences (lower and upper bounds) are of form $$z_1,\dots,z_m$$ on the condition that $$0\...
2
votes
0answers
47 views

Seeking bijective proof of a recurrence for generalized Narayana numbers

Consider lattice paths in $d$ dimensions with the steps $X_1\mathrel{:=}(1,0,\dotsc,0)$, $X_2\mathrel{:=} (0,1,\dotsc,0)$,…, $X_d\mathrel{:=} (0,0,\dotsc,1)$. Let $\mathcal C(d, n)$ denote the set of ...
1
vote
1answer
90 views

Calculating the values of a generalization of binomials to permutations

let $$\Pi\binom{n}{k}:=\mathrm{card}\left( \left\lbrace \lbrace \Pi_1^n\,\cdots\,\Pi_k^n\rbrace\,|\,0\leq \pi_{r,c}\in\sum_{i=1}^k\Pi_i^n\ni\pi_{r,c}\leq 1\right\rbrace\right)$$ be the number of sets ...
7
votes
2answers
300 views

Counting nilpotent self-maps of $\{1,\dots,n\}$ with image of a given cardinal

Let $\mathcal{C}_n$ be the monoid of self-maps $\alpha$ of $\{1\dots,n\}$ that are order-preserving ($\forall x,y$, $x\le y$ $\Rightarrow$ $\alpha(x)\le\alpha(y)$ and decreasing ($\forall x$, $\alpha(...
0
votes
1answer
82 views

Number of positive integer solutions with a lower bound

If $0\leq\gamma<\alpha<1$ and $t=\lceil n^\gamma\rceil$ hold then how many positive solutions to the linear diophantine equation $$x_1+\dots+x_t=\lceil n^\alpha\rceil$$ have the property $$n^\...
4
votes
2answers
175 views

Number of nonequivalent weight functions on a set of $n$ elements

For a finite set $S$ of $n$ elements, say a weight function is a function $f \colon S \to \mathbb{R}$. For any subset $T \subseteq S$, define $f(T) = \sum _{x \in T} f(x)$. Define two weight functions ...
1
vote
1answer
87 views

mapping integers to k-ary trees

Is there an algorithmic way to map the natural numbers to unique k-ary trees? I am familiar with the work of Tychonievich who created a mapping from integers to binary trees. https://www.cs.virginia....
3
votes
1answer
393 views

Sum of all products of k distinct integers in [1,n] [duplicate]

Let $S=\{1,2,3,...,n\}$ be the set of integers up to $n$ and $p_k(a_1,...,a_k)=a_1\cdots a_k$ the product of $k$ distinct integers $a_1,...,a_k \in S$. There are $\binom{n}{k}$ possibilities to ...
2
votes
0answers
84 views

Number of permutations with precedence constraints : DP case [closed]

I have two sets of balls (blacks and whites), each set is numbered from $1$ to $n$, and all are put in a jar. My precedence constraint is expressed as following : to pick a black ball with index $i$, ...
0
votes
0answers
61 views

Paths in graphs as a vector space or matroid

If I have a simple graph $G$, and what to count the number of simple paths between two distinct vertices, can the paths be seen as independent sets of a vector space, or even somehow, a matroid? I ...
4
votes
1answer
287 views

Enumerating all permutations that are “square roots” of derangements

Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement? Other information about those kind ...
4
votes
1answer
92 views

What is the probability of an empty convex $k$-gon among many given points?

Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points. For a big number $n$ of randomly distributed ...
0
votes
0answers
21 views

Iterated Inverse structures: polynomial representation of integer partitioning of preimages in Sigma Matrices (reference request)

I am studying iterated preimage structures of functions on a finite set. The main structure of interest to me, the Sigma Matrix, is derived from a matrix listing the element-wise preimage sets at ...
2
votes
2answers
125 views

enumerate line partitions of points in the plane

Let $S$ be a nonempty subset of $\mathbb{R}^2$ and $l$ a line in $\mathbb{R}^2$ disjoint from $S$. Then $l$ partitions $S$ into two disjoint sets $S = S_1 \cup S_2$ in the obvious way. Note that, at ...
12
votes
1answer
461 views

Dividing a chocolate bar into any proportions

Suppose I have a chocolate bar of integer length $L$, and there are $m\leq L$ people that are going to share it. We do not know ahead of time how much each person should receive, all we know is that ...
1
vote
1answer
52 views

Rank and edges in a combinatorial graph?

Fix a $d\in\mathbb N$ and consider the matrix $M\in\{0,1\}^{2^d\times d}$ of all $0/1$ vectors of length $d$. Consider the matrix $G\in\{0,1\}^{n\times n}$ whose $ij$ the entry is $0$ if inner product ...
1
vote
2answers
395 views

Constant row-column sum matrices?

Given an integer $T$ how many $n\times n$ matrices in $\mathbb Z_{\geq0}^{n\times n}$ we have such that every row and column sum to same $T$? Do the set of constant row and column sum matrices form ...
2
votes
0answers
56 views

Annihilator of the of the generating function not holonomic

The following is a generating function in $x,h$ with infinite parameters $q_1,q_2\ldots,$ and $w_1, w_2,\ldots$. $$\Psi(x, h)= \sum_{d=0}^{\infty} s_{(d)} (q_1, q_2, \ldots) \exp \bigg( \sum_{r=1}^{\...
1
vote
2answers
211 views

Fair partitioning of a set - Weighted sums of Bernoullis

For $n$ an integer, let $a_n$ be the number of ways in which one may partition the set $\{1, \ldots, 2n \}$ in two parts with: the same number of elements: $n$ and the same sum: $2n(2n+1)/4$. ...
2
votes
1answer
180 views

Filling $1..mn$ into a $m×n$ rectangle such that every number $<mn$ is dominated

This is a problem from my professor, who claimed that it's open: Combinatorial problem. Fill $1,2,...,mn$ into a rectangle of size $m\times n$, such that for every number other than $mn$, ...
3
votes
0answers
59 views

Using Kac-Rice formula to count average number of sub-regions carved out by $n$ random hyper-planes

Context. This is the first in a set of tiny pieces of a problem I've formulated to help me measure the "complexity" of certain piecewise linear functions. Thanks in advance for your help and patience. ...
7
votes
2answers
190 views

Estimating the number of functions which are at most $c$-to-$1$ for some constant $c \ge 2$

Notation: $[m] := \{1, 2, \dots, m \}$. How many functions are there $f: [a] \to [b]$? The answer is easily seen to be $b^a$. How many $1$-to-$1$ functions are there $f: [a] \to [b]$? Again the ...
0
votes
0answers
74 views

Generating uniformly distributed trees

I'm looking for closed (possibly approximate) formulae for the following problem. I am trying to generate (uniformly distributed) random trees of a given size n. The "size" is the number of symbols ...
1
vote
1answer
79 views

Circular (bracelets) permutations with alike things(reflections are equivalent) using polya enumeration

Circular permutations of N objects of n1 are identical of one type, n2 are identical of another type and so on, such that n1+n2+n3+..... = N? A similar question exists but it doesn't address the case ...
5
votes
1answer
174 views

Intuition for the expected number of returns of a Dyck path

It is known that the expected number of returns of a Dyck path of semilength $n$ to the $x$-axis is $3n/(n+2)$, so it tends to 3 as $n\to\infty$. (This was proved in the Dyck path context by Deutsch ...
13
votes
1answer
463 views

Coincidences between average Catalan tableaux

There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices: $$ P_n \, := \, \frac{1}{C_n} \, \...
4
votes
0answers
258 views

What arithmetic would you do in parallel?

This is a post asking for references, and soliciting problems and people interested in accelerated computing. I will add the big-list tag and make it community-wiki. If this interests you strongly, ...
0
votes
1answer
71 views

Primage structures: induced domain partitioning by itterated inverse (reference request)

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, the j-th such preimage list ...
5
votes
2answers
207 views

Eigenvalues of the Laplacian of the directed De Bruijn graph

We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ ...
4
votes
0answers
110 views

Count necklaces with fixed substring

I consider k-ary strings of the form $a_1 \cdots a_n$ where $a_i \in \{0,\ldots,k-1\}$ for $1\le i \le n$. A necklace is the lexicographically smallest representative of an equivalence class where two ...
1
vote
0answers
23 views

Extension of definition of Holonomic closure

My question is about finding the annihilator of a series. Let me begin with what is known and then ask my question. Let $s_d(\frac{q_1}{h},\ldots )$ denote schur function for partition $\lambda =[d]$ ...
6
votes
1answer
155 views

Sufficient conditions for the coefficients of a generating function to dominate those of its square

Let $f(z)$ be a generating function (so in particular, its power series coefficients are nonnegative). I am interested in conditions which would ensure that for every $n$, the coefficient of $z^n$ in $...
5
votes
0answers
115 views

Identity for classes of plane partitions

There are several classes of plane partitions in the literature. Among these, let's look at the enumeration of three of them: the symmetric (SPP), totally symmetric (TSPP) and totally symmetric and ...
3
votes
1answer
280 views

Graph isomorphism by invariants

Graph isomorphism is known to be a difficult computational problem. The problem get even worst if we want to find non-isomorphic graphs in a large family of graphs. Let us call a (numerical) ...
5
votes
0answers
446 views

Darkness in the lamplighter group

Consider paths through the lamplighter group $\mathbb{Z}_n\wr\mathbb{Z}$ with steps consisting of moving left, moving right, and toggling the lamp at the current position. How many paths of length $m$ ...
-2
votes
1answer
100 views

Sum of: k permutations of n $\times e^x$

Simplify the following: \begin{equation} \sum\limits_{\ell =1}^n P(n,\ell) (e^x -1)^\ell \end{equation} to something like $n!n^n$. I got curious about this expression after going through this ...

1
2 3 4 5 6