# Questions tagged [bijective-combinatorics]

The bijective-combinatorics tag has no usage guidance.

38
questions

3
votes

0
answers

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

2
votes

1
answer

136
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_{&...

21
votes

1
answer

664
views

### Combinatorial proof of a certain binomial identity

Let $n$, $p$, $q$ be non-negative integers. Then
$$
\sum_{k=0}^n{2k+2p\choose k+p,k,p}{2(n-k)+2q\choose n-k+q,n-k,q}=4^n{2p\choose p}{2q\choose q}{n+p+q\choose n}.\tag{$\heartsuit$}\label{heart}
$$
In ...

1
vote

1
answer

64
views

### Can $\omega$ be parity-separated with finitely many bijections?

We say that a bijection $\varphi:\omega\to\omega$ parity-separates $a\neq b\in \omega$ if $\varphi(a)$ is even and $\varphi(b)$ is odd, or vice versa.
Is there a finite set $\Phi$ of bijections such ...

1
vote

2
answers

566
views

### Terminology for a bijection from a set to itself

A current project uses bijections from a set to itself. (The set is the integer compositions of $n$, i.e., "ordered partitions of $n$," but that doesn't seem pertinent to the question.) Is ...

6
votes

0
answers

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

5
votes

1
answer

289
views

### Bijectively counting labeled trees by number of leaves

A rooted, labeled tree on $n$ vertices is a tree with vertex set $[n] := \{1,2,\ldots,n\}$ in which one vertex has been designated the root. A leaf of a rooted tree is a vertex $v$ for which either: $...

2
votes

0
answers

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

8
votes

3
answers

1k
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 ...

13
votes

1
answer

548
views

### Bijective proof of recurrence for rooted unlabeled trees

Would've been a better question for Christmas than Thanksgiving, but alas...
Let $t_n$ denote the number of rooted, unlabeled trees on $n$ vertices (OEIS A000081). These are the isomorphism classes of ...

5
votes

1
answer

201
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

307
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

113
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

340
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

249
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

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

11
votes

5
answers

893
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

241
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

406
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

291
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

255
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

222
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

363
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

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

10
votes

1
answer

701
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_{...

16
votes

3
answers

612
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

262
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

311
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

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

4
votes

2
answers

586
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

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

8
votes

3
answers

3k
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

493
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

925
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

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

38
votes

7
answers

9k
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$)?