Wikipedia:Reference desk/Archives/Mathematics/2010 September 7

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.

September 7

What does this expression count?

Hi. I'm working on a combinatorial problem, and I've encountered a lot of expressions with form similar to the following: ${\tbinom {9}{4}}-{\tbinom {8}{3}}+{\tbinom {7}{2}}-{\tbinom {6}{1}}+{\tbinom {5}{0}}$. Can anyone think of a situation where this counts something? If I can think about a real-world representation of it, I might be able to count that same quantity with a different technique, and thus establish some kind of identity.

Thanks in advance for any ideas. -GTBacchus^(talk) 02:06, 7 September 2010 (UTC)

You can often simplify that kind of expression mechanically with WZ theory, if that's of any interest. See the A=B book (online) linked in the references to that article. For your concrete example I'd put a few terms into OEIS and see what comes out. 67.122.211.178 (talk) 06:11, 7 September 2010 (UTC)

For example, you have this. -- Meni Rosenfeld (talk) 09:18, 7 September 2010 (UTC)

It looks like some form of the Inclusion-exclusion principle to me. 198.161.238.19 (talk) 18:02, 7 September 2010 (UTC)

What about the number of subsets S of {1,...,9} with card(S)=5 and such that max(S) has the same parity of 9?--pma 20:05, 7 September 2010 (UTC)

Good grief, not another homework question

If f is continuous on [0,2], and f(0) = f(2), prove that there is a real number x ∈ [1,2] such that f(x) = f(x-1).

Intuitively I know this should be true, but that hasn't helped me out much. The only approach I can think of is to show that you can find infinitely many pairs of numbers such that f(a) = f(b), and that a-b will range from 2 to 0, but this hasn't helped. Can anyone help me? 74.15.136.172 (talk) 23:02, 7 September 2010 (UTC)

Consider the function g on [1,2] with g(x)=f(x)-f(x-1). Algebraist 23:10, 7 September 2010 (UTC)

Got it, thanks! 74.15.136.172 (talk) 00:17, 8 September 2010 (UTC)

Dixon's Method of Factorization

Perhaps I'm being slow here, but under 'Method' on Dixon's factorization method, why is it the case that N = gcd(a − b, N) × gcd(a + b, N)? Surely N -divides- gcd(a − b, N) × gcd(a + b, N), since gcd(A,BC) divides gcd(A,B)gcd(A,C), but why must the equality hold here? Is it something to do with the method of computing a and b? Or perhaps I'm missing something?

Cheers, 92.40.243.116 (talk) 23:24, 7 September 2010 (UTC)

The equality is wrong, unless a + b and a − b are coprime (take N = lcm(a + b,a − b) for a counterexample).—Emil J. 10:03, 8 September 2010 (UTC)