e(ho0n3

P(n) is equal to the nth Catalan number. If you don't believe that P(4) is 14, here is printout of a program a made in perl for n = 4: 1 1 1 1 2 1 1 1 2 2 1 1 2 2 2 1 3 1 1 1 3 2 1 1 3 2 2 1 3 3 1 1 3 3 2 1 4 1 1 1 4 2 1 1 4 2 2 1 4 3 1 1 4 3 2 1 There are 14 number combinations above.

OK,what's the difference between the S-32, the S-37, the Su-43 and the Su-47? (They all seem like the same aircraft to me.) Both the F-22 and the Su-43 are human piloted planes. Therefore, the better combat pilot is going to win (whether on the F-22 or Su-43). Anyway, isn't the MiG 1.44 a more suitable match for the F-22. Personally, the Su-43 is "cooler" looking than the F-22. The best looking aircrafts of all time (in my opinion): YF-23, Su-43, X-36, YF-12, Su-37, and F-15S. What are your favorites?

The problem is P(4) shouldn't be 13, it should be 14. Hence my statement.

Are you in primary, secondary or college?

OK, I'm convinced (I just did a proof by induction and it worked). But anyways, your solution (the one with the fibonacci equation) is wrong. I suggest we start looking for another route towards solving this. I was thinking of looking at the number generated by the print statement in each iteration. In general we have that n ≥ i[1], n - 1 ≥ i[2], ... 1 ≥ i[n], and i[k] > 0 for k = 1, ..., n. Hmm...this is to ugly (and tricky). I'm becomming exasperated. OK. We have that: [math]P(n) = P(n-1) + \sum_{i=1}^{n-1}P(i)[/math] [math]P(n-1) = P(n-2) + \sum_{i=1}^{n-2}P(i)[/math] Then, [math]P(n) - P(n-1) = P(n-1) + \sum_{i=1}^{n-1}P(i) - P(n-2) - \sum_{i=1}^{n-2}P(i)[/math] Simplifying and solving for P(n) gives (and this seems strange to me), [math]P(n) = 3P(n-1) - P(n-2)[/math] This looks like the fibonacci recurrence doesn't it! Unfortunately this is all bogus (it doesn't work for n = 4).

As bloodhound said, we need a proof for the n-dimensional case. And how is your diagram a proof by induction (note that by induction, I mean MATHEMATICAL INDUCTION)?

Let's look at the second for loop, i.e. then one that goes from 1 to min(i[1], n - 1). When the i[1] = 1 (first iteration), the second loop goes from 1 to 1. This is your P(1). Then P(1) is "number of print statements executed in 1 loop, with the top most going from 1 to 1". This is clearly not true. It should be "the number of print statements executed in n - 1 for loops with the top most going from 1 to 1", which is just P(n-1,1). For i[1] = 2 (next iteration), the second loop goes from 1 to 2. This is your P(2). Then P(2) is "number of print statements executed in 2 loops, with the top most going from 1 to 2". This is clearly not true either. It should be "the number of print statements executed in n - 1 for loops with the top most going from 1 to 2", which is just P(n-1,2). And so on. Convinced? I'm supposed to solve this problem without the aid of a computer. As I said before, I know what the answer is; I just don't know how to derive it. The pattern isn't "pretty" so it would be very, very hard to guess from looking at a couple of numbers in the sequence.

It would be nice to see a proof of this (if you can). Until I find one, the answer will remain NO.

I think the problem stems from you definition of P(n). What exactly is your definition? I have something similar to what you have (and ended up with your exact same solution, i.e. P(n) = f(2n - 1)), but then I realized I made a mistake, that being the definition of P(n). Note there are n for loops, with the top for loop going from 1 to n. This is different from n for loops going from 1 to k, k < n, which is still different from k for loops, k < n, the top for loop going from 1 to n. So let me define P(a,b) as the number of times the print statement is executed given a for loops, the top for loop executing from 1 to b. I then get the following recurrence: P(n,n) = 2P(n-1,n-1) + P(n-1,n-2) + P(n-1,n-3) + ... + P(n-1,1) This is as far as I can go since I don't know how to solve such a recurrence relation. Maybe you can shine some light on this.

I would need to see your explanation since that is not the answer (at least according to my book). I know what the answer is, although I don't know how to derive it myself.

How many times does the print statement execute? for i[1] = 1 to n do for i[2] = 1 to min(i[1], n - 1) do for i[3] = 1 to min(i[2], n - 2) do . . for i[n - 1] = 1 to min(i[n - 2], 2) do for i[n] = 1 to 1 do print i[1], i[2], ..., i[n] I get a headache just from looking at it...

The most complete physical theory that I know is Quantum Chromodynamics (QCD) which explains how the electromagnetic force and the weak force are both forms (or come from) the electroweak force or something to effect. We still have the strong nuclear force to deal with and then there is of course gravity. A "unified theory" is one that will encompass the electroweak force with the strong force. Theories that encompass all four forces (i.e. weak, strong, EM, and gravity) are known as "Mother Theories" (or M-Theory for short). String theory seems to be the most promising of these "M-theories". As far as I understand it...

