\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{cor}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{prop}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{problem}[theorem]{Problem} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Lucasnomial Fuss-Catalan Numbers and \\ \vskip .1in Related Divisibility Questions } \vskip 1cm \large Christian Ballot\\ D\'epartement de Math\'ematiques et Informatique\\ Universit\'e de Caen-Normandie \\ France \\ \href{mailto:christian.ballot@unicaen.fr}{\tt christian.ballot@unicaen.fr} \\ \end{center} \def\D{{\Delta}} \def\d{{\delta}} \def\a{{\alpha}} \def\l{{\lambda}} \def\lf{\lfloor} \def\rf{\rfloor} \def\lc{\lceil} \def\rc{\rceil} \def\k{{\kappa}} \def\th{{\theta}} \def\e{{\epsilon}} \vskip .2 in \begin{abstract} For all integers $n\ge1$ we define the generalized Lucasnomial Fuss-Catalan numbers $$C_{U,a,r}(n):=\frac{U_r}{U_{(a-1)n+r}}\binom{an+r-1}{n}_U,$$ and prove their integrality. Here $U$ is a fundamental Lucas sequence, $a\ge2$ and $r\ge1$ are integers, and $\binom{*}{*}_U$ denotes a Lucasnomial coefficient. If $U=I$, where $I_n=n$, then the $C_{I,a,r}(n)$ are the usual generalized Fuss-Catalan numbers. With the assumption that $U$ is regular, we show that $U_{(a-1)n+k}$ divides $\binom{an}{n}_U$ for all $n\ge1$ but a set of asymptotic density $0$ if $k\ge1$, but only for a small set if $k\le0$. This small set is finite when $U\not=I$ and at most of upper asymptotic density $1-\log 2$ when $U=I$. We also determine all triples $(U,a,k)$, where $k\ge2$, for which the exceptional set of density $0$ is actually finite, and in fact empty. \end{abstract} \section{Introduction} The Catalan numbers $C_n$, which may be defined algebraically by the formula $\frac1{n+1}\binom{2n}{n}$, appear in all kinds of mathematical contexts and have numerous combinatorial interpretations. One may get seriously acquainted with them by consulting the recent book of Stanley \cite{St}. They admit several generalizations. Two of them are relevant to this paper. First, the generalized Fuss-Catalan numbers, defined for all integers $n\ge1$ as \begin{equation}\label{eq:FC} \frac{r}{(a-1)n+r}\binom{an+r-1}{n}, \end{equation} where $a\ge2$ and $r\ge1$ are fixed integers. Fuss-Catalan numbers, which correspond to $r=1$, are shown \cite[Exercise A14, pp.\ 108]{St} to have combinatorial interpretations that extend some of the interpretations for ordinary Catalan numbers. We note that Fuss-Catalan numbers are sometimes plainly called generalized Catalan numbers (e.g., \cite{Su}). The second generalization of interest to this paper are the Lucasnomial Catalan numbers \begin{equation}\label{eq:LC} \frac{1}{U_{n+1}}\binom{2n}{n}_U, \end{equation} where $U=(U_n)$ is a fundamental Lucas sequence and $\binom{2n}{n}_U$ is the generalized central binomial coefficient with respect to $U$. Both generalizations are known to yield integers only; see, e.g., \cite{Ba4, Ed}. In Section 2, the integrality of more general numbers is proved, namely the {\it generalized Lucasnomial Fuss-Catalan} numbers \begin{equation}\label{eq:3} C_{U,a,r}(n):=\frac{U_r}{U_{(a-1)n+r}}\binom{an+r-1}{n}_U, \end{equation} where $U$ is a regular fundamental Lucas sequence, and $a\ge2$ and $r\ge1$ are given integers. The numbers \begin{equation}\label{eq:sfc} C_{U,a,1}(n)=\frac{1}{U_{(a-1)n+1}}\binom{an}{n}_U, \end{equation} where $r=1$ are simply referred to as {\it Lucasnomial Fuss-Catalan} numbers. Thus, ordinary Catalan and Fibonomial Catalan numbers which correspond, respectively, to $(U,a,r)=(I,2,1)$ and $(U,a,r)=(F,2,1)$ are particular instances of Lucasnomial Fuss-Catalan numbers. Throughout the paper, the letter $I$ denotes the identity sequence, i.e., $I_n=n$ for all $n\ge0$, while $F$ denotes the Fibonacci sequence defined by $F_{n+2}=F_{n+1}+F_n$, for all $n\ge0$, $F_0=0$ and $F_1=1$. In Section 2, the integrality of various Lucasnomial generalizations of classical numbers is established. Indeed, Theorem \ref{thm:1} unconditionally establishes the integrality of all Lucasnomial Fuss-Catalan numbers, Theorem \ref{thm:2} proves the integrality of all generalized Lucasnomial Fuss-Catalan numbers with the restriction that $U$ be regular, Theorem \ref{thm:Lobb} deduces from Theorem \ref{thm:2} the integrality of the {\it generalized Lucasnomial Lobb} numbers $L_{m,s}^{U,a}$, defined by \begin{equation}\label{eq:Lobb} L_{m,s}^{U,a}:=\frac{U_{as+1}}{U_{(a-1)m+s+1}}\binom{am}{(a-1)m+s}_U, \end{equation} for $a\ge1$, $m>s\ge0$, and, given the author's patronym we could hardly fail to show Theorem \ref{thm:ballot}, which establishes the integrality of all {\it Lucasnomial ballot} numbers $B_U(a,b)$, defined by \begin{equation}\label{eq:ballot} B_U(a,b):=\frac{U_{a-b}}{U_{a+b}}\binom{a+b}{a}_U, \end{equation} for all $a>b\ge0$ integers. However, Section 2 apart, the rest of the paper is devoted to a variant of Lucasnomial Fuss-Catalan numbers, namely the numbers \begin{equation}\label{eq:k} \frac1{U_{(a-1)n+k}}\binom{an}{n}_U, \end{equation} where $k$ is a fixed integer. The investigation we launched into persues the research work conducted in two recent papers, one of Pomerance \cite{Po} and then one of the author \cite{Ba4}. Given a triple $(U,a,k)$, we consider the set $D_{U,a,k}$ of all positive integers $n$ for which $U_{(a-1)n+k}$ divides the Lucasnomial $\binom{an}{n}_U$. When $n$ is in $D_{U,a,k}$, then the numbers in (\ref{eq:k}) are integers. When $k=1$, they are Lucasnomial Fuss-Catalan numbers and are integers for all $n\ge1$. Thus, $D_{U,a,1}=\mathbb N$. The main question the paper addresses is how does replacing $1$ by $k$ affects the sets $D_{U,a,k}$? How far astray do we get from the Catalan phenomenon? In his clear and attractive paper \cite{Po}, Pomerance studied how often the middle binomial coefficients $\binom{2n}{n}$ are divisible by $n+k$, when $k$ is a fixed arbitrary integer. The enquiry brought out two chief phenomena: the singularity of the Catalan numbers and a drastic difference in behavior between the case $k\ge1$ and the case $k\le0$. Indeed, if $k\not=1$, then $\overline D_{I,2,k}$, the complementary set of $D_{I,2,k}$ in the positive integers, is infinite. That is, there are infinitely many $n$ for which $n+k$ does not divide $\binom{2n}{n}$. Secondly, if $k\ge1$, then $D_{I,2,k}$ has asymptotic density one, whereas if $k\le0$, although $D_{I,2,k}$ is infinite, its upper asymptotic density, whose value is still unknown --- see Section 3 --- is small and definitely less than $1/3$. Before describing the content of the second paper \cite{Ba4}, we recall some notions. A fundamental Lucas sequence $U=U(P,Q)$ is a binary linear recurrent sequence defined by the initial values $U_0=0$, $U_1=1$ and the recurrence \begin{equation}\label{eq:rec} U_{n+2}=PU_{n+1}-QU_n, \end{equation} for all integers $n\ge0$, where $P$ and $Q$ are nonzero integers. The discriminant $\Delta$ of $U(P,Q)$ is $P^2-4Q$, i.e., it is the discriminant of the characteristic polynomial associated with the recursion. In stating our results we often use the notation $U(P,Q)$, with parameters $P$ and $Q$, to designate a Lucas sequence later simply referred to as $U$ and with terms $U_n$. Note that all terms of a sequence $U$ are integers. With its initial conditions $U$ turns out to be a {\it divisibility}, or a {\it divisible} sequence, i.e., one that satisfies, for all positive integers $m$ and $n$, the property \begin{equation}\label{eq:div} m\mid n\implies U_m\mid U_n. \end{equation} A fundamental Lucas sequence is {\it nondegenerate} if $U_n\not=0$ for all $n\ge1$. Nondegeneracy occurs whenever the ratio of the zeros of $x^2-Px+Q$ is not a root of unity of order $\ge2$. Alternatively, the condition $U_{12}\not=0$ is necessary and sufficient to ensure the nondegeneracy of $U$ --- see, e.g., \cite[Section 2]{Ba1}. We sometimes use the abbreviation `NFLS', or `NFL-sequence', for a nondegenerate fundamental Lucas sequence. A {\it regular} Lucas sequence $U(P,Q)$ is a NFLS such that $\gcd(P,Q)=1$.\footnote{The nondegeneracy condition simplifies to $U_3\not=0$, i.e., to not having $P^2=Q=1$ when $\gcd(P,Q)=1$.} This property is well-known to confer a stronger form of divisibility to the sequence $U$, i.e., for all nonnegative integers $m$ and $n$ \begin{equation}\label{eq:reg} \gcd(U_m,U_n)=|U_{\gcd(m,n)}|. \end{equation} Conversely, property (\ref{eq:reg}) is easily seen to imply $\gcd(P,Q)=1$. A {\it Lucasnomial}, or a Lucasnomial coefficient, is a generalized binomial coefficient with respect to a nondegenerate fundamental Lucas sequence $U$. That is, for $m\ge n\ge1$, the Lucasnomial $\binom{m}{n}_U$ is defined as $$ \binom{m}{n}_U:=\frac{U_mU_{m-1}\cdots U_{m-n+1}}{U_nU_{n-1}\cdots U_1}, $$ and as $1$, if $m\ge0$ and $n=0$, and as $0$ otherwise. Thus, for instance, $$ \binom{6}{3}_F=\frac{F_6\cdot F_5\cdot F_4}{F_3\cdot F_2\cdot F_1}=\frac{8\cdot5\cdot3}{2\cdot1\cdot1}=60. $$ The important Lucasnomial identity \begin{equation}\label{eq:2} \binom{m}{n}_U=U_{n+1}\binom{m-1}{n}_U-QU_{m-n-1}\binom{m-1}{n-1}_U,\text{ for }m\ge n\ge1, \end{equation} easily follows from the Lucas identity \cite[Section 5]{Ba1} $$ U_m=U_{n+1}U_{m-n}-QU_nU_{m-n-1}. $$ The integrality of all Lucasnomials may be seen inductively from (\ref{eq:2}). There are two particular Lucas sequences $U(P,Q)$ for which the corresponding Lucasnomials have their own name. On the one hand, of course, the ordinary binomial coefficients $\binom{m}{n}=\binom{m}{n}_I$, for which $I=U(2,1)$ and $I_n=n$ for all $n\ge0$. On the other hand, we have the Fibonomials, $\binom{m}{n}_F$, derived from the much-studied Fibonacci sequence $F$ which is equal to $U(1,-1)$. Indeed, Fibonomials appeared earlier than general Lucasnomials in the mathematical literature. In the sequel, we usually assume $P>0$. Indeed, given $P$ and $Q$, $$ U(-P,Q)(n)=(-1)^{n-1}U(P,Q)(n), \text{ for all }n\ge0, $$ so that Lucasnomials with respect to $U(-P,Q)$ are, up to sign, identical to corresponding Lucasnomials with respect to $U(P,Q)$. Therefore, the two sets $D_{U(\pm P,Q),a,k}$ are identical. Lucasnomial Catalan numbers with respect to a NFLS $U$, defined in (\ref{eq:LC}), deserve their appellation as they are integral for all $n\ge 0$ \cite{Ba4, Ek, Go2, Sa2}. Gould \cite{Go1, Go2} might have been the first person to coin the term `Fibonomial Catalan number' for $U=F$ and to prove their integrality. To date and to our knowledge there is no combinatorial interpretation of Lucasnomial Catalan numbers for $U\not=I$, even though combinatorial interpretations of Lucasnomials themselves exist and have received attention \cite{Be1, Be2, Sa1, Sa2}. Because $I$ is a particular NFLS and because the Catalan phenomenon persists when we consider Lucasnomial Catalan numbers, it was natural to find out whether \begin{enumerate} \item The sets $D_{U,2,k}$ all missed infinitely many integers as soon as $k\not=1$, \item The cleavage observed between the cases $k\ge1$ and $k\le0$ for $U=I$ remained true generally. \end{enumerate} The answers \cite{Ba4} were essentially affirmative at least for all regular Lucas sequences if not for one exception with respect to question 1, namely the sequence $U(1,2)$. For this sequence, $D_{U,2,2}$ turns out to be the whole set of natural numbers. The behavioral dichotomy between $k\ge1$ and $k\le0$ is even sharper than for $U=I$. That is, if $\D\not=0$, then the sets $D_{U,2,k}$ are finite when $k\le0$, but still have asymptotic density $1$ when $k\ge1$. (The only two zero-discriminant regular Lucas sequences are $U(\pm2,1)$ and the only one with $P>0$ is $U=I=U(2,1)$.) This paper sets about discovering whether, for all regular Lucas sequences $U$ and all integers $k$, the divisor sets $D_{U,a,k}$ display the same features for $a>2$ as for $a=2$. Section 3 is a study of the case $k\le0$: Theorem \ref{thm:3} shows the finiteness of all $D_{U,a,k}$ when $U$ is not $I$, while, in Theorem \ref{thm:I}, the sets $D_{I,a,k}$ are once more proven to be of asymptotic density less than $1/3$. That all sets $D_{I,a,k}$, $k\le0$, are infinite, is conjectured, but only proven, given an $a\ge3$, for infinitely many values of $k$ in Theorem \ref{thm:I2}. The section ends by discussing the current knowledge about the size of $D_{I,2,0}$, the set of integers $n\ge1$ that divide the middle binomial coefficient $\binom{2n}{n}$. It may seem like a simple case, yet with much food for thought leftover. Section 4 establishes a number of lemmas and examines some examples that help to understand the direction we took and the methods we used, while speeding up the search carried out in Section 5. Indeed, Section 5 is devoted to the search for triples $(U,a,k)$, $k\ge2$, called {\it Catalan-like} triples, for which $D_{U,a,k}$ is the entire set of all natural numbers. We found exactly four new Catalan-like triples. Except for those five Catalan-like triples --- i.e., including the triple $\big(U(1,2),2,2\big)$ found in \cite{Ba4} --- the sets $D_{U,a,k}$, $k\ge2$, all miss infinitely many positive integers. Theorem \ref{thm:G} summarizes the various partial results of Section 5. The proof that all $D_{U,a,k}$ are of asymptotic density $1$ when $k\ge1$ is established in Section 6 and finalized in Theorem \ref{thm:4}. One of the findings that comes out of the proof of Theorem \ref{thm:4} is that for each triple $(U,a,k)$, $U$ regular, $a\ge2$ and $k\ge1$, there is a minimal integer $m\ge1$ such that \begin{equation}\label{eq:min} \frac{m}{U_{(a-1)n+k}}\binom{an}{n}_U\quad\text{ is integral for all }n\ge1. \end{equation} We may say that the triple $(U,a,k)$ {\it belongs} to the integer $m$. Thus, amongst all regular $U$, the triples $(U,a,1)$, $a\ge2$, and the five Catalan-like triples are {\it all} the triples that belong to $1$. The triple $(F,3,2)$ is seen to belong to $3$ as an outcome of the proof of Corollary \ref{cor:1} of Section 4. This observation raises numerous questions such as \medskip \noindent Question 1. What are all triples $(U,a,k)$, $U$ regular, that belong to $3$? \medskip \noindent Question 2. Are there triples that belong to $m$ for all $m\ge1$? If not, what is the set of $m$ not represented by any triple? \medskip \noindent Question 3. Can one find general criteria that describe the triples that belong to a given $m$? \medskip One might consider a further more general research problem which we tentatively state below. \begin{problem}\label{prob:1} Can one obtain even broader theorems using the {\it generalized} Lucasnomial Fuss-Catalan numbers defined in (\ref{eq:3})? Perhaps, the following problem, or a variant of it, would just do: Given a quadruple $(U,a,r,k)$, $a\ge2$, $r\ge1$, $k$ an integer, one could study the sets $D_{U,a,r,k}$ of integers $n\ge1$ such that \begin{equation}\label{eq:ext} \frac{U_r}{U_{(a-1)n+k}}\binom{an+r-1}{n}_U, \end{equation} is an integer. What density would these sets obey? Would one find a corresponding cleavage between the cases $k30$. So there are no $k$-defective regular Lucas sequences $U$, $U\not=I$, for $k>30$. Moreover, tables of all $k$-defective regular $U$ were made \cite{Bi} for all values of $k$, $10]$. \end{prop} The notation $x$, $\nu$, $\delta$ and $\delta_x$ is used consistently with the utilization of Proposition \ref{prop:AR} throughout the paper. In Proposition \ref{prop:AR}, we used the Iverson symbol $[-]$, defined by: $$ [\cal P]=\begin{cases}1,& \text{ if } \cal P \text{ is a true statement;}\\ 0,& \text{ if not.} \end{cases} $$ Here is the explicit Kummer rule obtained in \cite[Section 4]{Ba1}. \begin{prop}\label{prop:K} {\rm (Kummer's rule for Lucasnomials)} Let $U(P,Q)$ be a nondegenerate Lucas sequence and $p\nmid Q$ be a prime of rank $\rho$ in $U$. Let $m$ and $n$ be two positive integers. Then the $p$-adic valuation of the Lucasnomial $\binom{m+n}{n}_U$ is equal to the number of carries that occur to the left of the radix point when $m/\rho$ and $n/\rho$ are added in base-$p$ notation, plus $\nu_p(U_\rho)$ if a carry occurs across the radix point, plus $\delta$ if a carry occurs from the first to the second digit to the left of the radix point, where $\d$ was defined in Proposition \ref{prop:AR}. \end{prop} This proposition suggests we distinguish carries across or to the left of the radix point from the other carries. Thus, as in \cite{Ba2, Ba4}, when adding $m/\rho+n/\rho$ in base $p$, we call a carry {\it relevant} when it occurs across or to the left of the radix point. Here is an illustrative example of the use of Proposition \ref{prop:K} with $U(1,-5)$ in order to determine the $2$-adic valuation of $\binom{20}{5}_U$. We see that $U_3=6$ so that $\rho(2)=3$ and $\nu=1$. Also, $P^2-3Q=16$ so that $\d=3$. Now, using some self-evident base-$2$ writing, we find that \begin{eqnarray*} \frac{15}{\rho}&=&5\;=\;(101)_2,\\ \frac{5}{\rho}&=&1+\frac23\;=\;(1.\overline{10}\strut^\infty)_2. \end{eqnarray*} Hence, there is only one relevant carry from first to second digit left of the radix point in the base-$2$ sum of $15/\rho$ and $5/\rho$. Thus, by our Kummerian rule, $\nu_2\binom{20}{5}_U=1+0+\d=4$. Using Proposition \ref{prop:AR} one can directly check that $$ \nu_2\binom{20}{5}_U=\nu_2\bigg(\frac{U_{20}\cdot U_{19}\cdot U_{18}\cdot U_{17}\cdot U_{16}} {U_5\cdot U_4\cdot U_3\cdot U_2\cdot U_1}\bigg)=\nu_2\bigg(\frac{U_{18}}{U_3}\bigg). $$ However, $\nu_2(U_{18})=\nu_2(U_{3\cdot2^1\cdot\rho})=1+\nu_2(U_3)+\d$. We won't always mention the Propositions \ref{prop:AR} and \ref{prop:K} when using them. The letter $p$ invariably denotes a prime number except in Lemma \ref{lem:5}. Although we usually write the $p$-adic valuation of an integer $m$, i.e., the highest exponent $e\ge0$ of $p$ such that $p^e$ divides $m$, as $\nu_p(m)$, we omit the parentheses when $m$ is a Lucasnomial coefficient $\binom{\ell}{k}_U$ and write instead $\nu_p\binom{\ell}{k}_U$. We also occasionally use the alternative notation $p^e||m$. Given a subset $S$ of the natural numbers, we write $S(z)$ for the elements of $S$ not exceeding $z$ and $\#S(z)$ for the cardinality of $S(z)$. We say $S$ has asymptotic density $d$ to mean that the ratios $\#S(z)/z$ tend to $d$ as $z$ tends to infinity. The sentence ``almost all positive integers" means all but a set of asymptotic density $0$. The upper asymptotic density of $S$ is the upper limit of the ratios $\#S(z)/z$ as $z$ tends to infinity. \section{Integrality of Lucasnomial Fuss-Catalan numbers and other Lucasnomial extensions of classical numbers} The forthcoming lemma leads to an unconditional algebraic proof of the integrality of Lucasnomial Fuss-Catalan numbers. As for the integrality of generalized Lucasnomial Fuss-Catalan numbers, we provide an arithmetic proof, alas conditional to the regularity of the Lucas sequence. \begin{lemma}\label{lem:1} Let $U$ be a nondegenerate fundamental Lucas sequence and $a\ge2$, $r\ge1$ be integers. Then the generalized Lucasnomial Fuss-Catalan numbers satisfy, for all $n\ge1$, the identity \begin{equation}\label{eq:5} C_{U,a,r}(n)=U_r\cdot\binom{an+r-2}{n-1}_U-Q\frac{U_rU_{(a-1)n+r-1}}{U_n}\cdot\binom{an+r-2}{n-2}_U. \end{equation} \end{lemma} \begin{proof} Replacing $m$ by $an+r-1$ and $n$ by $(a-1)n+r-1$ in (\ref{eq:2}), we obtain $$ \binom{an+r-1}{(a-1)n+r-1}_U=U_{(a-1)n+r}\binom{an+r-2}{(a-1)n+r-1}_U- Q U_{n-1}\binom{an+r-2}{(a-1)n+r-2}_U. $$ That is, using the symmetry of the Lucasnomial triangle, $$ \binom{an+r-1}{n}_U=U_{(a-1)n+r}\binom{an+r-2}{n-1}_U- Q U_{n-1}\binom{an+r-2}{n}_U. $$ Multiplying through by $U_r/U_{(a-1)n+r}$, we find that $$ C_{U,a,r}(n)=U_r\binom{an+r-2}{n-1}_U-Q\frac{U_rU_{n-1}}{U_{(a-1)n+r}}\binom{an+r-2}{n}_U. $$ But \begin{eqnarray*} \frac{U_{n-1}}{U_{(a-1)n+r}}\binom{an+r-2}{n}_U&=&\frac{U_{n-1}}{U_{(a-1)n+r}}\cdot\frac{U_{an+r-2}\cdots U_{(a-1)n+r-1}}{U_n\cdots U_1}\\ &=&\frac{U_{(a-1)n+r-1}}{U_n}\cdot\frac{U_{an+r-2}\cdots U_{(a-1)n+r+1}}{U_{n-2}\cdots U_1}\\ &=&\frac{U_{(a-1)n+r-1}}{U_n}\cdot\binom{an+r-2}{n-2}_U, \end{eqnarray*} which yields equation (\ref{eq:5}). \end{proof} \begin{theorem}\label{thm:1} Let $U$ be a nondegenerate fundamental Lucas sequence and $a\ge2$ be an integer. Then the Lucasnomial Fuss-Catalan numbers $$ C_{U,a,1}(n)=\frac{1}{U_{(a-1)n+1}}\binom{an}{n}_U \quad\text{ are integers for all }n\ge1. $$ \end{theorem} \begin{proof} As $U_n$ divides $U_{(a-1)n}$, setting $r=1$ in identity (\ref{eq:5}) we readily see that $C_{U,a,1}(n)$ is an integer. \end{proof} We will use the next small lemma a few times. \begin{lemma}\label{lem:notQ} Let $U(P,Q)$ be a fundamental Lucas sequence and $p$ be a prime. If $p\nmid\gcd(P,Q)$, then either $p\nmid Q$, or $p$ does not divide any term $U_n$, $n\ge1$, i.e., $p$ has no rank. \end{lemma} \begin{proof} Suppose $p\mid Q$. Then $p\nmid P$. Using (\ref{eq:rec}) inductively, one finds $U_n\equiv P^{n-1}\pmod p$ for all $n\ge1$. Therefore, $p\nmid U_n$. \end{proof} Here is a straightforward observation about generalized Lucasnomial Fuss-Catalan numbers. \begin{remark} Ordinary Catalan numbers $C_{I,2,1}(n)=\frac1{n+1}\binom{2n}{n}$ have the well-known alternative representations $$ \frac{1}{2n+1}\binom{2n+1}{n}\quad\text{ and }\quad\frac{1}{n}\binom{2n}{n-1}, $$ which carry over to generalized Lucasnomial Fuss-Catalan numbers. That is, \begin{equation}\label{eq:4} C_{U,a,r}(n)=\frac{U_r}{U_{an+r}}\binom{an+r}{n}_U=\frac{U_r}{U_n}\binom{an+r-1}{n-1}_U. \end{equation} \end{remark} Using the last form of $C_{U,a,r}(n)$ in (\ref{eq:4}), we produce an arithmetic proof of the integrality of $C_{U,a,r}(n)$. However, it assumes the regularity of $U$. \begin{theorem}\label{thm:2} Let $U(P,Q)$ be a regular fundamental Lucas sequence. Let $r\ge1$ and $a\ge2$ be integers. Then the generalized Lucasnomial Fuss-Catalan numbers $$ \frac{U_r}{U_{(a-1)n+r}}\binom{an+r-1}{n}_U \quad\text{ are integral for all }n\ge1. $$ \end{theorem} \begin{proof} By (\ref{eq:4}), $$ C_{U,a,r}(n)=\frac{U_r}{U_n}\binom{an+r-1}{n-1}_U. $$ We claim that for all primes $p$ the $p$-adic valuation of $U_r\binom{an+r-1}{n-1}_U$ is at least that of $U_n$. If $p\mid Q$, then, by Lemma \ref{lem:notQ}, $p\nmid U_n$ and our claim holds. Now suppose $p\nmid Q$ and $p$ divides $U_n$. Then, by Proposition \ref{prop:AR}, $n=\l\rho p^x$ for some $x\ge0$ and some $\l$ prime to $p$, where $\rho$ is the rank of $p$, and $\nu_p(U_n)=x+\nu+\d_x$. Let us divide $r$ by $\rho$ and write $r=q\rho+r_1$ with $0\le q$ and $0\le r_1<\rho$. Then \begin{eqnarray*} \frac{n-1}{\rho}&=&\l p^x-\frac{1}{\rho}=(\l p^x-1)+\frac{\rho-1}{\rho},\\ \frac{(a-1)n+r}{\rho}&=&\l(a-1)p^x+q+\frac{r_1}{\rho}. \end{eqnarray*} If the sum of the fractional parts of $(n-1)/\rho$ and $((a-1)n+r)/\rho$ is at least $1$, then a carry occurs across the radix point which ensures, independently of the value of $q$, a minimum of $x$ carries left of the radix point in the base-$p$ addition of $(n-1)/\rho$ and $((a-1)n+r)/\rho$. Indeed, the first $x$ base-$p$ digits of $(n-1)/\rho$ left of the radix point are all $p-1$. Therefore, by Kummer's rule for Lucasnomials, $\nu_p\binom{an+r-1}{n-1}_U\ge x+\nu+\d_x=\nu_p(U_n)$. If the fractional parts add up to less than $1$, i.e., if $(\rho-1)+r_1<\rho$, then $r_1=0$ and $r=q\rho$. Let $p^i$, $i\ge0$, be the exact $p$-power dividing $q$. Then $p^{i+\nu+\d_i}||U_r$. If $i\ge x$ then $p^{x+\nu+\d_x}$ divides $U_r$ and our claim holds. If $i0])=x+\nu+\d_x=\nu_p(U_n). $$ Thus, $C_{U,a,r}(n)$ is always an integer. \end{proof} \begin{remark}\label{rem:0} We could have stated a stronger theorem by dropping the regularity assumption on $U(P,Q)$ and instead stating that for all primes $p\nmid\gcd(P,Q)$, the $p$-adic valuation of the numbers $C_{U,a,r}(n)$ is nonnegative, for all $n\ge1$. \end{remark} We do not resist giving another related theorem with a different simple proof technique that partially implies  Theorem \ref{thm:1} and Theorem \ref{thm:2}. \begin{theorem}\label{thm:2bis} Let $U(P,Q)$ be a regular fundamental Lucas sequence. Let $r\ge1$ and $m\ge n\ge1$ be integers with $\gcd(m+r,n)=1$. Then the generalized Lucasnomial Fuss-Catalan numbers $$ T_{m,n,r}:=\frac{U_r}{U_{m+r}}\binom{m+n+r-1}{n}_U \quad\text{ are integers.} $$ \end{theorem} \begin{proof} We see that $U_{m+r}T_{m,n,r}$ is an integer and that $$ U_nT_{m,n,r}=U_r\binom{m+n+r-1}{n-1}_U, $$ is also integral. Since $U$ is regular and $\gcd(m+r,n)=1$, we find that $\gcd(U_{m+r},U_n)=1$ and immediately infer that $T_{m,n,r}$ is the greatest common divisor of the two integers $U_{m+r}T_{m,n,r}$ and $U_nT_{m,n,r}$. Hence, $T_{m,n,r}$ is an integer. \end{proof} Putting $m=(a-1)n$ in $T_{m,n,r}$, we see that Theorem \ref{thm:2} holds albeit with the restriction that $\gcd(r,n)=1$. If $r=1$, then we obtain Theorem \ref{thm:1} though only for $U$ regular. Lobb numbers $L_{m,s}=L_{m,s}^2$ and generalized Lobb numbers $L_{m,s}^a$ are defined by the expression $$ L_{m,s}^a:=\frac{as+1}{(a-1)m+s+1}\binom{am}{(a-1)m+s}; $$ see \cite[Eq.~(11)]{Ch}. The integrality of generalized Lucasnomial Lobb numbers (\ref{eq:Lobb}) which are a natural Lucasnomial extension of the generalized Lobb numbers is the object of the next theorem. \begin{theorem}\label{thm:Lobb} If $U$ is a regular Lucas sequence, $a\ge1$, $m>s\ge0$ are integers, then the generalized Lucasnomial Lobb numbers $$ L_{m,s}^{U,a}=\frac{U_{as+1}}{U_{(a-1)m+s+1}}\binom{am}{(a-1)m+s}_U $$ are integers. \end{theorem} \begin{proof} Putting $r=as+1$ and $n=m-s$ in the expression (\ref{eq:3}) for $C_{U,a,r}(n)$ yields $L_{m,s}^{U,a}$, so that, by Theorem \ref{thm:2}, the numbers $L_{m,s}^{U,a}$ are integral. Indeed, \begin{eqnarray*} C_{U,a,r}(n)&=&\frac{U_{as+1}}{U_{(a-1)(m-s)+as+1}}\cdot\binom{a(m-s)+(as+1)-1}{m-s}_U\\ &=&\frac{U_{as+1}}{U_{(a-1)m+s+1}}\cdot\binom{am}{m-s}_U\\ &=&\frac{U_{as+1}}{U_{(a-1)m+s+1}}\cdot\binom{am}{(a-1)m+s}_U=L_{m,s}^{U,a}. \end{eqnarray*} \end{proof} Similarly, the natural Lucasnomial extension of ballot numbers is shown to always yield integers. Ordinary ballot numbers are defined by $B(m,n)=\frac{m-n}{m+n}\binom{m+n}{n}$; see (14) in \cite{Ch}. \begin{theorem}\label{thm:ballot} If $U$ is a regular Lucas sequence, $m>n\ge0$ are integers, then the Lucasnomial ballot numbers $$ B_U(m,n)=\frac{U_{m-n}}{U_{m+n}}\binom{m+n}{n}_U $$ are integers. \end{theorem} \begin{proof} If $m$ and $n$ have different parities, then replacing $m$ by $(m+n-1)/2$ and $s$ by $(m-n-1)/2$ in $L_{m,s}^{U,2}$ precisely yields $B_U(m,n)$. However, to obtain a proof for all $m>n\ge0$, we first notice that \begin{equation}\label{eq:ballot2} B_U(m,n)=\frac{U_{m-n}}{U_{m+n}}\binom{m+n}{n}_U=\frac{U_{m-n}}{U_n}\binom{m+n-1}{n-1}_U. \end{equation} So, if $B_U(m,n)$ is a nonintegral rational number, there must exist a prime number $p$ with respect to which $B_U(m,n)$ has negative $p$-adic valuation. In particular, $p$ divides both $U_{m+n}$ and $U_n$. By Lemma \ref{lem:notQ}, $p\nmid Q$. Thus, $m=\mu p^y\rho$ and $n=\eta p^z\rho$ with $p\nmid\mu\eta$, where $\rho$ is the rank of $p$. If $y\not=z$, then $\nu_p(m-n)=\nu_p(m+n)$ and so $\nu_p(U_{m-n})=\nu_p(U_{m+n})$, which would contradict the negativity of $\nu_p(B_U(m,n))$. Therefore, $y=z$ and $\nu_p(U_n)=z+\nu+\d_z\le\nu_p(U_{m-n})$, because $m-n=(\mu-\eta)p^z\rho$. But, by the last expression in (\ref{eq:ballot2}), this contradicts the negativity of the $p$-adic valuation of $B_U(m,n)$. \end{proof} \section{The smallness of $D_{U,a,k}$ when $k\le0$} We provide two main theorems to assess the smallness of $D_{U,a,k}$ when $k\le0$ and $U(P,Q)$ is regular. The first theorem treats sequences $U$ with $P^2\not=4Q$, while the second treats the zero-discriminant case. Our first theorem extends \cite[Theorem 5.1]{Ba4}, which treated the case $a=2$, to all values of $a\ge2$. \begin{theorem}\label{thm:3} Suppose $U(P,Q)$ is a regular Lucas sequence with $P^2-4Q\not=0$. Assume $a\ge2$ and $k\ge0$ are fixed integers. Then there are at most finitely many integers $n\ge1$ such that $U_{(a-1)n-k}$ divides $\binom{an}{n}_U$. \end{theorem} \begin{proof} Since the case $a=2$ corresponds to \cite[Theorem 5.1]{Ba4}, we may assume $a\ge3$. Put $$ M:=\text{ max }\bigg\{\frac{2k}{a-2}, \frac{30+k}{a-1}\bigg\}. $$ Suppose $n>M$. Since $n$ is larger than $(30+k)/(a-1)$, the primitive divisor theorem \cite[Theorem 1.4, p.\ 80]{Bi} ensures that $U_{(a-1)n-k}$ has a primitive prime divisor, say $p$. That is, $\rho=\rho_U(p)=(a-1)n-k$. Thus, we find that \begin{eqnarray*} \frac{n}{\rho}&=&0+\frac{n}{(a-1)n-k},\\ \frac{(a-1)n}{\rho}&=&\frac{(a-1)n}{(a-1)n-k}=1+\frac{k}{(a-1)n-k}. \end{eqnarray*} Observe that $n>2k/(a-2)$ implies that $(a-1)n-k>0$ and that $(n+k)/((a-1)n-k)<1$. Thus, we see that $n/((a-1)n-k)$ and $k/((a-1)n-k)$ are the fractional parts of, respectively, $n/\rho$ and $(a-1)n/\rho$, and they add up to less than $1$. Hence, in the base-$p$ addition of $n/\rho$ and $(a-1)n/\rho$, there is no relevant carry as $0+1M$, we find that $U_{(a-1)n-k}$ does not divide $\binom{an}{n}_U$. \end{proof} We now look at the case of regular Lucas sequences with null discriminant, which essentially corresponds to $U_n=I_n$ and ordinary binomial coefficients. Theorem \ref{thm:I} below extends \cite[Theorem 3]{Po} that covered the case $a=2$. \begin{theorem}\label{thm:I} Suppose $U(P,Q)$ is a regular Lucas sequence with $P^2-4Q=0$, i.e., $U_n=n$ for all $n\ge1$, or $U_n=(-1)^{n-1}n$ for all $n\ge1$. Assume $a\ge2$ and $k\ge0$ are fixed integers. Then the upper asymptotic density of the set of integers $n\ge1$ such that $U_{(a-1)n-k}$ divides $\binom{an}{n}_U$ is at most $1-\log 2$. \end{theorem} \begin{proof} It suffices to consider the case $U=I$. The proof we give is an adaptation of the proof of \cite[Theorem 3]{Po}. Moreover, this adapted proof yields the same upper bound of $1-\log2$ for the upper asymptotic density of $D_{I,a,k}$, $k\le0$, as the one obtained when $a=2$. We begin by observing that if $(a-1)n-k$ has a prime factor $p>\sqrt{2(a-1)n}$ and $p>ak$, then $\nu_p((a-1)n-k)>\nu_p\binom{an}{n}$ so that $n\not\in D_{I,a,-k}$. Indeed, say $(a-1)n-k=cp$. Then $$ c\le\frac{(a-1)n}{p}<\frac{(a-1)n}{\sqrt{2(a-1)n}}=\frac{\sqrt{2(a-1)n}}{2}<\frac{p}{2}. $$ Hence, $(a-1)n=cp+k$ with $c

0$ and estimate the number of $n$ in $(ak^2,z]$ that have a prime factor $p>\sqrt{2(a-1)z}$. The lower bound $ak^2$ for $n$ is sufficient to imply $p>ak$. In the interval $(ak^2,z]$, there are $z/p+O(1)$ multiples of a prime $p>\sqrt{2(a-1)z}$. As $p>\sqrt{z}\ge\sqrt{n}$, no integer $n$ may have two such prime factors. Hence, we find that $$ \#{\overline D_{I,a,-k}}(z)\ge\sum_{\sqrt{2(a-1)z}k$ and $3p/2k$, and \begin{equation}\label{eq:+} q=p+d\quad\text{ with }\quad\frac{p}{a}(a-1)(q-p/(a-1))=(a-2)q+(q-p)$ and $(a-1)p<(a-1)q<(a-2)q+q$. Thus, the base-$q$ addition of $n$ and $(a-1)n$ produces at least one carry. Hence, $pq$ divides $\binom{an}{n}$. From the lemmas of Section 6, one has that $a-1$ divides $\binom{an}{n}$ for almost all $n$. However, here, the integers $n$ we consider have a special form. So, in addition to $p$ and $q$ satisfying (\ref{eq:+}), we further impose the condition that $p\equiv m+1\pmod{(a-1)^2}$ and $q\equiv-1\pmod{(a-1)^2}$. Suppose $r$ is a prime factor of $a-1$ and $a-1=r^\a\l$, where $r$ and $\l$ are coprime. Then $p\equiv m+1\pmod{r^{2\a}}$ and $q\equiv-1\pmod{r^{2\a}}$. Thus, $pq+m\equiv-1\pmod{r^{2\a}}$, which says that the $r$-ary expansion of $n$ terminates with $2\a$ digits all $r-1$. Furthermore, the base-$r$ expansion of $(a-1)n=r^\a\cdot\l(pq+m)$ ends with a nonzero digit followed by $\a$ zero digits. Therefore, the base-$r$ addition of $n$ and $(a-1)n$ generates a minimum of $\a$ carries. By the Kummer rule, $r^{\a}$ divides $\binom{an}{n}$. As it is true of all prime factors $r$ of $a-1$, $a-1$ divides $\binom{an}{n}$. We conclude that for all such integers $n$, $(a-1)pq=(a-1)n-k$ divides $\binom{an}{n}$. Therefore, for all large enough real numbers $z\ge1$, we find that \begin{equation*} \#D_{I,a,-k}(z)\ge\sum_{k\sqrt{z}/3$ and $\log p\le\log(\sqrt{z}/2)$. Thus, as $z$ tends to infinity, $S_z$ is at least equivalent to $$ \frac23c\frac{\sqrt{z}}{\log z}\sum_{\frac{\sqrt{z}}3\nu_p\binom{an}{n}_U\bigg\}. \end{equation} Note that \begin{equation}\label{eq:ap'} \overline D_{U,a,k}=\bigcup_pA_p, \end{equation} where the union is over all primes. We proceed to show that $A_p$ is empty except, possibly, for the finitely many primes $p$ of rank less than $ak$. \begin{lemma}\label{lem:2} Suppose $U(P,Q)$ is a nondegenerate fundamental Lucas sequence, while $a\ge2$ and $k\ge1$ are fixed integers. Assume $p\nmid Q$ is a prime of rank $\ge ak$. Then, $A_p$ is empty. That is, for all $n\ge1$, $$ \nu_p\binom{an}{n}_U\ge\nu_p\big(U_{(a-1)n+k}\big). $$ \end{lemma} \begin{proof} Note that $$ \frac1{U_{(a-1)n+k}}\binom{an}{n}_U=\frac{\prod_{j=1}^{k-1}U_{(a-1)n+j}}{\prod_{i=0}^{k-1}U_{n-i}} \binom{an}{n-k}_U. $$ Thus, if our claim is wrong, then $p$ must divide some factor, say $U_{n-e}$, $0\le e\le k-1$, in the product $\prod_{i=0}^{k-1}U_{n-i}$. Thus, $\rho$ divides $n-e$, where $\rho$ is the rank of $p$ in $U$. But $p$ must also divide $U_{(a-1)n+k}$, that is, $\rho$ divides $(a-1)n+k$. As $n\equiv e\pmod \rho$, we see that $\rho$ divides $(a-1)e+k$. However, $0<(a-1)e+k2$, we see that $(\rho-2)/\rho$ is the fractional part of $2n/\rho$. Moreover, $\rho\mid 2n+2$ implies $\rho\nmid n$. Thus, $\big\{\frac{n}{\rho}\big\}\ge\frac1{\rho}$. If $\big\{\frac{n}{\rho}\big\}\ge\frac2{\rho}$, then there is a carry across the radix point and, due to the $x$ consecutive $p-1$ digits in the $p$-ary expansion of $p^x-1$, this carry over the radix point guarantees at least $x$ further carries left of that point in the base-$p$ addition of $2n/\rho$ to $n/\rho$. Thus, by the Kummer rule for Lucasnomials, the $p$-adic valuation of $\binom{3n}{n}_F$ is at least $x+1+\d_x$, which is $\nu_p(F_{2n+2})$. We conclude that if $\big\{\frac{n}{\rho}\big\}\ge\frac2{\rho}$, then $n\not\in A_p$. Hence, $\big\{\frac{n}{\rho}\big\}=\frac1\rho$, i.e., an $n\in A_p$ must be of the form $q\rho+1$. In particular, $2n+2=2q\rho+4$ so that $\rho\mid 4$, and, as $F_2=1$, $\rho=4$. But $F_4=3$. Therefore, $A_2$ and $A_5$ are empty and we now assume $p=3$. Since $n=4q+1$, equations (\ref{eq:8}) become \begin{align}\begin{split} \frac{2n}{\rho}&=2q+\frac{1}{2},\\ \frac{n}{\rho}&=q+\frac{1}{4}. \end{split}\label{eq:9} \end{align} Since $2n+2=\l\cdot 4\cdot3^x=4(2q+1)$, we see that $2q+1=(3j+i)3^x$, where we set $\l=3j+i$ with $i=1$ or $2$. Therefore, \begin{align}\begin{split} 2q&=(3j+i-1)\cdot3^x+(22\cdots 2)_3,\quad(x\;2\text{'s})\\ q&=\frac{3j+i-1}2\cdot3^x+(11\cdots 1)_3,\quad(x\;1\text{'s}) \end{split}\label{eq:10} \end{align} where $(dd\cdots d)_3$ with $x$ $d$'s stands for $d(3^{x-1}+3^{x-2}+\cdots+1)$. If the integer $\ell=(3j+i-1)/2\not=0$, then we obtain from (\ref{eq:10}) that the base-$3$ addition of $2q$ and $q$ produces at least $\nu_3(F_{2n+2})=x+1$ carries. Indeed, as easily seen, and as shown in \cite[Lemma 2.2]{Ba2}, adding $\ell\ge1$ and $(p-1)\ell$ in base $p$, $p$ a prime, yields at least one carry. However, if $3j+i-1=0$, the base-$3$ addition ``\,$2q+q$\," only produces $x$ carries so that $n$ belongs to $A_3$. But then $2q+1=3^x$ and $n=2\cdot3^x-1$. This proves the corollary. \end{proof} \begin{remark}\label{rem:2} The proof of Corollary \ref{cor:1} shows that $\frac3{F_{2n+2}}\binom{3n}{n}_F$ is an integer for all $n\ge1$. We also note that $D_{F,3,2}$ has asymptotic density one in the positive integers, but that it misses infinitely many integers. Do these facts hold in general? \end{remark} We will provide answers in due course, but we begin with the latter fact, which is that $\overline D_{F,3,2}$ is infinite. The only regular Lucas sequences $U(P,Q)$ with $P>0$ for which there exists a $k\ge2$ such that $\overline D_{U,2,k}$ is finite --- it is in fact empty --- corresponds to $(P,Q)=(1,2)$ \cite[Theorem 3.5]{Ba4}. We want to find out whether, when $a\ge3$, such examples occur. We say a triple $(U,a,k)$, with $k\ge2$, is a {\it Catalan-like} triple if and only if, for all natural numbers $n$, $$ \frac1{U_{(a-1)n+k}}\binom{an}{n}_U \quad\text{ is an integer.} $$ We proceed with a lemma which states conditions sufficient to guarantee the infinitude of $A_p(U,a,k)$. It gives a minimal infinite subset of $A_p$ when $p$ satisfies some rank condition. Actually, the set $A_3$ in Corollary \ref{cor:1} is equal to that minimal subset. \begin{lemma}\label{lem:3} Let $U(P,Q)$ be a nondegenerate fundamental Lucas sequence and $a\ge2$, $k\ge2$ be integers. Assume there exists a prime $p\nmid Q$ of rank $\rho$ in $U$, where $$ \rho=k+\ell(a-1), $$ for some $\ell$, $1\le\ell\le k-1$. Then $A_p(U,a,k)$ is infinite and contains all integers $n$ of the form $$\frac{\rho p^x-k}{a-1}, \text{ for all }x \text{ divisible by }\varphi(a-1), $$ where $\varphi$ denotes the Euler totient function. \end{lemma} \begin{proof} As $\rho\ge2+(a-1)=a+1$ and $p\ge\rho-1$, we have $p\ge a$. Hence, $p\nmid a-1$. Thus, the condition $\varphi(a-1)$ divides $x$ guarantees that $p^x-1$ is divisible by $a-1$. Also, because $\rho\equiv k\pmod{a-1}$, for each $x\ge0$ divisible by $\varphi(a-1)$, there is a unique $n=n_x\ge1$ such that $$ (a-1)n+k=\rho p^x. $$ Therefore, for these integers $n$, we find that \begin{align}\begin{split} \frac{(a-1)n}{\rho}&=p^x-1+\frac{\rho-k}{\rho},\\ \frac{n}{\rho}&=\frac{p^x-1}{a-1}+\frac{\ell}{\rho}, \end{split}\label{eq:11} \end{align} where we see that $(\rho-k)/\rho$ and $\ell/\rho$ are the fractional parts of, respectively, $(a-1)n/\rho$ and $n/\rho$. The sum of these two fractional parts is less than $1$ since $\rho-(k-\ell)<\rho$. By the Kummer rule for Lucasnomials, we see that $\nu_p\binom{an}{n}_U\le x+\d_x$. (In fact, it is $x+\d_x$ since, if $x>0$, the integer $(p^x-1)/(a-1)$ is prime to $p$ and the base-$p$ addition of $(a-1)n/\rho$ and $n/\rho$ produces exactly $x$ carries left of the radix point.) But, $\nu_p\big(U_{(a-1)n+k}\big)=x+\nu+\d_x > x+\d_x$. \end{proof} We add some power to Lemma \ref{lem:3} by observing that if $U_k$ possesses a primitive prime divisor $p$ prime to $Q$, then the equations in (\ref{eq:11}) remain valid. Thus, if $p\nmid a-1$, then, again, for all integers $n$ of the form $k(p^x-1)/(a-1)$, $x$ a multiple of $\varphi(a-1)$, $U_{(a-1)n+k}$ does not divide $\binom{an}{n}_U$. However, the condition $p\nmid a-1$ is no longer necessarily true. We state this observation as an additional lemma. \begin{lemma}\label{lem:4} Let $U(P,Q)$ be a nondegenerate fundamental Lucas sequence and $a\ge2$, $k\ge2$ be integers. Assume there exists a prime $p\nmid Q(a-1)$ of rank $k$. Then $A_p(U,a,k)$ is an infinite set. \end{lemma} One can see that the hypotheses of Lemma \ref{lem:3} are the weakest when $k=2$. Indeed, for $k=2$, we need a prime of rank $a+1$ to assert that $A_p$ is infinite. Some lemmas will help reach a conclusion whenever there are no primes of rank $a+1$. Inspired by the proof of Corollary \ref{cor:1}, we establish a first supplementary lemma for the case $k=2$. \begin{lemma}\label{lem:N} Let $U(P,Q)$ be a nondegenerate fundamental Lucas sequence and $a\ge2$ be an integer. If $p\nmid Q$ is a prime of rank $\rho$, with $\rho>2$ and $\rho\nmid a+1$, then $A_p(U,a,2)$ is empty. \end{lemma} \begin{proof} The argument is close to that of Corollary \ref{cor:1} so we abbreviate it. If $n\in A_p$, then there is an $x\ge0$ and a $\l\ge1$ not divisible by $p$ such that $(a-1)n+2=\l\rho p^x$. Hence, $$ \frac{(a-1)n}{\rho}=(\l-1)p^x+p^x-1+\frac{\rho-2}\rho. $$ In the base-$p$ addition of $n/\rho$ to $(a-1)n/\rho$ a carry across the radix point generates at least $x$ carries left of that point. As a consequence $\nu_p\binom{an}{n}_U\ge\nu_p\big(U_{(a-1)n+2}\big)$ and $n\not\in A_p$. Since $n\in A_p$, either $\rho\mid n$ or $n=q\rho+1$ for some integer $q$. As $\rho\mid(a-1)n+2$, if $\rho\mid n$, then $\rho=2$. If $n=q\rho+1$, then $$ (a-1)n+2=(a-1)q\rho+(a+1)=\l\rho p^x, $$ so that $\rho\mid a+1$. \end{proof} This, together with Lemma \ref{lem:notQ}, yields the immediate corollary. \begin{cor}\label{cor:2} With the hypotheses of Lemma \ref{lem:N} and $k=2$, if $P=1$ and $U_{a+1}=\pm1$, then $\overline D_{U,a,2}$ is empty. On the other hand, if $|U_{a+1}|>1$ and $\rho(p)=a+1$, then, by Lemma \ref{lem:3}, $\overline D_{U,a,2}$ is infinite. If $a$ and $P$ are even and $Q$ is odd, then $\overline D_{U,a,2}$ is infinite by Lemma \ref{lem:4}. \end{cor} Here is a theorem, which under fairly broad hypotheses, tells us that $A_p$ cannot be a finite nonempty set. \begin{theorem}\label{thm:D} Let $U(P,Q)$ be a NFL-sequence and $a\ge2$, $k\ge1$ be integers. Let $p\nmid Q(a-1)$ be a prime of rank at least $k$. Then $A_p$ is either empty or infinite. \end{theorem} \begin{proof} Denoting as usual the rank of $p$ by $\rho$, suppose $A_p$ is not empty. Then there is an integer $n_0\ge1$ in $A_p$ and integers $\l\ge1$, $p\nmid\l$, $x_0\ge0$ such that \begin{equation}\label{eq:star} (a-1)n_0+k=\l\rho p^{x_0}. \end{equation} In particular, $\nu_p\big(U_{(a-1)n_0+k}\big)=x_0+\nu+\d_{x_0}$. As $n_0\in A_p$ and $(a-1)n_0/\rho=\l p^{x_0}-1+(\rho-k)/\rho$, it must be, by the Kummer rule for Lucasnomials, that $$ \bigg\{\frac{n_0}{\rho}\bigg\}+\frac{\rho-k}{\rho}<1. $$ We are about to show that, with the same integer $\l$ which appears in (\ref{eq:star}), there are infinitely many integers $n\ge1$ such that $(a-1)n+k=\l\rho p^x$, for some $x\ge0$, which satisfy $\big\{\frac{n}{\rho}\big\}=\big\{\frac{n_0}{\rho}\big\}$. By the above analysis for $n_0$, this implies all such $n$ are in $A_p$. Now $(a-1)n+k=\l\rho p^x$ if and only if \begin{equation}\label{eq:star+} (a-1)(n-n_0)=\l\rho(p^x-p^{x_0}) \end{equation} As $p\nmid a-1$, $p^x\equiv p^{x_0}\pmod{a-1}$ occurs for all $x$ satisfying $x\equiv x_0\pmod h$, where $h$ is the multiplicative order of $p\pmod{a-1}$. For each $s\ge0$, put $x_s=x_0+sh$ and define $t_s$ by $p^{x_s}=p^{x_0}+t_s(a-1)$. Note that $(t_s)_{s\ge0}$ is an increasing sequence of integers. Putting $p^{x_s}-p^{x_0}=t_s(a-1)$ into $(\ref{eq:star+})$ we find that $n=n_s=n_0+t_s\l\rho$ satisfies $(\ref{eq:star+})$ with the fractional part of $n/\rho$ equal to that of $n_0/\rho$. \end{proof} Theorem \ref{thm:D} will come in handy in the next section, but mostly in the guise of the next corollary. \begin{cor}\label{cor:S} Suppose $U(P,Q)$ is regular, $a\ge2$ and $k=2$. Let $p\nmid a-1$ be a prime. If $p\mid U_{a+1}$, then $A_p(U,a,2)$ is infinite. \end{cor} \begin{proof} By (\ref{eq:reg}), if $p\mid U_{a+1}$, then $p\nmid U_a$. Hence, $\nu_p(U_{(a-1)+2})>\nu_p\binom{a}{1}_U$ and $1\in A_p(U,a,2)$. By Lemma \ref{lem:notQ}, $p\nmid Q$. So by Theorem \ref{thm:D}, $A_p$ is infinite. \end{proof} \section{Chasing all Catalan-like triples $(U,a,k)$, $k\ge2$,\\ and a proof that $\overline D_{U,a,k}$ is otherwise infinite} We first study the case $k\ge3$. \begin{prop}\label{prop:1} Let $a\ge3$ and $k\ge3$. Then for all nonzero-discriminant regular Lucas sequences $U(P,Q)$, there are infinitely many integers $n\ge1$ for which $U_{(a-1)n+k}$ does not divide $\binom{an}{n}_U$. \end{prop} \begin{proof} Suppose first $k\ge4$. To have a chance at finding a counterexample to our proposition, we need, by Lemma \ref{lem:3}, to find regular sequences $U$ that are $n$-defective for at least three indices $n$ in arithmetic progression, namely at least at $k+a-1$, $k+2(a-1)$ and $k+3(a-1)$ knowing that $k+a-1\ge6$. Inspecting Table A of Section 7, we discover only two such instances, namely the sequence $U(1,2)$ which is $n$-defective at $6$, $12$ and $18$ and also at $n=8$, $13$ and $18$. In the case of $6$, $12$ and $18$, the common difference is $6$. So $a-1=6$ and $k+a-1=6$. This yields $k=0$, a contradiction. In the second case, as $U(1,2)$ is not $23$-defective, there is no counter-example if $k\ge5$. So assume $k=4$. Solving $k+a-1=8$ for $a-1$ yields $a-1=4$. However, as the three indices $n=8$, $13$ and $18$ are $5$ apart, we would have needed $a-1=5$. So we now assume $k=3$. Using Table A, we now search for sequences that are both $(a+2)$ and $(2a+1)$-defective. For $a=3$, again the sequence $U(1,2)$ is both $5$ and $7$-defective. But $U_7$ has the primitive prime divisor $7$, which was discarded from Table A because $7$ divides the discriminant $P^2-4Q$. But that $p$ divides $\Delta$ does not invalidate Lemma \ref{lem:3}. Examining all values of $a$, $4\le a\le14$, we only find one candidate sequence when $a=6$, i.e., again $U(1,2)$, which is $8$ and $13$-defective as seen earlier. To show that $\overline D_{U,6,3}$, with $U=U(1,2)$, is infinite, it suffices to prove that the set $A_3(U,6,3)$, defined in (\ref{eq:ap}), is infinite. Note that $3\nmid a-1$. Moreover, $U_6=\binom{6}{1}_U=5$ is not divisible by $U_{(a-1)\cdot1+3}=U_8=-3$. That is, $1\in A_3$. By Theorem \ref{thm:D}, $A_3$ is infinite. \end{proof} We now study the case $k=2$. \begin{theorem}\label{thm:E} The four triples $\big(U(1,2),a,2\big)$, for $a=4$ and $a=12$, $\big(U(1,3),4,2\big)$ and $\big(U(1,5),6,2\big)$ are all four Catalan-like triples. That is, $$ \frac1{U_{(a-1)n+k}}\binom{an}{n}_U, $$ is integral for all natural numbers $n$. \end{theorem} \begin{proof} The first few terms of the most frequently defective Lucas sequence $U(1,2)$ are $$ 0,\,1,\,1,\,-1,\,-3,\,-1,\,5,\,7,\,-3,\,-17,\,-11,\,23,\,45,\,-1,\,-91,\,-89,\,93,\,271 \text{ and }85. $$ The first terms up to $U_7$ are $$\begin{cases} 0,\,1,\,1,\,-2,\,-5,\,1,\,16,\,13,& \text{ for }U(1,3);\\ 0,\,1,\,1,\,-4,\,-9,\,11,\,56,\,1,& \text{ for }U(1,5). \end{cases}$$ For $U(1,2)$ and $U(1,3)$, we see that $U_5=\pm1$. Therefore, by Corollary \ref{cor:2}, $\overline D_{U,4,2}$ is empty. For $U(1,5)$, $U_7=1$ so $\overline D_{U,6,2}$ is empty by the same Corollary \ref{cor:2}. Similarly, for $U(1,2)$, we find that $U_{13}=-1$ so $\overline D_{U,12,2}$ is empty. \end{proof} \begin{prop}\label{prop:2} Let $U(P,Q)$ be a nonzero-discriminant regular Lucas sequence, $a\ge3$ be an integer and $k=2$. Then, except for the four exceptions of Theorem \ref{thm:E}, there exist infinitely many integers $n\ge1$ for which $U_{(a-1)n+k}$ does not divide $\binom{an}{n}_U$. \end{prop} \begin{proof} We display the terms $U_2$, $U_3$, $U_4$ and $U_6$ of $U(P,Q)$ as polynomials in $P$ and $Q$: $$ U_2=P\;,U_3=P^2-Q,\;U_4=P(P^2-2Q),\;U_6=P(P^2-Q)(P^2-3Q). $$ We proceed case by case depending on the value of $a$. By Lemma \ref{lem:3}, the only values of $a$ to consider are those for which there is some $U$ with $U_{a+1}$ free of primitive prime divisors. \medskip \noindent{\bf Case $a=3$.} If $U_4$ has a primitive prime divisor, then, as $a+1=4$, we obtain that $\overline D_{U,3,2}$ is infinite as a consequence of Lemma \ref{lem:3}. (Note that the hypothesis $p\nmid Q$ holds by Lemma \ref{lem:notQ}.) If $U_4$ has no p.p.d., then $P^2-2Q=\pm1$. So $P$ is odd $\ge1$. If $P=1$, then $Q=1$, so that $P^2-Q=U_3=0$, which contradicts the nondegeneracy of $U$. Hence, $P$ is odd $>1$ and $U_2=U_k$ admits a p.p.d.\ $p\ge3$. As $p\nmid a-1=2$, we reach the result sought by applying Lemma \ref{lem:4}. \medskip \noindent{\bf Case $a=4$.} Since $a+1=5$ we need only consider the seven sequences listed as $5$-defective in Table A for, by Lemma \ref{lem:3}, they are the only ones for which $\overline D_{U,4,2}$ could be finite. But of these seven sequences three have a discriminant divisible by $5$. Thus, $5$ is a primitive divisor of $U_{a+1}$ and we may discard them by Lemma \ref{lem:3}. Two others are $U(1,2)$ and $U(1,3)$ for which, as seen in Theorem \ref{thm:E}, $\overline D_{U,4,2}$ is empty. The remaining two are $U(12,55)$ and $U(12,377)$ for which $p=2$ has rank $2$ with $2\nmid a-1$ so that Lemma \ref{lem:4} ensures our claim holds. \medskip \noindent{\bf Case $a=5$.} This might be the most intricate case because there are four infinite families of regular Lucas sequences that are $(a+1)$-defective, i.e., $6$-defective, according to Table A. However, for two of these four infinite families $3\mid P$. Hence, $p=3$ has rank $k$ and $p\nmid a-1$ so that, by Lemma \ref{lem:4}, $\overline D_{U,5,2}$ is infinite. The two remaining families are {\bf 1.} $(P,Q)=\big(P,(P^2-1)/3\big)$ for all $P>3$, $3\nmid P$, and {\bf 2.} $(P,Q)=\big(P,(P^2-(-2)^i)/3\big)$, where $i\ge1$, $P\equiv\pm1\pmod 6$, $(P,i)\not=(1,1)$. In both families, if $P$ has an odd prime divisor $p$, then, as $p\nmid a-1$, $\overline D_{U,5,2}$ is infinite by Lemma \ref{lem:4}. If not, then for the family {\bf 1.} $P=2^\a$ for some $\a\ge2$. Thus, $Q=(P^2-1)/3$ is odd. Moreover, $P^2-3Q=1$ and $4^\a-3Q=1$ implies that $Q\equiv1\pmod 4$. Thus, $U_3=P^2-Q=(2P^2+1)/3$ is $\ge11$ and $\equiv3\pmod 4$. Hence, there exists a prime $p\ge3$, $p\equiv3\pmod 4$ of rank $3$. Thus, we obtain an infinite sequence of integers $(n_x)_{x\ge1}$ defined by $4n_x+2=2\cdot3\cdot p^x$. Putting $n=n_x$ we see that $4n/3=2p^x-1+1/3$. Noting that $2p^x-1=4q+1$ for some integer $q$, we find that $n/3=q+1/4+1/12=q+1/3$. Therefore, the base-$p$ addition of $(a-1)n/\rho$ and $n/\rho$ generates exactly $x$ carries left of the radix point and none across that point. Therefore, $n_x\in A_p$ for all $x\ge1$ and $\overline D_{U,5,2}$ is infinite. Now for the second family {\bf 2.}, if $U_2$ does not have an odd p.p.d., then $P=1$. Thus, as $(P,i)\not=(1,1)$, we have $i\ge2$ and, putting $j=i-2$, we find that $U_3=1-Q=\big(2+(-2)^{j+2}\big)/3$, $j\ge0$, is divisible by $2$. We prove that $A_2$ is infinite. For each $\l\ge1$ odd, $\nu_2(U_{6\l})=j+3$. Indeed, $\nu_2(U_{6\l})=\nu_2(U_6)$. But $U_6=(1-Q)(1-3Q)$ and $1-Q=\big(2+(-2)^{j+2})/3$ has $2$-adic valuation $1$, whereas $1-3Q=(-2)^{j+2}$. For each $t\ge1$ define the odd integer $\l=(2\cdot8^t+5)/7$, which may be written in terms of the base-$2$ representation of $\l-1$ as $$ \l=(\l-1)+1=(\overline{010}\strut^t)_2+1, $$ where $\overline{010}\strut^t=010\,010\cdots010$ (the string $010$ being repeated $t$ times). To each such $\l$, corresponds a unique integer $n\ge1$ such that $4n+2=6\l$. Since $4n/3=2\l-1+1/3= (\overline{100}^t)_2+1+1/3$ and, thus, $n/3=(\overline{001}^t)_2+1/4+1/12=(\overline{001}^t)_2+1/3$, we see that the base-$2$ addition of $(a-1)n/\rho$ and $n/\rho$ creates a single carry from position $1$ to position $2$ left of the radix point. Therefore, $\nu_2\binom{5n}{n}_U=1+\d=j+2$, whereas $\nu_2(U_{6\l})=j+3$. Thus, $A_2$ is infinite. The only values of $a$ left for consideration are: 6, 7, 9, 11, 12, 17 and 29. For the other values, there are no $(a+1)$-defective sequences $U$. \medskip \noindent{\bf Case $a=6$.} The only $7$-defective sequences according to Table A, Section 7, are $(P,Q)=(1,2)$ and $(1,5)$. However, $7$ is a primitive divisor of $U_7=U_{a+1}$ for the first sequence since $7\mid\Delta$. So $A_7$ is infinite by Lemma \ref{lem:3}. The second sequence $U$ has parameters $(P,Q)=(1,5)$ and $(U,6,2)$ was identified as a Catalan-like triple in Theorem \ref{thm:E}. \medskip \noindent{\bf Case $a=7$.} There are only two $8$-defective regular Lucas sequences $U(2,7)$ and $U(1,2)$. For $(P,Q)=(2,7)$, $U_2=2$ and $U_8=-40$ so that, by Lemma \ref{lem:N}, we need only consider $A_2$ and $A_5$. Since $5\nmid a-1$, but $5\mid U_{a+1}$, $A_5$ is infinite by Corollary \ref{cor:S}. (In fact, $A_2$ is infinite as well. Indeed, for each even $x\ge2$, there is an $n\ge1$ which solves the equation $6n+2=2\cdot2^x$. Since for all such $x$ and $n$ we find that $6n/2=2^x-1$ is integral, the base-$2$ addition of $(a-1)n/\rho$ and $n/\rho$ does not produce a carry across the radix point so that $\nu_2\binom{7n}{n}_U\le x<1+x=\nu_2\big(U_{6n+2}\big)$.) For $(P,Q)=(1,2)$, we show that $A_3$ contains $\{1+4\cdot3^t,\;t\ge0\}$. Indeed, $\rho(3)=4$ and, for $n=1+4\cdot3^t$, we see that $6n/4=2\cdot3^{t+1}+1+1/2$ while $n/4=3^t+1/4$. Their base-$3$ addition raises no carry at all. So $3\nmid\binom{7n}{n}_U$. However, $4$ divides $6n+2$ implies that $\nu_3\big(U_{6n+2})\ge1$. \medskip \noindent{\bf Case $a=9$.} As usual if $U_{a+1}$ has a p.p.d.\ then $\overline D_{U,a,2}$ is infinite by Lemma \ref{lem:3}. So we look at Table A for the $10$-defective sequences. There are three: $(P,Q)=(2,3)$, $(5,7)$ and $(5,18)$. For the last two $P=5$ so the prime $5$ has rank $2$ and does not divide $a-1$. Hence, by Lemma \ref{lem:4}, $A_5$ is infinite. For $U(2,3)$, $U_5=-11$. So $11\mid U_{a+1}$, but $11\nmid a-1$. Hence, $A_{11}$ is infinite by Corollary \ref{cor:S}. \medskip \noindent{\bf Case $a=11$.} There are six $12$-defective sequences corresponding to $(P,Q)=(1,-1)$, $(1,2)$, $(1,3)$, $(1,4)$, $(1,5)$ and $(2,15)$. For $(1,-1)$, $(1,2)$, $(1,4)$ and $(1,5)$, $3\nmid Q$. So, as $\rho(3)$ is either $2$, $3$ or $4$, we see that $3\mid U_{12}$. As $3\nmid a-1$, we conclude that $A_3$ is infinite by Corollary \ref{cor:S}. For $U(1,3)$, $U_3=-2$ and $U_6=16$. Although $2\mid a-1$, we claim that $A_2$ contains $$\bigg\{\frac{3\cdot2^{4t+1}-1}5\;;\;t\ge0\bigg\}.$$ Indeed, if $n=(3\cdot2^{4t+1}-1)/5$, then $10n+2=3\cdot2^{4t+2}$. Thus, $\nu_2(U_{10n+2})=(4t+2)+1+\d=4t+5$. But $10n/3=2^{4t+2}-1+1/3$, while $n/3=(2^{4t+2}-1)/10+1/30\equiv3/10+1/30=1/3 \pmod 1$. Therefore, by the Kummer rule for Lucasnomials, $\nu_2\binom{11n}{n}_U\le(4t+2)+\d=4t+4<\nu_2(U_{10n+2})$. For $U(2,15)$, $U_3=-11$. Hence, $11\mid U_{12}$ and $11\nmid a-1$, so that $A_{11}$ is infinite by Corollary \ref{cor:S}. \medskip \noindent{\bf Case $a=12$.} The only $13$-defective sequence is $U(1,2)$. We saw in Theorem \ref{thm:E} that $\big(U(1,2),12,2\big)$ is a Catalan-like triple. \medskip \noindent{\bf Cases $a=17$ and $a=29$.} The sequence $U(1,2)$ is the only $18$-defective and the only $30$-defective regular Lucas sequence. As $U_6=5$, we see that $5\mid U_{18}$ and $5\mid U_{30}$. Since $5\nmid 17-1$ and $5\nmid 29-1$, we conclude, with the help of Corollary \ref{cor:S}, that $A_5(U,17,2)$ and $A_5(U,29,2)$ are both infinite sets. \end{proof} For the sake of completeness, we now address the case of zero-discriminant regular Lucas sequences $U$, i.e., of $U_n=I_n$ or $U_n=(-1)^{n-1}I_n$. Clearly it suffices to study the case of $U=I$. \begin{prop}\label{prop:3} The sets $\overline D(I,a,k)$ are infinite for all $a\ge2$ and all $k\ge2$. \end{prop} \begin{proof} Let $a$ and $k$ be integers exceeding $1$. Let $g=\gcd(a-1,k)$. The argument is split into three complementary cases. \medskip \noindent{\bf Case 1.} Suppose $g>1$. Let $p$ be a prime factor of $g$ and put $n=p^x$ for some $x\ge0$. Then the $p$-ary expansion of $(a-1)n$ ends with $x+1$ zeros, while $n$ has a single digit $1$ at position $x$. Thus, there is no carry in the base-$p$ addition of $(a-1)n$ and $n$. By Kummer's rule, $p$ does not divide $\binom{an}{n}$. But $p$ divides $(a-1)n+k$. So $(a-1)n+k$ does not divide $\binom{an}{n}$. Therefore, for all $x\ge0$, $p^x$ belongs to $\overline D(I,a,k)$. \medskip \noindent{\bf Case 2.} Assume $g=1$ and $k\nmid a$. Then there is a prime $p$ such that $p^\k||k$, $p^u||a$ for some $\k>u$. We write $a=p^ua'$. Put $n=p^x$ for some $x>\k$. Then \begin{eqnarray*} (a-1)n&=&an-n=a'p^{x+u}-p^x=(a'-1)p^{x+u}+(p-1)p^{x+u-1}+\cdots+(p-1)p^x\\ n&=&p^x. \end{eqnarray*} Their base-$p$ addition creates exactly $u$ carries since the carry into position $x+u$ does not propagate any further to the left. Indeed, $p\nmid a'\implies a'-1\not\equiv p-1\pmod p$. By the rule of Kummer, $p^u||\binom{an}{n}$. However, $p^\k$ divides $(a-1)n+k$. Therefore, all $p^x$, $x>\k$, are in $\overline D(I,a,k)$. \medskip \noindent{\bf Case 3.} Assume $a=k\ell$ for some $\ell\ge1$. Thus, $g=1$. Let $p$ be a prime factor of $k$ and write $k=p^\k k'$, $p\nmid k'$. Let $h$ be the multiplicative order of $p$ modulo $a-1$. Let $t>0$ be an integer large enough so that $p^x>k$, where $x=\k+ht$. Then $k'p^x-k=k(p^{ht}-1)$ is a multiple of $a-1$. Define $n=n_t$ as $(a-1)n=k'p^x-k$. The $p$-ary expansion of $k'p^x-k$ has the form $$ (k'-1)p^x+d_{x-1}p^{x-1}+\cdots+d_\k p^\k, $$ where the $d_i$'s are $p$-ary digits. If $d_x$ is the $(x+1)$-st $p$-ary digit of $k'p^x-k$, i.e., if $(k'-1)p^x \equiv d_xp^x\pmod{p^{x+1}}$, then $d_x\not=p-1$, because $d_x=p-1$ would imply that $p\mid k'$. Moreover, $(a-1)nu$, we will see that the form of $(a-1)n/\rho$ generally induces a minimum of $x-u$ carries right of position $x$ and left of the radix point. Thus, no matter how large $x$ we only need a bounded fixed number of carries left of position $x$ to guarantee $n$ is not $A_p$. This gives the desired conclusion. It is well-known \cite[Theorem 143, p.\ 120]{HW} that almost all natural numbers, when expressed in any scale, contain every possible sequence of digits. But we need to quantify somewhat this `almost all' statement. The editor-in-chief mentioned the work of Guibas and Odlyzko (\cite{GO} and their further papers) whose general results may well imply our lemma. \begin{lemma}\label{lem:5} Let $p\ge2$ and $b\ge1$ be integers. Let $x_n$ be the number of strings of $p$-ary digits of length $n$ which do not contain a block of $b$ consecutive digits all equal to $p-1$. Then, as $n$ tends to infinity, $$ x_n\sim c\cdot\o^n p^n, $$ for some $\o\in(0,1)$ and some positive constant $c$. \end{lemma} \begin{proof} The sequence $(x_n)$ forms a linear recurrent sequence with annihilating polynomial \begin{equation}\label{eq:12} P(X)=X^b-(p-1)X^{b-1}-(p-1)X^{b-2}-\cdots-(p-1). \end{equation} To see that $(x_n)$ is linear recurrent, we only consider the case $b=3$ as an example, but the reasoning may be carried out in all generality. We say that a string is {\it admissible} if it does not contain a block of three consecutive digits equal to $p-1$. Define $y_n$ as the number of length-$n$ admissible strings that end with two consecutive $p-1$ digits, $z_n$ as the number of length-$n$ admissible strings ending with only one $p-1$ digit and $t_n$ for those ending with a digit at most $p-2$. Then we readily see that for $n\ge2$, $z_n=t_{n-1}$ and $t_n=(p-1)x_{n-1}$. Consequently we see that for $n\ge3$ \begin{eqnarray*} x_{n+1}&=&(p-1)y_n+p(z_n+t_n)\\ &=&(p-1)(y_n+z_n+t_n)+(t_n+t_{n-1})\\ &=&(p-1)x_n+(p-1)x_{n-1}+(p-1)x_{n-2}. \end{eqnarray*} Noting that $x_i=p^i$ for $0\le i\le b-1$ and $x_b=p^b-1$, we see that the polynomial $P$ in (\ref{eq:12}) must be the characteristic polynomial of $(x_n)$, i.e., its minimal annihilating polynomial. Indeed suppose to the contrary that there is an $1\le s1$. Because $P$ is the characteristic polynomial of $(x_n)$, the closed-form expression of $x_n$ must contain a nonzero term in $\a^n$. Therefore, $x_n\sim c\a^n$, as $n$ tends to infinity, where $c$ is some positive constant that depends only on $p$ and $b$. Note that $P(x)$ is increasing for $x>p$. Indeed, the derivative $P'$ is positive, since for $x>p$ \begin{eqnarray*} P'(x)&=&bx^{b-1}-(p-1)\big((b-1)x^{b-2}+(b-2)x^{b-3}+\cdots+1\big)\\ &>&bx^{b-1}-(p-1)(b-1)(x^{b-2}+x^{b-3}+\cdots+1)\\ &=&bx^{b-1}-(p-1)(b-1)\frac{x^{b-1}-1}{x-1}\\ &>&bx^{b-1}-(b-1)(x^{b-1}-1)=x^{b-1}+b-1>0. \end{eqnarray*} Since $P(p)=1>0$, the polynomial $P$ has no zero larger than $p$. Thus, $\aa-1$, but $p^{\th-1}\le a-1$. If $n$ belongs to $C_{q+1$. Then $A_p$ splits into the two subsets $A_{p}^{ D/2$. For all $n$ in $A_p^x$, there is a unique $\l$ satisfying $(a-1)n+k=\l\rho p^x$. Thus, we get an upper estimate for $\#A_p^x(z)$ by bounding above the corresponding number of $\l$'s. Indeed, $$ \l\le\frac{(a-1)n+k}{\rho p^x}\le\frac{(a-1)z+k}{\rho p^{D/2}}\ll z^{1/2}, $$ as $z$ tends to infinity. Hence, $$ \sum_{D/20$, for all $n\ge2$. We did nothing more than concatenate in one table the data contained in the three tables \cite[Tables 1 and 3, pp.\ 78--79]{Bi}, \cite[p.\ 312]{Ab}, except for parametrizing the sequences in terms of $P$ and $Q$ rather than $P$ and $\D$. Semi-columns are used to separate different parametric families of $n$-defective sequences, while commas are used to specify constraints on the parameters. Parameters $i$ and $j$ are integers. The case $n=6$ has three lines. To alleviate the table we did not repeat at various lines that whenever a parametrization yields the sequence $I=U(2,1)$, it should be discarded. \begin{center} \begin{tabular} {|c|c|} \hline $n$ & $(P,\,Q)$,\quad $P>0$,\quad$(P,\,Q)\not=(2,\,1)$ \\ \hline & \\ \hline $2$ & $(1,\,Q),\;Q\not=-3;\qquad(2^i,\,2j+1),\;i\ge1$ \\ \hline $3$ & $(P,\,P^2\pm1);\qquad(P,\,P^2\pm3^i),\;3\nmid P$ \\ \hline $4$ & $\big(P,\,(P^2\pm1)/2\big),\;P\text{ odd};\qquad(2i,\,2i^2\pm1)$ \\ \hline $5$ & $(1,\,-1)\quad(1,\,2)\quad(1,\,3)\quad(1,\,4)\quad(2,\,11)\quad(12,\,55)\quad(12,\,377)$ \\ \hline & $\big(P,\,(P^2-1)/3\big),\;3\nmid P,\;P\ge4;\qquad\big(P,\,(P^2\pm3)/3\big),\;3\mid P;$ \\ $6$ & $\qquad\big(P,\,(P^2-(-2)^i)/3\big),\;P\equiv\pm1\pmod 6,\;i\ge1,\; (P,i)\not=(1,1);\qquad$ \\ & $\big(P,\,(P^2\pm3\cdot2^i)/3\big),\;P\equiv3\pmod 6,\;i\ge1$ \\ \hline $7$ & $(1,\,2)\quad(1,\,5)$ \\ \hline $8$ & $(1,\,2)\quad(2,\,7)$ \\ \hline $10$ & $(2,\,3)\quad(5,\,7)\quad(5,\,18)$ \\ \hline $12$ & $(1,\,-1)\quad(1,\,2)\quad(1,\,3)\quad(1,\,4)\quad(1,\,5)\quad(2,\,15)$ \\ \hline $13$ & $(1,\,2)$ \\ \hline $18$ & $(1,\,2)$ \\ \hline $30$ & $(1,\,2)$ \\ \hline \end{tabular} \smallskip \center{\rm{TABLE A.}} \center{List of all $n$-defective regular Lucas sequences $U(P,Q)$, $n\ge2$} \end{center} \section{Acknowledgments} We thank the referee for his fast return on a long paper and the referee and the editor-in-chief for their various inputs. We appreciated the remarks of J.-P. B\'ezivin on his reading of the former papers \cite{Ba4, Po}; Theorem \ref{thm:2bis} is derived from a remark of his. On a short private visit to Nicosia, Cyprus, last December, P. Damianou and E. Ieronymou kindly helped secure a fruitful office in the mathematics department for me. \begin{thebibliography}{99} \bibitem{Ab} M. Abouzaid, Les nombres de Lucas et Lehmer sans diviseur primitif, {\it J. Th\'eor. Nombres Bordeaux}, {\bf 18} (2006), 299--313. \bibitem{Ba1} C. Ballot, The congruence of Wolstenholme for generalized binomial coefficients related to Lucas sequences, {\it J. Integer Sequences}, {\bf 18} (2015) \href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Ballot/ballot14.html}{Article 15.5.4}. \bibitem{Ba2} C. Ballot, Divisibility of Fibonomials and Lucasnomials via a general Kummer rule, {\it Fibonacci Quart.}, {\bf 53} (2015) 194--205. \bibitem{Ba3} C. Ballot, On the constant in the average digit sum for a recurrence-based numeration, {\it Unif. Distrib. Theory}, {\bf 11} (2016), 125--150. \bibitem{Ba4} C. Ballot, Divisibility of the middle Lucasnomial coefficient, {\it Fibonacci Quart.}, {\bf 55} (2017) 297--308. \bibitem{Be1} A. Benjamin and S. Plott, A combinatorial approach to Fibonomial coefficients, {\it Fibonacci Quart.}, {\bf 46/47} (2008/09) 7--9. \bibitem{Be2} A. Benjamin and E. Reiland, Combinatorial proofs of Fibonomial identities, {\it Fibonacci Quart.}, Conference Proceedings, {\bf 52} (2014), no.~5, 28--34. \bibitem{Bi} Y. Bilu, G. Hanrot, P. M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers. With an appendix by M. Mignotte, {\it J. Reine Angew. Math.}, {\bf 539} (2001), 75--122. \bibitem{Ch} W. S. Chou, T. X. He and P. Shiue, On the Primality of the Generalized Fuss-Catalan Numbers, {\it J. Integer Sequences}, {\bf 21} (2018) \href{https://cs.uwaterloo.ca/journals/JIS/VOL21/He/he61.html}{Article 18.2.1}. \bibitem{Ed2} T. Edgar, Totienomial coefficients, {\it Integers}, {\bf 14} (2014), Paper A62. \bibitem{Ed} T. Edgar and M. Spivey, Multiplicative functions, generalized binomial coefficients, and generalized Catalan numbers, {\it J. Integer Sequences}, {\bf 19} (2016) \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Edgar/edgar3.html}{Article 16.1.6}. \bibitem{Ek} S. Ekhad, The Sagan-Savage Lucas-Catalan polynomials have positive coefficients. Preprint, January 21 2011. Available at \url{http://arxiv.org/abs/1101.4060}. \bibitem{Go1} H. W. Gould, Fibonomial Catalan numbers: arithmetic properties and a table of the first fifty numbers, Abstract 71T-A216, {\it Notices Amer. Math. Soc.}, (1971), 938. \bibitem{Go2} H. W. Gould, A new primality criterion of Mann and Shanks and its relation to a theorem of Hermite with extension to Fibonomials, {\it Fibonacci Quart.}, {\bf 10} (1972) 355--364, 372. \bibitem{GO} L. J. Guibas and A. M. Odlyzko, Long repetitive patterns in random sequences, {\it Z. Wahrsch. Verw. Gebiete}, {\bf 53} (1980), 241--262. \bibitem{HW} G. H. Hardy and E. M. Wright, \emph{An Introduction to the Theory of Numbers}, Fourth Edition, Oxford at the Clarendon Press, 1960. \bibitem{KW} D. Knuth and H. Wilf, The power of a prime that divides a generalized binomial coefficient, {\it J. Reine Angew. Math.}, {\bf 396} (1989), 212--219. \bibitem{Ku} E. Kummer, \"Uber die Erg\"anzungss\"atze zu den allgemeinen Reciprocit\"atsgesetzen, {\it J. Reine Angew. Math.}, {\bf 44} (1852), 93--146. \bibitem{LS} F. Luca and P. St\u anic\u a, Monotonic phinomial coefficients, {\it Bull. Aust. Math. Soc.}, {\bf 95} (2017), 365--372. \bibitem{Lu} \'E. Lucas, Th\'eorie des fonctions num\'eriques simplement p\'eriodiques, {\it Amer. J. Math.}, {\bf 1} (1878), 184--240, 289--321. \bibitem{My} G. Myerson, ed., with notes by K. Wooding, Western Number Theory Problems, 17 \& 19 December 2016. Available at \url{https://wcnt.files.wordpress.com/2017/09/wcnt-problems-2016.pdf}. \bibitem{Po} C. Pomerance, Divisibility of the middle binomial coefficient, {\it Amer. Math. Monthly}, {\bf 122} (2015), 636--644. \bibitem{Sa1} B. Sagan and C. Savage, Combinatorial interpretations of binomial coefficient analogues related to Lucas sequences, {\it Integers}, {\bf 10} (2010), A52, 697--703. \bibitem{Sa2} B. Sagan, Combinatorial interpretations of binomial coefficient analogues related to Lucas sequences, Part 5 of a Talk at Rutgers University videotaped by Edinah Gnang, December 9 2010, available at \url{http://www.youtube.com/watch?v=Fdn890jg2U0}. \bibitem{San} C. Sanna, Central binomial coefficients divisible by or coprime to their indices, {\it Int. J. Number Theory}, {\bf 14} (2018), 1135--1142. \bibitem{San2} C. Sanna, The $p$-adic valuation of Lucas sequences, {\it Fibonacci Quart.}, {\bf 54} (2016) 118--124. \bibitem{Sl} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Published electronically at \url{https://oeis.org}. \bibitem{St} R. P. Stanley, \emph{Catalan Numbers}, Cambridge University Press, New York, 2015. \bibitem{Su} B. Sury, Generalized Catalan numbers: linear recursion and divisibility, {\it J. Integer Sequences}, {\bf 12} (2009) \href{https://cs.uwaterloo.ca/journals/JIS/VOL12/Sury/sury31.html}{Article 09.7.5}. \bibitem{Ul} M. Ulas, A note on Erd\H{o}s-Straus and Erd\H{o}s-Graham divisibility problems (with an appendix by Andrzej Schinzel), {\it Int. J. Number Theory}, {\bf 9} (2013), 583--599. \bibitem{Wi} H. C. Williams, \emph{\'Edouard Lucas and Primality Testing}, Wiley, Canadian Math.\ Soc.\ Series of Monographs and Advanced Texts, 1998. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B83; Secondary 11B65, 11B39, 05A10. \noindent \emph{Keywords: } generalized binomial coefficient, Lucasnomial, generalized Fuss-Catalan number, Lobb number, ballot number, Lucas sequence, carry, Kummer's rule, asymptotic density, integrality, divisibility. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A001764}, \seqnum{A003150}, \seqnum{A014847}, \seqnum{A107920}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received March 6 2018; revised version received June 6 2018. Published in {\it Journal of Integer Sequences}, August 22 2018. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}