## 632

Posted by vlorbik on November 17, 2009

a couple days ago i discussed a

technique for listing all

the permutations of a (small)

set. essentially this.

count the elements.

suppose there are n of ’em.

there are n! (en-factorial) permutations.

our first letter… element…

whatever it is…

will be the first letter (say) *of*

the *same* number of permutations

as will the second letter

(or *any* letter… any element

of the set-to-be-permuted).

so we can say

that each letter begins (1/n)th

(one-enth) of the list.

note that (1/n)*n! = (n-1)!

and write out this many copies

of each letter in columns.

end of step one.

for {E,G,B,D,F}… the example

i “assigned”… my first inclination

is to remark that

{E,G,B,D,F} = {B,D,E,F,G}

(sets do *not* depend on order)

and so one could begin as follows.

B____ D____ E____ F____ G____

B____ D____ E____ F____ G____

B____ D____ E____ F____ G____

B____ D____ E____ F____ G____

.

.

.

B____ D____ E____ F____ G____

(24 rows… there are 5!= 120

permutations to discover

and 1/5 *of* ’em start with B:

so there are 24 B’s. etcetera.)

in step two we’ll fill in the

*second* letter of each permo.

consider the B column only

(for now). there are four

“remaining” letters. each

will appear as the *next*

letter just as many times

as each of the others:

this is 1/4 of the total…

of 24 B’s… and so *six*.

“count by sixes” down the

first column: 6 D’s, then

6 E’s, and so on down.

BD___ D____ E____ F____ G____

BD___ D____ E____ F____ G____

BD___ D____ E____ F____ G____

BD___ D____ E____ F____ G____

BD___ D____ E____ F____ G____

BD___ D____ E____ F____ G____

BE___ D____ E____ F____ G____

BE___ D____ E____ F____ G____

BE___ D____ E____ F____ G____

BE___ D____ E____ F____ G____

BE___ D____ E____ F____ G____

BE___ D____ E____ F____ G____

BF___ D____ E____ F____ G____

.

.

.

BG___ D____ E____ F____ G____

be sure you see what’s going on:

all the ideas are in place i think.

if it’s clear why we’re creating

120 entries in 24 rows and why

we counted by 6’s in this step,

everything else should fall into

place pretty easily i hope.

count by sixes throughout *each*

column, omitting whatever letter

has “already been used” of course.

BD___ DB___ EB___ FB___ GB___

BD___ DB___ EB___ FB___ GB___

BD___ DB___ EB___ FB___ GB___

BD___ DB___ EB___ FB___ GB___

BD___ DB___ EB___ FB___ GB___

BD___ DB___ EB___ FB___ GB___

BE___ DE___ ED___ FD___ GD___

BE___ DE___ ED___ FD___ GD___

BE___ DE___ ED___ FD___ GD___

BE___ DE___ ED___ FD___ GD___

BE___ DE___ ED___ FD___ GD___

BF___ …

.

.

.

BG___ DG___ EG___ FG___ GF___

each column falls into groups

of six unfinished permutations

as of now. each such set has

two letters present and hence

three letters left to “choose

from”. one-third of six is two

so considering “BD” (for example)

we’ll add *two* E’s, *two* F’s,

and *two* G’s.

and likewise for *each* of the

sets-of-six: count off

“missing” letters by twos.

BDE__ DB___ EB___ FB___ GB___

BDE__ DB___ EB___ FB___ GB___

BDF__ DB___ EB___ FB___ GB___

BDF__ DB___ EB___ FB___ GB___

BDG__ DB___ EB___ FB___ GB___

BDG__ DB___ EB___ FB___ GB___

BED__ …

.

.

(one is actually *saying*

“eee, eee, eff, eff, gee, gee”

during this step when working

with a fellowstudent typically).

fill in all the columns by the

same procedure. one now has

a collection of 60 pairs of

three-letter strings.

complete the strings by

attaching their two “missing” letters:

once in one order and once in the other.

of the two BDE’s, for example,

one becomes BDEFG

and the other BDEGF.

this completes the whole ordeal.

BDEFG DBEFG ….

BDEGF

BDFEG

BDFGE

BDGEF

BDGFE

BEDFG

.

.

.

more later. madeline’s awake.

## Leave a Reply