I forgot to mention two important details: m > 1 and d > 0. OK. I've managed to show that b[n] ≤ a[n] for all n assumming b[0] = a[0]. All I need to do now is show the following: Let f and g be functions of x such that f(x) ≤ g(x) for all x. For some function h, if f = O(h) then g = Ω(h). Proof: Define h such that f(x) ≤ h(x) ≤ g(x). In order to prove that a[n] = Ω(lg n), let f(n) = b[n] - 1 so f(n) < b[n] ≤ a[n] and since f(n) = O(lg n), then a[n] = Ω(lg n). Somehow I have a feeling that I've made an error somewhere. Can anybody check this for me please?

I thought statistics was the most used area of mathematics. I remember reading parts of a three volume series of books that contained articles, letters, etc. of many famous mathematicians about their ideas, notions and conclusions of certain areas in mathematics. I particularly remember one about B. Russell describing what numbers are. I don't recall what the series is called though, but it's very good. All I remeber is that it's three volumes long, the books have a blue cover and are rather old.

Yes. The recurrence is defined ONLY when m divides n. Interesting, but first I would need to show that b[n] is less than or equal to a[n] for all n. I haven't attempted this yet so bear with me. I would but the book I got this problem from does not mention the Master Theorem anywhere. We'll see. Note that the "d" in the recurrence of a[n] is not constant (in wouldn't make sense otherwise). I'll examine your suggestion more carefully later (I'm working and I shouldn't be doing this). Thanks.

I was reading through my parallel comp. book when I came across this sentence: If the bisection bandwidth of a network is w, the lower bound on the area in a two-dimensial packaging is Θ(w2), and the lower bound on the volume in a three-dimensional packaging is Θ(w3/2). This is where I stopped since I have no idea how and where they got these lower bounds from. Anybody here familiar with this? Maybe I should just stop reading this weird book.

The majority of the research being done in this field today is in the construction of quantum computers, particularly with the use of quantum optics. There are of course other ways to build a quantum computer. The amount of books on this subject is growing and I keep seeing more and more research articles about this subject almost every day. I guess everybody knows about Shor's prime factorization algorithm. Apparently Shor has become famous. Isn't he teaching at MIT now? One of the problem plauging quatum computers is the Uncertainty Principle, i.e. measuring the results of a quantum computation directly will destroy the results. To study any kind of quantum mechanical system via experimentation requires that one isolate the system completely from any outside contamination. This is the other problem in the field and has lead to the creation of what is known as quantum error-correction coding.

Here is another question I posted on PF but got little attention: I need to prove the following identity for Stirling numbers of the first kind: [math]s_{n,2} = (n-1)!\Big(1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n-1}\Big)[/math] For the uninitiated, s[n,k] is a Stirling number of the first kind and represents (as I was explained) the number of ways of sitting n people in k table so that every table has at least one person. The ordering of the tables doesn't matter but the ordering of the people on a table does. Example: Suppose three people (A, B, and C) are sitting at a table such that C is to the right of B and B is to the right of A. So ABC = BCA = CAB are all the same. Another way of sitting A, B, and C is by letting C be to the right of A and B to the right of C. So ACB = BAC = CBA. So, the number of ways of sitting three people on one table is s[3,1] = 2. OK. I know that s[n,1] = (n - 1)!. I need to find s[n,2] which is the number of ways of sitting n people in two tables. I'm going to assume n is even to simplify my analysis here. So, s[n,2] can be reduced to: The number of ways of sitting one person at one table and n - 1 persons at the other table, plus the number of ways of sitting two persons at one table and n - 2 persons at the other table, plus..., plus the number of ways of sitting n/2 persons at one table and n/2 persons on the other table. In other words, [math]s_{n,2} = s_{1,1}s_{n-1,1} + s_{2,1}s_{n-2,1} + ... + s_{n/2,1}s_{n/2,1}[/math] Now assuming this is right, how do I simplify this to what I gave above? I just can't seem to do it.

Oh yeah. I forgot to mention that it's a common convention to say [math]x^2 + x + 3 = O(x^2)[/math] instead of [math]x^2 + x + 3 \in O(x^2)[/math] They are both equivalent. It's just convention.

Actually those are sets. They are used in order analysis to determine how a particular function grows. We say that g(x) = O(f(x)) iff for any constanct c > 0 their exists a k >= 0 such that g(x) <= cf(x) for all x >= k. In other words, g(x) = O(f(x)) iff g(x) grows no more than f(x), i.e. O(f(x)) is the set of functions that grow no more that f(x). Example: x^2 + x + 3 = O(x^2). Also x = O(x^2), but x^3 != O(x^2). Similarly, we say that g(x) = Ω(f(x)) iff for any constant c > 0 their exists a k >= 0 such that g(x) >= cf(x) for all x >= k. In other words, Ω(f(x)) is the set of functions that grow no less than f(x), practically the opposite of O(f(x)). If g(x) = Ω(f(x)) and g(x) = O(f(x)) then g(x) = Θ(f(x)) and vice versa. So basically what I need to show is that a[n] grown no more and no less than lg n.

I posted this on PF but it didn't get very far: Suppose {a[n]} is an increasing sequence and whenever m divides n, then a[n] = a[n/m] + d where m is a positive integer and d is a real number. Show that a[n] = Θ(lg n). I can show that a[n] = O(lg n). All I need to do is show that a[n] = Ω(lg n). This is where I'm stuck. Any hints?

Yes and yes. Examples: sin(a + ib) = sin(a)cosh(b) + icos(a)sinh(b). It's a bit trickier with logarithms.

Maybe this link will help: http://mathworld.wolfram.com/Set.html