All Questions
Tagged with bijective-combinatorics reference-request
11 questions
2
votes
1
answer
148
views
A bijection between odd natural integers and compositions
Given an odd natural integer $2a-1$ with $a\geq 1$, associate to it recursively the composition $\psi(1)=\emptyset$ and $\psi(2^{-n}a)+(n+\delta_{>1}(m))$ if $a=2^n m$ with $m$ odd where $\delta_{&...
- 17.9k
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 ...
- 43.2k
8
votes
3
answers
2k
views
Bijective proof for a partition identity
I came across the following cute fact about partitions:
\begin{align}
& |\{\lambda \vdash n \text{ with an even number of even parts}\}| \\[8pt]
& {} - |\{ \lambda \vdash n \text{ with an odd ...
- 2,242
5
votes
1
answer
237
views
Bijection from "black-white balanced" partitions to pairs of partitions
Definition
Call a partition $\lambda$ of an even integer $2n$ "black-white balanced" if the following equivalent conditions are satisfied:
In the usual (Ferrers-)Young diagram of $\lambda$, ...
- 4,994
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$-...
- 24.2k
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^...
- 1,190
14
votes
2
answers
897
views
A canonical bijection from linear independent vectors to parking functions
Call an $n$-vector $v$ in $\mathbb{Z}^n$ cool when it has only entries 0 or 1 and the ones appear in only one block. Thus there are $n(n+1)/2$ such vectors. For $n=3$ they are:
[ <[ 1, 0, 0 ]>, &...
- 26.5k
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{...
- 128k
6
votes
2
answers
299
views
RSK and crystal operators
Is there a good reference on how RSK (and the 3 other variants)
interact with crystal operators on the semi-standard tableaux $(P,Q)$ in the image?
That is, we have biwords, $W$ which are in ...
- 15.8k
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.
...
- 2,896
11
votes
2
answers
652
views
Tableaux with limited rows and complementary skew shapes
Given a partition $\mu=(\mu_1,\mu_2...,\mu_d)$, define $\bar\mu=(\mu_1-\mu_d,\mu_1-\mu_{d-1},...,\mu_1-\mu_2,0)$, the complementary shape in the $d\times \mu_1$ rectangle. Then the number of skew ...
- 336