If $A = \{1, 2, 3, 4, ..., n\}$ and $B = \{x, y\}$, then the number of surjections from A to B is

Set $A = \{1, 2, 3, 4, ..., n\}$ has $n$ elements.

Set $B = \{x, y\}$ has $2$ elements.

A surjection (onto function) requires every element in $B$ to be mapped to by at least one element from $A$. Both $x$ and $y$ must be used.

Each element in $A$ can map to either $x$ or $y$, giving 2 choices per element.

Total functions from $A$ to $B$:

$= 2 \times 2 \times 2 \times ... \text{ (n times)}$

$= 2^n$

A function is not surjective when at least one element in $B$ is not mapped to.

Case 1: All elements from $A$ map only to $x$ (y is unused)

Number of such functions $= 1$

Case 2: All elements from $A$ map only to $y$ (x is unused)

Number of such functions $= 1$

Total non-surjective functions $= 1 + 1 = 2$

Number of surjections from $A$ to $B$:

$= \text{Total functions} - \text{Non-surjective functions}$

$= 2^n - 2$