Chaitanya's Random Pages

August 31, 2013

UNESCO World Heritage sites with both natural and cultural significance

Filed under: geography — ckrao @ 11:29 am

As of now there are 981 places on the UNESCO World Heritage list, of which 759 have cultural value, 193 are significant natural landmarks and 29 are both. Here are the 29 with mixed properties listed with a brief description, I feel I should have learned more about them long ago. Most of the information is from the UNESCO site (maps found there too) and Wikipedia.

Country  Name Significance
 Algeria Tassili n’Ajjer  geological formations and more than 15,000 drawings dating back to 6000BC
 Australia Kakadu National Park  a third of Australia’s bird species and a quarter of its freshwater fish species here, rock paintings date back 20,000 years, evidence of settlement for 40,000
Willandra Lakes Region  oldest known human cremation site (26,000 years old), evidence of settlement 45-60,000 years ago, clay dune formations
Tasmanian Wilderness  one of world’s last expanses of temperate rainforest, 37 Aboriginal cave sites dating back up to 30,000 years
Uluru-Kata Tjuta National Park  sandstone monolith and conglomerate rock domes, symbolic of Aboriginal spiritual connection to the land
 China Mount Taishan  a traditional scenic place of worship with its geological birth over 3 billion years ago
Mount Huangshan  granite peaks often emerging from clouds, inspiring source of art and literature
Mount Emei Scenic Area, including Leshan Giant Buddha Scenic Area  largest Buddha statue in the world (71m high),3200 plant species including 100 endemic
Mount Wuyi  largest and most representative forest encompassing the diversity of the Chinese Subtropical Forest and the South Chinese Rainforest, cradle of Neo-Confucianism
 France/Spain Pyrénées – Mont Perdu  display of deep canyons and spectacular cirque walls, illustrates traditional mountain way of life now rare in Europe
 Gabon Ecosystem and Relict Cultural Landscape of Lopé-Okanda  last remnants of grass savannas created in central Africa created during last Ice Age, home to many endangered land mammals, migration route for very early human settlement
 Greece Meteora  six monasteries on sandstone rock pillars up to 400m above the valley below
Mount Athos  Orthodox spiritual centre with 20 monasteries and school of painting, well preserved Mediterranean forest
 Guatemala Tikal National Park  major centre of Mayan civilisation from 6th to 10th century, rainforest includes over 300 bird species
 Jordan Wadi Rum Protected Area  25,000 petroglyphs dating back 12,000 years, large diversity of desert landforms
 Lesotho/South Africa Maloti-Drakensberg Park  more than 250 endemic plant species, vast gallery of rock paintings by the San people over a period of 4000 years, a refuge for many threatened large mammals
 Mali Cliff of Bandiagara (Land of the Dogons)  150km long sandstone cliff up to 500m high, some of impressive architecture dates back to 14th century
 New Zealand Tongariro National Park  volcanic summits in central North Island sacred to Maoris
 Palau Rock Islands Southern Lagoon  mushroom-shaped limestone islands, highest concentration of marine lakes in the world, human remains date back over 3000 years
 Peru Historic Sanctuary of Machu Picchu  symbolic of Inca Empire at its height, mountainous scenery
Río Abiseo National Park  outstanding example of early human occupation at high altitudes in the Andean region with over 30 sites found, much undisturbed landscape
 Spain Ibiza, Biodiversity and Culture  well-preserved seagrass, evidence of Phoenician settlements
 Sweden Laponian Area  world’s largest unmodified nature area to be still cultured by natives (Sami people), variety of natural glacial phenomena, large population of brown bear and alpine flora
 Tanzania Ngorongoro Conservation Area  world’s largest inactive, intact, and unfilled volcanic caldera, evidence of hominid evolution dating back 4 million years, part of large mammal migration route, high density of lions
 the Former Yugoslav Republic of Macedonia Natural and Cultural Heritage of the Ohrid region  one of most ancient European settlements, early manuscripts of Slavonic literature, more than 200 endemic species in lake
 Turkey Göreme National Park and the Rock Sites of Cappadocia  mountain ridges, valleys and pinnacles known as “fairy chimneys”, large cave dwelling complexes, settled in Roman times
Hierapolis-Pamukkale  Greco-Roman ruins, visually appealing landforms and pools of mineralised water from hot springs
 United Kingdom St Kilda  Scottish archipelago with architectural features from historic and prehistoric times, breeding ground for many seabird species including gannets and puffins
 USA Papahānaumokuākea  spiritually significant to Hawaiians, supporting 7000 marine species, a quarter endemic
Advertisements

August 28, 2013

Permutations of 1,1,2,2,…,n,n with no two adjacent terms equal

Filed under: mathematics — ckrao @ 9:12 pm

A nice question from the Australian Mathematics Competition of 1983 asks how many ways 4 differently coloured pairs of socks can be lined up so that no socks of the same pair are adjacent. More generally, in how many ways can we permute the numbers 1,1,2,2,...,n,n, so that no two consecutive terms are equal? For example, 1,2,3,2,3,1 is permitted but 1,2,2,3,1,3 is not.

