13

For infinite-dimensional vector spaces this not possible. According to this paper of Brenner and Ringel, if $A$ is any principal ideal domain that is not a field or a complete valuation ring, then there is an $A$-module $V$ such that $V\cong V\oplus V\oplus V$ but $V\not\cong V\oplus V$. In particular, if $k$ is a field and $A=k[\mathbb{Z}]=k[x,x^{-1}]$, ...

12

Here is Eytan's proof in more detail. First, there is a canonical way to write the cycle decomposition of a permutation. You order the cycles in descending order based on the largest member they contain, then you order each individual cycle to start with this largest member. An example of a permutation written in this canonical form is
$$(614)(523).$$
...

answered May 19 '15 at 18:11

Qiaochu Yuan

93.4k2929 gold badges333333 silver badges619619 bronze badges

12

Yes, and the original paper is the following.
MR1774748 Reviewed Bóna, Miklós; McLennan, Andrew; White, Dennis Permutations with roots. Random Structures Algorithms 17 (2000), no. 2, 157–167.

11

Division by two, with your naturality condition, is equivalent to division by two in the category of representations of a group:
If $V$ and $W$ are two finite-dimensional representations of a group $G$ such that $V + V = W+ W$, then $V=W$.
As Eric said, this is all about stabilizers. Given no other conditions, there is a $GL(V) \times GL(W)$-equivariant ...

10

I'm glad to see you're interested in this question. A number of people have thought about it including Art Benjamin and myself. The person who seems to have gotten the furthest is Curtis Bennett who came up with a new way to view the rectangular tilings in terms of tilings of a triangle with a lattice path through it which explains those special dominoes ...

9

For the first identity, see additional problem A33 in my book Catalan Numbers. References are given to bijective proofs by Andrews and Nagy.

answered Dec 11 '17 at 1:29

Richard Stanley

34.1k99 gold badges121121 silver badges196196 bronze badges

9

As mentioned in the comments, the FindStat project is aiming at what you want. Concerning the size: it contains currently about 1000 'combinatorial statistics', that is maps $s:\mathcal C_n\to \mathbb Z$ on some (graded) set of 'combinatorial' objects $\mathcal C_n$ and about 150 'combinatorial maps' between two collections. What makes FindStat powerful is ...

7

Oliver Pechenik and I have some partial progress to report. Maybe someone else can see how to supply the remaining missing ingredients.
First, let's establish some notation.
We say your ascent statistic enumerates the $D$-inversions of the permutation $\sigma$, denoted $\iota_D(\sigma)$.
This makes sense since $\iota_\varnothing(\sigma)$ counts the usual ...

6

I think the following might do the trick:
Erdös, Péter L., A new bijection on rooted forests, Discrete Math. 111, No.1-3, 179-188 (1993). ZBL0785.05049.

6

Here is a sketch of a more explicit answer than the one referred to by Eric Wofsey. (The paper by Brenner and Ringel is quite abstract, and obtains results that are both harder and more general.)
In the paper On direct decompositions of torsionfree abelian groups, Jónsson constructs the following failure of division by two in the category of abelian groups:...

answered Apr 10 '15 at 15:12

Greg Kuperberg

50.6k99 gold badges174174 silver badges259259 bronze badges

4

There is an obvious bijective proof of the identity
$$ 2 \binom{2n}{n} + 2 \binom{2n}{n + 1} = \binom{2n+2}{n+1}$$
and also a bijective proof of
$$ 2\binom{2n}{n} - 2 \binom{2n}{n+1} = 2C_n,$$
see the paragraph "second proof" in the wiki page. By combining the two, you get a bijective proof of your identity, in the form
$$ 4 \binom{2n}{n} =\binom{2n+2}{n+1}...

4

