## there is no frigate like a boat

Posted by vlorbik on November 17, 2009

in recent posts i’ve typed out

rather detailed descriptions

of a fairly simple process:

forming lists of all the

permutations of a given

(small) finite set.

four or five elements, say.

any more than five

would be impractical for in-class work

though i can easily imagine assigning a

“neatness counts” *poster* project along

the lines “create a display showing…

exactly once each, prominently and distinctly…

all 720 permutations of the set

{A,B,C,D,E,F}”. you fail if it’s wrong

of course so check it over several times…

*by several different methods* if

possible (usually one settles for two

actually… but this is math ed so

the more the better [let’s pretend]).

so i now propose to look at methods

of *generating* our lists. thus far

we’ve examined what i hope is much

the commonest: **trees**.

given the symbols of {@, ^, *}

(“at, hat, and splat”) to permute.

let’s see if i can draw it

with this typer here.

[tries and fails; that would be “no”.]

to heck with it then. the point is,

you can draw what’s called a tree.

[

this is as good a time as any to mention

that if there were any doubt in anyone’s

mind what the heck i’m going on about

they’d take advantage of the web format

and enter a few well-chosen words into

the search engine of their choice. what

would owen do. quite often i tack “wiki”

onto the end of my search string (i.e.,

my list of words to search *for*) so as

to be taken quickly to the amazingly

useful wikipedia (the pearl of the net).

on “tree diagram” it’s *not* so useful

but you’ll see a real one quick enough

if you do the search. think “family

tree” by the way if you haven’t seen

the connection yet….

]

@

@

^

^

*

*

each pair… the ats, the hats, the splats…

should be imagined… since i’m helpless to

*draw* it… as connected by “branches”

to a “root” to the left of the left margin.

*three* branches at this stage…

one for each of the “objects to be permuted”.

in the next stage, two branches

sprout from each of our current ones:

@^

@*

^@

^*

*@

*^

(the “at” is here imagined as having

sprouted new leaves: one for “hat”

and one for “splat”… and so on down

[*two* leaves for each new set because

there are two “unused” symbols

left to permute]).

there are no more “choices to make”:

we can complete each partial-permutation

at this stage by appending the

only-available-symbol. and of course

we get

@^*, @*^, ^@*, ^*@, *@^, *^@

: i hereby propose to call this

the *tree order* for the

permutations of the symbols

in the (ordered) list [@, ^, *].

note that this “tree” procedure

vividly illustrates the “factorial”

process. there are six orders

because 6 = 3*2*1…

three choices of first letter

(the first set of branches),

two of the next… so on.

this “tree” algorithm is exactly that

of the previous posts; if this isn’t

obvious i urge you (strongly) to

write out the tree for [A,B,C,D]

and compare your result to

(what i’ve already posted)

ABCD

ABDC

ACBD

ACDB

ADBC

ADCB

BACD

BADC

BCAD

BCDA

BDAC

BDCA

CABD

CADB

CBAD

CBDA

CDAB

CDBA

CDAB

DABC

DACB

DBAC

DBCA

DCAB

DCBA

now it’s no coincidence that this

is not only *tree* order but

*alphabetical* order…

also known as “dictionary”

or “lexicographic” order.

this can be very helpful when

alphabetical symbols are used.

alphabetical order is actually a technique

of astonishing power. this is why we must

endure shrill voices *singing* the damn

thing over and over, and even encourage

them to continue until they’re sure they

have it right, and to teach others, and to

correct mistakes whenever they’re encountered.

once you can find words in a dictionary

you’ve got it made: you don’t need

teachers to learn what words mean

anymore. just tools and motivation.

back to permutations.

where i believe something very similar

is going on.

a hugely important point:

“list the permutations”

calls for full credit when

the permutations are given

in *any* order. hard work

for the grader then. too bad.

my {ABCD, ABDC, …, DCBA},

listed alphabetically, is no better or worse

(unless there were more *rules* imposed)

than any other.

i think… vaguely… of our “tree” method

as *top-down*. we’ve got four letters

so we spread ’em out onto different

parts of our working space and work

“down” the list.

by contrast, a “bottom-up” method might

examine a *single* permutation… the

“standard” ABCD, say… and work “up”

from there. as follows.

suppose i decide to “move letters”

in producing new permos from old.

start at the end with D. move it

as far as it’ll go.

ABCD

ABDC

ADCB

DABC

that’s it for strings having A, B, C

in their standard order. what’s next?

well suppose we reposition the C

one step leftward and repeat.

ACBD

ACDB

ADCB

DACB

so on (“reposition” C again and slide the D’s)

CABD

CADB

CDAB

DCAB

and so on (we’ve “gone as far as we can”

moving D’s and C’s only… so B is up next.

and so on:

BACD

BADC

BDAC

DBAC

BCAD

BCDA

BDCA

DBCA

CBAD

CBDA

CDBA

DCBA

notice that

once having “repositioned” C

for the first time we then

“go through a D subroutine”.

we then reposition the C again

and go through the D-subroutine

again. until we can’t repostion C.

we then reposition *B* and go through

the *C-and-D* subroutine

(consisting of running *several* D-routines).

the towers of hanoi should be mentioned around here.

that’s it for now; i hope there’s somebody still following.

exercise. take a hostage and don’t let ’em go

until they satisfy you that they can write out all 24

permuations of {A, ?, 17, *e*}.

## jd2718 said

In my “combinatorics” class (can I really teach that in high school?) every test has at least one list-making exercise.

Point is, skill is crucial. Second point is, it’s really easy, anyone can do it. Third point is, without practice, the second point’s not really true.

Taught derangements (Derangements!) this week, and we got up to D(5) by listing. D(4) they got without me, D(5) required joint effort. But that’s listing! Couldn’t have done it if we hadn’t done our 24s and our 30s (AABBC, or, in my class, VANNA)

Jonathan

## vlorbik said

darn right you can teach combinatorics in HS.

looks like you’re doing rather well at it too.

your class is already way ahead of the

finite-math-for-bs classes i taught.

some of those pre-business students

are pretty well-prepared too and *could*

have handled work at this level.

but we were lucky to get to the 24s & 30s

(…let’s see…

AA NN V

ZY XW U

#comment: the previous line

#comment: is a “hint” for any-

#comment: body seeking to

#comment: understand the next

#comment: line below (but one)

#comment: from first principles

5! / (2! * 2! * 1!)…

vanna would appear to be among the 30’s…)

whatever that means.

students were made to compute the number of *these*…

and i’ve forgotten *their* name (& had to look up

derangement)…

but sure as blazes never to *display* ’em.

so one learns the n! /[ (a_1)!*(a_2)*… *(a_n)! ]

thing… one more obviously-incomprehensible

“formula”…

stayed in MISSISSIPPI a day too long.

## jd2718 said

With one term of “logic” and one term of this stuff, our non-mathy kids come back after a one-term Discrete and say they already knew a large chunk of the material. So I know we do stuff that you guys do.

But what I’m searching for is two things – to do the stuff well, and to pick the stuff to do that has value. Making those lists – that has value beyond math and within math, and glad to hear you do it, too.