Skip to main content

All Questions

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
14 votes
0 answers
270 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. ...
Robin Houston's user avatar
10 votes
0 answers
349 views

A bijective proof for the odd companion to Shapiro's Catalan convolution

Shapiro's Catalan convolution is the following formula (where $C_n$ is the $n$th Catalan number): $$ \sum_{k=0}^{n}{C_{2k}C_{2(n-k)}}=4^nC_n. $$ In other words, letting $C(z)=\sum_{n=0}^{\infty}{C_nz^...
Alexander Burstein's user avatar
9 votes
0 answers
180 views

Are there fast rank and unrank algorithms for integer vectors under the action of a permutation group?

We are distributing $m$ indistinguishable balls in $k$ numbered boxes $S=\{1,2,\ldots,k\}$. A distribution is a tuple of nonnegative integers $a=(a_1,\ldots,a_k)$ whose sum is $m$. We also have a ...
Jukka Kohonen's user avatar
8 votes
0 answers
260 views

Efficient listing of ASMs

Famously, the alternating sign matrix theorem gives a product formula for the number $a(n)$ of ASMs of size $n$. There are multiple proofs of this formula, all somewhat involved. My question is ...
Igor Pak's user avatar
  • 17k
6 votes
0 answers
188 views

Natural bijection between join- and meet-irreducibles in modular lattices?

A well known property of finite modular lattices is that they have the same number of join-irreducible and meet-irreducible elements. I was wondering if there exists a natural bijection between these ...
Igor Makhlin's user avatar
  • 3,513
6 votes
0 answers
381 views

Reference request: colored Motzkin path interpretation of Catalan numbers

Recall that a Dyck path of length $2n$ is a lattice path in $\mathbb{Z}^2$ from $(0,0)$ to $(2n,0)$ consisting of $n$ up steps $U=(1,1)$ and $n$ down steps $D=(1,-1)$ which never goes below the $x$-...
Sam Hopkins's user avatar
  • 24.2k
6 votes
0 answers
115 views

Distribution of peaks in permutations, after a sorting operation

Let $S_n$ be the set of permutations on $\{1,2,\dotsc,n\}$. A peak-value of $\pi$ is some $\pi_i$ such that $\pi_{i-1} < \pi_i > \pi_{i+1}$, where $1<i<n$. Let $PV(\pi)$ denote the set of ...
Per Alexandersson's user avatar
4 votes
0 answers
225 views

For a combinatorial proof of a symmetric identity

In my paper Supercongruences involving dual sequences [Finite Fields Appl. 46(2017), 179-216], I gave a new symmetric identity which states that if $x+y=-1$ then $$\sum_{k=0}^n(-1)^k\binom xk^2\binom{...
Zhi-Wei Sun's user avatar
  • 15.6k
2 votes
0 answers
413 views

A (really!) cute identity between product of binomials

As an off-shot of my earlier MO question, I have found a "really cute" identity. The connection is revealed in the limit $q\rightarrow 1$. So, I would like to ask: QUESTION. Is there a ...
T. Amdeberhan's user avatar
2 votes
0 answers
495 views

Bijective proof of a combinatorial identity: $\sum\limits_{k=0}^n\binom nk^2 \binom k{n-m}=\binom nm \binom{n+m}m$

Identity \begin{equation} \sum_{k=0}^n\binom nk^2 \binom k{n-m}=\binom nm \binom{n+m}m \tag{1} \end{equation} was used in an answer here. As shown in that answer, (1) easily reduces to \begin{...
Iosif Pinelis's user avatar