# Questions tagged [bijective-combinatorics]

The bijective-combinatorics tag has no usage guidance.

28
questions

**4**

votes

**1**answer

148 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$, ...

**6**

votes

**0**answers

202 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$-...

**6**

votes

**0**answers

105 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 ...

**10**

votes

**0**answers

296 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**

vote

**1**answer

219 views

### A combinatorial problem about partitions [closed]

A partition of $n$ is a unordered list, whose sum is exactly $n$.
The total number of $2$’s in all partitions of $n$ is equal to the total
number of singletons in all partitions of $n−1$. A singleton ...

**14**

votes

**2**answers

828 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 ]>, &...

**9**

votes

**5**answers

806 views

### The number of ways to merge a permutation with itself

Let $\sigma$ be a permutation of $[k]=\{1,2, \dots , k\}$. Consider all the ordered triples $(\pi, s_{1},s_{2})$, such that $\pi$ is a permutation of length $2k-1$ that is a union of its two ...

**6**

votes

**1**answer

227 views

### Enumerating subspaces of $\mathbb{F}_q^n$ in terms of words and inversions

When $q$ is a prime power, then on the one hand the $q$-binomial coefficient $\binom{n}{k}_q$ equals the number of $k$-dimensional subspaces of $\mathbb{F}_q^n$, and on the other hand it is the ...

**2**

votes

**0**answers

283 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{...

**10**

votes

**1**answer

264 views

### Is there a bijective proof of an identity enumerating independent sets in cycles?

Let $C_m$ be the cycle with $m$ vertices, defined so that $C_1$ has a self-loop on its unique vertex. Let $p_m$ be the generating function enumerating the number of ways to choose $k$ vertices in $C_m$...

**6**

votes

**2**answers

205 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 ...

**4**

votes

**0**answers

196 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{...

**4**

votes

**1**answer

297 views

### Bijection between noncrossing matchings on $2b$ points and Standard Young Tableaux of size $2 \times b$

I'm currently reading a review article called Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance by Jessica Striker. In this article, Striker writes that there is a ''nice'' ...

**30**

votes

**1**answer

1k views

### Mysterious symmetry - in search for a bijection

I have a mysterious symmetry that I have not managed to prove.
First some definitions (see picture below)
Fix a partition that fit in a staircase shape with $n$ rows.
There are $Catalan(n)$ such ...

**6**

votes

**1**answer

203 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 ...

**9**

votes

**1**answer

531 views

### Curious Catalan convolutions

Question. Do these identities involving even-index Catalan numbers have a known combinatorial interpretation? They look as though they should. I haven’t seen one in the literature.
$$\sum_{a+b=n}C_{...

**14**

votes

**2**answers

457 views

### Automated search for bijective proofs

In enumerative combinatorics, a bijective proof that $|A_n| = |B_n|$ (where $A_n$ and $B_n$ are finite sets of combinatorial objects of size $n$) is a proof that constructs an explicit bijection ...

**14**

votes

**0**answers

232 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.
...

**12**

votes

**0**answers

245 views

### Bijective proof of an identity involving number of standard Young tableaux and semistandard tableaux

Question. Can you find a bijective proof of the identity
$$ \operatorname{dim}(S^{\lambda} \mathbb{C}^m)\ \operatorname{dim}(S^{\lambda'} \mathbb{C}^n) \ f^{n^m}
= \dim \Lambda^p (\mathbb{C}^m \...

**8**

votes

**1**answer

271 views

### Bijective proof of formula for rooted binary forests

For $n\ge 1$, let $f(n)$ be the number of rooted complete (unordered) binary trees with $n$ leaves labeled from $1$ to $n$ ("complete binary" means that every vertex has either $0$ or $2$ children and ...

**3**

votes

**2**answers

513 views

### Is there a combinatorial interpretation or bijective proof for this Catalan number identity?

Is there any combinatorial interpretation or bijective proof for this identity
$$2C_n=4{2n \choose n}-{2n+2 \choose n+1}$$
where $C_n$ is the sequence of Catalan numbers?

**11**

votes

**2**answers

561 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 ...

**6**

votes

**3**answers

2k views

### Permutations with all cycles odd length and permutations with all cycles even length

If $n$ is even, then the number of permutations of $n$ in which all cycles have odd length equals the number of permutations of $n$ in which all cycles have even length. This fact is easily proved, ...

**23**

votes

**4**answers

1k views

### Dividing by two in the category of vector spaces

Does every invertible linear map $M$ between $V \oplus V$ and $W \oplus W$ naturally yield an invertible linear map $L$ between $V$ and $W$?
Here "naturally" means "in an $GL(V) \times GL(W)$-...

**2**

votes

**1**answer

419 views

### A Simple Bijective Proof Of Stanley's Hook-Content Formula for Hook Shapes

this is my first post on math overflow so I hope it goes well. I believe I have a fairly simple bijective proof for Stanley's Hook-Content Formula in the case of hook shapes. I wanted to see if ...

**13**

votes

**1**answer

897 views

### Two to the power of a triangular number: bijections

The numbers $2^{n(n+1)/2}$ come up in various enumerative contexts. In addition to the trivial example (bit-strings of length $n(n+1)/2$) and the old example of domino tilings of Aztec diamonds (...

**3**

votes

**1**answer

183 views

### Matching in the Boolean Algebra

We consider the Boolean Algebra of the set $[n]=\{1,\dots,n\}$ and the matching $\psi$ from the $m+1$ subsets of $[n]$ into the $m$ subsets of $[n]$ for $(n+1)/2\leq m+1\leq n$, which is used to show ...

**33**

votes

**7**answers

7k views

### Bijection between irreducible representations and conjugacy classes of finite groups

Is there some natural bijection between irreducible representations and conjugacy classes of finite groups (as in case of $S_n$)?