## Archive for April, 2014

i just filed the last grades for the semester.

that’s 22 years a pro (albeit a minor-league

player), with two or three years off here and

there (for good behavior; no good deed goes

unpunished… don’t you know there’s a *war*

on?). mostly i worked summers but that appears

unlikely this year. in other words, i’m on

vacation as of this hour. yay me. time for

an ep of the cooking show, i guess.

letting

(i.e., … en-sub-kay stands

for the set of positive integers from

one to kay, in other words)…

and immediately turning right around

and redefining {1, 2, 3, … k} as

“N_k” instead, without all the fancy

type…

last monday’s bogart so far

was a ramble on stirling numbers (of the second

and first kind, SN2K & SN1K) and how it was

to read about ’em in KPB (kenneth p.~bogart’s

_introductory_combinatorics_… or should i

just say “op cit.”?). the notations i’ve just

introduced are mine not bogart’s; this will

persist as i imagine.

now i’ve read that section some more and

its pages are littered with my pencil notes.

for instance,

,

copied out verbatim for the sheer joy

of it, and

* [ (k)_n counts one-to-one F^n’s]

* [ k^n (counts functions)]

* [ S(n,k)k! counts “onto”

functions N_n —->> N_k]

,

written out on p.~50 (where the “falling

factorial” function (k)_n = k!/(k-n)!

is defined) because it seems to me

as clear a summary of what for me

is the heart of the matter as i can

produce at this time: this is what

SN2K’s are *for*, in the context of

some very familiar material (one has

delivered *many*many lectures

bearing on “one to one” and “onto”

functions [and even quite a few

devoted to those topics specifically]…

but typically in a context where

“infinitely many” such functions

will be imagined to “exist”… which

makes “counting” the functions sort

of beside the point).

we could go so far as to *define*

stirling numbers of the second kind by

SN2K(n,k) := #{ f | f: N_n —>> N_k}/k!

.

“count the onto functions and divide by

the permutations of the range”… this

of course give the number of *partitions*

of N_n into k “classes” (regardless of

order “within a given class”).

not that i think this would be a good idea.

okay. like i said on monday, a good section

of KPB (2.3 “partitions and stirling numbers”).

i’ve read over all 18 exercises & even set some up.

heck, some could even be considered “done”.

but really i came to ramble about sections 3.1

and 3.2. or so i thought. but *really* i came

to avoid marking up some pages. and i’ve done

about enough of that. for now.

6.1.5

Let a, b, c, & d

be integers satisfying

b > 0, d > 0, and

ad – bc = 1.

Let n = max{b,d}.

Then a/b and c/d are consecutive

fractions in the n^th Farey Sequence.

Proof:

Since ad-bc=1, we have

ad/(bd) = (1+bc)/(bd), hence

a/b = 1/(bd) + c/d and so

a/b > c/d.

Note that (cf. Corollary 6.2)

ad-bc = 1 also implies

(a,b) = 1 and (c,d) = 1;

our fractions are in

“lowest terms” (and hence

appear in F_n).

Now suppose c/d & a/b are *not* adjacent.

Then there is at least one fraction,

which we may assume is in “lowest terms”,

“p/q”, say, with (p,q) = 1, such that

p/q is *between* c/d and a/b

in the Farey sequence F_n:

F_n = { …, c/d, …, p/q, …, a/b, …}.

Then

q = (ad-bc)q

= adq ___________ – bqc

= adq – bdp + bdp – bcq

= d(aq-bp) + b(dp-cq)

(*).

But a/b > p/q implies

aq – pb > 0, and so

(since the variables are integers)

we have that

aq – bp is greater-or-equal to 1

(aq – bp \ge 1).

The same computation with different

letters shows that

[p/q > c/d] \implies [dp – cq \ge 1].

These inequalities together with (*) give

q = d(aq-bp) + b(dp-cq)

q \ge d + b.

Recall that n = max{b,d}.

It follows that d + b > n.

This gives us q > n, a contradiction

(“p/q” cannot be in F_n with q > n).

Hence a/b and c/d *are* adjacent in F_n; done.

leaving only the “typing it up worse

for the net” to me… the -set

homework i’m about to loosely base my

plain-text solutions on is quite a lovely

thing to look upon… as my versions will

not be. now. make it so.

6.1.3

Let a/b, a’/b’, and a”/b” be consecutive fractions

in the Farey sequence of order n.

(i.e., in

F_n = {0/1, 1/n, …, 1/2, … , (n-1)/n, 1/1}

[for the record… it’s convenient to

have a “symbol” for this sequence;

F-subscript-n is standard but the

text doesn’t include it.]

)

