# Questions tagged [bijective-combinatorics]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
103 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,028
160 views

1 vote
227 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 ...
854 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 ]>, &...
• 22.5k
849 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 ...
• 123
233 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 ...
• 57.2k
332 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{...
• 82.6k
281 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.4k
228 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 ...
• 14.8k
211 views

• 2,616
504 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 ...
• 67.1k
249 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,616
283 views

588 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
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, ...
• 67.1k
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)$-...
• 17.6k
452 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 ...
912 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 (...
• 17.6k
189 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
Is there some natural bijection between irreducible representations and conjugacy classes of finite groups (as in case of $S_n$)?