bogart so far (progress report at random)

April 21, 2014 in Combinatorics, Graphics

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.

Advertisement