/sci/ - Science & Math

>>11654138
If by calculus you also refer to analysis. Then calculus, otherwise fuck both.

Got a combinatorics question that should be straightforward but I fucking suck with combinatorics. I'm thinking about drawing various combinations from the set [math][n] := \{ 1, \ldots, n \}[/math]. Fix some [math]\ell[/math]-length combination [math]t \subset [n][/math], i.e. [math]|t| = \ell[/math] for [math]1 \leq \ell \leq n[/math]. Now consider the set of all [math]m[/math]-length combinations, [eqn]S_m := \{ s \subset [n] \mid |s| = m \}.[/eqn] There are [math]\binom{n}{m}[/math] element in each [math]S_m[/math].

My question is: for how many elements of [math]S_m[/math] does [math]t[/math] have an odd number of overlaps? That is, for how many [math]s \in S_m[/math] is it true that [math]|s \cap t| = 1 \text{ mod } 2[/math]? (Equivalently, one could calculate it [math]0 \text{ mod } 2[/math]. and subtract that answer from [math]\binom{n}{m}[/math].) Keep in mind that [math]|t| = \ell[/math] and [math]m[/math] and [math]\ell[/math] are completely independent of each other.

Even just a potentially useful combinatoric method to attack this problem would be much appreciated.

>>10649799
Are you fucking registered as a masters student, or a phd student? There's your answer. I don't understand what you're trying to ask that isn't answerable by going to your student portal.

>>9390680
To count the real numbers, you need to put them in a list.
Say you have a list of all the real numbers, in whatever order you want. We're going to write the numbers in decimal notation, and we'll remove all the numbers which are not between 0 and 1 for now. We also have to be careful not to write any numbers with infinitely many 9's trailing at the end, since we can just write these numbers with infinite zeros. In fact, just throw zeros on any terminating decimal. Our list is still valid.
For example, our list could start:
0.5823...
0.4821...
0.5000...
0.8917...
And on and on.

Let's think and see if we missed a number on our list.

For instance, what if there was a number whose first decimal place was different from the first decimal place of the first number in our list? In the list I made, our real number has something that isn't 5 in the first position.
0.2...

Now what if it has a different 2nd place from the 2nd place of the second number? We can't pick 8, so I'm going to now pick 0.26...

Continue this and get some number, in this case I'm constructing 0.2613... which is pretty random but you can construct such a number systematically (if 1, change to 2, if not 1, change to 1)

But this number can't be anywhere on the list! Because it's different from the first number by at least one decimal place, and from the second number, and the third, and so on, all the way down the entire list. It's not any of the numbers on the list, so we missed one number. In fact, we were supposed to have all the numbers between 0 and 1 to begin with - but we were missing a ton - so that's it. Our list is always going to be incomplete.
Since that's just an interval of the real numbers, you definitely can't count the whole set!
This method is called Cantor's Diagonal Argument.