# Chaitanya's Random Pages

## July 30, 2015

### Nineteenth century non-avian dinosaur discoveries

Filed under: nature,science — ckrao @ 11:05 am

Below is an attempted chronological list of non-avian dinosaur discoveries of the 19th century that today are considered valid genera. There may still be some where there are only scant remains of the fossil (e.g. a tooth or single bone remain). The list came from [1] with some help from [2] and Wikipedia to filter out doubtful names. Many of the best known dinosaurs are listed here and it looks like most of the major groups are covered. Good histories of dinosaur paleontology are in [3] and [4].

 Genus Discoverer Year Dinosaur type Megalosaurus Buckland 1824 tetanuran (stiff-tailed) theropod Iguanodon Mantell 1825 beaked ornithopod Streptospondylus von Meyer 1830 megalosaurid Hylaeosaurus Mantell 1833 armoured Thecodontosaurus Riley & Stutchbury 1836 prosauropod Plateosaurus von Meyer 1837 prosauropod Poekilopleuron Eudes-Deslongchamps 1838 megalosaurid Cardiodon Owen 1841 sauropod Cetiosaurus Owen 1841 sauropod Pelorosaurus Mantell 1850 brachiosaur Aepisaurus Gervais 1852 sauropod Oplosaurus Gervais 1852 sauropod Massospondylus Owen 1854 prosauropod Nuthetes Owen 1854 maniraptoran Troodon Leidy 1856 raptor Stenopelix von Meyer 1857 pachycephalosaur Astrodon Johnston 1858 sauropod Hadrosaurus Leidy 1858 duckbilled ornithopod Compsognathus J. A. Wagner 1859 coelurosaur (fuzzy theropod) Scelidosaurus Owen 1859 armoured Echinodon Owen 1861 heterodontosaurid (early bird-hipped dinosaur) Polacanthus Owen vide [Anonymous] 1865 armoured Calamospondylus Fox 1866 oviraptorosaur Euskelosaurus Huxley 1866 prosauropod Acanthopholis Huxley 1867 armoured Hypselosaurus Matheron 1869 sauropod Hypsilophodon Huxley 1869 beaked ornithopod Rhabdodon Matheron 1869 beaked ornithopod Ornithopsis Seeley 1870 sauropod Struthiosaurus Bunzel 1870 armoured Craterosaurus Seeley 1874 stegosaurian Chondrosteosaurus Owen 1876 sauropod Macrurosaurus Seeley 1876 sauropod Allosaurus Marsh 1877 carnosaur Apatosaurus Marsh 1877 sauropod Camarasaurus Cope 1877 sauropod Dryptosaurus Marsh 1877 tyrannosaur Dystrophaeus Cope 1877 sauropod Nanosaurus Marsh 1877 early bird-hipped dinosaur Stegosaurus Marsh 1877 plated dinosaur Diplodocus Marsh 1878 sauropod Brontosaurus Marsh 1879 sauropod Anoplosaurus Seeley 1879 armoured Coelurus Marsh 1879 coelurosaur (fuzzy theropod) Mochlodon Seeley 1881 beaked ornithopod Craspedodon Dollo 1883 horned dinosaur Ceratosaurus Marsh 1884 theropod Anchisaurus Marsh 1885 prosauropod Camptosaurus Marsh 1885 beaked ornithopod Aristosuchus Seeley 1887 coelurosaur (fuzzy theropod) Ornithodesmus Seeley 1887 raptor Cumnoria Seeley 1888 beaked ornithopod Priconodon Marsh 1888 armoured Coelophysis Cope 1889 early theropod Nodosaurus Marsh 1889 armoured Triceratops Marsh 1889 horned dinosaur Barosaurus Marsh 1890 sauropod Claosaurus Marsh 1890 duckbilled ornithopod Ornithomimus Marsh 1890 ostrich dinosaur Ammosaurus Marsh 1891 prosauropod Torosaurus Marsh 1891 horned dinosaur Argyrosaurus Lydekker 1893 sauropod Sarcolestes Lydekker 1893 armoured Dryosaurus Marsh 1894 beaked ornithopod

#### References

[1] Dinosaur Genera List – http://www.polychora.com/dinolist.html

[2] Genus List for Holtz (2007) Dinosaurshttp://www.geol.umd.edu/~tholtz/dinoappendix/HoltzappendixWinter2011.pdf

[3] Benton, M. J. 2000. A brief history of dinosaur paleontology. Pp. 10-44, in Paul, G. S. (ed.), The Scientific American book of dinosaurs. St Martin’s Press, New York. – http://palaeo.gly.bris.ac.uk/Essays/dinohist.html

[4] Equatorial Minnesota The generic history of dinosaur paleontology 1699 to 1869 – http://equatorialminnesota.blogspot.com.au/2014/06/the-generic-history-of-dinosaur.html

## July 25, 2015

### Compositions of positive integers where adjacent parts have different parity

Filed under: mathematics — ckrao @ 5:39 am

Here is an interesting problem based on one I found in the 2008 AIME (Q11).

How many compositions of the positive integer n have adjacent parts with different parity?

For example, a valid composition of n=14 is

14 = 1 + 2 + 5 + 2 + 1 + 2 + 1,

since the 1,2,5,2,1,2,1 alternate between being odd and even.

The first terms of the sequence are (OEIS A062200)

1, 1, 3, 2, 6, 6, 11, 16, 22, 37, 49, 80, …

Interestingly the sequence decreases between n=3 and 4 since the only valid compositions of 4 are 4 = 1 + 2 + 1 and 4, while 3 = 1 + 1 + 1 = 2 + 1 = 1 + 2.

