Present Remotely

Send the link below via email or IM

Present to your audience

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation
• A maximum of 30 users can follow your presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

Thesis

No description
by

Jessica Whalen

on 28 November 2012

Report abuse

Transcript of Thesis

The Mathematics behind lacings your shoes Definitions Mathematical Shoe: a pair of vertical lines in a plane that are one unit apart and n horizontal lines that intersect with the two vertical lines and are h units apart.

Eyelets: represented by the intersections of the vertical and horizontal lines in the mathematical shoe Lacing Rules Every eyelet must be visited once, and only once.

Every eyelet must contribute to pulling the two sides of the shoe together, which means at least one of the two segments of shoelace that end in each eyelet also ends in the other column so that there are no gaps. Types and Classes There are are four different types of lacings and six different family types. The classes are Dense, Straight, Superstraight, and Simple. One-Column Lacings One-Column n-lacings are closed paths within a plane containing a single column of n eyelets that are equally spaced apart and form a single vertical column.

They can be formed by creating permutations of the n eyelets or by a process called contraction. When creating the one-column n-lacing contraction of a two-column n-lacing, horizontal lacings are disregarded and diagonal lacings are considered the same as vertical lacings. One-Column Lacings (Cont.) One-column n-lacings are made by permutations of the eyelets. They always start in the first eyelet, but after that the order doesn't matter as long as each eyelet is visited exactly once and the lacings returns to the first eyelet. Thus, there are (n-1)! different permutations of the eyelets for all n≥2.

However, each permutation is exactly the same as the permutation in which the order that the eyelets are visited is reversed. One-column lacings will make certain calculations much simpler later on. Counting Laces - General Lacings Assume n is an odd number. There are 2k verticals, k in column A and k in column B where 0 ≤ k ≤ (n-1)/2. Let G(k, n) denote the number of oriented n-lacings with 2k verticals.

The number of oriented n-lacings is the sum of G(k,n) from k=0 to k=(n-1)/2. To calculate G(k, n) consider the permutation of an oriented n-lacing with 2k verticals. If the last element in the permutation is in column A, move it to the beginning of the permutation. The permutation should now alternate between groups of elements in column A and elements in column B, where each group is either a single or a double and the first group is an A group.

ABABAABBABBABAAB

There is a total of k double A’s, k double B’s, n-2k single A’s, and n-2k single B’s. Counting General Lacings Let GA(k, n) be the number of permutations starting with a single A group, and GAA(k, n) be the number of permutations starting with a double A group. Thus:

GA(k, n) = ((n-k-1)C(k))((n-k)C(k)) and
GAA(k, n) = ((n-k-1)C(k-1))((n-k)C(k))
where k = 0, 1, 2, …, (n-1)/2.

Given one of the sequences that start with a single A group, all of the oriented lacings that arise from it can be reconstructed by adding indices to the elements in the permutation. As long as the index of the first A is 1 and all of the indices are represented exactly once, this can be done arbitrarily. There are n!(n-1)! ways of doing this. (n-1)! ways of assigning indices to the A's and n! ways of assigning indices to the B's. Counting General Lacings The same thing can be done for permutations that start with a double A group with the additional requirement that the index of the second A is 2. There are 2n!(n-1)! ways of doing this. Combining all of this gives us:
n!(n-1)! ∑(from k=0 to k=(n-1)/2) GA(k,n)+GAA(k,n)
= n!(n-1)! ∑(from k=0 to k=(n-1)/2) ((n-k-1)C(k))((n-k)C(k))+2((n-
k-1) C(k-1))((n-k)C(k))
= n!(n-1)! ∑(from k=0 to k=(n-1)/2) ((n-k)C(k))[((n-k-1)C(k))+2((n-
k-1)C(k-1))]
= n!(n-1)! ∑(from k=0 to k=(n-1)/2) [(n-k)C(k)^2 (1+ k/(n-k))]
= (n!)^2 ∑(from k=0 to k=(n-1)/2) [1/(n-k)((n-k)C(k))^2 ] oriented
n-lacings.

