Vlorbik's Diner

son of owen's cooking show

Archive for the ‘Permutations’ Category

works in progress

Posted by vlorbik on May 22, 2016

Photo on 5-22-16 at 9.44 AM

the twenty-four heptagons can of course each be
“rotated” seven ways (in such a way that faces
are taken to faces… and so on [vertices to
vertices, squags to squags…]). hold on there.
what’s a squag, you say. well, a blend, a blur,
or the ideal.
anyhow, 24*7=168; these diagrams, then (were they
complete) would display (all of the) 168 ways to
“rearrange the colors” of MRBGPYO in such a way
that squags stay squags.

how do i turn off auto-“correct”?
it is impossible to work under these conditions.
when i say squag i mean squag and if the typer
won’t let me do it, we’re through.

Photo on 5-22-16 at 9.34 AM

Posted in DAADD, Permutations | 1 Comment »

mr. big pie, oh! (from ohio)

Posted by vlorbik on April 29, 2014

Photo on 2014-03-14 at 16.06

Photo on 2014-04-29 at 11.56

mud, red, blue,
green, purple, yellow,

there is one ideal: mud.

Posted in DAADD, Permutations | Leave a Comment »

the chinese room

Posted by vlorbik on November 18, 2009

this moving-around-of-letters
activity of the past couple of
rambles is, or could and (i hope
someday to convince *some*body)
should be, as foundational
in the study of mathematics as
elementary arithmetic (+, -, *, 1/n) or
compass-and-straightedge constructions.

“trust the code” shall be
the whole of the law whenever
*i* set up as math dictator.

this means symbol-by-symbol
every-keystroke-perfect *code*
is, first of all our *subject matter*
when we’re studying algebra
every bit as much as it is for its
johnny-come-lately derivative
“computer programming” (whatever
the proper euphemism is these days).

enforcing this level of attention to
detail *without* a computer turns out
to be quite difficult. one of the great
frustrations of my life is that *with*
a computer you can pretty much get
*any*body to perform rituals of
*arbitrary* complexity as long
as no actual *reasoning* is involved
just by convincing them that there’s
a paying job in it for them somewhere
if only way down the line behind all
those other poor desparate bastards
that already graduated and have nothing
better to do now but spy on *them*.

but computers are are hard.
to pay for. to understand.
and altogether *impossible*
to maintain for long.

whereas the game
is “simple things first”.
(another fine game is
“don’t let machines
tell you how to live”.
this one’s *much* harder.)

*you can do this*.
what’s more, having done it…
and had the right *conversations*…
you’ll be darn *sure* you can.
and when anybody else…
human or robot overlord
or one of the many blends
emerging all around us daily…
has it *wrong*, you’ll *know*.

here is power.
*that*’s what the simplicity is for.

let me go ahead here and admit that
there’s plenty of good math you can do
*without* this almost-machine-code
letter-by-letter detail-oriented
*algebra* stuff.

i was an algebra *major*. so i’m biased.
anyway, logicians are worse. but no. really.
this is the stuff that’ll make you *good*.

story-of-the-blog-so-far stuff.
last winter when i was blogging
about my math148 precalculus class
(as i think of it; three classes really),
i devoted quite a bit of attention to
finding and implementing the “right”
for, what was one of
the big themes of the course,
transformations of the xy-plane.

here as maybe nowhere else
one has an opportunity to *use*
the “points as ordered pairs”
point-of-view so sloppily
developed throughout math101.

because the centerpiece
in everybody *else’s* imagination
seems to be the xy-plane
itself… the admittedly epoch-making
observation that by laying down
co-ordinates over a euclidean plane
you get a cartesian plane and all
of a sudden equations have *pictures*.

ooo. aaah.

and these pictures are all well and good
and the basis for the scientific revolution
whether *i* like it or not and all that.

the kids don’t get it. and won’t
until they believe they can. and
as to “functions as sets of ordered pairs”,
the examples given typically…
graphs of polynomials and whatnot…
have manymany scary confusing aspects
already known by the audience to be
well beyond their comprehension.

