# Questions tagged [enumerative-combinatorics]

The enumerative-combinatorics tag has no usage guidance.

**0**

votes

**0**answers

28 views

### k-ary necklaces with conserved/fixed indexes

I asked a question in a previous post about enumerating all possible k-ary bracelets with certain positions fixed to a specific bead/character. I asked a few mathematicians, and it seems its quite ...

**1**

vote

**0**answers

42 views

### Generate all connected non-isomorphic graphs of n vertices modulo local complementation?

I'd like to generate a list of all simple, connected, undirected graphs of $n$ vertices, modulo standard graph isomorphism, and modulo local complementation, which is the following operation: for a ...

**3**

votes

**0**answers

51 views

### How likely is a matrix with exactly $n$ number $1$s per row to avoid a large wide empty submatrix?

Consider the finite collection $M(N,n)$ of all $N \times N$ matrices with exactly $n$ entries per row equal to $1$ and all other entries equal to zero $0$.
By an $a \times b$ submatrix of $M$ we ...

**9**

votes

**0**answers

261 views

### Why does Loday call the permutohedra “zylchgons”?

Today I was reading Jean-Louis Loday's classic paper, "Realization of the Stasheff polytope", in which he produces a simple and very pretty realization of the associahedra as convex polytopes. He ...

**6**

votes

**1**answer

110 views

### Are there Prüfer sequences for rooted forests?

One well-known, extremely slick proof of Cayley's tree enumeration theorem is the use of Prüfer sequences. Cayley also proved a version for forests, namely that the number of forests with $n$ ...

**2**

votes

**1**answer

168 views

### Guess (or upper bound) the general formula for a double sequence

Let $t,s \geq 0$ be integers. We have the following recursive formula:
$$f(t+1,s) = f(t,s) + f(t,s-1) + \sum_{0\leq a,b,c \leq h(t):\\a+b+c = s-1}f(t,a)f(t,b)f(t,c),$$ where
$$h(t) = \frac{1}{2}3^t -\...

**7**

votes

**0**answers

186 views

### Counting hyperplane arrangements up to combinatorial equivalence, simple examples and history

Two arrangements of (affine) hyperplanes in $d$-dimensional Euclidean space are combinatorially isomorphic (or combinatorially equivalent) if they have isomorphic posets of faces.
Counting the ...

**3**

votes

**0**answers

102 views

### Permutation statistics in multiple rows

Usually we study the statistics of a permutation written in one row. Is there any result for the statistics of a permutation written in multiple rows? Let me give an example in order to be more clear: ...

**3**

votes

**0**answers

46 views

### How to represent the even signed permuation by Young tableaux?

The well-konwn RSK correspondence established the connection between table pair (P,Q) and the permutations in symmetry group Sn(Coxeter group of type A). Also, there is a similar correspondence for ...

**0**

votes

**1**answer

91 views

### The number of a family of sequences of subsets of $\{1,2,\cdots,n\}$

Given integers $m,n\geq 1$, let $W_{n,m}$ denote the family of all sequences $S_1,S_2,\cdots,S_m$ satisfying
(1) every $S_i$ is a subset of $\{1,2,\cdots,n\}$;
(2) $\mid S_i\cap S_j\mid\geq 3$ for ...

**13**

votes

**1**answer

415 views

### Character theoretic proof of the Littlewood–Richardson rule?

The Littlewood–Richardson coefficients are the multiplicities
$$
c(\lambda,\mu,\nu)= \dim_{\mathbb{C}}\operatorname{Hom}_{S_n}(S(\nu),S(\lambda/\mu))
$$
and the Littlewood–Richardson rule says that ...

**1**

vote

**0**answers

98 views

### Combinatorial problem involving sets (+graph theoretic interpretation)

I have the follwing combinatorial question, which I motivate below.
Let $N:=\lbrace 1,\dots,n \rbrace$ be a set and let $\lambda_1,\dots,\lambda_l$ be a collection of $l:=n+3$ subsets of $N$ with the ...

**7**

votes

**1**answer

623 views

### Is there a natural relationship between OEIS A127670 and Cayley's tree formula?

I apologize in advance that this question must sound highly amateurish, but I am wondering if there is any connection between the formula https://oeis.org/A127670 , which counts the number of fixed $n$...

**4**

votes

**0**answers

241 views

### How many conjugacy classes of elementary abelian subgroups of rank $2$ does $GL_{n}(Z / pZ)$ have?

