0
$\begingroup$

In my university we learn Set Theory prior to starting Combinatorics but they don't seem to be making a clear and explicit connection between the two. Yet it seems to me that there is in fact a very strong relation between well known combinatorial formulas like $D(n,k),c(n,k),p(n,k),n^k$ and the algebra of sets. Could someone explain it and make it explicit?

Edit

Combinations with repetitions: $D(n,k)=\binom{n+k-1}{k}=\binom{n+k-1}{n-1} = \frac{(n+k-1)!}{(n-1)!}$

Combinations without reps: $c(n,k)=\binom{n}{k}=\frac{n!}{k!(n-k)!}$

Permutations with reps: $n^k$

Permutations without reps: $p(n,k)=\frac{n!}{(n-k)!}$

  • 0
    @hardmath Hope this edit helps.2011-12-19

2 Answers 2

1

Many of those things count functions of various types between two finite sets, or the number of partitions of a set into subsets, and so on. See for example http://en.wikipedia.org/wiki/Twelvefold_way.

  • 0
    +1: This looks really good, but it's pretty long and going to take me a while to read it and see if it's what I'm looking for :-).2011-12-19
1

Most combinatorial (families of) numbers count the elements in certain (families of) finite sets; this is the basis of enumerative combinatorics. Whether those families of finite sets play a very important role in set theory rather depends. Powers of $2$ count the powerset (collection of all subsets) of finite sets, which is an important notion in set theory. Combinations count those subsets with a fixed number of elements, which is somewhat less fundamental though still important in set theory. Powers of another number $n$ than $2$ count all maps to an $n$-element set, and $p(n,k)$ counts such maps that are injective; both these notions are fairly central to set theory. However combinations with repetitions $D(n,k)$ count multisets of $k$ elements chosen from an $n$ element set, which is a notion not usually encountered in set theory. They can be modeled by maps from an $n$-element set to $\mathbf N$ such that the sum of the values taken is $k$, but the importance of such a construction in set theory is not so obvious. On the other hand this number does occur in algebra as the number of monomials in $n$ (commuting) variables, of total degree $k$.