Wikipedia:Reference desk/Archives/Mathematics/2007 June 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 27

Number of possibilities

I have 8 balls and 3 gates; all the balls must pass through a gate exactly once before a possibility is created. How do I calculate the number of possibilities? (The order in which the balls pass through the gates is irrelevant, let's assume the balls are all exactly the same). --The Dark Side 01:11, 27 June 2007 (UTC)

For a simple example like this, one approach is to list all the possible separate cases, of which I believe there are 10. Working out the possibilities in each case and adding them gives the answer, which I won't provide in case this is homework. But if it were about 162 balls and 57 gates, I'm not sure how I'd go about it. -- JackofOz 01:27, 27 June 2007 (UTC)

I don't understand the question. To me, it looks like it's about the number of compositions of 8 into exactly 3 parts, in which case the answer is 21. What are these "possibilities" we are counting? nadav (talk) 04:00, 27 June 2007 (UTC)

I'm going to take this opportunity to point out that the article on compositions could use some work. I'll try to make some time, but if one of you Wikipedia all-stars wants to take a crack at it... 209.189.245.114

Depends what you mean, the question is a little too vague. If we number the balls 1 thru 8 and the gates A,B,C then I imagine that one configuration is A=12345678, B=empty, C=empty. Another is A=158, B=27, C=346 etc. There are thousands of combinations like this. On the otherhand, as you say the balls are all the same, maybe it is only the number of balls rather than which balls, so my previous two examples would change to A=8, B=0, C=0 and A=3, B=2, C=3. If you can define what you seek better, it will be answerable. Please give a couple of examples - probably a "typical" example and an "extreme" example. -- SGBailey 11:44, 27 June 2007 (UTC)

Assuming gates are distinguishable but balls are not, then I make it 45 possibilities. It's like allocating 8 indistinguishable balls to 3 distinguishable bins (we must have an article on that, but I can't find it) so it is ${10 \choose 2}$. (Nadav - I don't think you included cases where some gates have 0 balls). Gandalf61 14:56, 27 June 2007 (UTC)

I didn't include them on purpose because I (mistakenly, I guess) interpreted the wording as saying that at least one ball should pass through a gate. From now on, I propose all questions be posed in mathematical symbols only ;) Also, the compositions article is what you are looking for (the article says if the zero case is included then it's called a "weak composition") nadav (talk) 15:00, 27 June 2007 (UTC)

I assume this is homework, so hints only for you! :) Try to figure out the answer for just 1 ball and 1 gate. Simple, right? Then figure it out for 1 ball and two gates. How did it change? Then 2 balls, then 3, then 4. How is the number of possibilities growing? Can you generalize this? Now do the same for increasing gates. Good luck! --TotoBaggins 15:23, 27 June 2007 (UTC)

1 ball and 1 gate obviously means just 1 possibility since each ball must pass through a gate. When I have 2 gates, that works out to be 2 possibilities for 1 ball, 3 for 2, 2 for 3 (4 for 3), 5 for 4, 6 for 5. If I have 2 balls and 3 gates there are 6 possibilities. If I have 3 balls and 3 gates there are 10 possibilities. If I have 4 balls and 3 gates there are 12 (15) possibilities. If I have 3 balls and 4 gates I have 19 (20) possibilities. Unfortunately, I do not see a pattern yet and I cannot give any extreme examples, as I do not even know how to find the answer to this one. SGBailey's idea about "the number of balls rather than which balls" is what I am looking for. As most people are assuming (incorrectly, as school is out anyways) that this is homework, I ask only for someone to help me find the answer (i.e. process). A solution would help me this time, but not the next time I encounter something like this. --The Dark Side 15:55, 27 June 2007 (UTC)

After going through that composition article I found an article on binomial coefficients. This lead me to the formula

${\frac {n!}{k!(n-k)!}}\quad {\mbox{if}}\ n\geq k\geq 0\qquad$

Using that, I got 56 as the answer. Can anyone verify that?--The Dark Side 16:16, 27 June 2007 (UTC)

I got 45. Look at it this way. Suppose there are b balls and g gates, and what you are looking for is f(b,g), or, in your specific case, f(8,3). If there is one gate, there is only one possibility, so f(b,1)=1. If there aren't any balls there's only one possibility, so f(0,g)=1. If there is more than one gate, the number of possibilities with having no balls in the first gate is f(b,g-1). The number with one ball in the first gate is f(b-1,g-1). Since there can't be more balls in the first gate than there are balls. If you add all the possibilities, you get f(b,g-1)+f(b-1,g-1)+...+f(1,g-1)+f(0,g-1), or $\sum _{k=0}^{b}f(k,g-1)$. f(b,2) is $\sum _{k=0}^{b}f(k,1)$, $\sum _{k=0}^{b}1$, or just b+1. f(b,2) becomes $\sum _{k=0}^{b}k+1$, $\sum _{k=1}^{b+1}k+1$, or the b+1th triangular number. f(b,3) is the b+1th tetrahedral number and so on. These can all be found along the diagonals of Pascal's triangle which are all binomial coefficients. Specifically, it's ${b+g-1 \choose b}$, ${\frac {(b+g-1)!}{b!((b+g-1)-b)!}}$, or ${\frac {(b+g-1)!}{b!(g-1)!}}$. — Daniel 16:51, 27 June 2007 (UTC)

