Mathematics desk
< September 1	<< Aug \| September \| Oct >>	Current desk >

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 2

Graph theory

How many trees are there with n vertices such that each vertex has degree at most 4, if ones that are the same other than the naming of the vertices are excluded? --168.7.237.248 (talk) 04:08, 2 September 2012 (UTC)[reply]

By working out the first few terms by hand and searching the OEIS, I found A000602. -- BenRG (talk) 06:06, 2 September 2012 (UTC)[reply]

What's the closed form for that sequence? --128.42.223.234 (talk) 16:03, 2 September 2012 (UTC)[reply]

I don't know. The OEIS entry links to some unreadable Maple code. -- BenRG (talk) 21:00, 3 September 2012 (UTC)[reply]

The answer would depend on the meaning of a tree—whether you consider a tree as defined in a graph theory (i.e. undirected connected graph with no cycles) or as defined in computer science (a connected directed graph with a specific root and a transitive is-a-child relation, in which every node is a child of exectly one parent, except a root which has no parent). In the latter case also decide whether to consider (or not) specific ordering of children (is a root with a single left child equivalent to the root with a single right child etc.).
Anyway I do not know the answer in any case. --CiaPan (talk) 05:35, 5 September 2012 (UTC)[reply]

PS. Is this problem related to classifying carbon chain structures of organic compounds in organic chemistry? (e.g. IUPAC nomenclature of organic chemistry) CiaPan (talk)

Maths and music

Hi. First of all, I want to acknowledge that the following is homework. However, I've come here because I actually don't understand the problems:

I'm asked to find the continued fraction for $\log _{2}(3/2)$ , calculate convergents ${\frac {p_{n}}{q_{n}}}$ , and then find the first $q_{n}>12$ . That's all fine: $q_{n}=29$ . But then "Compute the relative frequency of the fifth harmonic in equal temperament in this scale with $q_{n}$ semitones and compare to the error to 3/2 to that of our usual scale with 12 semitones." I don't understand any of this. I've tried reading a few Wikipedia articles, but it still makes no sense to me; I have no musical background.
And I have no idea where to begin with this one: "When building a guitar it is useful to be able to determine where to put fret i in relation to fret i + 1. Find the numerical value of the ratio of the length of the string remaining when pressing down at fret i to the distance of fret i to fret i + 1, assuming the usual 12 semitone scale and equal temperament."

Can anyone give some advice on these questions? As I said, I've tried reading a few articles, but the musical terminology is lost on me. I'd appreciate it if someone could distill these problems into a more pure mathematical form, or – just as helpfully – explain in very simple terms the music theory I need to know to comprehend them. PS: I have quoted these questions verbatim. Feeling like they're grammatically incorrect? You and me both. —Anonymous Dissident^Talk 13:36, 2 September 2012 (UTC)[reply]

What does "the first

q_{n}>12

" mean? Please, write down something like

log 2 3/2 =

(some fraction with

p

and

q

). Incnis Mrsi (talk) 14:50, 2 September 2012 (UTC)[reply]

Surely that means "the value of

q_{n}

for the least n such that this is more than 12" (I don't know continued fractions.) However, I do know what 12-semitone equal temperament is so I'll try to be helpful. Musical intervals, in terms of frequencies, are ratios. An octave corresponds to doubling the frequency. In an octave under the standard system there are 12 semitones (A-A#-B-C-C#-D-D#-E-F-F#-G-G#-A), and equal temperament divides them equally (in a logarithmic sense), so that going up a semitone is multiplies the frequency by the twelfth root of two. Presumably you are considering a twenty-nine semitone equally tempered scale so going up a semitone is multiplying by the twenty-ninth root of two. Then for the fifth harmonic, I think we're looking at perfect fifths. I can't make out harmonic series (music), but the former says that the "just" interval for a perfect fifth is 3/2 (ie the frequency goes up by that factor). In equal temperament, it's a bit wrong (because the twelfth root of two is ugly) - I don't see where the fifth harmonic comes in. For the second question, Guitar#Frets says that changing by one fret changes by a semitone. By virtue of the assumption of twelve-tone equal temperament, that means the frequency changes by (a factor of) the twelfth root of two. If you (like I was) are having trouble with parsing the sentence we want the ratio of the (remaining string when you press at the i'th fret) [i.e. that bit that vibrates to give you that note] to the (distance between the i'th and (i+1)'st). So you need to assume frequency f for the ith fret, work out how long the string needs to be, work out how long it needs to be for the next note, and hope f cancels.

I hope that helps slightly, but it probably won't. Straightontillmorning (talk) 16:09, 2 September 2012 (UTC)[reply]