Here is another solution, based on the paper "Robinson-schensted algorithms for skew tableaux" by Sagan and Stanley (Darij Grinberg was the one who suggested that this algorithm might work, I'm just filling in the details in a pretty straightforward fashion).
Fix integers $k$ and $n$, and denote $[n]=\{1,2,\dots,n\}$. We say that
$$\pi=\begin{pmatrix}i_1 &...

4

"Domino-shuffling on Novak Half-Hexagons and Aztec Half-Diamonds" by Nordenstam and Young (http://arxiv.org/abs/1103.5054) discusses the classes AD($n$) (domino tilings of Aztec diamonds), NILP($n$) (non-intersecting lattice paths), LT($n$) (lozenge tilings of trapezoids), HH($n$) (perfect matchings of the half hexagon), IPP($n$) (interlacing particle ...

4

There is a very readable bijective proof of this fact in Miklós Bóna's book Walk Through Combinatorics.

3

There is a detailed analysis in Chapters 7 and 8 of Bump and Schilling's Crystal Bases. They work through the connection between RSK and crystals in careful detail, though I don't recall how much detail they give on the variant you are interested in.

3

This comment is about the "natural" part of the question. Suppose we move to Banach spaces so that one naturally expects that if one has a bounded linear isomorphism between $V\oplus V$ and $W\oplus W$, then the corresponding linear isomorphism between $V$ and $W$ should be also bounded. Well, in this case the answer is negative: Gowers and Maurey ...

2

For the hook shapes the following bijection becomes especially simple.
Christian Krattenthaler, Another involution principle-free bijective proof of Stanley's hook-content formula, see here.

rt.representation-theory symmetric-groups symmetric-functions schur-functions bijective-combinatorics

1

If you can understand Mathematica, the following code does what you wish.
It first convert the SSYT to a Dyck path (0 and 1), always starting with a 0,
and then from there, convert to perfect matching.
SSYTToDyckWord[tab_List] := Module[{n = Length[tab[[1]]]},
Table[Boole[! MemberQ[tab[[1]], k]], {k, 2 n}]
];
DyckWordToNoncrossingMatching[dw_List] :=
...

answered May 29 '18 at 18:18

Per Alexandersson

11.2k77 gold badges4848 silver badges9191 bronze badges

1

At first, we reformulate your problem. Denote $m_i=\mu_i-i$, then $m_1>m_2>\dots>m_d$. Consider $d$ bugs $B_1,\dots,B_d$ initially sitting in corresponding points $m_i$ on $\mathbb{Z}$. When we fill a box in $i$-th row, let bug $B_i$ move from its place $x$ to $x+1$. For example, in your first figure the sequence of movements is $(B_3,B_2,B_3,B_1,...

answered Apr 14 '16 at 10:03

Fedor Petrov

63.8k66 gold badges141141 silver badges263263 bronze badges

1

In the wikipedia page on Catalan numbers there is the following:
"There are many counting problems in combinatorics whose solution is given by the Catalan numbers. The book Enumerative Combinatorics: Volume 2 by combinatorialist Richard P. Stanley contains a set of exercises which describe 66 different interpretations of the Catalan numbers."
I guess it is ...

1

One can understand the image of $\psi$ or $\psi|_M$ in terms of the inverse map $\phi$.
$\phi$ maps an $m$ set to an $(m+1)$ set (if possible) in the following way. If $$A=\{i_1,\dots,i_m\}$$ is our $m$-set, we again look at the set of indices for which $i_j -2j$ is minimized $$N(A)=\{j\in\{0,1,\dots,m\}\mid i_j -2j=\min\},\quad i_0:=0$$ but this time we ...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

bijective-combinatorics × 18co.combinatorics × 14

enumerative-combinatorics × 4

reference-request × 3

young-tableaux × 3

catalan-numbers × 3

rt.representation-theory × 2

permutations × 2

symmetric-groups × 2

algebraic-combinatorics × 2

linear-algebra × 1

polynomials × 1

computer-science × 1

random-walks × 1

group-actions × 1

posets × 1

binomial-coefficients × 1

generating-functions × 1

symmetric-functions × 1

definitions × 1

trees × 1

applications × 1

combinatorial-identities × 1

matching-theory × 1

q-analogs × 1