Factorial Formula

The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n:

n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1

With the base case: 0! = 1.

Calculation of 3!

3! = 3 × 2 × 1
3! = 6

Subfactorial (Derangement) Formula

The subfactorial of n, denoted !n, counts the number of derangements of a set of n elements. A derangement is a permutation where no element appears in its original position.

!n = n! × Σ(from k=0 to n) [ (-1)^k / k! ]

This can also be defined recursively:

!n = (n - 1) × [ !(n-1) + !(n-2) ]

With base cases: !0 = 1 and !1 = 0.

Calculation of !3

Using the summation formula:
!3 = 3! × [ (-1)^0/0! + (-1)^1/1! + (-1)^2/2! + (-1)^3/3! ]
!3 = 6 × [ 1/1 + (-1)/1 + 1/2 + (-1)/6 ]
!3 = 6 × [ 1 - 1 + 0.5 - 0.1667 ]
!3 = 6 × [ 0.3333 ] = 2

Proof of Derangements for n=3

For the set {A, B, C} with original order (A, B, C), the derangements are:

1. (B, C, A) - No element in original position
2. (C, A, B) - No element in original position

There are exactly 2 derangements, which matches our calculation of !3 = 2.

Logical Foundations

Propositional Logic

Limitations: Can only handle atomic propositions and their combinations using connectives (∧, ∨, →, ¬). Cannot express quantifiers or internal structure of mathematical objects.

Example: Can represent "3! = 6" as a proposition P, but cannot express the general rule for factorial calculation.

First-Order Logic

Advantages: Adds quantifiers (∀, ∃) and functions. Can express general rules and relationships.

∀n ( (n = 0 → fact(n) = 1) ∧ (n > 0 → fact(n) = n × fact(n-1)) )

Allows formal definition of derangements and their relationship to permutations.

Zermelo-Fraenkel Set Theory

Most robust foundation: Axiomatic system that can formalize all mathematics. Provides framework to define functions, relations, numbers, and recursive structures.

In ZF, the factorial function can be defined via the axiom of recursion, and derangements can be defined using set-builder notation:

!n = |{f ∈ S_n : ∀i ∈ n, f(i) ≠ i}|