Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
9
votes
0answers
204 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
1answer
106 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$ ...
0
votes
1answer
131 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 -\...
6
votes
0answers
177 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
0answers
98 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
0answers
45 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
1answer
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 ...
11
votes
1answer
372 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
0answers
95 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
1answer
620 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
0answers
223 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
4answers
790 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
0answers
220 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
0answers
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
0answers
34 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
2answers
131 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
1answer
159 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
2answers
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
1answer
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
1answer
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
1answer
149 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
0answers
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
1answer
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
1answer
225 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
3answers
141 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
1answer
89 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
0answers
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
2answers
115 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
0answers
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
0answers
182 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
3answers
379 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 ...
0
votes
0answers
134 views

On a permanent related rank?

Given a matrix $M\in\Bbb Z^{n\times n}$ let $r(m,M)$ be the number of $m\times m$ submatrices of $M$ whose permanent is $\neq0$. Given a matrix $M$ what is the typical behavior of the function $r(m,M)...
5
votes
2answers
183 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
2answers
260 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
0answers
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
0answers
269 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
0answers
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
1answer
278 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
1answer
163 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
1answer
173 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
1answer
148 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
0answers
74 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
1answer
246 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
0answers
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
1answer
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
1answer
127 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
0answers
405 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
3answers
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 ...
13
votes
2answers
1k views

An interesting identity: in search of a proof -Part I

I like the following binomial identity in that the RHS extracts the indeterminate $w$ from the LHS. Question. Can you show that $$\sum_{k=0}^n\binom{x+kw}k\binom{y-kw}{n-k}=\sum_{k=0}^n\binom{x+y-...
5
votes
0answers
158 views

A close cousin of involutions?

If $\mathfrak{S}_n$ denotes the permutation group on $n$ letters, then $Inv(n)=\{\pi: \pi^2=1\}\subset\mathfrak{S}_n$ is the set of involutions or self-inverse permutations. The latter is enumerated ...