Counting

Sum of first n natural numbers:
(1 ≤ j ≤ n) Σj = 1 + 2 + 3 + 4 + ...+ (n-1) + n
= n * (n+1)/2
Interesting view 1: The structure of the formula suggests that the sum is half the area of a rectangle of dimension n X n+1
Taking an example, let n=5 the sum (being 15) can be arranged like this:

                1
              1   1
            1   1   1
          1   1   1   1
        1   1   1   1   1

Starting with the arrangement shown below (left) and doing the translation of the bottom half of the arrangement, shows that the sum is half the area of a rectangle of dimension of 5 X 6.

                1
              1   1
            1   1   1
          1   1   1   1
        1   1   1   1   1
        1   1   1   1   1
          1   1   1   1
            1   1   1 
              1   1
                1

= >

                1
              1   1
            1   1   1
          1   1   1   1
        1   1   1   1   1
          1   1   1   1   1
            1   1   1   1
              1   1   1 
                1   1
                  1

The number of ways m objects can be chosen from given n unique objects (n ≥ m) is given by ⁿC_m = n!/ (m! * (n-m)!).

Observation 1:This problem is same as number of ways m slots can be occupied out of n slots (n ≥ m).

Observing an instance of the two problems stated above:

Choosing m (=2) objects out of given n(=6) unique objects:

Given objects: a, b, c, d, e, f. Number of pairs will be 15.
(Strat I) Choosing i^th (1 ≥ i < n) object and form a pair with any other j^th (i < j ≤ n) object :
- (a,b), (a,c), (a,d), (a,e), (a,f)
- (b,c), (b,d), (b,e), (b,f)
- (c,d), (c,e), (c,f)
- (d,e), (d,f)
- (e,f)
(Strat II) Choosing pairs that are adjacent, 1 "unit away", ...,4 "units away":
- choosing adjacent pairs (5):
  - (a,b)
  - (b,c)
  - (c,d)
  - (d,e)
  - (e,f)
- choosing objects that are one "unit away" (4):
  - (a,c)
  - (b,d)
  - (c,e)
  - (d,f)
- choosing objects that are two "units away" (3):
  - (a,d)
  - (b,e)
  - (c,f)
- choosing objects that are three "units away" (2):
  - (a,e)
  - (b,f)
- choosing objects that are four "units away" (1):
  - (a,f)

Occupying m(=2) slots out of available n(=6) slots:

Slots: | | | | | | |. Number of ways 2 slots can be occupied will be 15.
(Strat I)
- adjacent arrangements (5)
  - |.|.| | | | |
  - | |.|.| | | |
  - | | |.|.| | |
  - | | | |.|.| |
  - | | | | |.|.|
- one slot empty between the two occupied slots (4)
  - |.| |.| | | |
  - | |.| |.| | |
  - | | |.| |.| |
  - | | | |.| |.|
- two slots empty between the two occupied slots (3)
  - |.| | |.| | |
  - | |.| | |.| |
  - | | |.| | |.|
- three slots empty between the two occupied slots (2)
  - |.| | | |.| |
  - | |.| | | |.|
- four slots empty between the two occupied slots (1)
  - |.| | | | |.|
(Strat II): Assigning letters a-f to the slots, the number of ways two slots can be occupied is same as the problem solved on the left column.

(Strat II) on the left column is same as the (Strat I) on the right column. (Strat II) on the right column transforms the problem into the one in column one and then (Strat I) on the left column can be applied.

Looking at the formula for sum of first n natural numbers ( n * (n+1) /2 ), it looks just like ⁽ⁿ⁺¹⁾C₂.

Observation 2: Sum of first n natural numbers is same as the number of ways a pair can be formed from (n+1) unique objects.

Let S_n = ⁿC₀ + ⁿC₁ + ⁿC₂ + .. + ⁿC_(n-1) + ⁿC_n.

As per Observation 1 stated above, number of ways m objects can be chosen from n unique objects is same as number of ways m slots can be occupied out of given n slots.

Let the following exploration be viewed with the interpretation of ⁿC_m as finding number of ways m slots can be occupied out of n slots. Taking an instance of the problem (n=6, m=2), the possible arrangements are:

|.|.| | | | |
| |.|.| | | |
| | |.|.| | |
| | | |.|.| |
| | | | |.|.|
|.| |.| | | |
| |.| |.| | |
| | |.| |.| |
| | | |.| |.|
|.| | |.| | |
| |.| | |.| |
| | |.| | |.|
|.| | | |.| |
| |.| | | |.|
|.| | | | |.|

Let the following way of encoding be followed: let '1' represent that a given slot is occupied and '0' represent that a given slot is empty. With this method of encoding the above listing of possible arrangements of occupying 2 slots out of 6 slots is given by:

|1|1|0|0|0|0| ∼ 110000
|0|1|1|0|0|0| ∼ 011000
|0|0|1|1|0|0| ∼ 001100
|0|0|0|1|1|0| ∼ 000110
|0|0|0|0|1|1| ∼ 000011
|1|0|1|0|0|0| ∼ 101000
|0|1|0|1|0|0| ∼ 010100
|0|0|1|0|1|0| ∼ 001010
|0|0|0|1|0|1| ∼ 000101
|1|0|0|1|0|0| ∼ 100100
|0|1|0|0|1|0| ∼ 010010
|0|0|1|0|0|1| ∼ 001001
|1|0|0|0|1|0| ∼ 100010
|0|1|0|0|0|1| ∼ 010001
|1|0|0|0|0|1| ∼ 100001

It is well know that given n bits, total number of things that can be represented is 2ⁿ. Since S_n represents the sum total of number of ways j (ranging from 0 to n) slots can be occupied out of n slots, S_n is 2ⁿ.

Observation 3 Total number of things that can be represented using n bits is the same as the sum total of number of ways j (ranging from 0 to n) slots can be occupied out of n slots. S_n = ⁿC₀ + ⁿC₁ + ⁿC₂ + .. + ⁿC_(n-1) + ⁿC_n = 2ⁿ

Following table demonstrates S₆ = 1+6+15+20+15+6+1 = 64= 2 ⁶:

⁶C₀ = 1

000000

⁶C₁ = 6

000001
000010
000100
001000
010000
100000

⁶C₂ = 15

000011
000110
001100
011000
110000
000101
001010
010100
101000
001001
010010
100100
010001
100010
100001

⁶C₃ = 20

000111
001110
011100
111000
001101
011010
110100
001011
010110
101100
011001
110010
010011
011001
110010
110001
100011
110001
010101
101001

⁶C₄ = 15

001111
011110
111100
011101
111010
010111
111001
100111
110101
101011
101101
101110
110011
011011
110110

⁶C₅ = 6

111110
111101
111011
110111
101111
011111

⁶C₆ = 1

111111