Let $p$ be a prime number and $G=GL_n ( \mathbb{Z} / p \mathbb{Z}
)$. Consider the set $U$ of upper-triangular matrices of $G$
having entries of $1$ on the diagonal. The cardinality of $U$ is $p^{\...

**14**

votes

**4**answers

812 views

### Number of collinear ways to fill a grid

A way to fill a finite grid (one box after the other) is called collinear if every newly filled box (the first excepted) is vertically or horizontally collinear with a previously filled box. See the ...

**1**

vote

**0**answers

224 views

### On the number of Eulerian orderings

This post is a sequel of Eulerian ordering of the integers modulo n.
Let us recall the definition of an Eulerian ordering:
Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$....

**4**

votes

**0**answers

73 views

### Maximum number of integer points in a polytope

What is the maximum number of integer points $\#M$ in a dimension $n$ closed bounded convex polytope $M$ given by $Ax\leq b$ with number $m$ of constraints and $O(d)$ bits in any entry of $A\in\Bbb Z^{...

**1**

vote

**0**answers

35 views

### Counting arrangements around a table with constraints

I have $n$ guests seated around a circular table. I want to serve them meals so that given any two guests $u$ and $v$, either
i. $u$ and $v$ have different meals, or
ii. $u$'s two neighbors have a ...

**4**

votes

**2**answers

132 views

### Asymptotics of unrooted labeled forests

It is well known that the number of unrooted labeled trees on vertex set
$[n]={1,2,...,n}$ is $n^{n-2}$. Let $U(z)$ be the exponential generating function of the sequence of these numbers. Then $F(z)=\...

**1**

vote

**1**answer

164 views

### Bit complexity of Barvinok's algorithm

I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension.
What exactly is this arithmetic complexity?
...

**1**

vote

**2**answers

137 views

### How to compute number of ways to partition a set under certain constraints?

Let us have a set $A$ of $|A|=n$ objects. I would like to know the number of ways to partition the set into $k$ non-empty subsets. This, I believe, is given by the Stirling numbers of the second kind, ...

**2**

votes

**1**answer

157 views

### count the number of words in a set

Consider the words obtained from the alphabet $\{a,b,c\}$, we require that for each $b$ in the word, the number of times that $a$ appears before $b$ should be greater or equal to the number of times ...

**1**

vote

**1**answer

75 views

### An asymptotic characterization for a series

I have been working on characterizing the asymptotic behavior for large $n$ for the following sum:
$$\Gamma(1+t)\sum_{k=1}^n \frac{\binom{n}{k} (-1)^{k-1}}{k^t}$$
where $t(>0)$ is a given ...

**6**

votes

**1**answer

154 views

### Direct bijections for $s,t$-Fibonomial identities

Sagan and Savage gave a combinatorial interpretation of a polynomial generalization of Fibonomial coefficients. Their proof uses the recurrence relation for the Lucas polynomials that generalize the ...

**0**

votes

**0**answers

43 views

### Multiplicities of ordered pairs in pairing of two multisets

This is a repost from a question on math.stackexchange.
Problem: I have two multisets, $X$ and $Y$. Each is a $k$-combination with repetition of a set $N=\{1,2,3,\dots,n\}$, where $n$ can be greater, ...

**3**

votes

**1**answer

204 views

### What does this permutation polynomial look like?

What is the number of terms of the unique multilinear polynomial $f\in\Bbb F_2[x_{1,1},\dots,x_{n,n}]$ in $n^2$ variables such that $f$ vanishes only on matrices that are permutations?
Are there good ...

**1**

vote

**1**answer

250 views

### An explicit formula for the number of different (non isomorphic) simple graphs with $p$ vertices and $q$ edges

I would like to know if there is an explicit formula for the number of different (non isomorphic) simple graphs with a given number of vertices $p$ and edges $q$, and if yes what is it.
Trying to ...

**2**

votes

**3**answers

171 views

### Number of binary arrays of length n with k consecutive 1's [closed]

What is the number of binary arrays of length $n$ with at least $k$ consecutive $1$'s?
For example, for $n=4$ and $k=2$ we have $0011, 0110, 1100, 0111, 1110, 1111$ so the the number is $6$.

**1**

vote

**1**answer

91 views

### Number of iterations required for a transposition cipher to yield the original input

I have asked this question on math.stackexchange.com but received no response; hoping someone on here can help.
Suppose a function $f$, representing what I call a "dynamic transposition cipher" ...

**1**

vote

**0**answers

78 views

### Partition of sets of monomials

Given a degree $d>0$ and $x_1,\dots,x_n$, consider the set $S$ of monomials
\begin{equation*}
x_1^{i_1} \cdots x_n^{i_n}
\end{equation*}
with $0\leq i_j\leq d$ for $1\leq j\leq n$ (the exponents ...

**2**

votes

**2**answers

117 views

### Questions about interlacing polynomials

If we have a finite set of real-rooted polynomials of the same degree such that any two of them have a common interlacing then does it imply that this set has a common interlacer?
Lemma $4.2$ (top of ...

**0**

votes

**0**answers

57 views

### Permutations with restricted pairwise intersections

Preparing problem sets for an exam I encountered the next question:
Assume we have $n$ topics and $k_1$ different problems on the first topic, $k_2$
on the second, etc. We need to generate problem ...

**13**

votes

**0**answers

186 views

### A symmetry of lattice paths

The number of $n$-step NSEW lattice paths from $(0,0)$ to $(a,b)$ that intersect the line $y=k$ precisely $t$ times is independent of $k$, for $0\leq k\leq b$, where we assume $b\geq0$ for simplicity.
...

**10**

votes

**3**answers

380 views

### Enumerating all arrangements of intervals with given lengths

Suppose I am given a set of $n$ intervals, each having length $\ell_i$. Is there a bound on the number of possible orderings of their left and right endpoints? For example, if each interval is ...

**5**

votes

**2**answers

191 views

### What upper bounds are known on the number of non-isomorphic cycle matroids?

For $n\in\mathbb{N}^{+}$, let $c_{n}$ denote the number of simple non-isomorphic cycle matroids of graphs on $n$ vertices. That is, let
$$A(n)=\{M(G)\;;\;G\text{ is a graph on }n\text{ vertices}\},$$
...

**11**

votes

**2**answers

262 views

### Number of matchings of even cycles

By doing some calculations on the generating function of matching polynomials of cycles I made the following interesting observation:
For all positive integers $n>1$ and $k <n $, the number of ...

**3**

votes

**0**answers

77 views

### ``de-polarizing" a univariate P-recurrence

Is every univariate P-recurrence the diagonal of a constant coefficient multivariate recurrence?
For example, the Delannoy numbers satisfy $n d(n) = 3(2n-1) d(n-1)-(n-1) d(n-2)$, and it is the ...

**7**

votes

**0**answers

270 views

### How many solutions $\pm1\pm2\pm3…\pm n=0$

As the title said, I'm very interested how many variants to choose $n$ signs from all $2^n$ variants when expression lead to zero. I tried to get recurrent formula but nothing happened.

**12**

votes

**0**answers

300 views

### The number of labeled pairs of edge disjoint trees and related questions

I wonder what is known on the following:
1) What is the number $T_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ with $n$ labelled vertices?
2) (harder, it seems) What ...

**6**

votes

**1**answer

279 views

### Rational generating function and recursion

Let $\lambda$ denote a hook of size $d$ and $c(\Box)$ the content of $ \Box \in \lambda $. Let $ \text{Hooks}(d) $ be the set of hooks with $d$ boxes. Define
\begin{align}
B(d)&=
\frac{1}{d!} \...

**5**

votes

**1**answer

171 views

### Largest number of points one can pick in finite projective space without getting three on a line

Consider the projectivization $\mathbb P\mathbb F_p^n$ of $\mathbb F_p^n$. How large a set $B \subseteq \mathbb P \mathbb F_p^n$ can I pick so that no three points of $B$ lie on the same line?

**4**

votes

**1**answer

179 views

### Hankel determinant evaluation of special lattice paths

Let $n$ be a positive integers and $T=T_{n,n}$ be the $n\times n$ table in the first quadrant composed of $n^2$ unit squares, whose $(x,y)$-blank is locate in the $x^{th}$-column ...

**5**

votes

**1**answer

149 views

### Result attribution for eigenvalues of a matrix of Pascal-type

A few years ago, I wanted to cite a result in a paper, for which I could not find a reference. I ended up not using the full strength of it, and the part that I needed could be easily proved. Still, I'...

**2**

votes

**0**answers

77 views

### Counting Cycle Vertex Covers on Hypercube

Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle ...

**4**

votes

**1**answer

247 views

### A Geometric Combinatorial/Graph Theory Question

I have a combinatorics problem that seems pretty general - I'd be surprised if the answer is not known. Unfortunately, I can't seem to solve it.
The question concerns the following situation: ...

**4**

votes

**0**answers

161 views

### Counting “deflected” permutations: Part II

This is the second sequel to my earlier question on MO. Although the the current problem appears very similar, the answer is certainly different as experiments indicate.
As usual, let $\mathfrak{S}_n$...

**4**

votes

**1**answer

154 views

### Counting “deflected” permutations: Part I

Let $\mathfrak{S}_n$ denote the group of permutations on $\{1,2,\dots,n\}$. Now, introduce the sets
$$\mathcal{A}_n^{(k)}:=\{\pi\in\mathfrak{S}_n: -1\leq \pi(j)-j\leq k,\,\forall j\}.$$
I would like ...

**4**

votes

**1**answer

128 views

### Counting block-equivalent permutations

Consider the group $\mathfrak{S}_n$ of permutations on the letters $\{1,2,\dots,n\}$.
We say two permutations are b-equivalent, $\pi_1\,\pmb{\sim^b}\,\pi_2$, if one can be determined from the other ...

**11**

votes

**0**answers

413 views

### Wilf's conjecture: complementary Bell numbers

The complementary Bell numbers or Uppuluri-Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by
$$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$
Definition. Fix an integer $m\geq0$....

**13**

votes

**3**answers

1k views

### A “quantum” identity: in search of a proof -Part II

As usual, denote $[n]_q=1+q+\cdots+q^{n-1}=\frac{\,\,1-q^n}{1-q}$ and $[n]_q!=[1]_q[2]_q\cdots[n]_q$. Furthermore, we write
$$\binom{n}k_q=\frac{[n]_q!}{[k]_q!\cdot[n-k]_q!}.$$
As a follow up on this ...