Distinguishable and Indistinguishable
eharetea

Distinguishable and Indistinguishable boxes and objects. Combinations and permutations. Placing objects into boxes.

Distinguishable and Indistinguishable boxes and objects. Combinations and permutations. Placing objects into boxes.

Date Created:Thursday October 30th, 2008 05:18 PM
Date Modified:Wednesday November 05th, 2008 12:52 AM


PERMUTATIONS
Finding permutations of objects is found by the function

tex: \displaystyle P(n,k)=\frac{n!}{(n-k)!}

where n is the number of elements to choose from and k represents the number objects in an ordered arrangement.
(define (permute n k)
  (/ (factorial n) (factorial (- n k))))

COMBINATIONS
tex: \displaystyle C(n,k) = {n \choose k} = \frac{P(n,k)}{k!} = \frac{n!}{(n-k)!k!}

(define (choose n k)
  (/ (permute n k) (factorial k)))
PLACING N DISTINGUISHABLE OBJECTS INTO K DISTINGUISHABLE BOXES

Since there is k choices for n objects:
tex: \displaystyle k^n

(define (d-to-d n k)
   (** k n))

PLACING N INDISTINGUISHABLE OBJECTS INTO K DISTINGUISHABLE BOXES

Since there are n balls, and k-1 walls:
tex: \displaystyle C(n,k) = {n+k-1 \choose n}
(define (i-to-d n k)
  (choose (+ n k (- 1)) k))

PLACING N DISTINGUISHABLE OBJECTS INTO K DISTINCT OBJECTS

tex: k_i in box tex: i where tex: i \in \{1,2,\cdots,n\} and tex: k_1 + k_2 + \cdots + k_n = n

tex: \displaystyle \frac{n!}{k_1!k_2! ... k_n!} = {n \choose k_1,k_2,...,k_n}

(define (d-to-d-with-rep n list-k)
  (/ (factorial n) (accumulate * 1 (map (lambda (y) (factorial y)) list-k))))



Downloads:
Download: boxes.scm 1 KB

Please login or Click Here to register for downloads
Creative Commons License
Distinguishable and Indistinguishable by Dan Lynch
is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
Based on a work at www.3daet.com
Permissions beyond the scope of this license may be available at http://www.3daet.com