Archive for the ‘Combinatorics’ Category

probably also in our text somewhere; easier to find here if the net happens to be in a good mood

February 6, 2015 in Combinatorics

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

bogart so far, so far

April 26, 2014 in Combinatorics, Meta

or,
contents-page for
the “combinatorics” category of
_a_grader’s_notes_ (so far).
(in its natural order.)

a couple of good exercises
at random before breakfast (april 17)
handwritten marginal translations:
english-to-code & code-to-english.

hey. this is fun and easy. (april 17)
the ross-collection copy of bogart
(1983) falls into my hands and i begin
to annotate it.

bogart so far (progress report at
random) (april 21) longish.
stirling numbers of the second kind.
(i’ve got it this time at last.)
the “onto arrow” —–>> and its ilk.

a thing unto itself (april 25)
more about KPB2.3
(= bogart \section 2.3).
specifically,”
* [ (k)_n counts one-to-one F^n’s]
* [ k^n (counts functions)]
* [ S(n,k)k! counts “onto”
functions N_n —->> N_k]
“.
also… filling a much-needed gap…
N_k = {1, 2, … ,k}.
(why *is* there no standard symbol
for these amazingly-useful sets?)
{\Bbb N}_k := \{i\}_{i=1}^k

bogart so far, so far (april 26)
this very post, in some weird
go-to-hell-escher-and-back self-
reference-gone-mad. (what’s next,
two spocks at once?)

and that’s it. heck, if it’d been
a *big* project, i’d’ve never taken
it on. BIJAGDH. maybe some day…
maybe today!… i’ll say something
about the infuriating treatment of
“the basic counting functions” or
the amazing “poyla’s change-making
example”. not now.

Advertisement

a thing unto itself

April 25, 2014 in Combinatorics, Rambles

letting
{\Bbb N}_1 = \{1\},{\Bbb N}_2 = \{1,2\},
{\Bbb N}_3 = \{1,2,3\} \ldots
(i.e., {\Bbb N}_k = \{i\}_{i=1}^k… 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,
x^n = \sum_{j=0}^n S(n,j)(x)_j,
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 manymany 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.

bogart so far (progress report at random)

April 21, 2014 in Combinatorics, Graphics

Photo on 2014-04-21 at 13.56

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 S_h = \{i\}_{i=1}^h
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
S(n,k)\cdot k! = \sharp \{ f| f: S_n \rightarrow S_k, ({\forall y}\in S_k) ({\exists x}\in S_n) f(x)=y \}.

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.

hey. this is fun and easy.

April 17, 2014 in Combinatorics, Cool Tricks, Gush

\sharp \{ (v_1, v_2, \ldots , v_k) \in (\{ j\}_{j=1}^{n})^k \mid [a \not= b] \Rightarrow [v_a \not= v_b]\}=
{{n!}\over{(n-k)!}} = \null_n P_k.
— 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*?)

a couple of good exercises at random before breakfast

April 17, 2014 in Combinatorics, Exercises

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 an ordered composition of k with n parts, because it gives a list of n numbers that add up to k.
and replace it with “f“.

because theorem 2.2, as it turns out,
tells us that

Theorem 2.2. The number of functions f from a set {x_1, x_2, \ldots x_n} to the nonnegative integers such that \sum_{i=1}^n f(x_i) = k is C(n + k – 1; k).

or, in other words, that
\sharp \{ f \mid f: \{x_i\}_{i=1}^{n} \rightarrow {\Bbb N}, \sum_{i=1}^n f(x_i) = k\} ={{n+k-1}\choose k}.

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
\sum_{i=1}^n f(x_i) = k
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 \TeX” 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!