I think when they say "fifth harmonic" they must be really mean the perfect fifth, since they ask to compare the ratio to 3/2. In that case all the question is asking is to compare 2^7/12 to 3/2 and then compare 2^17/29 to 3/2. Rckrone (talk) 23:58, 2 September 2012 (UTC)[reply]

"fifth harmonic" may really mean fifth harmonic, or rather the major third; the history of musical temperament can be seen as a series of attempts to express 4:5 with factors of 2 and 3. So here's my paraphrase of the first question: Using the method of continued fractions, find the next rational approximation to lg(3/2) after 7/12, and discuss the quality of major thirds in the equally-tempered scale implied by that ratio. (I don't get 17/29; I get 24/41 and then 31/53 – but never mind, maybe you used a slightly different form of the CF, and you ought to get 41 next!) So: what is 2^9/29 or 2^13/41? —Tamfang (talk) 04:35, 3 September 2012 (UTC)[reply]

Reading Perfect fifth#The pitch ratio of a fifth, I would interpret "compare to the error to 3/2 to that of our usual scale with 12 semitones" as: for 12 semitones you get 1200*ln(1.5)/ln(2)=701.995 or 2% of a semitone wider than semitone 7; for 29 semitones it's 2900*ln(1.5)/ln(2)= 1696.39... 3.6% of a semitone different from semitone 17. But I've got no idea what the "relative freq of the 5th harm" would mean; relative to what, a semitone? Ssscienccce (talk) 05:34, 3 September 2012 (UTC)[reply]

Relative to the tonic. —Tamfang (talk) 23:15, 3 September 2012 (UTC)[reply]

In guitar tuning, there are subtleties in frettage that I don't understand, and you're probably not expected to understand either. The simple version is that the frets are placed so that the lengths of a given string from the bridge to each fret form a geometric sequence, whose ratio is (usually) the twelfth root of two. Note that you're not asked for the length of the string, though. —Tamfang (talk) 04:45, 3 September 2012 (UTC)[reply]

Scale (string instruments) has the details; lets call a=

\scriptstyle {\sqrt[{12}]{2}}

for short; P(i+1)=P(i)/a , you need Pi/(Pi-P(i+1)) = Pi/(Pi-Pi/a) = ... = a/(a-1) = 17.817 Ssscienccce (talk) 06:30, 3 September 2012 (UTC)[reply]

~~Are you sure about 29? I get: [0;1,1,2,2,3,1,5,2,23,2,2,1,1,55,..], calculate it till 23: 1/(1+1/(1+1/(2+1/(2+1/(3+1/(1+1/(5+1/(2+1/23)))))))) = 0.5849625024, and 2^0.584... gives me 1.500000002~~ Dooh! I should learn to read.. Ssscienccce (talk) 06:58, 3 September 2012 (UTC)[reply]

I also get q_n=41 rather than 29. How did you get 29? I also know that Harry Partch composed for a 41-note scale. My first thought (like some others) about "fifth harmonic" was that it really should have said perfect fifth, but Tamfang's explanation about the major third also makes sense. The equal-tempered major third in the 12-note scale is off by about 0.8% and you can similarly calculate the error in the 41-note scale. I'll skip the details since I think figuring them out yourself is part of the exercise. 67.119.15.30 (talk) 15:05, 7 September 2012 (UTC)[reply]

Woops, after I noticed my mistake (thinking it was about a_n > 12, instead of the resulting denominator), I didn't bother checking any further, but you're right, [0;1,1,2,2,3] becomes 24/41. Ssscienccce (talk) 17:01, 7 September 2012 (UTC)[reply]

Binomial process

I have a closed population which is subjected to a hazard which removes them from the population. I am modelling the number removed each month using a binomial distribution with a constant percentage hazard rate. What is the distribution of the cumulative number of removals after the first T months? I don't necessarily need an exact distribution - the population is large enough that a normal approximation should be sufficient for my purposes. Is it as simple as a mean of n*(1-(1-p)^T) and a variance of n*(1-(1-p)^T)*(1-p)^T? I know it is that simple for a Poisson process, but I suspect it doesn't work the same way for a Binomial. Thanks for your help. --Tango (talk) 17:25, 2 September 2012 (UTC)[reply]

I don't think it's a question of Poisson versus binomial. My intuition is that with a constant percentage hazard rate, the strong law of large numbers should give you a log-normal distribution in the limit of large T. Looie496 (talk) 17:46, 2 September 2012 (UTC)[reply]

Thanks, but I should have said, T is quite small. For a Poisson, the absolute rate is constant, so you can just scale it. In this case, the rate is reducing because n is reducing, so I doubt it is so simple. --Tango (talk) 18:17, 2 September 2012 (UTC)[reply]

