#3 Bijections and Encoding Objects

To a subset \(A\), assign the string \(a_1\ldots a_n\), where \(a_i=1\) if \(i\in A\), and \(a_i=0\) otherwise. From such a string we recover \(A=\{i:a_i=1\}\). Hence this is a bijection. There are \(2^n\) binary strings of length \(n\).

Each path consists of exactly \(5\) steps \(R\) and \(4\) steps \(U\). The step sequence gives a word of length \(9\), and conversely every such word gives a path. Hence the number is \(\binom{9}{4}=126\).

A solution corresponds to a string of \(10\) stars and \(2\) bars: the numbers of stars in the three gaps are \(x_1,x_2,x_3\). Conversely, every such string gives a solution. There are \(\binom{12}{2}=66\) strings.

Since \(x_i\ge1\), set \(y_i=x_i-1\ge0\). Then \(y_1+y_2+y_3+y_4=13\). By stars and bars, the number of solutions is \(\binom{13+4-1}{4-1}=\binom{16}{3}=560\).

To each \(k\)-subset \(A\subseteq[n]\), assign \([n]\setminus A\). It has \(n-k\) elements. The inverse map is again taking the complement, so this is a bijection.

Fix an element \(a\). To each subset \(S\), assign \(S\triangle\{a\}\): if \(a\in S\), remove it; otherwise add it. The size changes by \(1\), so parity changes. The operation is its own inverse, hence a bijection between even-sized and odd-sized subsets.

All \(k\)-subsets of \([n]\) split into two classes. If a subset does not contain \(n\), it is a \(k\)-subset of \([n-1]\): \(\binom{n-1}{k}\) choices. If it contains \(n\), the remaining \(k-1\) elements are chosen from \([n-1]\): \(\binom{n-1}{k-1}\) choices. These classes are disjoint and cover all objects.

The path to \((3,2)\) contains \(3\) steps \(R\) and \(2\) steps \(U\), so there are \(\binom{5}{2}=10\) choices. From \((3,2)\) to \((7,5)\), we need \(4\) steps \(R\) and \(3\) steps \(U\), so \(\binom{7}{3}=35\) choices. The parts are independent, so the answer is \(10\cdot35=350\).

Set \(y_1=x_1-2\), \(y_2=x_2-4\), \(y_3=x_3\), \(y_4=x_4-5\). Then \(y_i\ge0\), and the sum is \(30-2-4-5=19\). The number of nonnegative solutions to \(y_1+\cdots+y_4=19\) is \(\binom{19+4-1}{3}=\binom{22}{3}=1540\).

The no-adjacency condition gives \(a_{i+1}\ge a_i+2\). Then \(b_i=a_i-i+1\) form an ordinary \(5\)-subset of \(\{1,\ldots,14\}\). Conversely, from \(b_1<\cdots

A partition into at most \(k\) parts is represented by a diagram with at most \(k\) rows. Transpose the diagram: rows become columns. Now each row length is at most \(k\), so every part of the new partition is at most \(k\). The inverse transformation is transposition again, hence a bijection.

Write \(n\) ones in a row. To split them into \(k\) nonempty groups, choose \(k-1\) of the \(n-1\) gaps between consecutive ones and place bars there. The group sizes are the summands. Conversely, every composition gives such bars. The answer is \(\binom{n-1}{k-1}\).

There are \(\binom{2n}{n}\) paths in total. A bad path first goes above the diagonal by a step \(U\), landing at a point with \(y=x+1\). Reflect the initial part up to this step in the line \(y=x+1\). This gives a bijection from bad paths to paths from \((-1,1)\) to \((n,n)\), of which there are \(\binom{2n}{n-1}\). Therefore the number of good paths is

\[\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}.\]

There are \(\binom{p+q}{q}\) words in total. The classical reflection bijection shows that the number of bad words is \(\binom{p+q}{q-1}\): a bad word first reaches equality after an initial \(A\)-lead, and reflecting the corresponding initial segment changes one \(A\) into an extra \(B\). Hence the number of good words is

\[\binom{p+q}{q}-\binom{p+q}{q-1}=\frac{p-q}{p+q}\binom{p+q}{q}.\]

Encode an opening parenthesis as a step \(R\), and a closing parenthesis as a step \(U\). In a correct parenthesis sequence, every prefix has at least as many opening parentheses as closing ones, so the number of \(U\)'s does not exceed the number of \(R\)'s. This is exactly \(y\le x\). There are \(n\) opening and \(n\) closing parentheses, so the path ends at \((n,n)\). Conversely, any path with \(y\le x\) gives a sequence whose every prefix has at least as many openings as closings, hence a correct parenthesis sequence.

From a partition into odd parts, group equal odd parts \(q\). If \(q\) appears \(m\) times, write \(m\) in binary: \(m=\sum 2^s\). Replace these \(m\) copies of \(q\) by parts \(2^s q\). For each \(q\), the powers \(2^s q\) are distinct, and different odd \(q\)'s give different parts. Thus we get a partition into distinct parts.

Conversely, write each distinct part uniquely as \(2^s q\), with \(q\) odd, and replace it by \(2^s\) copies of \(q\). This gives a partition into odd parts. The two operations are inverse.

The sum counts even-sized subsets with sign \(+\) and odd-sized subsets with sign \(-\). Fix element \(1\). The map \(S\mapsto S\triangle\{1\}\) changes the parity of the size and is its own inverse. Thus every even subset is paired with an odd subset, and each pair cancels. The sum is \(0\).

From a tree, build a sequence of length \(n-2\): while more than two vertices remain, remove the leaf of smallest label and record the label of its neighbour. Conversely, from a sequence \(c_1,\ldots,c_{n-2}\), reconstruct the tree: at each step take the smallest label not appearing in the current sequence, connect it to \(c_1\), then remove that label from the vertex set and delete \(c_1\) from the sequence. Finally connect the two remaining vertices.

These procedures are inverse: the leaf removed at each step is exactly the smallest label that will no longer appear in the code. Thus trees are in bijection with sequences of length \(n-2\) over \(n\) labels. There are \(n^{n-2}\) such sequences.

Fix a side of the polygon. In any triangulation, there is a unique triangle adjacent to this side; its third vertex splits the polygon into two smaller parts. Similarly, every correct parenthesis sequence is uniquely written as \((A)B\), where \(A\) and \(B\) are correct sequences. Choose the third vertex so that the number of pairs in \(A\) equals the number of triangles in the left part, and \(B\) corresponds to the right part. Applying the same rule recursively gives a bijection. The base case \(n=0\) is clear.

There are \(\binom{a+b}{b}\) paths in total. A bad path first violates the condition by stepping to the line \(y=x+1\). Reflect the initial segment up to this step in the line \(y=x+1\). This gives a path from \((-1,1)\) to \((a,b)\). Such a path must have \(a+1\) steps \(R\) and \(b-1\) steps \(U\), so the number of bad paths is \(\binom{a+b}{b-1}\). Therefore the number of good paths is

\[\binom{a+b}{b}-\binom{a+b}{b-1}=\frac{a-b+1}{a+1}\binom{a+b}{b}.\]