Therefore, ((n!)^2)/2 ∑(from k=0 to k=(n-1)/2) [1/(n-k)((n-k)C(k))^2] is the total number of (unoriented) n-lacings when n is odd. When n is even it is dealt with in a similar manner and comes out to:
((n!)2 )/2∑(from k=0 to k=(n-1)/2) 1/(n-k)((n-k)C(k))^2 . Counting Dense Lacings Without including the indices of the elements, the permutation of an oriented dense n-lacing is always ABAB…AB. While the first A always has an index of 1, the remaining n-1 A’s and the n B’s can be in any order as long as they are all used exactly once. This means there are (n-1)! ways to arrange the remaining A’s and n! ways to arrange the B’s. Dividing by 2 to remove duplicates caused by the orientations gives us ½(n!)(n-1)! dense n-lacings. Counting Straight Lacings This is where our work with one-column n-lacings comes in useful. A straight n-lacing contains every possible horizontal segment, so when attempting to undo the contraction on a one-column n-lacing there is no question as to whether or not there is a horizontal segment at any given eyelet. If it is an n-lacing, then there are n-1 segments that must be either a vertical or a diagonal, meaning there are 2^(n-1) combinations of verticals and diagonals for each one-column n-lacing. As we previously found, there are ½(n-1)! different one-column n-lacings. Thus, taking into account the fact that each one-column n-lacing has two orientations, the total number of straight n-lacings is:
2*2^(n-1)*1/2(n-1)! = (n-1)!2^(n-1) Counting Simple Lacings Simple lacings always contain the top and bottom horizontal segments. There are six different simple configurations that use the top horizontal, and as such every simple lacing begins with one of these configurations. They are the Fishtail, Box, Zee, Mirror Zee, Cee, and Mirror Cee. Every simple lacing contains one of these configurations at the top of the lacing. Fishtale: deleting the configuration and connecting the two resulting “loose ends” with a horizontal segment creates a simple (n-1)-lacing. Alternately, deleting the top horizontal of any simple (n-1)-lacing and replacing it with a Fishtail will create a simple n-lacing. Counting Simple Lacings Zee/Mirror Zee: deleting this configuration n-lacing leaves one “loose end” in the top row where it used to connect to the top horizontal and one in the other column, one row down. Moving the top “end” down one row and connecting it to the other “end” with a horizontal segment forms an (n-1)-lacing. Inverting this process turns a simple (n-1)-lacing into a simple n-lacing.

Box: deleting this configuration does not just give a simple (n-1)-lacing, it gives a simple (n-1)-lacing where top segments are diagonals. If these segments were not both diagonals, then the n-lacing would have contained an invalid lacing. Any simple (n-1)-lacing that has only diagonals connecting to the top horizontal can easily be transformed into a simple n-lacing by deleting the top horizontal and replacing it with a Box. n-lacing: a closed path on a mathematical shoe representing the path of the shoelace Counting Simple Lacings n-diagonaldiagonals (d-d): simple n-lacings with diagonal segments ending in both of the top two eyelets; s_n^dd represent the number of such lacings.
n-verticalverticals (v-v): simple n-lacings with verticals ending in both of the top two eyelets; s_n^vv represent the number of such lacings.
n-diagonalverticals (d-v) and n-verticaldigonals (v-d): simple n-lacings with one vertical and one diagonal ending in the top two eyelets; s_n^dv and s_n^vd represent the number of such lacings respectively. It should be fairly obvious that s_n^dv = s_n^vd.
Ceediagonals (Cee-d) and Ceeverticals (Cee-v): simple n-lacings that contain a Cee configuration and a diagonal or vertical respectively that ends in the remaining top eyelet; the number of such lacings is represented by s_n^Ceed and s_n^Ceev.
Mirror Cee’s: s_n^Ceed = s_n^mCeed and s_n^Ceev = s_n^mCeev. Cee/Mirror Cee: If a simple n-lacing does contain a Cee, then the Cee is part of one of the six configurations seen below. Counting Simple Lacings Using these we can form an equation to find the total number of simple n-lacings. The equation is:
s_n = s_n^dd + s_n^vv + 2s_n^dv

Cee-ds are extended by Cee1s, Cee2s, Cee3s, and Cee4s. Cee-vs are extended by Cee1s, Cee4s, Cee5s, and Cee6s. D-ds are extended by Fishtails, Zees, and Mirror Zees. D-v's are extended by Zees, Cee-d's, and Mirror Cee-d's, and v-v's are extended by Boxes, Cee-v's, and Mirror Cee-v's. Counting Simple Lacings This gives the following system of recursive equations:

