#3 Combinations

Ordered selection gives \(5\cdot4=20\) ways, but each pair is counted twice. Answer: \(10\).

There are \(2^4=16\) subsets. One is empty, so \(15\) are nonempty.

We get \(\binom{7}{3}=7\cdot6\cdot5/3!=35\).

Each choice of \(3\) elements corresponds to the choice of the \(7\) elements not taken. This is a bijection, so the numbers are equal.

Choose \(2\) positions out of \(6\). Answer: \(\binom{6}{2}=15\).

Choose the girls in \(\binom{5}{2}=10\) ways and the boy in \(4\) ways. Total: \(40\).

We get \(\binom{5}{2}\binom{4}{2}+\binom{5}{3}\binom{4}{1}+\binom{5}{4}=10\cdot6+10\cdot4+5=105\).

Any two vertices determine a segment: \(\binom{12}{2}=66\). Among these are \(12\) sides. Therefore there are \(66-12=54\) diagonals.

Total: \(\binom{10}{4}=210\). Without top students, choose \(4\) from the other \(7\): \(\binom{7}{4}=35\). Answer: \(175\).

Let \(a_1

The string consists of \(8\) ones and \(2\) dividers, \(10\) symbols total. Choose the divider positions: \(\binom{10}{2}=45\).

Let \(x'=x-1\), \(y'=y-1\), \(z'=z-1\). Then \(x'+y'+z'=7\) in nonnegative variables. Answer: \(\binom{9}{2}=36\).

Count \(k\)-element subsets of an \(n\)-element set. The special element is either not chosen: \(\binom{n-1}{k}\), or chosen: \(\binom{n-1}{k-1}\). The sum of these disjoint cases gives all subsets.

A team of \(3\) can contain \(3,2,1,0\) boys. These cases are disjoint. In each case choose the required number of boys and girls, giving the stated sum.

For chosen \(a_1<\cdots

Total: \(\binom{20}{4}=4845\). There are \(16\) numbers not divisible by \(5\), so subsets with no multiple of \(5\): \(\binom{16}{4}=1820\). Answer: \(3025\).

Cases: \(3\) boys and \(2\) girls: \(\binom{6}{3}\binom{5}{2}=200\); \(4\) boys and \(1\) girl: \(\binom{6}{4}\binom{5}{1}=75\); \(5\) boys: \(\binom{6}{5}=6\). Total: \(281\).

Choose \(3\) vertices from \(9\). Answer: \(\binom{9}{3}=84\).

Let \(x'=x-2\), \(y'=y-3\). Then \(x'+y'+z=7\), all variables nonnegative. The number of solutions is \(\binom{9}{2}=36\).

Cases: \(3\) red and \(2\) blue: \(\binom{10}{3}\binom{8}{2}=3360\); \(4\) red and \(1\) blue: \(\binom{10}{4}\binom{8}{1}=1680\); \(5\) red: \(\binom{10}{5}=252\). Total: \(5292\).

Consider all \((r+1)\)-element subsets of \(\{1,\ldots,n+1\}\). There are \(C(n+1,r+1)\). If the largest element is \(t+1\), where \(r\le t\le n\), then the other \(r\) elements are chosen from the first \(t\) elements: \(C(t,r)\) ways. Summing over \(t\) gives the left side.

After choosing \(1\), choose \(4\) more numbers from \(\{3,\ldots,15\}\) with no adjacency. This is an interval of length \(13\). The number of ways to choose \(4\) nonconsecutive elements from \(13\) is \(\binom{13-4+1}{4}=\binom{10}{4}=210\).

The possibilities are \(2\) boys and \(4\) girls, \(3\) and \(3\), \(4\) and \(2\). We get \(\binom{8}{2}\binom{7}{4}+\binom{8}{3}\binom{7}{3}+\binom{8}{4}\binom{7}{2}=28\cdot35+56\cdot35+70\cdot21=4410\).

It is enough to split all subsets into \(6\) chains, because then \(7\) chosen subsets hit one chain twice by the pigeonhole principle. For example, take the chains \(\varnothing\subset\{1\}\subset\{1,2\}\subset\{1,2,3\}\subset\{1,2,3,4\}\); \(\{2\}\subset\{2,3\}\subset\{2,3,4\}\); \(\{3\}\subset\{1,3\}\subset\{1,3,4\}\); \(\{4\}\subset\{1,4\}\subset\{1,2,4\}\); and the singleton chains \(\{2,4\}\), \(\{3,4\}\). Any two sets in one chain are comparable by inclusion.