Questions tagged [bijective-combinatorics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9 votes
0 answers
158 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 ...
Jukka Kohonen's user avatar
2 votes
1 answer
142 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_{&...
Roland Bacher's user avatar
21 votes
1 answer
705 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 ...
Fedor Petrov's user avatar
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 ...
Dominic van der Zypen's user avatar
1 vote
2 answers
620 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 ...
Brian Hopkins's user avatar
6 votes
0 answers
147 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 ...
Igor Makhlin's user avatar
  • 3,493
5 votes
1 answer
334 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: $...
Sam Hopkins's user avatar
  • 22.5k
2 votes
0 answers
409 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 ...
T. Amdeberhan's user avatar
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 ...
Nate's user avatar
  • 1,992
13 votes
1 answer
581 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 ...
Sam Hopkins's user avatar
  • 22.5k
5 votes
1 answer
215 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$, ...
aorq's user avatar
  • 4,934
6 votes
0 answers
312 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$-...
Sam Hopkins's user avatar
  • 22.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 ...
Per Alexandersson's user avatar
10 votes
0 answers
342 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^...
Alexander Burstein's user avatar
1 vote
1 answer
281 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 ...
oyyj603450138's user avatar
14 votes
2 answers
887 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 ]>, &...
Mare's user avatar
  • 25.7k
11 votes
5 answers
910 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 ...
sdd's user avatar
  • 109
6 votes
1 answer
242 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 ...
Martin Brandenburg's user avatar
2 votes
0 answers
443 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{...
Iosif Pinelis's user avatar
10 votes
1 answer
295 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$...
Mark Wildon's user avatar
  • 10.8k
6 votes
2 answers
267 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 ...
Per Alexandersson's user avatar
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{...
Zhi-Wei Sun's user avatar
  • 14.4k
4 votes
1 answer
391 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'' ...
Joakim Uhlin's user avatar
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 ...
Per Alexandersson's user avatar
6 votes
1 answer
234 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 ...
Alexander Burstein's user avatar
10 votes
1 answer
714 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_{...
Robin Houston's user avatar
17 votes
3 answers
703 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 ...
Timothy Chow's user avatar
14 votes
0 answers
264 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. ...
Robin Houston's user avatar
12 votes
0 answers
317 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 \...
Piotr Śniady's user avatar
8 votes
1 answer
334 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 ...
Timothy Chow's user avatar
4 votes
2 answers
590 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?
Radmir Sultamuratov's user avatar
11 votes
2 answers
633 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 ...
Jordan's user avatar
  • 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, ...
Timothy Chow's user avatar
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)$-...
James Propp's user avatar
  • 19.4k
2 votes
1 answer
502 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 ...
jlimahaverford's user avatar
13 votes
1 answer
926 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 (...
James Propp's user avatar
  • 19.4k
3 votes
1 answer
195 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 ...
Richard's user avatar
  • 243
39 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$)?
Dan's user avatar
  • 1,288