# Number and types of functions between two sets

Given two set `a` and `b`, where `a = { x, y, z }` and `b = { 1, 2, 3 }`

* cardinality:
  * |a| = |b| = 3
  * |a⨯b| = 3⨯3 = 9
  * powerset `𝒫(a⨯b)`
    * |𝒫(a)| = |𝒫(b)| = 2³ = 8
    * the distribution of the powerset's elements is indicated by the Pascal's triangle, where the row that encodes it, is indicated by the second number which needs to be equal to the cardinality of the base set. In our example, for the base set `a`, it is |a| = 3, hence we're interested in is 4th row of the Pascal's triangle, the one that contains the sequence `(1,3,3,1)`.
    * |𝒫(a⨯b)| = 2⁹ = 512
* number of relations:
  * total relations: |a𝓡b| = 512 since a𝓡b ⊆ a⨯b
    * 1 null relation, R₀ = ∅
    * 1 total relation, R₅₁₁ = a⨯b
    * other relations: each element of the powerset `𝒫(a⨯b)` represents a relation between `a` and `b`; we need not add 1 for the null (empty) relation since it is repr by the ∅ in the powerset, `𝒫(a⨯b)`
* number of functions:
  * total nr. of functions: 2³ = 8

How many

* total number of functions `a -> b`: 8
  * identity function: 1
  * bijections: 
  * injections
  * surjections (constants)

```
a = { x, y, z }       |a| = 3
b = { 1, 2, 3 }       |b| = 3

|𝒫(a)| = 2³ = 8   𝒫(a) = { ∅, {x,y,z}, {x}, {y}, {z}, {x,y}, {x,z}, {y,z} }
|𝒫(b)| = 2³ = 8   𝒫(b) = { ∅, {1,2,3}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3} }

|a⨯b| = 3⨯3 = 9

|𝒫(a⨯b)| = 2⁹  = 512

a⨯b = { (x,1), (x,2), (x,3)
      , (y,1), (y,2), (y,3)
      , (z,1), (z,2), (z,3) }

Given some base set A, many info about the powerset 𝒫(A) is encoded in the Pascal's triangle. Each row of the Pascal's triangle encodes info about the powerset of a base set whose cardinality is equal to the second number in a row.

Thus, the last row of the sample given below, has the number 4 in that place, indicating that it encodes info about the powerset of any base set whose cardinality is 4. The sum of that row, 1+4+6+4+1 = 16 = 2⁴, amounts to 16, the same as the formula for the cardinality of a powerset based on the cardinality of a base set, 2ⁿ, but it encodes a lot more info.

The sequence (1,4,6,4,1) indicates that there is:
- 1 set  with 0 elements
- 4 sets with 1 element
- 6 sets with 2 elements
- 4 sets with 3 elements
- 1 set  with 4 elements


      1           = 2⁰ = 1
     1 1          = 2¹ = 2
    1 2 1         = 2² = 4
   1 3 3 1        = 2³ = 8
  1 4 6 4 1       = 2⁴ = 16
 1 5 A A 5 1      = 2⁵ = 32
1 6 F J F 6 1


┌ 1 set with 0 elements
│  ┌ 3 sets with 1 element
│  │  ┌ 3 sets with 2 element
│  │  │  ┌ 1 set with 3 element
1  3  3  1
│  └ n   │
└───┬────┘
    8 elements in the powerset


n is the cardinality of the base set


─  ┌ ┬ ┐  ├ │ ┼ ┤  └ ┴ ┘




A -> B
1       2         3       4         5       6         bijections
x ⟼ 1  x ⟼ 1    x ⟼ 2  x ⟼ 2    x ⟼ 3  x ⟼ 3
y ⟼ 2  y ⟼ 3    y ⟼ 1  y ⟼ 3    y ⟼ 1  y ⟼ 2
z ⟼ 3  z ⟼ 2    z ⟼ 3  z ⟼ 1    z ⟼ 2  z ⟼ 1
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mandober.gitbook.io/math-debrief/260-function-theory/topics/number-of-functions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.