### Our other blog

### Blog Stats

- 305,121 hits

### Recent Comments

### Top Posts

- Integration Bee, Challenging Integrals
- Continued fraction for e
- Platonic idealism and geometry
- Analyzing the hairy ball theorem
- Solution to POW-6: Tiling with Triominoes
- Platonic Solids and Euler's Formula for Polyhedra
- Toward Stone Duality: Posets and Meets
- Naive Set Theory (Paul Halmos)
- Section 2 - The Axiom of Specification
- ZFC and ETCS: Elementary Theory of the Category of Sets

### Archives

### Categories

- Abstract Algebra
- Algebraic Geometry
- Boolean Algebra
- Category Theory
- Category Theory for Beginners
- Elementary Math Problem Solving
- Exposition
- Geometric Algebra
- Math Conferences
- Math Topics
- Mathematical philosophy
- Mathematics
- Music
- Naive Set Theory
- Philosophy & Logic
- Physics
- Posets and Lattices
- Problem Corner
- Problem of the Week (POW)
- Propositional Calculus
- Puzzles
- Some theorems
- Uncategorized

### Blogroll

- A Dialogue on Infinity
- A Mind for Madness
- A Neighborhood of Infinity
- A Singular Contiguity
- Absolutely Useless
- AMS Graduate Student Blog
- Antimeta
- Arcadian Functor
- Ars Mathematica
- Complex Zeta
- Courtney Gibbons
- Danielle Fong
- Epsilonica
- Game Theorist
- Global Dashboard
- God Plays Dice
- Jocelyn Paine
- Lambda the Ultimate
- Language Log
- Louis Yang Liu
- Mark Reid
- Musings on general topology and order
- Noncommutative Geometry
- Reasonable Deviations
- Recursivity
- Reperiendi
- Rigorous trivialities
- SbSeminar
- The Accidental Mathematician
- The Everything Seminar
- The Infinite Seminar
- The n-Category Cafe
- Theoretical Atlas
- XOR’s Hammer

### chess

### Computers and Technology

### Elementary Math Problem Solving

### Fun, Humor

### Higher Mathematics

### Math Education

### Non-technical

### People in Computer Science

### People in mathematics

### Philosophy & Logic

### Physics

### Politics, News

### Sciences

### Useful general links

### Useful Math Links

### Tag Cloud

advice
andreescu
Aussonderungsaxiom
Axiom of Extension
Axiom of pairing
axiom of powers
Axiom of Specification
axiom of unions
blog
Boolean Algebra
career
carnival of mathematics
Category Theory
chess
complements
continued fractions
definite integrals
elementary
emil artin
empty set
Exposition
Fermat's Last Theorem
Geometric Algebra
golberg
hard integral
Harvard College Mathematics Review
heyting algebra
identities
identity
inclusion-exclusion principle
Inequality
integration
integration bee
intersections
Invariant
lattices
log
love
mason-stothers theorem
math
mathematical
Mathematical Reflections
mathematics
math puzzle
naive set theory
noah snyder
number
oleg
Oxford
Paul Halmo
Paul Halmos
Polya
polynomial
power set
prime
principle of duality
problem
Propositional Calculus
propositional logic
puzzle
reflections
russell's paradox
Simon Singh
singleton
stone duality
Szego
Tao
Terence
Terry Tao
theory
titu
topos theory
universe
Valentine's day
Yakov Perelman

## 8 comments

Comments feed for this article

March 22, 2008 at 12:14 am

#John SmithVishal, here is another thing I cannot prove:

Given P is prime and n is a natural number, the highest power of p which divides n! is sigma k=1~infinity [n/(p^k)].

March 22, 2008 at 1:14 pm

Todd TrimbleI hope it’s okay if I give some hints/spoilers. If not, stop reading now!

Problem 1 asks to count the number of surjections from a 5-element set X to a 3-element set Y; call it S(5, 3). One method would be to consider the image factorization of functions from X to Y, and deduce that . Use also . There are other general methods of calculation which are connected with Stirling numbers (see e.g. Concrete Mathematics by Graham, Knuth, and Patashnik).

For problem 2, . This gives information on the prime factorizations of n-1 and n+1, and we quickly conclude where i+j = m. So is twice an odd number; therefore i = 1…

For problem 3, one can use calculus. Suppose a and b are different. We are trying to solve f(a) = f(b) where f(x) = x^{1/x}. This function is strictly increasing on [1, e) and strictly decreasing on (e, infinity). Therefore one of the integers, say a, lies in (1, e) and is thus 2. There is at most one b in (e, infinity) which satisfies f(2) = f(b)…

March 24, 2008 at 4:34 pm

#John SmithTodd, regarding your first hint, I do not understand the notion of image factorisation. Please can you expand on the meaning of this phrase?

March 24, 2008 at 11:45 pm

