# 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

## 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 .

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}

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_n$s 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.

Blog at WordPress.com.