This can be solved by the principle of inclusion-exclusion as follows. For i=1,...,n Let P_i be the set of permutations of 1,1,2,2,...,n,n in which that the two copies of i are adjacent. We wish to find the number of permutations in \left( \cup_{i=1}^n P_i \right)^c, as we are interested in permutations not contained in any P_i. The total number of permutations (without restriction of order) is (2n)!/2^n. Using symmetry the cardinality a_n of this set can be enumerated as

\begin{aligned} a_n &= \left| \left( \cup_{i=1}^n P_i \right)^c \right| \\ &= \frac{(2n)!}{2^n} - \sum_{i=1}^n \left|P_i \right| + \sum_{i <j} \left| P_i \cap P_j \right| - \sum_{i < j < k} \left| P_i \cap P_j \cap P_k \right| - \ldots + (-1)^{n} \left| P_1 \cap P_2 \ldots \cap P_n \right|\\ &= \frac{(2n)!}{2^n} - n \left| P_1 \right| + \binom{n}{2} \left| P_1 \cap P_2 \right| - ... + (-1)^{n} \left| P_1 \cap P_2 \ldots \cap P_n \right|.\end{aligned}.

The general term \left| P_1 \cap P_2 \ldots \cap P_k \right| can be found by permuting the k + 2(n-k) objects 1-1, 2-2, …, k-k, k+1, k+1, k+2, k+2, …, n, n, where the adjacent terms 1-1 up to k-k are treated as one compound object. This can be done in (2n-k)!/2^{n-k} ways, where the division by 2^{n-k} is performed as the last n-k pairs are indistinguishable when permuted. We end up with

\displaystyle a_n = \sum_{k= 0}^n (-1)^{k} \binom{n}{k} \frac{(2n-k)!}{2^{n-k}}.

Evaluating this for n = 4 gives \displaystyle a_4 = 8!/2^4 - 4.7!/2^3 + 6.6!/2^2 - 4.5!/2 + 4! = 1080 - 240 + 24 = 864 (noting that the first two terms always cancel). The Venn diagram below shows the number of permutations of 1,1,2,2,3,3,4,4 that contain each consecutive pair of 11, 22, 33, 44. For example, there are 246 permutations containing the two 2s adjacent, but the two 1s, two 3s and two 4s are not adjacent. All the numbers shown are found again by inclusion-exclusion. For example,

\begin{aligned} \left|P_1^c \cap P_2 \cap P_3^c \cap P_4^c \right| &= \left|P_2 \right| - 3 \left|P_1 \cap P_2 \right| + 3 \left|P_1 \cap P_2 \cap P_3 \right| - \left| P_1 \cap P_2 \cap P_3 \cap P_4 \right| \\&= \frac{7!}{2^3} - 3 \frac{6!}{2^2} + 3\frac{5!}{2} - 4! \\ &= 630 - 540 + 180 - 24 \\ &= 246.\end{aligned}

4Venn

All of the numbers shown in the Venn diagram add to 864 + 4\times 246 + 6 \times 84 + 4 \times 36 + 24 = 2520 = 8!/2^4, the total number of permutations of 1,1,2,2,3,3,4,4.

Note that our answer of 864 to the original question is divisible by 4! – this makes sense since we can permute the numbers 1,2,3,4 in any of 24 ways to arrive at another way of arriving at a sequence with the same property that no adjacent terms are equal. With this in mind, let us turn our attention to the sequence b_n = a_n / n!. The first terms are 0,1,5,36,329 and we can think of b_n as counting the number of ways we can permute 1,1,2,2,...,n,n so that no two adjacent terms are equal and the first occurrence of i always precedes the first occurrence of i+1 (i = 1,2,..., n-1). Call such a sequence allowable. For example 1,2,3,2,3,1 is allowable but 2,3,1,3,1,2 is not. It turns out that the sequence b_n is linked to the Bessel polynomial y_n(x) evaluated at x=1 (hence it’s the sum of the coefficients of the polynomials – see OEIS A000806 for more information).

Interestingly the b_ns are linked by the recurrence relation

b_n = (2n-1) b_{n-1} + b_{n-2}, \quad b_0 = 1, b_1 = 0,

which we shall now derive.

To be more concrete we shall link b_4 = 864/4! = 36 to b_3 = 5 and b_2 = 1 (b_4 = 36 = (2(4)-1) \times 5 + 1). The general case follows similarly.

We can list the allowed permutations of 1,1,2,2 and 1,1,2,2,3,3 as

  • (1,2,1,2) for n=2 and
  • (1,2,1,3,2,3), (1,2,3,1,2,3), (1,2,3,2,1,3), (1,2,3,2,3,1), (1,2,3,1,3,2) for n = 3.

We now create an allowable permutation for n=4 in one of three ways:

  1. from each n=2 sequence, add 1 to each element, insert 1 at the start of the sequence and 4,1,4 at the end (e.g. (1,2,1,2) \leftrightarrow (1,2,3,2,3,4,1,4)).
  2. from each n=3 sequence, firstly move the final element next to its other occurrence in the sequence, then add 1 to each element, insert a 1 at the start of the sequence and finally insert a 1 between the two duplicated elements to prevent them from appearing twice in a row (e.g. (1,2,3,1,3,2) \leftrightarrow (1,2,2,3,1,3) \leftrightarrow (1,2,3,1,3,4,2,4)).
  3. from each n = 3 sequence, add 1 to each element, insert 1 at the start of the sequence and a second 1 in any of the remaining (2n-2) = 6 allowable positions – it cannot be placed next to the first 1 (e.g. (1,2,3,1,3,2) \leftrightarrow (1,2,3,1,4,2,4,3)).

