3Daet.com | Distinguishable and Indistinguishable

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

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

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