so it’s… well… just *logic*
(not *rocket science*[!]): simple
things first. confused about why
some “transformation” (that doesn’t
even have a proper name, let
alone appropriate symbol)
causes “it” (the graph of…
something… but “it” isn’t usually
any one thing in these discussions)
to *change* in some particular way?
well, how about a bunch of highfalutin
*technical terms* that you know very
well *you* don’t know (and have no
very good reason to be sure about
the teacher)? that’ll sure be useful.
(depending on your goals.)

confused about A, B, and C?
*where*, precisely?
how did *yours* look?

in the *spirit* of “keep it simple”
i now propose to ramble some more
about the “simplest interesting case”
of permuting the elements of a set:
the case of *three* elements.


here are two isomorphic “strings”.

“isomorphic” means “having the same form”.
that the strings… lists of symbols…
*do* have the same form
in some sense is probably obvious to
any reader. heck, six groups of three.
but more than this.

the set isomorphism
A \rightarrow X
B \rightarrow Y
C \rightarrow Z
“induces” (what i’m here calling)
an isomorphism of lists:
replacing each left-hand object
wherever it appears in
our first string with the
corresponding right-hand object
produces the second string.

note that “isomorphism of sets”
is (and deserves to be) standard language
for the kind of one-to-one (and “onto”)
function we’ve displayed here.
two (finite) sets “are isomorphic”
as soon as they have the same number
of elements.

but there will be many different
isomorphisms between any
pair of isomorphic sets.
indeed… theorem 1!… there’ll
be n! (en-factorial) of ’em
between any pair of n-element
sets. (you see this, right?…
remember that factorials count

A \rightarrow X
B \rightarrow Y
C \rightarrow Z

A \rightarrow X
B \rightarrow Z
C \rightarrow Y

A \rightarrow Y
B \rightarrow X
C \rightarrow Z

A \rightarrow Y
B \rightarrow Z
C \rightarrow X

A \rightarrow Z
B \rightarrow X
C \rightarrow Y

A \rightarrow Z
B \rightarrow Y
C \rightarrow X

now. in the spirit of the introductory
from a couple weeks back.

two exercises are isomorphic
when one can be worked out from the
solution of the other simply by
replacing “letters”.

consider the six isomorphisms
from {A, B, C} to {X, Y, Z}
(as shown above).

for a low pass, write out all six
isomorphisms from {a, b, c} to {x, y, z}.

for a passing grade, write out all
six isomorphisms from {P,D,Q} to {E,I,O}.
let (the particular isomorphism)
P\rightarrow E, D \rightarrow I, Q \rightarrow O
be denoted by “elbowgrease”.
write out the result of applying
elbowgrease to the string PDPDQ.

for a high pass write out the
iso’s from {1,2,3,4} to itself.
what happens if you “apply”
an isomorphism to the result
of the application-of-an-iso’ism?

for a pass with distinction learn
“cycle” notation and how to calculate
with isomorphisms-of-sets considered
as members of the so-called
symmetric group on three elements.

essay question for advanced credit.
we’ve “gone meta” twice in “lifting”
correspondences of sets first
to what we called isomorphisms
of strings, and then to
isomporphisms of exercises.

one could continue to “lift” the
concept to even “higher-level”
groups of data… perhaps introducing
some metaphor along the way to
replace strict symbol-for-symbol

find a pair of textbooks covering
transformations of the plane.
display an “isomorphism” between
the bone-headed wrong ways the
relevant sections of your chosen
texts leave out crucial concepts and
fudge important details.

develop a theory of how this state
of affairs came about. for the
love of god and the gratitude
of generations still to come
do something to change it.

Posted in Exercises, Permutations, Rambles, VME | 4 Comments »

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)

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.


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.


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


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:


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

Posted in Permutations, Rambles | 3 Comments »


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.



more later. madeline’s awake.

Posted in Permutations | Leave a Comment »

never get outta the boat

Posted by vlorbik on November 16, 2009

