Tricki
a repository of mathematical know-how

Counting techniques

Counting techniques

May I propose the following addition to the counting techniques page: an article on `elementary techniques.' I would be happy to write an initial version of this article. It would include the following:

  • Counting a cartesian product of fixed sets (which is trivial but important),

  • Counting a cartesian product where the k^{th} set where the k^{th} component takes values depends on the values of the first k-1 components.

  • Counting a set by representing it as a set equivalence classes of larger sets.

  • Change of variables and counting.

  • Examples for each of these techniques.

This sounds like a good a page for someone to write. One comment I have is that many of these techniques occur (in a perhaps special, and slightly modified, form) in finite group theory, and it would be good to have links illustrating this. (In general, much of finite group theory proceeds by elementary counting, and it would be good if the Tricki made this clear in its link structure.)

For example, there are at least two proofs of Cauchy's theorem currently on the Tricki, one using a group action on a carefully chosen subset of G^p, and one using the class equation. These are related to your second example, and a variation of your third example, namely: counting a set by decomposing it into equivalence classes and counting these separately.

Also, in group theory, ``counting" may mean something slightly weaker, along the lines of ``investigating divisibility of the order of a set by a prime". But the methods are never the less very similar in spirit to the basic counting methods that you listed.

I just created an `elementary counting techniques page' (http://www.tricki.org/article/Elementary_Counting_Techniques) and also wrote a first draft of an article describing the first two items above. I think it would be great to write these articles so that they illustrate the connections you mention with group theory and other fields.