Wikipedia:Reference desk/Archives/Mathematics/2010 October 6

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.

October 6

combinatorial identity

Resolved

How do I establish the following identity: $\sum _{k=0}^{m}{\tbinom {m}{k}}{\tbinom {n}{r+k}}={\tbinom {m+n}{m+r}}$. Also is there a book which has many exercises related to such problems. Thanks-Shahab (talk) 02:18, 6 October 2010 (UTC)

I think you need to start from ${\binom {m}{k}}={m! \over k!(m-k)!}$. You should find lots of factors in the factorials cancelling one another out. As for books, I'm sure many end-of-high-school/beginning-college stats textbooks cover this sort of thing in depth. --81.153.109.200 (talk) 05:28, 6 October 2010 (UTC)

Rewrite it as $\sum _{k=0}^{m}{\tbinom {m}{m-k}}{\tbinom {n}{r+k}}={\tbinom {m+n}{m+r}}$ and then as $\sum _{k=0}^{m}{\tbinom {m}{k}}{\tbinom {n}{l-k}}={\tbinom {m+n}{l}}$ and it should be obvious. Algebraist 09:49, 6 October 2010 (UTC)

The "best" way to prove an identity like this, from a combinatorial perspective, is not to play around with manipulating algebraic symbols but to find an interpretation so that both sides are clearly counting the same thing. (This is called double counting.) In the case of $\sum _{k=0}^{m}{\tbinom {m}{k}}{\tbinom {n}{r+k}}={\tbinom {m+n}{m+r}}$, such an interpretation might go like this: The right side clearly counts the number of ways to choose a total of m + r items out of the (disjoint) union of a set M of size m and a set N of size n. When you make such a choice, you are choosing some number of items from M to leave out—call that number k. (In other words, you pick some k items out of M not to include in your collection.) To make up for the k items you didn't include from M, you need to choose r + k items from N in order to bring the total number of chosen items to m + r, as desired. Now, the value of k (the number of items from M that were not chosen) can range from 0 to m, so the number of ways to choose a value for k, then choose k items from M to leave out, then choose r + k items from N to complete the collection, is $\sum _{k=0}^{m}{\tbinom {m}{k}}{\tbinom {n}{r+k}}$, which is the left side of the identity. Since both sides are counting the number of ways to choose a collection of m + r items from the union of M and N, they must be equal. —Bkell (talk) 13:14, 6 October 2010 (UTC)

I can't guarantee I know the BEST book or anything but I know one book that covers a huge amount of this stuff, I would think way more than any "end-of-high-school/beginning-college stats textbooks" (though those are good sources probably). It is Concrete Mathematics by Graham, Knuth, and Patashnik. Chapter 5 is Binomial Coefficients and it is over 100 pages long, including exercises. This chapter goes into stuff that may be beyond what you are looking for but at least the first 40+ pages seem to be about this sort of thing. StatisticsMan (talk) 14:02, 6 October 2010 (UTC)

Thank you all, and especially Bkell:). I have started reading from the Concrete Mathematics book.-Shahab (talk) 14:29, 6 October 2010 (UTC)

"Algebraist"'s way of rewriting it is good, but with combinatorial identities you can often get some insight by doing what Bkell suggests: think of what is being counted. Michael Hardy (talk) 20:25, 9 October 2010 (UTC)

Stuck trying to prove a division problem

Hi,

I am stuck trying to prove the following: If A,B,C are positive integers and A|BC, then A|B or A|C.

Here is what i have: Assume A|BC. This means that AX = BC for some positive integer X.

My issue is trying to get A multiplied by some expression to equal B or C. If i divide both sides by C, for instance, i have AX/C = B ---> A(X/C) = B, which would prove A|B if X/C is an integer, but we dont know that X/C is an integer! How can i prove/disprove the statement? I am not looking for someone to shoot me the answer, just help me be unstuck please? :)

Thanks! 137.81.118.126 (talk) 08:18, 6 October 2010 (UTC)

The statement is false, try to find a counterexample. -- Meni Rosenfeld (talk) 08:36, 6 October 2010 (UTC)

