Wikipedia:Reference desk/Archives/Mathematics/2009 August 18

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.

August 18

Combinatorics question

I have a list of N categories with Nk members each. (i.e. the kth category has Nk members, and these number of members may be unique, but not necessarily distinct.) I'd like to take a random member from only 3 of the categories. How many ways can I do this? The brute force way to do select 3 groups (and there are obviously N choose 3 ways to do this) and then multiply the cardinality of each of those 3 groups to get the number of ways to choose an item from each. Iterate over all distinct groups of 3 categories. Is there an analytical way to do this? or a combinatorial formula? Any relevant literature?

Here's an example if my above explanation was confusing.

|A| = 4, |B| = 3, |C| = 5, |D| = 1.
A, B, C = 4*3*5 ways = 60
A, B, D = 4*3*1 ways = 12
A, C, D = 4*5*1 ways = 20
B, C, D = 3*5*1 ways = 15
                     
Sum                   107

Also, if anyone knows how to do this in R (I'm sure it's really simple, that would be much appreciated.)

Thanks, --Rajah (talk) 03:32, 18 August 2009 (UTC)

Notice that, for instance, (a+b+c+d)*(a+b+c+d) = aa+bb+cc+dd+2(ab+ac+ad+bc+bd+cd). So, if the sum of a through d is s1, and the sum of the squares of a through d is s2, ((s1^2)-s2)/2 is the sum of all pairs of different letters. If S_n is the sum of all the nth powers of the letters, I think what you want is ${\frac {1}{6}}S_{1}^{3}-{\frac {1}{2}}S_{1}S_{2}+{\frac {1}{3}}S_{3}$. That would be, in this case, (1/6)(a+b+c+d)³-(1/2)(a+b+c+d)(a²+b²+c²+d²)+(1/3)(a³+b³+c³+d³) = (1/6)(13)³-(1/2)(13)(51)+(1/3)(217) = 107. It doesn't look too helpful for a small example, but imagine how much easier it would be for a list of 20 numbers. Black Carrot (talk) 05:25, 18 August 2009 (UTC)

Some related ideas: multiplicative functions (such as the divisor function) and symmetric polynomials. Black Carrot (talk) 05:34, 18 August 2009 (UTC)

Yes, you want the 3rd elementary symmetric polynomial, and as BC shows you can express it in other bases of symmetric polynomials. If you need to deal more heavily with the combinatorics of symmetric polynomials you may find useful R.P.Stanley's book "Enumerative Combinatorics", (chapt 7, vol 2). [1]. PS: what do you mean by how to do this in R? --pma (talk) 06:01, 18 August 2009 (UTC)

Yeah, I meant R, the programming language, as Bo Jacoby pointed out. I was just being lazy, sorry about that. Elementary symmetric polynomials are exactly what I wanted, nice work. --Rajah (talk) 15:12, 18 August 2009 (UTC)

R (programming language) probably. Note that f(x)=(x+a)(x+b)(x+c)(x+d)= x⁴+(a+b+c+d)x³+(ab+ac+ad+bc+bd+cd)x²+(abc+abd+acd+bcd)x+abcd, so the number you want is the coefficient of x in the taylor expansion of f(x). A solution coded in J (programming language) looks like this

  (<-4 3 5 1)&p. t. 1
107

Bo Jacoby (talk) 14:11, 18 August 2009 (UTC).

Awesome, thanks. All of these replies are very helpful! --Rajah (talk) 15:00, 18 August 2009 (UTC)

Limit of integral

Show that if

$\lim _{h\to 0}{\frac {1}{h}}\int _{a}^{b}|f(x+h)-f(x)|\,dx=0$,

then there is some constant c such that $f(x)=c$ a.e.

Here's the thing. I have a proof, but I just read it through again and I have a statement in the middle that I am not sure is true. The first thing to do is, for any $a\leq x_{1}<x_{2}\leq b$, given $\epsilon >0$

$|\int _{x_{1}}^{x_{2}}{\frac {1}{h}}(f(x+h)-f(x))\,dx|\leq \int _{x_{1}}^{x_{2}}{\frac {1}{h}}|f(x+h)-f(x)|\,dx\leq \int _{a}^{b}{\frac {1}{h}}|f(x+h)-f(x)|\,dx<\epsilon$

for $h\in (-\delta ,\delta )$ (where $\delta$ comes from $\epsilon$ since the limit is 0). What this proves is

$\lim _{h\to 0}{\frac {1}{h}}\int _{x_{1}}^{x_{2}}f(x+h)-f(x)\,dx=0$

for any such $a\leq x_{1}<x_{2}\leq b$. From here, what I have down is set $F(x)=\int _{a}^{x}f(t)\,dt$ and that since f is integrable on [a, b] for $h\in (-\delta ,\delta )$, then $F'(x)=f(x)$ a.e. But, I never showed f is integrable and I am not sure if it is. Any ideas?

Just so you know, the next step I have, assuming that is right:

$0=\lim _{h\to 0}{\frac {1}{h}}\int _{x_{1}}^{x_{2}}f(x+h)-f(x)\,dx=\lim _{h\to 0}{\frac {F(x_{2}+h)-F(x_{2})}{h}}-{\frac {F(x_{1}+h)-F(x_{1})}{h}}$