We will show that these fractions

satisfy the “Mediant Property”:

a’/b’ = (a+a”)/(b+b”).

Consecutive “Farey fractions”

satisfy Theorem 6.1 and so

a’b – ab’ = 1 and

a”b’ – a’b” = 1.

Equating the left-hand sides,

a’b – ab’ = a”b’ – a’b”.

Regroup; factor;

“divide through by b'(b+b”)”:

a'(b+b”) = b'(a”+a)

a’/b’ = (a+a”)/(b+b”).

(We are done.)

it turns out (chapter 2, section 3)

that “stirling numbers of the 2nd kind” count

the ways to *partition* an n-element set into k classes:

letting

whenever h is a positive integer (so that “S_h”…

as i propose to call it in ordinary type…

denotes {1, 2, … , h} [and in particular,

S_h has h elements]), we have

.

now, this would be much easier to say

if i had an “onto arrow”. instead of

S(n,k)k! = \sharp \{ f| f: S_n \rightarrow S_k, ({\forall y}\in S_k) ({\exists x}\in S_n) f(x)=y \}

i would’ve had only

S(n,k)k! = \sharp \{ f| f: S_n \ontoarrow S_k \}.

in ordinary type,

f: A—->B

means that f is a function from A to B,

g: A >—-> B

means that g is a *one-to-one* function

from A to B (an “injection”), and

h: A —->> B

means that A is an *onto* function

(a “surjection”) from A to B.

the code for the “distinguished” functions

(one-to-one or onto) is very similar to that

for “ordinary” functions… the symbols differ

*just enough* to mark the relevant distinctions.

this helps to make these “arrows” very easy

to understand and to use; anybody whose work

regularly calls for distinguishing surjections

or injections from “generic” functions would

be *crazy* to *prefer* writing out “f is onto”

or “f is one-to-one”.

of course, no one dares even *try* teaching

’em to undergrads: because a sizable fraction

of any sizable class at any level will insist

on trying to do mathematics *without*

making clear distinctions… particularly

in *writing*.

no, just scribbling “f onto”

somewhere on the page oughta do it.

who am i kidding. just scribbling “onto”

somewhere. “you know what i *meant*…”

i despair.

it turns out there’s a pascal-triangle-like aspect

to S(n,k); one easily sees that

S(n,k) = S(n-1, k-1) + kS(n, k)

and so one may crank out a “SN2K triangle”

1

1 1

1 3 1

1 7 6 1…

forming the k^{th} entry of the n^{th} row

by adding k-times-number-above to

number-above-and-to-the-left

(imagining invisible zeroes as needed).

i’ve penciled in

“1 15 25 20 1”

under bogart’s Table 2.1.

and on and on it goes.

the SN1K number s(n,k)

turns out to be the “k coefficient” in

the polynomial expansion of

(x)_n = x(x-1)(x-2)…(x-n+1).

the “falling factorial” function (k)_n

is already familiar to many students as

(k)_n = nPk = n!/(n-k)!

(and so “counts one-to-one functions”…

“lists” that *don’t reuse* any listed

objects).

then there are a bunch of “summation identities”

allowing us to apply stirling numbers in counting

ways to manipulate various sets (again, one has

the famous “pascal’s triangle” situation ready to

hand as a motivating example of this *kind* of thing).

the “bell numbers” (named for the famous ET).

some exercises. it’s a great section.

i’m particularly grateful to professor bogart for

explicitly remarking that “If you have had linear

algebra, you may recognize that the Stirling numbers

are “change of basis” coefficients.”

well, now that you *say* so, yes.

so *this* is what all the fuss (about

“coefficients in the polynomial expansion”)

is about! it’s all about getting back and

forth between the “standard”

{1, x, x^2, x^3, …}

basis for F[x] (the “space” of polynomials

in x) and the “falling factorial” basis

{(x)_0, (x)_1, (x)_2, …} =

{1, x, (x^2 -x), (x^3 -3x^2 +2x), …}

(which, presumably, arises “naturally”

in certain problems about *listing* things).

why was i not *informed*?

knowing *this*… “SN1K numbers are

change-of-basis coefficients from

falling-factorials to powers-of-ex”…

will allow me (finally) to *remember*

how they’re defined. meanwhile, i’m

that little bit more comfortable with

“summation formulas” in combinatorics

generally. a real good section.

section 3.2 is even *more* exciting.

“polya’s change-making example”

is used to motivate the use of

“generating functions”. this topic

has been sort of a sore spot with me

since *senior year* (a long time ago)

when it was last-on-the-list one