Is it really? my intuition tells me its true. Perhaps i need to play with primes and composites then? or maybe proof by contradiction? I'll give that a thought... :) 137.81.118.126 (talk) 08:41, 6 October 2010 (UTC)

So far, im choosing B and C, trying different combinations of primes or composites, and the only thing i can make sense of is that you cant divide BC unless you have a prime that is in common with B or C.... so i really dont see how this is false. 137.81.118.126 (talk) 08:48, 6 October 2010 (UTC)

Disproof is simple - as Meni says, you just need to find a counterexample. Look at multiples of 4 or 6 to find one. To create a version of the statement that is true, you need to add an extra condition on A. Gandalf61 (talk) 08:52, 6 October 2010 (UTC)

I think i found it! Let B = C = 3, and A = 9. Then you have that 9|9, but NOT(9|3). The problem doesnt say that i cant have A = BC. Is this the way to go here? and the restriction would be A ≠ BC ? 137.81.118.126 (talk) 08:56, 6 October 2010 (UTC)

Yes, that is a counterexample (personally I would go with $6|2\cdot 3$). No, that's not the restriction, you can have this happen even when $A\neq BC$. -- Meni Rosenfeld (talk) 09:03, 6 October 2010 (UTC)

(edit conflict) I know much more about this now. It is simply that to force an error in the statement, A has to be a combination of the factors of B and C such that A > BC. This works for things too like A= 27, B=C=9. I just needed to think outside the box. Thanks alot everyone! 137.81.118.126 (talk) 09:08, 6 October 2010 (UTC)

See Euclid's lemma. Bo Jacoby (talk) 09:12, 6 October 2010 (UTC).

No, I still don't think you get it. You can't have $A>BC$ and $A|BC$. If you meant $A>B,\ A>C$ then that's still not it - think about $6|8\cdot 9$. Bo's link will give you the missing ingredient to the statement being true, but you may want to try to figure it out yourself first. -- Meni Rosenfeld (talk) 11:12, 6 October 2010 (UTC)