Assuming f is integrable, F is absolutely continuous so that we end up getting the limit to be $0=F'(x_{2})-F'(x_{1})=f(x_{2})-f(x_{1})$ for those $x_{1},x_{2}$ where $F'(x)=f(x)$ and thus it is equal to the same constant almost everywhere. StatisticsMan (talk) 21:37, 18 August 2009 (UTC)

Ok, so we only have $f:\mathbb {R} \to \mathbb {R}$ with no assumptions of integrability nor measurability; for all $a<b$ in $\mathbb {R}$ that limit is 0 and the thesis is f(x)=0 a.e. (Alternatively, one can assume the limit to be 0 of a fixed pair a<b, and then the conclusion is that f(x)=0 a.e. in the interval [a,b]. One can easily prove each of the two statements from the other).

Maybe there are simpler ways, but one possibility is doing your program for the function $\textstyle g_{y}(x):=f(x+y)-f(x)$ for any fixed $\textstyle y\in \mathbb {R}$ and draw the consequences. By hypothesis, each $g_{y}\in L_{\mathrm {loc} }^{1}(\mathbb {R} )$, and since we have

${\frac {g_{y}(x+h)-g_{y}(x)}{h}}={\frac {f(x+y+h)-f(x+y)}{h}}-{\frac {f(x+h)-f(x)}{h}}$

you can do your complete argument and conclude that the function $g_{y}(x)$ is a constant (depending on y). Going back to the hypothesis on f(x), this tells us that the integral in $x$ is an integral of a constant function, thus just multiplication by (b-a), that is, f is a function with $f^{\prime }(x)=0$ in the classical sense for all x, and the conclusion follows. --pma (talk) 07:07, 19 August 2009 (UTC)

But in fact in the above argument I assumed $\scriptstyle x\mapsto g_{h}(x):=f(x+h)-f(x)$ to be locally integrable. Assuming also w.l.o.g. that f is compactly supported, one can write e.g. $\scriptstyle f(x)=-g_{1}(x)+f(x+1)=-\sum _{k=1}^{N}g_{1}(x+k)$ for N large enough, so f is $L^{1}$ too. If we assume the minimal requirement only, that is, that $|f(x+h)-f(x)|$ is (loc) integrable for all h, I am not sure about whether f is measurable. For sure the original statement is already of interest in the assumption of f measurable or integrable; a result under a more general hypothesis wouldn't necessarily be more useful.--pma (talk) 12:06, 19 August 2009 (UTC)

Well, I have seen a "solution" from a professor where he provides almost no detail. It took me a long time to fill them in, perhaps wrongly. But, he seems to be assuming f is measurable, though it is not in the problem. I actually did not notice that I was assuming that without being told, so good point. His entire solution is: "If the limit holds at the end points, then for every a < x1 < x2 < b it is surely true that $\lim _{h\to 0}{\frac {1}{h}}\int _{x_{1}}^{x_{2}}|f(x+h)-f(x)|\,dx\to 0$ as h goes to 0 and hence the limit without the absolute value signs inside also tends to zero with h. However

${\frac {1}{h}}\int _{x_{1}}^{x_{2}}(f(x+h)-f(x))\,dx={\frac {1}{h}}\left(\int _{x_{2}}^{x_{2}+h}f(x)\,dx-\int _{x_{1}}^{x_{1}+h}f(x)\,dx\right)\to f(x_{2})-f(x_{1})$

and hence the result." Perhaps he is also assuming that it is integrable. It seems so, right? StatisticsMan (talk) 12:25, 19 August 2009 (UTC)

Nice; I suppose you mean the last expression to be written without the big parentheses. For the last equality, f should be assumed to be integrable, yes. After all it seems that the point of the exercise is not that. NOte that your proof with F(x) is almost identical to your professor's one (in both the key point is using that (F(x+h)-F(x))/h converges to f(x) as h tends to 0; you are not using anything else about absolute continuity, and you may even avoid mentioning it) --pma (talk) 14:23, 19 August 2009 (UTC)

What you said would make it what I meant, but what I really meant to do was the big parentheses and not have the 1/h on the inside. So, I just took that out. Thanks for the info. I guess if he is assuming those things as well, I am fine with assuming them. I just didn't know for sure. My test starts tomorrow morning! So, I must go study some more. StatisticsMan (talk) 15:19, 19 August 2009 (UTC)

very good; as your coach, I recommend you to stop studying in the afternoon and relax till tomorrow. You have all to do it. and everybody in the RD/M roots for you!  ;) --pma (talk) 16:33, 19 August 2009 (UTC)

Hehe, thanks. Unfortunately, I am not going to take the afternoon off because I am trying to read through every solution I have written up to qual problems. This will end up taking about 2 full days and I still have 30 problems to read. Then, I have some other problems with solutions I want to look through as well. Thanks for the support. StatisticsMan (talk) 18:58, 19 August 2009 (UTC)

Well, I did enough to pass if everything I did was correct, or so I think. And, I think it was but I could be wrong. They aren't real clear about what it takes to pass. But, the first problem on the real analysis side was to show if the integral of a function is 0 on ever interval, then the function is 0 a.e. So, thanks for explaining to me how to do that problem, pma. Without it, I definitely did not pass. I will find out in a week or so if I passed. StatisticsMan (talk) 20:34, 20 August 2009 (UTC)