semester in a probability class and

hurried through with no understanding

by me at all. then i’d come across

it from time to time. but never in

the context of “stuff i need, on a

deadline”… and so, until now,

never seriously studied. but now?

it’s starting to sort of make sense.

— the number of “permutations of k things

from a set of n” (“en-permute-kay”, in its

most convenient say-it-out-loud version);

the number of ways to make an (ordered)

*list* of k (distinct) things chosen from

a set of n things. one has known this from,

well, time immemorial. but never written

it out in straight-up *set* notation

until today.

now it’s on page 5 of my “bogart”.

(_introductory_combinatorics_, kenneth

p.~bogart, 1983; mine’s a recent acquisition

from the math complex, once of the

“bertha halley ross collection” according

to its bookplate. that turns out to have

been mrs. *arnold* ross, late of the OSU

[an all-time giant in recruiting new talent

into mathematics, founder of the “ross program”].

you can see from the edges of the pages that

somebody read it up to chapter six and stopped.

they didn’t write on the pages though.

[but that’s being put right now.])

and cranking out suchlike “set code” *is* fun

and easy… for me. showing somebody how to

*read* it? fun but *not* easy. showing some-

body how to *write* it? well… how would i

*know*? (how would *anyone*?)

in one sense, “textbook” exercises.

but in the usual sense, not.

i made up these “exercises” for myself,

but they sure as heck involve a *textbook*.

just now… very much in my usual way…

i made some pencil notes on a textbook page.

there was even a “warm-up”.

my *first* marks on that page…

“page 43”, let’s say… were to

scratch over the first “of” of

In number theory, the function of given in Theorem 2.2 would be called anand replace it with “ordered compositionofkwithnparts, because it gives a list ofnnumbers that add up tok.

*f*“.

because theorem 2.2, as it turns out,

tells us that

Theorem 2.2.The number of functionsffrom a set to the nonnegative integers such that isC(n + k – 1; k).

or, in other words, that

.

and that was, if you will, “exercise 1”:

“restate theorem 2.2 wordlessly”.

this code now appears in the (generous)

margin of page 43 (with the unimaginative

label “THEOREM 2.2”).

exercise 2?

well, the

bit appears *twice* on page 43

centered on a line of its own

(in a “display”, in other words).

so next to the first such display

i wrote out

(

*f* TAKES

*n* VALUES

ADDING UP

TO *k*

)

… where the parens “(“,”)” indicate

big ol’ *handwritten* parens

bracketing the whole “block”

of handwritten “f takes n

values adding up to k” thing;

it fills the “display” space

(to the right of the displayed code)

rather nicely from top to bottom.

so the first “exercise” was of the form:

“translate from english into code”

and the second was of the form

“translate from code into english”.

“write it up in ” will here

be considered *beyond the scope of our
post*… it *is* time for breakfast…

i just couldn’t wait to observe here that such

“translating”, back-and-forth, code-to-language,

language-to-code is a *large part* of “doing math”.

throw in code-to-graph (and back) and get even more.

venn-diagrams back-and-forth to truth tables.

(hey, look. “isomorphisms”!)

anyhow. we’re *always* doing suchlike exercises.

trouble is. what-you-mean-“we”?

*feed* me!

my recent example of bad freshman calculus

was, heaven knows, something egregious.

but *this*! this is something else again.

on another day, i might have just bitten down

and let it go with full credit… the very

kind of thing i have to do dozens of times

a night when i sit down to earn my right

to go on calling myself a math teacher.

ordinary unambitious undergrads

will *never* be made in classes like ours

to write carefully. and they’ll take any

attempt to do it as a violation of their

basic civil rights *as* undergrads and

threaten to vote with their feet.

so you’ve got to play it pretty cool.

even though it might break your heart.

just mark it wrong, again.

and tell ’em why, again.

“CODE IS NOT ENGLISH”

usually doesn’t get points-off

*regardless* of how badly the little

dears have mangled plain sense into

worse-than-meaningless mumbo-jumbo

by using “syncopated style”.

but this example, on this day?

i just couldn’t do it. its author

lost a half a point (out of two).

“f(x) = log_a x = (ln x)/(ln a)

f'(x) = 1/(ln a) * 1/x” …

thus far well and good …

“since the derivative of ln x = 1/x”.

and my first instinct, and indeed my

first move, is to circle the “=”,

write “IS” near it, put a big “X” near

the whole mess so far, and write out

“CODE IS NOT ENGLISH”.

and let it go at that.

like usual.

but, finally, dammit.

if that thing deserves a perfect score

then i’m carl friedrich gauss.