I'm in the dark when patterns of passing-throughs are considered the same possibility, and when different. Let's name the balls A, B, C, ... and the gates 1, 2, 3, .... For 2 balls and 2 gates I see the possibilities (1:AB, 2:-), (1:A, 2:B), (1:B, 2:A), and (1:-, 2:AB). You write that there are 3 possibilities; which of the above do you consider the same possibility? Likewise, for 2 gates and three balls, we have (1:ABC, 2:-), (1:AB, 2:C), (1:AC, 2:B), (1:A, 2:BC), (1:BC, 2:A), (1:B, 2:AC), (1:C, 2:AB), (1:-, 2:ABC). You count 2 possibilities. Which of these eight are one possibility, and which the other?  --Lambiam^Talk 22:44, 27 June 2007 (UTC)

I took the liberty of changing the third term in the 2-ball-2-gate example above from "(1:B, 2:-)" to "(1:B, 2:A)" in the hopes of reducing confusion. I hope this isn't too presumptuous of me. Tesseran 23:31, 27 June 2007 (UTC)

Only the number of balls that pass through a gate matters, not the order of the balls or which ball passes through which gate. This means that (1:A, 2:B) and (1:B, 2:A) are the same since they still end up with the same number of balls that passed through the gates. For 2 gates and 3 balls (1:AB, 2:C), (1:AC, 2:B), (1:BA, 2:C), (1:BC, 2:A), (1:CA, 2:B), and (1:CB, 2:A) are all the same. However, I did make a mistake, for 3 balls and 2 gates there are 4 possibilities. --The Dark Side 00:44, 28 June 2007 (UTC)

Each ball either passes through a particular gate or it doesn't. For ball A, there are 2^3 possibilities.

For eight separate balls there are 2^(8*3) = 16777216 possibilities.

202.168.50.40 02:11, 28 June 2007 (UTC)

I just had to find this out myself, for a question I asked further up the desk. The problem as I understand it is to count how many ways there are to place 8 identical balls in 3 baskets, or equivalently, how many choices of nonnegative integers A, B, and C sum to 8. This would be equal to the number of vertices in a barycentric graph of side length 9. As Daniel said above, this is a triangular number, equal to 9(9+1)/2 = 45. The generalization of this to n-1 balls and r+1 baskets is given at Figurate number, and is equivalent to running down diagonals of Pascal's Triangle. Black Carrot 08:12, 29 June 2007 (UTC)

Constant Dollars formula

Greetings;

I am doing some research. But I cannot find what I am looking for anywhere on the Net or the Library. I need TWO mathematical formulas.

The first one I need is the formula for Constant dollars in economics. The second formula I need is the formula for the AVERAGE of gravity on Earth.

How can I find this information?

Mark Carrillo Los Lunas, New Mexico

You could look it up at Wikipedia, for example! Regarding constant dollars, what is it you want to calculate and what data do you have? For average gravity, the standard gravity (9.80665 m·s⁻²) might be appropriate to use. —Bromskloss 14:44, 27 June 2007 (UTC)

Jensen's inequality extravaganza

Hi all, another question. This time it's in realm of real analysis.

Let $(X,\Sigma ,\mu )$ be a measure space with $\mu X=1$, and let f be a function which is positive a.e. on X. Show that

$\lim _{h\to 0}\left(\int _{X}f^{h}\ d\mu \right)^{1/h}=\exp \left(\int _{X}\ln f\ d\mu \right).$

I can use Jensen's inequality to show that for all h > 0, $\left(\int _{X}f^{h}\ d\mu \right)^{1/h}\geq \exp \left(\int _{X}\ln f\ d\mu \right)$, so at least the lim inf of the expression on the left hand side is bound below by the expression on the right hand side, but I'm having issues getting the lim sup to be bound above by the right hand side. Maybe my technique of using lim sup and lim inf is not the way to go on this problem, but I don't know what else to do.

I've also tried writing $\exp \left(\int _{X}\ln f\ d\mu \right)=\lim _{h\to 0}\left(1+h\int _{X}\ln f\ d\mu \right)^{1/h}$ to try to get something to work out. For instance, I can write 1 as $\int _{X}1\ d\mu$ since μX = 1, but I did not achieve any success.

Any help would be appreciated! Thanks in advance.

