Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)!}$

share|improve this question
    
Set theory provides a natural framework for most topics in mathematics, so combinatorics is not at all unique in this respect. Combinatorics might be regarded as techniques for counting, particularly when applied to counting a finite set in two different but equivalent ways in order to establish the equality of two expressions, a "combinatorial identity". Functions like the binomial coefficients come up a lot in this connection, but it would be helpful if you want some "explicit" explanations if you define your notations. –  hardmath Dec 19 '11 at 10:18
    
@hardmath Hope this edit helps. –  Robert S. Barnes Dec 19 '11 at 10:41
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
+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 :-). –  Robert S. Barnes Dec 19 '11 at 10:44
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.