if i *ever* encounter “ln x = 1/x”

*without* letting it bother me,

may my right hand lose its cunning.

take away my mathbooks and send me

to seminary or something; i’ll’ve

quit being a *math* teacher altogether.

the student in question will almost certainly

take my comments for raving lunacy. and so,

i suppose, will some portion of readers of this

post. none of *my* business either way, though,

i suppose. sometimes you’ve just gotta get up

on the net and *vent*. thanks for reading.

by quotiant rule

EXHIBIT A

but this is *senior level* stuff…

“analysis” *not* freshman-calc.

and even *there*, one seldom encounters

such an *explicit* version of the

natural-log-equals-reciprocal fallacy

.

(the “quotiEnt rule”…

or rather, *the* quotient rule…

our subject has fallen into the

“leaving out articles makes it

harder to understand and so is

in my best interest” trap…

has *no bearing* on this [mis]-

calculation [we aren’t diff-

erentiating a fraction (or any-

thing else for that matter)].)

here’s the whole sad story.

math is hard and everybody knows it.

what they *don’t* know is that it’s

nonetheless easier than anything else.

*particularly* when one is trying

to do things like “pass math tests”.

there’s always a widespread (and *very*

persistent) belief abroad in math

classes that trying to understand

what the technical terms mean (for

example) is “confusing” and should

be dodged at every opportunity.

we teachers go on (as we must)

pretending that when we say things like

“an *equation*” or “the *product* law”

we believe that our auditors

are thinking of things like

“a string of symbols

representing the assertion

that a thing-on-the-left

*has the same meaning as*

a thing-on-the-right”

or “the rule (in its context)

about *multiplication*”.

but if we ever look at the documents

produced by these auditors in attempting

to carry out the calculations we only

wish we could still believe we have been

*explaining* for all these weeks?

we soon learn that they have been thinking

nothing of the kind.

anyhow. the example at hand.

calculus class is encountered by *most* of its students

as “practicing a bunch of calculating tricks”.

the “big ideas”… algebra-and-geometry, sets,

functions, sequences, limits, and so on…

are imagined as *never to be understood*.

math teachers will perversely insist on

*talking* in this language when demonstrating

the tricks.

well, the “big ideas” that *characterize*

freshman calc are “differentiation” and

“integration”. for example “differentiation”

transforms the expression “x^n” into the

expression “n*x^(n-1)” (we are suppressing

certain details more or less of course).

this “power law” is the one thing you can

count on a former calculus student to have

remembered (they won’t be able to supply

the context, though… those pesky “details”),

in my experience.

anyhow… long story longer… somewhere

along the line, usually pretty early on…

one encounters the weirdly mystifying

*natural logarithm* function. everything

up to this point could be understood as

glorified sets, algebra, and geometry…

and maybe i’ve been able to fake it pretty well…

but *this* thing depends on the “limit” concept

in a crucial way. so to heck with it.

and a *lot* of doing-okay-til-now students

just decide to learn *one thing* about

ell-en-of-ex

(the function [x |—-> ln(x)],

to give it its right name

[anyhow, *one* of its right

“coded” names; “the log”

and “the natural-log function”

serve me best, i suppose,

most of the time]):

“the derivative of ln(x) is 1/x”.

anything else will have to wait.

but here, just as i said i would,

i have given the student too much

credit for careful-use-of-vocabulary:

again and again and again and again,

one will see clear evidence that

whoever filled in some quiz-or-exam

instead “learned” that

“ln(x) is 1/x”.

because, hey look.

how am *i* supposed to know

that “differentiation” means

“take the derivative”?

those words have *no meaning*!

all i know… and all i *want* to know!…

is that somewhere along the line in

every problem, i’ll do one of the tricks

we’ve been practicing. and the only trick

i know…. or ever *want* to know!… about

“ln” is ell-en-is-one-over-ex. so there.

it gets pretty frustrating in calc I

as you can imagine. to see it in analysis II

would drive a less battle-hardened veteran

to despair; in me, to my shame, there’s a

tendency… after the screaming-in-agony

moments… to malicious glee. (o, cursed spite.)

because, hey, look. if we all we *meant* by

“ln(x)” was “1/x” what the devil would we have

made all this other *fuss* about? for, in

your case, grasshopper, several god-damn *years*?

did you think this was never going to *matter*?

in glorified-advanced-*calculus*? flunking fools

like this could get to be a pleasure.

but how would i know. i’m just the grader;

it’s just a two-point homework problem.

and anyway, that’s not really the *exact* thing

i sat down to rant about.

next ish: *more* bad freshman calc from analysis II.