s_n^Ceed = s_(n-2)^dd+s_(n-2)^dv+s_(n-1)^Ceed+s_(n-1)^Ceev+ s_(n-1)^Ceed
+ s_(n-2)^dd + s_(n-2)^dv
s_n^Ceev = s_(n-2)^dd + s_(n-2)^dv + s_(n-1)^Ceev + s_(n-2)^dd + svvn-2 +
2s_(n-2)^dv + s_(n-2)^dv + s_(n-2)^vv
s_n^dd = s_(n-1)^dd + s_(n-1)^vv + 2s_(n-1)^dv + 2(s_(n-1)^dd + s_(n-1)^dv)
s_n^dv = s_(n-1)^dv + svvn-1 + s_n^Ceed
s_n^vv = s_(n-1)^dd + 2s_n^Ceev

Using s_d^dd=1, s_2^vv = 1, s_2^dv = 0, s_2^Ceed = 0, s_2^Ceev = 0, s_3^dd = 4, s_3^vv = 3, s_3^dv = 2, s_3^Ceed = 1, s_3^Ceev = 1, and standard generating function techniques we can come up with the final equation:
∑(i from 1 to 5) [(2-3r_(i )-5r_i^3+4r_i^4)/(r_i^(n-1) (7-20r_i+27r_i^2-84r_i^3 +60r_i^4))] where r_i, i = 1, 2, …, 5 roots of 12r^5-21r^4+9r^3-10r^2+7r-1. Counting Summary Shortest Lacings The shortest lacings is a simple lacing. Simple lacings go from top to bottom, and bottom to top exactly once. All non-simple lacings travel up and down more than once, adding length.

The shortest possible lacing is the Bowtie.

The Crisscross is the shortest dense lacings.

When n is even, then the Serpent lacing is the shortest straight lacing. When n is odd, the Zigsag is the shortest straight lacing. There are three types of lacings: horizontal, diagonal, and vertical. The family classes are Crisscross, Zigzag, Star, Bowtie, Serpent, and Zigsag. Because these two permutations form the same diagram, we do not differentiate between the two orientations. As such, the total number of one-column n-lacings is ½(n-1)!. Shortest General Explanation Horizontals add length without adding vertical distance, so the shortest n-lacing will not contain any horizontal except for the top and bottom horizontal.

The rest of the lacing will be a combination of vertical and diagonal segments. Because a vertical segment is shorter than diagonal segment, the lacing should contain as many vertical segments as possible.

There cannot be two vertical segments in a row and
still be a valid lacing, so the vertical and diagonal
segments will have to alternate.

This is the description of a Bowtie lacing. Shortest Dense Explanation This requires some shortening rules. In the image below it should be obvious that a straight line from A to C and from B to D would be shorter that the lines connecting A to D and B to C, and that replacing lacing segments like those on the left with segments like those on the right will result in a shorter overall lacing. All other shortening rules are variations of this one. A lacing is reduced when the shortening rules do not affect it and it cannot be shortened any further. If the shortening rules can still be applied, then the lacing is considered to be reducible.

The crisscross lacing is the only dense n-lacing that is reduced, which automatically makes it the shorted dense n-lacing. Shortest Straight Explanation Unlike the shortest general lacing, the shortest straight lacing will contain every horizontal segment. Like the shortest general lacing, vertical segments are still shorter than diagonal segments and should be included as often as possible. Relearning Your Lacings Strongest Lacings The purpose of a shoelace is to pull the two sides of a shoe together, and different types of lacings do this with carrying levels of success. When laced and tied properly, the tension on the shoelace should be constant over the entire shoelace. The ability of a shoelace to pull the sides of a shoe together is measured by the horizontal component of the tension on the shoelace.

Horizontal segments have the most horizontal tension (obviously).

Vertical segments have no horizontal tension.

The amount of horizontal tension in diagonal segments is inversely proportional to their length. The shorter it is, the more horizontal tension it has. Strongest Lacings (Cont.) With this in mind, it is easy to see which lacing classes have a high level of horizontal tension, and which do not. Bowtie, Serpent, and Zigsag lacings obviously have very little horizontal tension, making them weak.

Crisscross, Zigzag, and Star lacings are the strongest classes of lacings. Tieing The Ends There are enough ways to lace a shoe, there's no reason your shoes can't be unique.

A Bowtie lacing will save you from a broken shoelace.

The more back and forth, the stronger the lacing. When n is even it is possible to create a superstraight (Serpent) lacing and avoid using diagonal segments entirely.

When n is odd, it is impossible to create a lacing without using a diagonal. A Zigsag lacing is a straight lacing with exactly one diagonal segment.
Full transcript