Any single individual will have a probability of survival equal to (1-(1-p)^T). And this will be independent from all other individuals. So the whole T months period for all individuals will be n independent trials with sucess chance (1-(1-p)^T). This means that the number of survivors will be Binomially distributed with mean and variance as given in original post. Taemyr (talk) 21:24, 2 September 2012 (UTC)[reply]

Of course it is - I was over complicating the whole thing. Thanks! --Tango (talk) 21:36, 2 September 2012 (UTC)[reply]

Resolved

Stone Cetch Compactification using ultrafilters

Hello, In this topology, I saw in a proof that: $x\in {\overline {\cup A}}$ and $x\in {\overline {\cup B}}$ implies that $(\cup A)\cap (\cup B)\neq \emptyset$ . Can somone explain why this is true? since, this claim is not true in topology in general... Thanx. — Preceding unsigned comment added by General Topology (talk • contribs) 18:32, 2 September 2012 (UTC) General Topology (talk) 18:43, 2 September 2012 (UTC)[reply]

If I understand from your mention of ultrafilters and such, you are talking about the Stone–Čech compactification of a discrete space X, is that right? In that case, the compactificaiton of X is equivalent to the Stone Space of the set of all subsets of X. For x a subset of X let b(x) be all ultrafilters of X containing x, then {b(x) : x} is a basis. It's obvious, then, that for every open set U there is a collection Y of subsets of X so that U is the collection of ultrafilters meeting Y. [I'm putting TA, TB, etc. for the union of all sets in A, B, etc.] So, in your case, given collections of ultrafilters A and B, it follows cl(A) is exactly the ultrafilters made from sets in TA, similarly for cl(B). Thus, Tcl(A) = TA and the result follows. Two quick notes: since you didn't say what A was exactly, I'm guessing that A is a set of uf's and that you meant to write union(closure A) not closure(union A), I'm sorry if I'm wrong; I haven't thought about this in a while and am just working this out in my head, so I apologize if there is any stupidity in my answer. :-) Phoenixia1177 (talk) 22:43, 2 September 2012 (UTC)[reply]

Hi:) yes, I ment the Stone–Čech compactification of a discrete space X. I have a problem with some convergence properties of this space. Let me try and ask a slightly different question. From what I understand, this space is not Frechet Urysohn (a topological space is frechet urysohn if for every $x\in {\overline {A}}\setminus A$ there is a sequence of points in A that converges to x). Can anyone tell why?? General Topology (talk) 11:31, 4 September 2012 (UTC)[reply]

I'm working this out on a pad of sketch paper at work, so I apologize for any stupidity. That said, via our above basis, if a(n) is a sequence of ultrafilters, then a(n) converges to a iff for every b in a there is an n(b) so N >= n(b) implies b is in a(N)[assume n(b) is the smallest such indice in what follows]. Now, let X be infinite and a(n) be a nontrivial sequence converging to a, an ultrafilter. Well order a and define F(N) to be the least element larger than everything in {b : n(b) <= N}. Clearly, F(n(b)) >= b for any b, thus, F has to have an unbounded subsequence. However, by Easton's Theorem, the cofinality of a must be larger than the cardinality of X [a has the cardnality of X's power set.] In other words, since X is, at least, countable, we cannot have an unbounded sequnce in a, thus, there can be no nontrivial convergent sequences; which answers your question:-) Phoenixia1177 (talk) 06:28, 5 September 2012 (UTC)[reply]

A simpler proof would be to observe that the set of principal ultrafilters is dense, but has the same cardinality as X, where as the set of ultrafilters has cardinality the power set of the power set of X; hence there should be more ultrafilters than can be gotten than through convergence, in general.Phoenixia1177 (talk) 08:15, 5 September 2012 (UTC)[reply]

(This is my last response, I swear) If you're looking for something more concrete using free ultrafilters, let's take X to be the naturals. Put p(k) for the kth prime, A(k) for all numbers divisible by p(k), and B(k) for all numbers congruent 1 mod p(k). Then, for any collection of infinite sets with the finite intersection property there is a free ultrafilter contatining each of them, thus we have free ultrafilters U(n) corresponding to the collection {A(k) : k >= n} union {B(k) : k < n}. Clearly, there is an ultrafilter U for {A(n) : n} in {U(n) : n}'s closure since A(n) is in U(n) for all n, however, there is no sequence in {U(n): n} that converges to it. Since A(k) cannot be in any U(n > k) because A(k) is disjoint B(k), we cannot have A(k) in a tail of any sequence in {U(n) : n}, thus the result:-)Phoenixia1177 (talk) 09:46, 5 September 2012 (UTC)[reply]