Below we see how the n=2 and n=3 generate allowable n=4 sequences.

(1,2,1,2) \leftrightarrow (1,2,3,2,3,4,1,4)

(1,2,1,3,2,3) \leftrightarrow (1,2,3,2,4,1,4,3), (1,2,1,3,2,4,3,4), (1,2,3,1,2,4,3,4), (1,2,3,2,1,4,3,4), (1,2,3,2,4,1,3,4), (1,2,3,2,4,3,1,4), (1,2,3,2,4,3,4,1)
(1,2,3,1,2,3) \leftrightarrow (1,2,3,4,1,4,2,3), (1,2,1,3,4,2,3,4), (1,2,3,1,4,2,3,4), (1,2,3,4,1,2,3,4), (1,2,3,4,2,1,3,4), (1,2,3,4,2,3,1,4), (1,2,3,4,2,3,4,1)
(1,2,3,2,1,3) \leftrightarrow (1,2,3,4,1,4,3,2), (1,2,1,3,4,3,2,4), (1,2,3,1,4,3,2,4), (1,2,3,4,1,3,2,4), (1,2,3,4,3,1,2,4), (1,2,3,4,3,2,1,4), (1,2,3,4,3,2,4,1)
(1,2,3,2,3,1) \leftrightarrow (1,2,3,4,1,4,3,2), (1,2,1,3,4,3,4,2), (1,2,3,1,4,3,4,2), (1,2,3,4,1,3,4,2), (1,2,3,4,3,1,4,2), (1,2,3,4,3,4,1,2), (1,2,3,4,3,4,2,1)
(1,2,3,2,3,1) \leftrightarrow (1,2,1,2,3,4,3,4), (1,2,1,3,4,3,4,2), (1,2,3,1,4,3,4,2), (1,2,3,4,1,3,4,2), (1,2,3,4,3,1,4,2), (1,2,3,4,3,4,1,2), (1,2,3,4,3,4,2,1)
(1,2,3,1,3,2) \leftrightarrow (1,2,3,1,3,4,2,4), (1,2,1,3,4,2,4,3), (1,2,3,1,4,2,4,3), (1,2,3,4,1,2,4,3), (1,2,3,4,2,1,4,3), (1,2,3,4,2,4,1,3), (1,2,3,4,2,4,3,1)

Let us now see why all allowable n=4 sequences have indeed been generated and that no allowable sequence has been repeated (justifying the use of double arrows above).

If we take an allowable n=4 sequence, either it ends with 4,1,4 or it does not – if it does it begins to class 1 above. Deleting the 1 at the start and 4,1,4 at the end, then subtracting 1 from each element will map it to an allowable n=2 sequence.

e.g. (1,2,3,2,3,4,1,4) \rightarrow (2,3,2,3) \rightarrow (1,2,1,2)

If it does not end in 4,1,4, the second 1 either is between two repeated elements (class 2) or it is not (class 3).  The two repeated elements cannot appear at the end since such a sequence could only end with 4,1,4 and we are back to class 1. (If say a 3,1,3 were at the end, the first 4 could only appear after the first 3 and so has not occurred earlier in the sequence.) Deleting the two 1s, moving the second of the repeated elements to the end (we have just seen it is not already at the end so it will become separated from its partner) and then subtracting 1 from each element maps it to an allowable n =3 sequence. The first occurrence of i will still precede the first occurrence of i+1 in the n=3 sequence.

e.g. (1,2,3,4,1,4,3,2) \rightarrow (2,3,4,4,3,2) \rightarrow (2,3,4,3,2,4) \rightarrow (1,2,3,2,1,3)

In class 3, since the second 1 is not between two repeated elements, deleting it and the first 1, then subtracting 1 from each element would lead to an allowable n=3 sequence.

e.g. (1,2,1,3,4,3,4,2) \rightarrow (2,3,4,3,4,2) \rightarrow (1,2,3,2,3,1)

This shows that all allowable n = 4 sequences can be mapped uniquely into one of class 1, 2 or 3, so we have a desired generation of new n = 4 sequences from n=2 and n = 3 through steps 1-3 above. The above can be generalised by replacing 4 with n. Enumerating these now, we have b_{n-2} sequences from case 1, b_{n-1} sequences from case 2 and (2n-2)b_{n-1} sequences from case 3. In total,

\displaystyle b_n = b_{n-2} + b_{n-1} + (2n-2) b_{n-1} = (2n-1) b_{n-1} + b_{n-2},

as we wished to show. The b_0 = 1, b_1 = 0, b_2 = 1 instances are easy to verify and satisfy the above recurrence.

 

Create a free website or blog at WordPress.com.

%d bloggers like this: