### bogart so far (progress report at random)

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.

April 25, 2014 at 4:59 pm

4. express (x)_4 as an ordinary polynomial

5. express x^4 in terms of falling factorial polynomials

April 25, 2014 at 5:48 pm

one bonehead mistake spotted and corrected

(in three “formulas”). never mind the details.