(For those unfamiliar with my wheelings and dealings, this is not a homework problem; I'm studying for PhD qualifying examination, and this problem appeared on one of the past exams.) –King Bee ^{(τ • γ)} 18:49, 27 June 2007 (UTC)

OK, since no real mathematicians are stepping up, here is a humble physicist's pedestrian approach, which is probably invalid in your more refined spheres: $\partial {f^{h}}/\partial h=\ln {f}$ at h=0 for positive f, so $f^{h}=1+h\ln {f}+O(h^{2})\,$. Thus $\int {f^{h}}=\int 1+h\int {\ln {f}}+O(h^{2})$, and $\int 1=1$ since $\mu X=1$. We also know that $\lim _{h\to 0}\left(1+ah\right)^{1/h}=e^{a}$ as this is one definition of e. From these we have $\lim _{h\to 0}\left(\int f^{h}\right)^{1/h}=\lim _{h\to 0}\left(1+h\int {\ln {f}}+O(h^{2})\right)^{1/h}$ $=\lim _{h\to 0}\left(1+h\int {\ln {f}}\right)^{1/h}=\exp \left(\int \ln f\right)$. Is any of that salvageable to mathematical standards? --mglg_(talk) 23:30, 27 June 2007 (UTC)

Thanks for the help. I might be able to use your idea of taking the derivative of f^h with respect to h, but I don't think this "big oh" notation is going to fly. Especially since when you take that integral, you are not integrating with respect to h; I feel like there might be an issue with passing the limit inside the parentheses.

Thanks for the ideas though! I appreciate the help. –King Bee ^{(τ • γ)} 11:08, 29 June 2007 (UTC)

Here's how I approach the problem: $\lim _{h\to 0}\left(\int _{X}f^{h}\ d\mu \right)^{1/h}=\exp \left(\lim _{h\to 0}{\frac {\log \int _{X}f^{h}\ d\mu }{h}}\right)=\exp \left(\lim _{h\to 0}{\frac {\int _{X}(\log f)f^{h}\ d\mu }{\int _{X}f^{h}\ d\mu }}\right)=\exp \int _{X}(\log f)\ d\mu$, by way of l'Hopital's rule, Dominated convergence theorem, and Differentiation under the integral sign [1]. I may have implicitly assumed some property of f that wasn't given. I'll think more about this problem. Best, nadav (talk) 19:03, 30 June 2007 (UTC)

By the way, this is sort of a cool problem. It reminds me of the average of logarithms identity in Geometric mean. nadav (talk) 19:08, 30 June 2007 (UTC)

I see. The function you're differentiating then is $F(y)=\log \int f^{y}\ d\mu$ at the point 0? Brilliant. I'll run this by a few people, but I think I can fill in all the justifications for those equal signs. Thanks! –King Bee ^{(τ • γ)} 02:48, 2 July 2007 (UTC)

Yeah, the second limit is an indeterminate form, so we just differentiate the top and bottom of the fraction with respect to h. In many ways, this is just a calc problem with other stuff thrown in to confuse and make it look harder. (I thought of it by first doing the limit $(a^{h}+b^{h})^{1/h}$ as h gos to 0 with a+b = 1) nadav (talk) 08:06, 2 July 2007 (UTC)

I guess what I was saying is that you don't have to use l'Hopital's rule; that the second item in that string of equalities up there is indeed the derivative of the F(y) function I described above. –King Bee ^{(τ • γ)} 13:01, 3 July 2007 (UTC)

Ah, I understand what you mean now. Yes, I agree that directly using the definition of derivative is nicer. nadav (talk) 04:25, 4 July 2007 (UTC)

So what is the dimension of the symplectic lie algebra?

Hello,

I'm having an argument here with someone else. We are trying to determine the dimension of the real symplectic lie algebra $sp(2n,\mathbb {R} )$ . That is the Lie algebra of$2n\times 2nA$ satisfying $A^{T}J+JA$ where $J$ stands for the matrix $J={\begin{bmatrix}0&I_{n}\\-I_{n}&0\end{bmatrix}}$

I keep finding that it's $3n^{2}$ Some source I have says it's $n(2n+1)$ . All hints or sources of remarks are welcome. Thank,Evilbu 18:53, 27 June 2007 (UTC)

Well back when I taught algebra, some of my students thought that $2n^{2}+n=3n^{2}$. Donald Hosek 00:23, 28 June 2007 (UTC)

Hey I'm not a noob anymore:). In fact, if all goes well, the exam I'm asking this for should be my very last. But I found it, I forgot to take the transpose in those blockmatrices. That's what you get when beoming "too comfortable" when block matrices are in town....Evilbu 07:05, 28 June 2007 (UTC)

I'm assuming you want the dimension over the reals of the real symplectic Lie algebra

${\mathfrak {sp}}_{2n}\mathbb {R} ,\,\!$

the Lie algebra of the Lie group Sp_2n R of real (2n)×(2n) matrices M satisfying M^TJM = J. (Differentiating the constraint at the identity gives the stated condition, X^TJ+JX = 0.) Do you not trust the answer in our table of Lie groups? We agree with your sources that say n(2n+1). In the case of 4×4 matrices (that is, n = 2), the prediction is dimension 10; yours is dimension 12. You should be able to check this by hand, and also consult other sources to confirm. Our symplectic matrix article agrees that the dimension is n(2n+1), as does symplectic group, but can we trust Wikipedia? You might try proving that any X belonging to the Lie algebra has the form JS, where S is symmetric (sufficiency is easy); then note that S has ∑_k=1…2n k independent entries, implying dimension n(2n+1). --KSmrq^T 07:33, 28 June 2007 (UTC)