Todd TrimbleSure — it’s just the idea that any function f: X –> Y can be decomposed as a surjective function s: X –> I followed by a subset inclusion i: I –> Y, as Vishal was explaining in his recent Geometric Algebra post, and the pair (s, i) is uniquely determined. Here I is just the image of the original function f (the set {y in Y: y = f(x) for some x in X}, the surjection s sends x to f(x) in I, and i just maps y in I to itself (considered as an element in Y).

The point was to use this principle to compute the number of surjections S(n, j) from an n-element set to an i-element set. By the image factorization, there is a bijective correspondence between functions f (say from an n-element set to an m-element set) and pairs (s, I), where I ranges over subsets of the m-element set and s is a surjection from the n-element set to I. Taking into account the possible cardinalities i of I, this bijection gives an equation

(there being i-element subsets of an m-element set). These equations can be used to solve recursively for S(n, i).

March 25, 2008 at 5:06 pm

#John Smiththere being i-element subsets of an m-element set

Would that not only be iff the m elements are distinct?

Can I ask why you chose to view this problem in this light? I am interested to know the various angles one may look at the same thing.

Also do you have a homepage?

cheers.

March 25, 2008 at 8:03 pm

AnonymousThe elements of a set are distinct by definition…

March 25, 2008 at 10:24 pm

Todd TrimbleNo, it’s shameful, but I don’t have a homepage. I’ve been daydreaming about starting up a math blog myself, but it would be even more time out of the day…

Actually, it wasn’t so much a choice; it was just the approach which felt most natural to me. (Perhaps the fact that I have a lot of experience with category theory guides my mind in certain directions, without my willing it.) I guess the idea is that surjections and injections are (in an interesting sense) dual notions, and they interlock beautifully in the notion of image factorization [which is numerically expressed in that formula for m^n], and my mind naturally gravitates to that sort of thing when I see the word “surjection”. Surjections are “hard” to count, but inclusions are easy (binomial coefficients), and the two define one another through the formula for m^n.

Just to expand a little more in connection with Vishal’s image factorization post (the recent Geometric Algebra one): you’ll recall that actually he factored or decomposed a function f: X –> Y into

threeparts. The first was a “canonical” surjection which maps an element x to its equivalence class under the equivalence relation x ~ x’ iff f(x) = f(x’). The number of equivalence relations on an n-element set X with i equivalence classes is called aStirling number(of the second kind); I think Knuth’s favored notation for this is {n i} (with the n, i in a column), to suggest the number of ways of partitioning an n-element set into i (nonempty) subsets. These have been intensively studied; the wonderful book Concrete Mathematics by Graham, Knuth, Patashnik has an extensive discussion.The second part of Vishal’s factorization was a bijection from an i-element set (the set of equivalence classes) to the image I (another i-element set). The number of possibilities there is i!. The third part was how the image I was included in the m-element set Y; there are possibilities there. Since the three-part factorization is uniquely determined, this gives a proof of the formula

which is equivalent to my formula. In particular, the number of surjections S(n, i) is equal to {n i}i!, a Stirling number times a factorial.

You may already know all about Stirling numbers, but in case not, there are recursive ways of computing them (or the surjection numbers S(n, i)). Here’s one. Suppose s: {1, …, n} –> {1, …, i} is onto. Then either the restriction of s to 1, …, n-1 is already onto [S(n-1, i) possibilities] or, if not, then at least that restriction maps onto i-1 elements, and there are i possibilities for the remaining element s(n). Putting this all together,

S(n, i) = S(n-1, i) + iS(n-1, i-1)

and this leads to a surjection number triangle which you can use to calculate S(5, 3) for instance. Or, you can get a Stirling triangle using similar reasoning: in an i-fold partition of {1, …, n}, either n is in an equivalence class by itself (and 1, …, n-1 are then partitioned into i-1 classes: {n-1 i-1} possibilities), or {1, …, n-1} is already partitioned into i classes, and it is a matter of placing the remaining element n into one of these i classes. Putting this together,

{n i} = {n-1 i-1} + i{n-1 i}.

March 26, 2008 at 11:00 pm

VishalJohn,

Here is the answer to your first question you posed in the comment section.

In this case, to prove the general result, it helps a lot if we examine a particular case and then extend the argument to the general case.

Let’s say and suppose . So, we want to find the highest power of that divides . Now, we can see that the integers and are the only ones that contribute ‘s.

Also, note that each of the integers and contribute ‘s exactly once, contributes exactly twice and contributes exactly thrice. We need a way to count all those ‘s.

Now, observe that is the number of ‘s contributed by and with each of those five even integers contributing

exactlyonce. But that count obviously misses the extra ‘s contributed by and . And this is taken care of by , which is the (extra) number of ‘s contributed by and . Though this does take care of all the ‘s contributed by , we haven’t counted all the ‘s contributed by . And this last contribution by equals .So, our final answer is . You can similarly provide the same argument for , or any prime for that matter.

Lastly, note that the expression is really finite because eventually exceeds , and so after a certain number of terms in the above expression, the rest of the terms will be zeros.