Vlorbik's Diner

son of owen's cooking show

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}.

Advertisements

3 Responses to “there is no frigate like a boat”

  1. 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

  2. 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.

  3. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: