Wikipedia:Reference desk/Archives/Mathematics/2007 September 4

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 4

Will it pull free?

I've looked at the knot theory article, but find it too hard to follow, so wondered if someone could answer the following more directly.

While playing with a single piece of string, I twisted and fed it into various shapes to get different configurations of loops and crossings. With the more complex cases it was not at all obvious whether or not the string would form a knot when the two free ends were pulled apart. Is there a quick way of establishing if such a tangle will pull free, i.e. back to just a length of string?

To describe each tangle I devised a notation of lettering successively each crossing met while moving along the string from one end, using capital for "over" and lowercase for "under", e.g. a simple loop is Aa (or aA), and a loop with twist is AbBa, both of which pull free. An overhand knot can be described by AbCaBc, while all of these pull free: ABCabc, ABcabC, AbcaBC.

Increasing the number of crossings, AbCdBaDc, aBcDeAbEdC and aBcdEfDeFAbC form knots while AbCdBEfaDceF and aBcCDeFAbgEdGf pull free. Increasing again, both of abcDeABfdGhCFEgH and aBCdeFGchAigDEfIbh form knots. So is there a set of rules, extending the obvious fact that a pair like Aa disappear, whereby any such letter sequence can be simplified and assessed? There seems to be an analogy with Boolean algebra, but I can't go any further.…86.132.166.112 12:58, 4 September 2007 (UTC)

You seem to be developing a notation similar to Dowker notation. You can develop a set of equivalence relations based on the Reidemeister moves, for example the first Reidermeister move implies that the sequence αaAβ can be manipulated to give a knot with sequence αβ. The other rules would give other ways of manipulating the sequence. This would give a set of rules to manipulate the string, which hopefully be able to distinguish whether you have the Unknot, that is whether you can solve the Unknotting problem. In practice such algorithms will work for small numbers of crossings but will become computationally much harder for larger crossing numbers. This sort of system was one of the earliest approaches to knot theory. --Salix alba (talk) 14:34, 4 September 2007 (UTC)

This is just semigroup/term rewriting... —Preceding unsigned comment added by 129.78.64.102 (talk) 04:10, 5 September 2007 (UTC)

I don't know if the most recent contribution above was intended to be helpful, but it meant absolutely nothing to me as the OP. Regarding the other contribution, I've tried to simplify my letter strings using the three rules cited, but with no great success. It is a great surprise to me to learn that a knot diagram with even a small number of crossings can't quickly be assessed as the unknot or not.…81.151.247.205 12:15, 7 September 2007 (UTC)

I think that's not quite the case. There are systems that can immediately tell you that two reasonably small knots are different, if you get lucky - the problem is, they don't always work, and they never tell you whether they're the same. That is, they lump knots into categories. If yours falls outside the unknot's category, you know they're different, but you know nothing if it falls in the same category. Knot invariant might help. Black Carrot 18:21, 7 September 2007 (UTC)

Another way, incidentally, is to show that it is equivalent (through Reidemeister moves or something similar) to something that is demonstrably not equivalent to the unknot (through some more efficient system). You could, for instance, get a table of the most basic knots, and see if you can turn it into one of them. They've all been proved distinct. Black Carrot 18:23, 7 September 2007 (UTC)

I've skimmed through some of the links, and I recommend Fox n-coloring as an interesting starting point. Black Carrot 18:31, 7 September 2007 (UTC)

Is there palindromic numbers in decimals & fractions?

Is there palindromic numbers in decimals & fractions? —Preceding unsigned comment added by 82.148.97.69 (talk) 13:46, 4 September 2007 (UTC)

I think you'll have to elaborate on what you mean. Capuchin 14:49, 4 September 2007 (UTC)

Probably this 12345.54321 and 12321/45654 ? the answer is yes.87.102.81.184 16:09, 4 September 2007 (UTC)

Or 25349/94352? The meaning is not fully clear.  --Lambiam 21:07, 4 September 2007 (UTC)

Binomial coefficient

I know that ${n \choose k}={\frac {n!}{k!(n-k)!}}$ but the thing I don't understand is how the denominator eliminates any repititions. Could someone explain (paying particular attention to why the factorial of 'k' and '(n-k)' are chosen as the denominator)? Thanks 172.206.6.102 18:16, 4 September 2007 (UTC)

Consider first the number of permutations, where the ordering of the elements is important. That is n! / (n−k)!. Why? Well, there are n ways of selecting the first element, (n−1) ways of selecting the second (since one was already selected, you have one less to choose from), down to (n−k+1) ways of selecting the kth. What is the product of these terms? Note that if you continued to multiply the terms (n−k), (n−k−1), ... 3, 2, 1, this product would be n! But what is the product of those extra terms? Simply (n−k)! That is where n! / (n−k)! comes from. Do you see where to go from here? Baccyak4H (Yak!) 18:24, 4 September 2007 (UTC)

I'm sorry but no. I understand the reasoning behind the numerator, but I still don't have a clue about the denominator. I'm afraid I'm still in need of help. I just learnt this in class today and I *really* want to understand it by tomorrow's lesson. Could someone please explain to me - I would be very grateful. 172.206.6.102 18:38, 4 September 2007 (UTC)

Let me try another way. Consider ordering n objects in a row. There are n! ways to do this. But now let's focus only on the first k objects. Whatever they are, there are (n−k)! ways to arrange all the rest of the objects after the first k, which do not affect which objects are in the first k objects since we are only looking at the ordering of objects we are not interested in. This means we have to divide by (n−k)! So now we have k objects selected. But note that the order of these k do not matter. For k=2, picking "AB" gives us the same combination as "BA". How many orderings are there? Here there are 2. For k=3, there are 3!=6 (ABC, ACB, BAC, BCA, CAB, CBA); in general there are k! orderings. So you need to divide by k! as well, giving the final result. Baccyak4H (Yak!) 20:23, 4 September 2007 (UTC)

Is the part you don't understand that n!/(n-k)! is n(n-1)(n-2)...(n-k+1)? Here's an example: 10!/5!=(10*9*8*7*6*5*4*3*2*1)/(5*4*3*2*1)=(10*9*8*7*6*5*4*3*2*1)/(5*4*3*2*1)=(10*9*8*7*6) Get it? — Daniel 22:51, 4 September 2007 (UTC)

I understand the operation it means, I just don't understand why the denominator is what it is. 172.206.6.102 05:24, 5 September 2007 (UTC)

Well, the denominator does not eliminate 'any repititions', it eliminates permutations. Consider n items ordered in a line. There are n! possible orders (permutations) of n items. Choose any of those orders and select k items from the left. There are, of course k! permutations of those k items, which change their order but keep the whole k-elements subset on the same k positions. Similarly there are (n−k)! permutations of the remaining items, which change their order but do not insert any of them into the initial k-items subset. So, for every chosen k-items subset of the n-items set there are k!·(n−k)! oders which give you those selected k items on first k positions. That's why you need to divide n! (number of all possible orders) by k! and (n−k)! (number of orders of the 'head' and 'tail') to get the number of distinct k-items subsets.
HTH. --CiaPan 06:03, 5 September 2007 (UTC)

Here's something that's helped before in questions like this. Take a small set of things like the letters A,B,C,D,E. Try to choose a small set from them, maybe any set of 3 things. The number of ways to do that would correspond to 5 choose 3, or ${5 \choose 3}$. Write down all possible ways of picking three letters, ignoring order:

ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE

That's 10. Now, in how many orders could you pick each of those? 3!, so 6. Therefore, we get:

ABC ACB BAC BCA CAB CBA

ABD ADB BAD BDA DAB DBA

ABE AEB BAE BEA EAB EBA

ACD ADC CAD CDA DAC DCA

ACE AEC CAE CEA EAC ECA

ADE AED DAE DEA EAD EDA

BCD BDC CBD CDB DBC DCB

BCE BEC CBE CEB EBC ECB

BDE BED DBE DEB EBD EDB

CDE CED DCE DEC ECD EDC

So, the total number of ways of choosing three letters, including order, is ${5 \choose 3}3!$ = 10*3! = 60. But the total number of ways of choosing three letters, including order, is also 5*4*3 = 5*4*3*2*1/2*1 = 5!/2!. The denominator there is just to cut the factorial off after a certain amount. So, divide both by 3! to get ${5 \choose 3}={\frac {5!}{3!2!}}$. Is that clearer? Black Carrot 06:05, 5 September 2007 (UTC)

Combinatorics often comes up with the same numbers in many different ways. Here's another way to look at binomial (and multinomial) coefficients.

Suppose we have a number of distinct items, say seven of them. The first question we ask is how many ways can we rearrange them; that is, we count the number of permutations. We reason that we have seven choices for the first item, six remaining for the second, and so on until we have only one choice for the last item. Using the convenient factorial notation, we have 7×6×5×4×3×2×1 = 7! permutations of seven items; or, more generally, n! permutations of n distinct items.

Now we play a game of "musical chairs"; for each ordering, we separate the first four items from the last three. Here are some examples:

abcdefg	gfedcba	gabcdef
dabcefg	dgfecba	cgabdef
dabcgef	dgfeacb	cgabfde
cdabgef	edgfacb	bcgafde

If all we care about is who gets a seat, not the ordering itself, then we notice that many different orderings produce the same outcome. We can order the first four items in 4! different ways, and for each of those ways we can order the last three items in 3! different ways. That is, a given outcome (who gets a seat) will be produced by 4!3! different orderings of the seven items. Therefore, we can count the number of distinct outcomes (combinations) by dividing the total number of orderings (7!) by the number of equivalences (4!3!). The same reasoning generalizes to tell us that when we must choose k items from n distinct items we have n! ⁄ (k!(n−k)!) possible outcomes.

We can easily generalize once more, to multinomial coefficients. For example, instead of splitting seven as four and three ("in or out"), split it as two and two and three.

abcdefg	gfedcba	gabcdef
dabcefg	dgfecba	cgabdef
dabcgef	dgfeacb	cgabfde
cdabgef	edgfacb	bcgafde

Redundancy elimination now yields 7! ⁄ (2!2!3!) possible outcomes. --KSmrq^T 16:20, 5 September 2007 (UTC)

Thank you all for that, I now understand. Thought of a new question though; how is it that a formula that works out the number of distinct combinations of items also works out the coefficient of a binomial expansion. How/why are they connected? asyndeton 17:48, 7 September 2007 (UTC)

That is really easy. Consider (x+y)⁴ expressed as a product of four binomials, and subscript each factor's x and y like so:

$(x_{\mathsf {a}}+y_{\mathsf {a}})(x_{\mathsf {b}}+y_{\mathsf {b}})(x_{\mathsf {c}}+y_{\mathsf {c}})(x_{\mathsf {d}}+y_{\mathsf {d}}).\,\!$

When multiplied out, this gives terms like y_ax_bx_cy_d, where we have a product of four items, one from each factor, each of which is either x or y. But, of course, we do not really have subscripts and we ignore ordering, so this is really just x²y², and we can also get it from, say, x_ay_bx_cy_d.

To see the equivalence, consider all possible factor orderings, a total of 4! for this example of degree 4. From the first two factors we choose x, and from the remaining two we choose y. This is identical to our previous concept, so we will get x²y² in 4?2 = 4! ⁄ (2!2!) = 6 ways. Done!

Now consider (x+y+z)⁷, and count the number of ways to get x²y²z³. Again start with all 7! permutations of the factors, and for each permutation choose x from the first two factors, y from the next two, and z from the remaining three. This is equivalent to our multinomial picture, so we will get x²y²z³ in 7?⟨2,2,3⟩ = 7! ⁄ (2!2!3!) = 210 ways. Thus if we have variables x₁ through x_M raised to powers k₁ through k_M and multiplied together, x₁^k₁x₂^k₂⋯x_M^k_M, then the coefficient will be ?⟨k₁,…,k_M⟩ = (∑_i=1…M k_i)! ⁄ (∏_i=1…M k_i!).

Many, many situations give rise to these same numbers. For example, suppose I want to go two blocks south and two blocks east (without going out of my way); how many different ways can I do it? Clearly I can go ESSE or SESE and so on. No matter how I choose, I must travel four blocks, heading south two times and east two times. Once again we have a binomial coefficient. --KSmrq^T 19:52, 7 September 2007 (UTC)