The Lucas sequences is a sequence of polynomials in $s,t$ defined recursively by $\{0\} = 0, \{1\} = 1,$ and $\{n\} = s \{n-1\} + t \{n-2\}$ for $n \geq 2$. On specialization of $s$ and $t$ one can recover the Fibonacci numbers, the nonnegative integers, and the $q$-integers $[n]_q$. Given a quantity which is expressed in terms of products and quotients of positive integers, one obtains a Lucas analogue by replacing each factor of $n$ in the expression with $\{n\}$. It is then natural to ask if the resulting rational function is actually a polynomial in $s$ and $t$ and, if so, what it counts. Using lattice paths, we give a combinatorial model for the Lucas analogue of the binomial coefficients. This is joint work with Curtis Bennett, Juan Carrillo, and John Machacek. We then give an algebraic method for proving polynomiality using a connection with cyclotomic polynomials. This part of the talk is joint work with Jordan Tirrell and based on an idea of Richard Stanley. Finally, we also consider Catalan numbers and their relatives, such as those for finite Coxeter groups.