i first encountered the factorial function
at about age ten. in fact, i recently
acquired a copy of the very book i
leaned about factorials from.
i blogged about it here,
mentioning the (classic!) problem—”four fours”—
i learned about ’em from.
the game is, using only “standard” operations
like powering and rooting and multiplying
and subtracting and whatnot…
and *exactly* four 4’s…
and no other numerals..
to write representations of
small natural numbers.

1 = 44/44
2 = 4*4/(4+4)
3 = (4+4+4)/4
4 = 4*4^(4-4)
and so on. a great game for kids.
(you can see it had something of
an influence on *me*…)

kids of all ages lest that go without saying.

anyhow, sooner or later you’ll get stuck.
two things happen. you give up or you
get mad and start looking more carefully.
okay, three. you can *cheat* and allow
“new” symbols… like factorial (!).

the factorial function “counts permutations”.
in the example that should be given
every time the subject come up
until the student indicates that
they’re already doing it “in their
head” every time it come up already
and you can stop again (already):
the permutations of the elements
of {A, L, T} are

*any* three letters can be used of course;
the permutations of {X, Y, Z}
(i’m being sloppy) are

the point… *a* point anyway…
is that a set of *three* letters
will always have *six* permutations.

one easily sees that this is “because”
6 = 3*2*1. likewise for {A,B,C,D}
one has 4*3*2*1 permutations.

4! = 4*3*2*1 = 24
3! = 3*2*1 = 6
2! = 2*1 = 2
1! = 1 = 1

