Question related to Pascal Triangles and Counting Patterns

Question

I was working on two separate problems and came across a potential pattern involving Pascal's triangle. I would like to know if Pascal's triangle applies to either of these problems and if so, is there a formula I can use to come up with these patterns explicitly?

Potential Pattern 1:

Whenever I was counting the number of possible functions between set $A$ and set $B$, where $A=\{a,b,c\}$ and $B=\{0,1\}$

I noticed the following:

There is one function from $A$ to $B$ that sends zero elements to element $1$ in $B$. Three functions from $A$ to $B$ that only send one element in $A$ to element $1$ in $B$. Three functions from $A$ to $B$ that send two elements in $A$ to element $1$ in $B$. One function from $A$ to $B$ that sends three elements in $A$ to element $1$ in B.

Thus we have $1+3+3+1$ possible functions.

Potential Pattern 2:

I was looking at a set of $4$-elements and began generating the elements of its powerset and noticed it has $1$ zero element set, $4$ one element sets, $6$ two element sets, $4$ three element sets and $1$ four element set.

This follows the pattern of $1,4,6,4,1.$

For instance, how can I use a formula to calculate the following: given the power set of a 4-element set, how many three element sets does it have? Could I see an example of how to calculate this with a formula? The answer is 4, but I know that because I wrote all the subsets down and counted them by hand.

Answer 1

For problem nr1:

A function can be thought of as a subset of the so called Cartesian product between two sets. That is $$ f: A\to B, \ f(a)=b $$ can be thought of as a subset of $\{(a,b)\mid a\in A, b\in B\}$ so what you are actually counting here is the number of ways you can create these pairs with some particular restrictions say you would like everything to be mapped to only one specific member of the target domain, that is $B$.

For problem nr2:

You are counting "how many ways can I pick $0$ elements from a set having $n$ elements" this is usually expressed as a so called binomial coefficient $$ \binom{n}{0}=\frac{n!}{0!(n-0)!}=1 $$ for exaample.

How this is tied to the pascal triangle is as follows:

If you number the rows of the triangle starting from $0$ then the $k$th element in $n$th row is $$ \binom{n}{k}=\frac{n!}{k!(n-k)!}. $$

The name binomial coefficient comes from the fact that these numbers represent the coefficients in $$ (a+b)^n. $$ Let us look at an example:

$$ (a+b)^3=1\cdot a^3+3\cdot a^2b+3\cdot ab^2+1\cdot b^3 $$

How come? Well, we are actually counting the number of ways we can pick factors from the sums:

$$ (a+b)^3=(a+b)(a+b)(a+b) $$

so $a^3$ has coefficeint $1$ since there is only one way to pick $3$ "a"s. $a^2b$ has coefficient $3$ since we can pick $2$ "a"s and $1$ "b" in three different ways $$ (\underline{a}+b)(\underline{a}+b)(a+\underline{b}) $$ $$ (\underline{a}+b)(a+\underline{b})(\underline{a}+b) $$ and $$ (a+\underline{b})(\underline{a}+b)(\underline{a}+b). $$

I hope this clarified a bit :)

Answer 2

The numbers in pascal's triangle represent number of combinations... Starting the numbering of rows/columns in zero, the $k^{th}$ element in the $n^{th}$ row in the triangle is given by $\binom{n}{k}$, which is the number of ways you can choose $k$ objects out of a set of $n$ elements. In your case, selecting a function means selecting a certain number of elements in to domain to be mapped on to zero (or one), so you see the connection is immediate.

Answer 3

Yes. Both follow from the binomial theorem:

$$2^n = (1+1)^n = {n \choose 0}1^n + {n \choose 1}1^{n-1}1 + {n \choose 2} 1^{n-2}1^2\dots + {n \choose n}1^n$$

Since the rows of Pascal's triangle correspond to the binomial coefficients, then the sum of the $n$-th row is $2^n$ (numbering the topmost row that only has one 1 with 0).

$2^n$ is indeed the number of functions describes, or the size of the power set.