Binomial coefficients

binomial_cfs.clj

;; Grouped by n (0 choose k, 1 choose k, 2 choose k ... 19 choose k)

;; Again, making it harder than it needs to be
(let [binomial-cfs (for [n (range 20)
                         k (range (inc n))]
                     {:n n
                      :k k
                      :nCk (choose n k)})]
  (doseq [n (into #{} (map :n binomial-cfs))]
    (println (map :nCk (filter #(= n (:n %)) binomial-cfs)))))

;; Same as
(doseq [n (range 20)]
  (println (map (fn [k] (choose n k)) (range (inc n)))))

; (1)
; (1 1)
; (1 2 1)
; (1 3 3 1)
; (1 4 6 4 1)
; (1 5 10 10 5 1)
; (1 6 15 20 15 6 1)
; (1 7 21 35 35 21 7 1)
; (1 8 28 56 70 56 28 8 1)
; (1 9 36 84 126 126 84 36 9 1)
; (1 10 45 120 210 252 210 120 45 10 1)
; (1 11 55 165 330 462 462 330 165 55 11 1)
; (1 12 66 220 495 792 924 792 495 220 66 12 1)
; (1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1)
; (1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1)
; (1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1)
; (1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1)
; (1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1)
; (1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1)
; (1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1)

;; Grouped by k (n choose 0, n choose 1, n choose 2, ... n choose 19)
(let [binomial-cfs (for [n (range 20)
                         k (range (inc n))]
                     {:n n
                      :k k
                      :nCk (choose n k)})]
  (doseq [n (into #{} (map :n binomial-cfs))]
    (println (map :nCk (filter #(= n (:k %)) binomial-cfs)))))

; (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
; (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)
; (1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171)
; (1 4 10 20 35 56 84 120 165 220 286 364 455 560 680 816 969)
; (1 5 15 35 70 126 210 330 495 715 1001 1365 1820 2380 3060 3876)
; (1 6 21 56 126 252 462 792 1287 2002 3003 4368 6188 8568 11628)
; (1 7 28 84 210 462 924 1716 3003 5005 8008 12376 18564 27132)
; (1 8 36 120 330 792 1716 3432 6435 11440 19448 31824 50388)
; (1 9 45 165 495 1287 3003 6435 12870 24310 43758 75582)
; (1 10 55 220 715 2002 5005 11440 24310 48620 92378)
; (1 11 66 286 1001 3003 8008 19448 43758 92378)
; (1 12 78 364 1365 4368 12376 31824 75582)
; (1 13 91 455 1820 6188 18564 50388)
; (1 14 105 560 2380 8568 27132)
; (1 15 120 680 3060 11628)
; (1 16 136 816 3876)
; (1 17 153 969)
; (1 18 171)
; (1 19)
; (1)

;; Relation of sizes for a set S and its power set

;; AGAIN, making it harder than it needs to be
(let [binomial-cfs (for [n (range 20)
                         k (range (inc n))]
                     {:n n
                      :k k
                      :nCk (choose n k)})]
  (doseq [n (into #{} (map :n binomial-cfs))]
    (pprint {:n n 
             :power-set (reduce + (map :nCk (filter #(= n (:n %)) binomial-cfs)))})))

;; Same as
(doseq [n (range 20)]
  (println {:n n 
            :power-set (reduce + (map (fn [k] (choose n k)) (range (inc n))))}))

; {:n 0, :power-set 1}
; {:n 1, :power-set 2}
; {:n 2, :power-set 4}
; {:n 3, :power-set 8}
; {:n 4, :power-set 16}
; {:n 5, :power-set 32}
; {:n 6, :power-set 64}
; {:n 7, :power-set 128}
; {:n 8, :power-set 256}
; {:n 9, :power-set 512}
; {:n 10, :power-set 1024}
; {:n 11, :power-set 2048}
; {:n 12, :power-set 4096}
; {:n 13, :power-set 8192}
; {:n 14, :power-set 16384}
; {:n 15, :power-set 32768}
; {:n 16, :power-set 65536}
; {:n 17, :power-set 131072}
; {:n 18, :power-set 262144}
; {:n 19, :power-set 524288}

;; Equivalence classes of n mod 7 (me making things harder than necessary)
(let [n 105
      eq-classes (for [n (range n)]
                   {:n n 
                    :mod7 (mod n 7)})]
  (->> (for [n (range 7)]
         (map :n (filter (fn [m] (= n (:mod7 m))) eq-classes))) pprint))

; ((0 7 14 21 28 35 42 49 56 63 70 77 84 91 98)
;  (1 8 15 22 29 36 43 50 57 64 71 78 85 92 99)
;  (2 9 16 23 30 37 44 51 58 65 72 79 86 93 100)
;  (3 10 17 24 31 38 45 52 59 66 73 80 87 94 101)
;  (4 11 18 25 32 39 46 53 60 67 74 81 88 95 102)
;  (5 12 19 26 33 40 47 54 61 68 75 82 89 96 103)
;  (6 13 20 27 34 41 48 55 62 69 76 83 90 97 104))

;; Equivalence classes of n mod 7 (easier)
(pprint (group-by #(mod % 7) (range 105)))

; {0 [0 7 14 21 28 35 42 49 56 63 70 77 84 91 98],
;  1 [1 8 15 22 29 36 43 50 57 64 71 78 85 92 99],
;  2 [2 9 16 23 30 37 44 51 58 65 72 79 86 93 100],
;  3 [3 10 17 24 31 38 45 52 59 66 73 80 87 94 101],
;  4 [4 11 18 25 32 39 46 53 60 67 74 81 88 95 102],
;  5 [5 12 19 26 33 40 47 54 61 68 75 82 89 96 103],
;  6 [6 13 20 27 34 41 48 55 62 69 76 83 90 97 104]}