the “factorial of” a (natural) number…
n, say…
is denoted by “postfixing”
(like some… trouble aplenty…
the symbol “!”
(i pronounce this “bang”
usually in class…
“exclamation point”
has five times the
necessary number
of syllables…).

we now introduce the weird-looking
but not-so-weird-if-you-just-look-closer
convention that
0! = 1
(there’s one way, from anyway
one point of view to “list”
the “elements of” the empty set
[i.e., the set of *no* elements…
the “zero” case of “how many elements?”]:
namely the empty *list*).

we can now (though i consider it highly
optional) define the factorial function

!(0) = 1
!(n) = n*!(n-1) [ n\=0],

a “recursive” definition.
these amuse prepared minds
and horrify the rest.
best not try it on the class as a whole
unless they’ve got some “math maturity”.

really n-factorial is spelled “n!”.
i used !(n)
to be perfectly explicit
about the fact that we
*are* considering a
function on N
(the set of natural numbers
[including zero; rant still
to come unless it’s around
here somewhere.

the point is to know like your own middle name
that when you need to count orderings you’ll
*use* this thing (and to know when you *see* it
what the heck it is).

students that can’t write out all 120
permutations of {E,G,B,D,F} at this point,
and go on to the rest of the course anyway,
are *damaged* thereby
and indeed constitute damage to
their whole class and to society at large.

i don’t like this any better than anybody else.
but what i *really* don’t like is being the only
god-damn doctor of philosophy i know of
saying so on the record at this level of detail.

your philosophy is sick and i’m here to fix it.
oh, cursed spite.

you don’t have to be all tough-guy
this-is-college-kid about it… never mind
the if-you-were-serious-you’d-already-*know*
game that wrecks most math classes
before they even get started…
actually, starry-eyed idealist that i am,
i believe that material much easier
than tying your fucking shoes
can probably be taught even
to the dimmest kid admitted
to your college if that’s what
you actually want to fucking do.

i could be wrong of course.

Posted in Exercises, Permutations, Rambles, Rants | 3 Comments »

use the source luke

Posted by vlorbik on November 15, 2009

the gospel i preach: simple things first.

basic arithmetic, for example, turns out
to possess a bottomless depth… and will
reveal new secrets to any investigator
that can bring it new eyes.

the easiest way to get new eyes is of course
to find a student.

or rather to have students
provided for you as i did at indiana u,
ohio dominican, columbus state cc, ohio state u,
and capital u at various times. finding students
outside ivory tower walls is a new challenge for me.
i’m recruiting. and at reasonable rates too but so far
i haven’t really got anything you could dignify with
the name of “a plan”. or for that matter any students.

but the easiest way to find the depth
is to lend one’s own eyes to old texts.
and start simple.

better to understand arithmetic,
for example, one could and should
investigate (as soon as possible)
modular arithmetic.
the most familiar example
(“clock arithmetic”) uses the
hour-numbers marked on a clockface.
replacing “12” with “0” gives
the commonest mathclass
representation of “the integers
mod 12”:
i’ve “primed” the numerals
representing the elements
of Z_12 (the set of integers-mod-12)
here to emphasize a point…
namely that they are *not*
integers. 3’+5′ = 8′ all right
like anybody would expect but
we also have… what would just
look *horribly wrong* without
the “primes” 8’+7′ = 3′
(because starting at eight
o’clock and waiting seven hours
takes us to three o’clock…
we “throw out multiples of
twelve” to do arithmetic mod 12.)
it turns out you can multiply too.
very important this. turns out if
you use a *prime* number in place
of twelve you get something called
a finite field. manymany
very simple examples to be found
of phenomena whose depth remains
unsounded. the ever-growing subject
of “crypto” more or less *begins*
with the study of these fields
from what i’ve been given to understand.

but that’s not the subject of today’s ramble.
which is counting permutations. and starting simple.

there’s one permututation of one thing.
that’s it.

there are two permutations of two things.
pretty simple still.
and uninstructive.

things get much more interesting
when three things are considered.

this is the key example in understanding
what goes on. but the key *exercise*
is “write out the permuations of
the elements of {W, X, Y, Z}”.
(one will have been given a solution to
“write out the permutations of
the elements of {A, B, C, D}”
already in the body of the text.)

how does it work? well.

the “reason” that the
six permutations of
the elements of the set
{A, B, C} are six
is that 6 = 3*2*1.
(where “star” denotes “times”:
5*3 =15 etcetera).
the point here being that we can
imagine writing our letters
one-at-a-time into three “spots”
“_ _ _”
with *three* choices for the first letter
and *two* (we are, thus far implicitly,
but now by explicit decree, not allowing
ourselves to repeat letters [and moreover
each letter *must* be used]) choices
for the next. finally, there’s one letter
left… our only “choice”. the “3” (A, B, or C),
the “2” (don’t reuse the one you picked!)
and the “1” (whatever’s “left over”)
in 6 =3*2*1 are now all accounted for.

the same reasoning tells us than in the case of four letters
one will have 4*3*2*1 = 24 possible permutations.

one-fourth *of* ’em will start with “A”;
one-fourth with “B”; so on. six each.
so one might write down


first. (the underlines denote
*blank space*… the very model
of “harder than it looks” in my book).

then “go down the A’s column”.
there are six entries…
and B, C, and D
(the “unused” letters so far)…
will each have the same chance
of appearing next: twice each
as it turns out. so fill in two B’s,
two C’s, and two D’s.


likewise for the B’s…
“go down” the column
distributing “missing letters”
(in this case A, C, and D).
and the C’s… finally the D’s.

we’re now at

finally go down each column one more time.
there are two of each “string” so far.
in the first, AB, add the remaining letters
first in their “natural” order (ABCD)
then in the opposite order (ABDC).
continue with this pattern:
two missing letters in each case,
first in the natural then in the opposite
order. go through the whole list.
voila. all twentyfour permutations
of four things. in alphabetic order
no less.

i’ve taught this procedure to dozens.
one-at-a-time, too. somehow seeing me
do it in class doesn’t do a thing *for* ’em
sometimes. the student has to move the pencil
(and wants an expert standing by
to bail out at the first sign of trouble).

sure it’s tedious. but it’s just incredibly necessary.
you can’t do *anything* with certain sections of
very common textbooks until students can rattle off
lists like this.

one way or another. certainly there’s no need
to learn *my* algorithm if you’ve got one
of your own that works. i’d love to have you show me.
better if you show the whole class.

there is nothing for “knowing what you’re talking about”
quite like “being able to write it down”.

Posted in Notations, Permutations, Ring Theory | 4 Comments »