Take the 2-minute tour ×

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?


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


