All Questions
Tagged with bijective-combinatorics co.combinatorics
35 questions
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 ...
- 15.8k
21
votes
1
answer
766
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 ...
- 109k
18
votes
3
answers
785
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 ...
- 82.7k
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
14
votes
1
answer
647
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 ...
- 24.2k
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
13
votes
1
answer
929
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 (...
- 19.7k
11
votes
5
answers
927
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 ...
- 109
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
10
votes
1
answer
752
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_{...
- 2,896
10
votes
1
answer
302
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$...
- 11.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
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 ...
- 4,219
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
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, ...
- 82.7k
8
votes
1
answer
344
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 ...
- 82.7k
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 ...
- 17k
7
votes
1
answer
253
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 ...
- 63.1k
6
votes
1
answer
239
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 ...
- 1,190
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
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 ...
- 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$-...
- 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 ...
- 15.8k
5
votes
1
answer
413
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: $...
- 24.2k
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
4
votes
2
answers
599
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?
4
votes
1
answer
433
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'' ...
- 95
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{...
- 15.6k
3
votes
4
answers
380
views
Bijections on the set of integer partitions of $n$
I am looking for natural bijections from the set of integer partitions
of $n$ to itself. Of course, I have no definition of natural, but for
the purpose of this question it suffices that it appears ...
- 5,822
3
votes
1
answer
206
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 ...
- 243
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
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
1
vote
2
answers
788
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 ...
- 4,589
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 ...
- 48.9k
1
vote
1
answer
304
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 ...
