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 ...
- 3,914
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_{&...
- 17k
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 ...
- 98.7k
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 ...
- 44.4k
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 ...
- 4,054
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 ...
- 3,370
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: $...
- 21.5k
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 ...
- 41.2k
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 ...
- 1,992
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 ...
- 21.5k
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$, ...
- 4,914
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$-...
- 21.5k
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 ...
- 15.4k
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,160
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 ]>, &...
- 25.3k
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 ...
- 109
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{...
- 110k
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$...
- 10.7k
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 ...
- 15.4k
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{...
- 14.3k
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'' ...
- 95
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.4k
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 ...
- 1,160
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_{...
- 2,746
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 ...
- 76.8k
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.
...
- 2,746
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 \...
- 381
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 ...
- 76.8k
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 ...
- 336
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, ...
- 76.8k
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)$-...
- 19k
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 ...
- 121
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 (...
- 19k
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 ...
- 243
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$)?
- 1,278