hmm, maybe then 6|8*9 because it contains prime factors of BOTH B and C which are exclusive? (in this case it borrows a 3 from C, and B doesnt have a 3. It also uses a 2 from B, and C has no 2. Is that what you are getting at? 137.81.118.126 (talk) 12:38, 6 October 2010 (UTC)

That's not exactly it either, consider $36|12\cdot 18$. I'm not getting at anything. It's possible to characterize the situation $A|BC,\ A\not |B,\ A\not |C$ using the prime factorizations of A, B, C. In any case, Euclid's lemma tells us that this situation is impossible if A is prime. -- Meni Rosenfeld (talk) 13:05, 6 October 2010 (UTC)

include or not to include

I am about to publish a mathematical proof and thought I would begin with a germane quotation from the Hebrew bible / "old testament". However, since I am including a bible quotation in a somewhat patronizing way (as I am not a believer in any bible), I thought I would also include a brief, pertinent quotation from the Qu'ran (the Arabic bible).

My question is, would this patronizing quotation from two ancient texts, specifically the latter, be received very negatively? Specifically, would any Jewish or Israeli readers here be offended if a math proof began with a relevant quote from the Qu'ran (after a relevant quote from Ecclesiastes)? I am not really trying to start a debate, and I might as well pull both (leaving no quote). The only reason I even think to include one is because I have seen this done a lot of times in other serious scientific works. (That introductory quote probably even has a special name, though this name escapes me at the moment). Obviously what I have seen is mostly Christian bible (/"bible as literature") quotations. someone else mentioned that while secular, Israeli high courts often quote hebrew scripture as well in their judgments, likely for the same historical flavor I am seeking.

So I would just like practical advice, your honest gut reaction please. You do not have to specify any reasons for your advice, I appreciate the advice itself most, and this is really not that big of a deal to me. Thank you. 85.181.48.173 (talk) 16:35, 6 October 2010 (UTC)

Are you writing something that is explicitly patronizing, or is it just that you feel that including a quotation without believing the Tanakh is patronizing? If the former it depends. If the latter then I don't think there should be a problem with including a quotation from either the Tanakh or the Qur'an or both. (note the position of apostrophe in Qur'an - it denotes that it is pronounced "Qur an" rather than "Qu ran".) -- Meni Rosenfeld (talk) 17:11, 6 October 2010 (UTC)

Good work Meni! — Fly by Night (talk) 19:59, 6 October 2010 (UTC)

Optimal strategy for coin flipping game

The game proceeds as follows. A player flips a coin as many times as he likes. At each stage the player has some fraction of heads of the total number of coin flips. If the player decides to stop at some point then the fraction of heads at that point is what he will win. So, if after 7 coin flips the player has 4 heads, the player will win 4/7 dollars if he decides to stop here.

The problem is then, of course, to decide if after N coin throws of which M are heads, to continue or to stop. Count Iblis (talk) 19:31, 6 October 2010 (UTC)

Well, the game is memoryless, so at any point the expected fraction of heads you should expect to obtain in the future is 1/2, regardless of your past performance. (This assumes that you know the coin is fair.) This seems to indicate to me that as soon as your fraction M/N at any point is greater than 1/2, you should stop. —Bkell (talk) 19:55, 6 October 2010 (UTC)

(ec) Is there an entry fee? Say 0.5 dollars? But whatever the entry fee, the flipper can set a threshold (say 75%) and carry on flipping until he achieves that percentage. If he fails in the first 100 throws, maybe by 1000 he'll have got there. Or by 1,000,000 flips. Or by 10^99 flips... IE keep going forever until your desire is achieved. The lower the threshold, the more likely it is to be achieved in finite time. -- SGBailey (talk) 20:00, 6 October 2010 (UTC)

I thought about that, but the law of large numbers implies that the fraction will almost surely converge to 1/2 as N goes to infinity, which means that, for any fixed threshold r > 1/2, there will almost surely be a point beyond which the fraction never exceeds r. So it's not clear to me that you can say, "You can always reach a given threshold if you flip long enough." I believe it is also true that if there is a maximum allowed number of flips, even if that maximum is enormous (but finite), then you should stop the first time your fraction rises above 1/2, because the expected fraction of heads you'd get in the future if you continue is 1/2, meaning that you expect your cumulative fraction to drop. —Bkell (talk) 20:22, 6 October 2010 (UTC)

It's true that you cannot say "You can always reach a given threshold", but it's also not true that the best you can expect is 1/2. And I don't think you can say that the analysis would be as you specify if the maximum number of flips is large but finite. The analysis is more complicated than that. For the original case, the strong law of large numbers central limit theorem implies that, if your current position is M/N, then the distribution at time N + P is normal with mean:

${\frac {M+{\tfrac {1}{2}}P}{N+P}}$

and standard deviation

${\frac {\sqrt {{\tfrac {1}{12}}P}}{N+P}}$

It follows then that, if M is sufficiently close, but larger than N/2, then the strategy of waiting until time P, and then continuing if the new value is less than 1/2, would produce a better result. — Arthur Rubin (talk) 20:45, 6 October 2010 (UTC)

[ec] Let's denote by $f(m,n)$ the expected gain if the player plays optimally and has already made n throws of which m are heads. Then we have $f(m,n)=\max \left({\tfrac {m}{n}},{\tfrac {1}{2}}(f(m,n+1)+f(m+1,n+1))\right)\;\!$. It can also be seen that

1. If n is large and m is significantly larger than $n/2$ (by some multiple of ${\sqrt {n}}$, I think) then $f(m,n)=m/n$ exactly (realized by stopping).
2. If n is large and m is approximately or less than $n/2$, then $f(m,n)\approx 1/2$.
3. If n is small, $f(m,n)$ can be significantly more than half. If we limit the number of tosses to 1000, then $f(0,1)=0.582395...$ and $f(11,20)=0.558973...$ (so at (11,20) you should keep playing). Without the limit, f is slightly higher.

How to find an exact value for f is something I'll keep working on. -- Meni Rosenfeld (talk) 20:46, 6 October 2010 (UTC)

For whomever it may interest, here are the minimal values of m for which you'll want to stop, assuming a limit of 1000 throws (the real values should only be slightly off, if at all), for $n=1,2,3,\ldots ,50$:

1, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 12, 12, 13, 13, 14, 14, 15,
15, 16, 16, 17, 17, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28

-- Meni Rosenfeld (talk) 20:58, 6 October 2010 (UTC)

The continuous approximation may be easier to solve: Given a Wiener process W(t) with instantaneous variance 1/12, try to solve the stopping problem with payoff W(t)/t. (Or, it might not be easier or relevant.) — Arthur Rubin (talk) 21:07, 6 October 2010 (UTC)

That's indeed the plan. I do believe it's easier and relevant. This reminds me of the nerd sniping problem - at first I thought "well, at least I can get an approximation by starting with the obvious boundary conditions and solving inwards". Then it turned out the boundary conditions were not obvious at all, and before I knew it I was deep in some very vicious differential equations. -- Meni Rosenfeld (talk) 21:16, 6 October 2010 (UTC)

It's a simple Parabolic partial differential equation (aka, 1-dimensional heat equation) with a free boundary condition (for which we don't have an article, although we have a stub for yet another free boundary condition of which I had never heard.) It may be similar to the adaptation of the Black–Scholes model to American options, but much less complicated. — Arthur Rubin (talk) 21:51, 6 October 2010 (UTC)

In case it wasn't clear, my anecdote was for the nerd sniping problem. I haven't had time to think about the OP's problem yet. -- Meni Rosenfeld (talk) 08:47, 7 October 2010 (UTC)

Some formalization. Consider Bernoulli random variables (with p=1/2)$X_{1},X_{2}\ldots$. Denote $S_{n}=\sum _{i=1}^{n}X_{i}$. Then $Y_{n}={\frac {S_{n}}{n}}$ is exactly your pay off after n throws. Centralize it with $Z_{n}=S_{n}/n-1/2$ (which incidentally would be your profit if you paid 1/2 to participate in the game) to get

$E(Z_{n+1}|Z_{n})=Z_{n}\left(1-{\frac {1}{n+1}}\right)$, $n\geq 1$

.So understandably, you should continue flipping the coin as long as $Y_{n}<1/2$ per Bkell above. And intuitively, Bkell's suggestion above also makes sense because on average the next throw will decrease your pay off if $Y_{n}>1/2$ However the issue is more complicated because if we look at

$P(\sup _{k>n}Y_{k}>Y_{n}),$

which is clearly more than 1/2. And what's about $E(\sup _{k>n}Y_{k})$? (Igny (talk) 23:19, 6 October 2010 (UTC))

See Optimal stopping#Examples (Coin problem), which doesn't have the solution. On the other hand, if the payoff were to be ${\sqrt {12}}\left({\frac {S_{n}}{n}}-{\frac {1}{2}}\right),$ then it would be equivalent to the continuous stopping problem with payoff ${\frac {W_{t}}{t}}$, where $W_{t}$ is a Wiener process. The expected payoff satisfies the differential equation:

${\frac {\partial }{\partial t}}f(x,t)=-{\frac {1}{2}}{\frac {\partial ^{2}}{\partial x^{2}}}f(x,t)$ for $x<X(t)\,$

$f(x,t)={\frac {x}{t}}$ for $x\geq X(t)$

$\lim _{x\rightarrow -\infty }f(x,t)=0$

and probably some other conditions relating to path integrals.... — Arthur Rubin (talk) 03:10, 10 October 2010 (UTC)

$E(\sup _{k>n}Y_{k})$ (or $E(\sup _{T>t}W_{T}/T)$)is a different problem entirely, because you won't know in advance when the sup is attained. — Arthur Rubin (talk) 04:34, 10 October 2010 (UTC)

Thanks! Count Iblis (talk) 02:23, 13 October 2010 (UTC)

Set theory notation

If you don't understand the first part, don't worry; just stick with it. The first part is just a motivation. The last part should be simple and I'm annoyed that I can't answer it for myself. Any way, here goes...

The set of functions in n variables with critical point 0 and whose hessian matrix has corank k ≤ n has codimension 1⁄2·k·(k+1) in the space of function germs with critical value 0 at 0. Thus, the set of functions of corank 2 has codimension 3, the set of functions of corank 3 has codimension 6, and those of corank 4 have codimension 10. That means that in generic one and two parameter families of functions we have only singularities of corank 1. If the number of parameters is less than six we have singularities of corank at most 2. If the number of parameters is less than 10 we have singularities of corank at most 3. If the number of parameters is less than 15 we have singularities of corank at most 4. In general, if the number of parameters is less than 1⁄2·k·(k+1) then we have singularities of corank at most k. I want to express this relationship the other way around. So, if the number of parameters is less than p then we have singularities of corank at most k(p). Well, we can invert p < 1⁄2·k·(k+1). We consider 2k² + k – 2p = 0, and so

$k=-{\frac {1}{2}}\pm {\frac {1}{2}}{\sqrt {1+8p}}.$

The positive sign of the radical is the correct one since k ≥ 0. Since k should be a whole number we use the floor function:

$k(p)=\left\lfloor -{\frac {1}{2}}+{\frac {1}{2}}{\sqrt {1+8p}}\right\rfloor .$

Evaluating the the sequence { k(p) : p ≥ 0} give a sequence where the first two terms are equal to 1, the next three terms are equal to 2, the next four terms are equal to 3, the next five terms are equal to 4, etc. In other words:

$\{k(p):p\geq 1\}=\{1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,\ldots \}\ .$

After all that, here's my question:

• Can anyone come up with a set notation definition that doesn't use radicals or the floor function?

— Fly by Night (talk) 21:26, 6 October 2010 (UTC)

If you agree to have an ordered pair representation, $\{(1,1),(2,1),(3,2),\cdots \}$, then it is $\{(m(m+1)/2+n,m)|m>0,0\leq n\leq m\}$. Otherwise you should be a bit clearer about what we can use. For example, you have $k(p)=\sum _{i=1}^{p}I(\exists m\in \mathbb {N} (i=m(m+1)/2))$ but I don't know if that's legal. -- Meni Rosenfeld (talk) 09:08, 7 October 2010 (UTC)

I think I've got it. They elements in the sequence are given by

$a_{k}=n\ \ \forall \ \ {\frac {1}{2}}n(n+1)\leq k<{\frac {1}{2}}(n+1)(n+2)\ .$ — Fly by Night (talk) 10:58, 7 October 2010 (UTC)

Minimal domain hash function

First, I want to define what I mean by hash to avoid confusion... Given unique values I₀, I₁, ... I_n over the domain R_I, a hash function H(I) will return a unique values J₀, J₁, ... J_n over the domain R_J. Often, to ensure uniqueness, R_J is much larger than R_I. What I want to learn about is how to solve the following problem. Given a set of unique values I, create a hash function that ensures unique values in J with a minimal domain R_J. The catch is that the values of I given do not completely fill the domain. For example, you can receive A, H, U, and T over the domain A through Z. I am not interested in sequential hash functions, such as the trivial "mod by the size of the domain" hash. The order of I should not be the same as the order of J - that is the entire point of the problem being solved. This function should randomize the order of the original values and replace the actual values with new values. I assume this problem has both a common name and a simple solution, but I haven't been able to find it. -- kainaw™ 23:34, 6 October 2010 (UTC)

See minimal perfect hashing. 72.229.127.238 (talk) 05:48, 7 October 2010 (UTC)

Thanks. I was certain it would have a common name. -- kainaw™ 14:48, 7 October 2010 (UTC)

Complete theory with a finite number of countable models

I'm teaching an intro Model Theory course, and I'm getting to the number of countable models (Vaught's Conjecture, Morley's Theorem). I'd like to give an example of complete theories with 3, 4, 5, ... countable models. I know Ehrenfeucht's standard example, of course. Unfortunately, I wasn't really thinking ahead and put the 3 model version of it on the final, so I can't use that. I'm aware of a fair number of results suggesting that all examples are fundamentally the same as Ehrenfeucht's, but I just need it to be superficially different. Preferably hiding the linear order, for example. —Preceding unsigned comment added by 130.195.5.7 (talk) 23:53, 6 October 2010 (UTC)