Here are three “little” problems that my friend John (from UK) gave me yesterday.

How many 5-digit numbers can be constructed using only and such that each of those three digits is used at least once?

Find all pairs of positive integers such that .

Find all positive integers such that .

Advertisements

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