## Archive for the ‘Combinatorics’ Category

combinations with repetition (from a course by one “miguel a.~lerma” at northwestern).

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.

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!