Here is the first approach I came up with to solve the problem. Let $a_n$ be the number of such compositions starting with an even number and let $b_n$ be the number of compositions starting with an odd number. We wish to find $t_n := a_n + b_n$. We identify four cases:

• If $n$ is odd and the composition starts with an even number $2c$, we remove that even number and have a composition of $n-2c$ starting with an odd number. Summing over choices of $c$,
$a_{2k+1} = b_{2k-1} + b_{2k-3} + \ldots + b_1. \quad (1)$
• If $n$ is odd and the composition starts with an odd number $2c+1$, we either have the single term composition $n$, or we remove that odd number and have a composition of $n-(2c+1)$ starting with an even number. Summing over choices of $c$,
$b_{2k+1} = 1 + a_{2k} + a_{2k-2} + \ldots + a_2. \quad (2)$
• If $n$ is even  and the composition starts with an even number $2c$, we either have the single term composition $n$, or we remove that even number and have a composition of $n-2c$ starting with an odd number. Summing over choices of $c$,
$a_{2k} = 1 + b_{2k-2} + b_{2k-4} + \ldots + b_2. \quad (3)$
• If $n$ is even and the composition starts with an odd number $2c+1$, we remove that odd number and have a composition of $n-(2c+1)$ starting with an even number. Summing over choices of $c$,
$b_{2k} = a_{2k-1} + a_{2k-3} + \ldots + a_1.\quad (4)$

Recursions (1)-(4) with the initial conditions $a_1 = 0, b_1 = 1, a_2 = 1, b_2 = 0$ allows us to generate the following table.

 $n$ 1 2 3 4 5 6 7 8 9 10 11 12 $a_n$ 0 1 1 1 3 2 6 6 11 16 22 37 $b_n$ 1 0 2 1 3 4 5 10 11 21 27 43 $t_n$ 1 1 3 2 6 6 11 16 22 37 49 80

After writing out some terms I noticed the pattern

$\displaystyle a_n = a_{n-2} + b_{n-2} \text{ and } b_n = a_{n-1} + b_{n-2}.\quad \quad (5)$

I later saw why this is so. Firstly, a composition of $n$ that starts with an even number can be obtained from any composition of $n-2$ by adding 2 to the first term if even or inserting 2 at the start if odd. Hence $a_n = t_{n-2} = a_{n-2} + b_{n-2}$. For the second relation, if the composition of $n$ starts with an odd number, it either is 1 plus an even-starting composition of $n-1$ or it can be obtained from an odd-starting composition of $n-2$ by adding 2 to the first term. Hence $b_n = a_{n-1} + b_{n-2}$.

From (5) and using $t_n = a_n + b_n$ we find that

\begin{aligned} t_n &= a_n + b_n\\ &= t_{n-2} + (a_{n-1} + b_{n-2})\\ &= t_{n-2} + t_{n-3} + t_{n-2} - a{n-2}\\ &= 2t_{n-2} + t_{n-3} - t_{n-4}.\quad \quad (6) \end{aligned}

Together with the initial terms $t_1 = 1, t_2 = 1, t_3 = 3, t_4 = 2$, (6) enables us to generate our desired terms without requiring $a_n$ or $b_n$.

The OEIS page also gives the following expression for $t_n$:

$\displaystyle t_n = \sum_{k=0}^{n+1} \binom{n-k+1}{3k-n+1}.\quad \quad (7)$

Here is how to show this result, with help from the solution at AoPS here. For ease of exposition convert the problem to one of binary strings: we require the number of length-n 0-1 strings so that maximal continguous blocks of 1s have even length and maximal contiguous blocks of 0s have odd length.

Suppose there are $b$ maximal blocks of 0s. All but the last such block must necessarily be followed by a pair of 1s. That is, the string has the form

$\displaystyle [....][....0][11....][....0][11....] \ldots [....0][....],$

where blocks enclosed by [] contain the same digit (0 or 1) and 0 or more pairs of digits are in place of the sets of four dots. We have shown $2b+1$ blocks above but the first and last may be empty.

Let $k = (n-b)/2$, which is the number of pairs of digits to use after $b$ 0s are used (noting that $n-b$ must be even). We have $b$ 0s used above along with $b-1$ pairs of 1s. Therefore $(n-(b + 2(b-1)))/2$ pairs of 0s or 1s need to inserted into the $2b+1$ blocks above. The blocks that they end up determine whether they are 0 or 1.

Now $x$ pairs can be inserted into $y$ blocks in $\binom{x+y-1}{x}$ ways, since we write out $x+y-1$ symbols in a row and choose $x$ of them to be pairs, with the remaining symbols representing separators between blocks. In our case,

$x = \frac{n-(b + 2(b-1))}{2}$, $y = 2b+1$ and $b = n-2k$, so

\begin{aligned} x &= \frac{n-3b+2}{2}\\ &= \frac{n-3n+6k+2}{2}\\ &= 3k-n+1,\end{aligned}

and $x+y-1 = 3k-n+1 + 2(n-2k) + 1 = n-k+1$.

Summing over choices of $k$ gives (7) as desired. Note that some of the terms will be 0 as $k$ ranges from 0 to n+1.

For example, when n=11 and 12, we have

$\displaystyle t_{11} = \binom{8}{2} + \binom{7}{5} = 28 + 21 = 49,$

$\displaystyle t_{12} = \binom{9}{1} + \binom{8}{4} + \binom{7}{7} = 9 + 70 + 1= 80,$

matching the values given in the table above.

Create a free website or blog at WordPress.com.