space of the Kingman $n$-coalescent is in bijection with the set of timed and *labeled* binary trees with $n$ leaves, the state space of the Tajima $n$-coalescent is in bijection with the set of timed and *unlabeled* binary trees with $n$ leaves. The cardinality of the space of the timed and unlabeled binary tree topologies with $n$ leaves is given by the $(n-1)$-th Euler zigzag number [@di13], which behaves like $2 (2/\pi)^{n} \, (n-1)!$ when $n$ increases. While the cardinality of the space of Tajima trees still grows superexponentially in $n$, its rate of growth is drastically smaller than that of the space of Kingman trees. [@pal19] show that when all sequences are sampled at the same time, employing the Tajima coalescent allows fast inference of $(N_e(t))_{t\geq 0}$. The main focus of this work is to develop a scalable model for sequences observed at different time points like those at the tips of the genealogy in Figure \[fig:coalescent\]. The need to model heterochronous data is motivated by both applications and statistical reasons. In applications, viral samples (HIV, influenza) are routinely collected serially. Ancient DNA studies are another very active area of research in which the sampling design is intrinsically sequential. 