\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}}} \def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}} \DeclareMathOperator{\lcm}{lcm} \newcommand{\lphi}{\varphi} \newcommand{\N}{\mathbb{N}} \newcommand{\bth}{\begin{theorem}} \newcommand{\beq}{\begin{eqnarray*}} \newcommand{\eeq}{\end{eqnarray*}} \DeclareRobustCommand{\rs}{\genfrac\{\}{0pt}{}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\Large\bf On the Periodicity Problem for \\ \vskip .1in Residual $r$-Fubini Sequences } \vskip 1cm \large Amir Abbas Asgari\\ National Organization for Development of Exceptional Talents (NODET)\\ Tehran \\ Iran\\ \href{mailto:asgari@helli.ir}{\tt asgari@helli.ir}\\ \ \\ Majid Jahangiri\\ School of Mathematics \\ Department of Science\\ Shahid Rajaee Teacher Training University \\ P. O. Box 16785-163\\ Tehran \\ Iran\\ \href{mailto:jahangiri@ipm.ir}{\tt jahangiri@ipm.ir}\\ \end{center} \vskip .2 in \begin{abstract} For any positive integer $r$, the $r$-Fubini number with parameter $n$, denoted by $F_{n,r}$, is equal to the number of ways that the elements of a set with $n+r$ elements can be weakly ordered such that the $r$ least elements are in distinct orders. In this article we focus on the sequence of residues of the $r$-Fubini numbers modulo an arbitrary positive integer $s$ and show that this sequence is periodic and then, exhibit how to calculate its period length. \end{abstract} \section{Introduction} \textit{The Fubini numbers} (also known as the \textit{ordered Bell numbers}) form an integer sequence in which the $n$th term counts the number of weak orderings of a set with $n$ elements. Weak ordering means that the elements can be ordered, allowing ties. Cayley \cite{C} studied the Fubini numbers as the number of a certain kind of trees with $n+1$ terminal nodes. The Fubini numbers can also be defined as the sum of the \textit{Stirling numbers of the second kind}, $\rs{n}{k}$, which counts the number of partitions of an $n$-element set into $k$ non-empty subsets. The sequence of residues of the Fubini numbers modulo a positive integer $s$ was studied by Poonen \cite{P}. He showed that this sequence is periodic and calculated the period length for each positive integer $s$. \textit{The $r$-Stirling numbers of the second kind} are defined as an extension to the Stirling numbers of the second kind, in which the first $r$ elements contained in distinct subsets. Similarly the $r$-Fubini numbers, which are denoted by $F_{n,r}$, are defined as the number of ways which the elements of a set with $n+r$ elements can be weakly ordered such that the first $r$ elements are in distinct places. Consider the sequence of remainders of $F_{n,r}$ modulo an arbitrary number $s\in \mathbb{N}$ in which $r$ is fixed, which is denoted by $A_{r,s}$. One can study the periodicity problem for this sequence. Mez\H{o} \cite{M} investigated this problem for $s=10$. In this article $\omega(A_{r,s})$, the period of $A_{r,s}$, is computed for any positive integer $s$. Based on the fundamental theorem of arithmetic, $\omega(A_{r,p})$ is calculated for powers of odd primes $p^m$. The cases $s=2^m$ are studied separately. Therefore if $s=2^m p_{1}^{m_{1}} p_{1}^{m_{1}} \cdots p_{k}^{m_{k}}$ is the prime factorization, then the $\omega(A_{r,s})$ is equal to the least common multiple of $\omega(A_{r,p_i^{m_i}})$s and $\omega(A_{r,2^m})$, for $i=1,2,\ldots,k$. Section \ref{Basic concepts} contains the basic definitions and relations. The length of the periods in the case of odd prime powers are computed in the Section \ref{primes}. The similar results about the 2 powers are stated in the Section \ref{two}. The last section contains the final theorem which presents the conclusion of the article. \section{Basic concepts} \label{Basic concepts} Let $\rs{n}{k}$ be the Stirling number of the second kind with the parameters $n$ and $k$ and let $\rs{n}{k}_r$ be the $r$-Stirling number of the second kind with parameters $n$ and $k$. It is clear that $n \geq k \geq r$. Fubini numbers are computed as follows \cite{M}: \begin{align*} F_{n}=\sum_{k=0}^{n} k!\rs{n}{k}. \end{align*} In a similar way we can evaluate the $r$-Fubini number $F_{n,r}$ by \begin{align*} F_{n,r}=\sum_{k=0}^{n} (k+r)!\rs{n+r}{k+r}_{r}. \end{align*} There are simple relations and formulae about $\rs{n}{k}_{r}$ which are listed below. One can find a proof of them in \cite{B,M,MR} and \cite[Thm.\ 4.5.1, p.\ 158]{CC}. \begin{align} &\rs{n}{m}_{r}= \rs{n}{m}_{r-1}-(r-1)\rs{n-1}{m}_{r-1}, 1 \leq r \leq n \label{1}\\ &\rs{n}{m}_{1}= \rs{n}{m}\label{2}\\ &\rs{n+r}{r}_{r}= r^n\label{3}\\ &\rs{n+r}{r+1}_{r}= (r+1)^{n}-r^n\label{4}\\ &\rs{n}{m}= \frac{1}{m!}\sum_{j=1}^{m}(-1)^{m-j}\binom{m}{j}j^n\label{5}\\ &\rs{n}{m}_{r}=\frac{1}{m!}\sum_{j=r}^{m}(-1)^{m-j}\binom{m}{j}j^{n-(r-1)} \left(\frac{(j-1)!}{(j-r)!}\right). \end{align} By $\varphi(n)$ we indicate the number of positive integer numbers less than $n$ and co-prime to it. It is known as Euler's totient function. The value of $\varphi(n)$ can be computed via the following relation \cite[Example\ 4.7.3, p.\ 167]{CC}: \begin{align*} \varphi(n)=n\prod_{p \mid n}(1- \frac{1}{p}). \end{align*} \section{The $r$-Fubini residues modulo prime powers}\label{primes} Let $p$ be a prime number greater than 2 and $m$ be a positive integer. If $\left(F_{n,r}\right)$ denotes the sequence of $r$-Fubini numbers for a fixed positive integer $r$, we indicate by $A_{r,q}=\left( F_{n,r} (\bmod\ q) \right)$, for $n\in \mathbb{N}$, the sequence of residues of the $r$-Fubini numbers modulo the positive integer $q$. In this section we try to compute the period length of the sequence $A_{r,q}$ when $q=p^m$. This length is denoted by $\omega(A_{r,q})$. \begin{proposition} Let $p$ be an odd prime and let $q=p^m$, $m\in\N$. If $q \leq r$, then $\omega(A_{r,q})=1$. \end{proposition} \begin{proof} The proof is very simple. Since $p \leq r$, we can deduce that $p \mid (k+r)!$, for $k \geq 0$, and by the relation $F_{n,r}=\sum_{k=0}^{n}(k+r)!\rs{n+r}{k+r}_{r}$, we have $p \mid F_{n,r}$. Therefore $\omega(A_{r,p})=1$. \end{proof} As pointed out in the above proposition, it is sufficient to investigate the period length in the cases of $q>r$. \begin{lemma}\label{firstlem} Let $p$ be an odd prime and $r,m\in \mathbb{N}$ with $p \geq r+1$. Then \begin{align*} p^{m}-r \geq m. \end{align*} \end{lemma} \begin{proof} For $m=1$ the result is obvious. Suppose the inequality holds for any $m\geq 2$. Since $p(p+m) > 2(p+m) > 2p+m$, we have \begin{eqnarray} p^2+pm-p\geq p+m\label{6}. \end{eqnarray} Since $p-1 \geq r$, the induction hypothesis can be reformulated to $p^m\geq p-1+m$. Multiplication by $p$ results $p^{m+1}\geq p^2+pm-p$. By \eqref{6} we have $p^{m+1}\geq p+(m+1)-1$. \end{proof} \bth Let $p$ be an odd prime and $q=p^m$. After the $(m-1)$th term the sequence $A_{r,q}$ has a period with length $\omega(A_{r,q})=\lphi(q)$. In other words, $F_{n+\lphi(q),r} \equiv \modd{F_{n,r}} {q}$, for $n \geq m-1$. \end{theorem} \begin{proof} If $n \geq q-r-1$ we can write \begin{align*} F_{n+\lphi(q),r}- F_{n,r}=& \sum_{k=0}^{n+\lphi(q)}(k+r)!\rs{n+\lphi(q)+r}{k+r}_{r}-\sum_{k=0}^{n}(k+r)!\rs{n+r}{k+r}_{r}\\ & \equiv \sum_{k=0}^{q-r-1}(k+r)! \left(\rs{n+\lphi(q)+r}{k+r}_{r}-\rs{n+r}{k+r}_{r}\right)\\ & \equiv \sum_{k=0}^{q-r-1} \sum_{j=r}^{k+r}(-1)^{k+r-j} \binom{k+r}{j}j^{n+1} \left(\frac{(j-1)!}{(j-r)!}\right)(j^{\lphi (q)}-1) \pmod q. \end{align*} If $j=cp$, $c\in\N$, then $j^{n+1}=(cp)^{q-r+h}$, for some $h\geq 0$, so from Lemma \ref{firstlem} it follows that $j^{n+1}\equiv 0 \ (\bmod\ q)$. If $\gcd(j,q)=1$, by Euler's theorem $j^{\lphi(q)}-1\equiv 0 \ (\bmod\ q)$, so the right hand side of the above congruence relation vanished and we have \begin{align}\label{case1} F_{n+\lphi(q),r} & \equiv F_{n,r} \pmod q, \text{ for $n \geq q-r-1$}. \end{align} If $m-1 \leq n1$ we have \begin{eqnarray} 2^m-2 \geq m\ . \label{7} \end{eqnarray} This can be shown by using the relation $2^{m+1} \geq 2m+4 > m+3$, for $m>1$. The following lemma provides a simple but essential relation used in the next theorem. Its proof is provided in Appendix A. \begin{lemma}\label{appendix} For $m\geq 7$ and $5 \leq i \leq 2^{m-6}$ we have $2^{m-6}-i \mid 2^{i-5}\binom{2^{m-6}-1}{i}$. \end{lemma} \begin{theorem} \label{thm2fubini128} If $m \geq 7$, after the $(m-1)$th term, the sequence $A_{2,2^m}$ has a period with length $\omega(A_{2,2^m})=2^{m-6}$. \end{theorem} \begin{proof} In the case of $n \geq 2^m-3$, from \eqref{7} we can deduce that $n \geq 2^m-3 \geq m-1 $. So we have \begin{align*} F_{n+2^{m-6},2}- F_{n,2} & \equiv \sum_{k=0}^{n+2^{m-6}}(k+2)!\rs{n+2^{m-6}+2}{k+2}_{2}-\sum_{k=0}^{n}(k+2)!\rs{n+2}{k+2}_{2} \\ & \equiv \sum_{k=0}^{2^m-3}(k+2)!\left(\rs{n+2^{m-6}+2}{k+2}_{2}-\rs{n+2}{k+2}_{2}\right) \\ & \equiv \sum_{k=0}^{2^m-3}\sum_{j=2}^{k+2}(-1)^{k+2-j}\binom{k+2}{j}j^{n+1} (j^{2^{m-6}}-1) (j-1) \pmod {2^m}. \end{align*} When $j$ is even, then $j^{n+1}=(2c)^{2^m-2+h}$, for some $h \geq 0$. So by \eqref{7}, $2^m \mid j^{n+1}$. For odd $j$ we have \begin{align*} F_{n+2^{m-6},2}- F_{n,2} & \equiv \sum_{k=0}^{2^m-3}\sum_{l=1}^{\lfloor (k+1)/2 \rfloor}(-1)^{k+2-(2l+1)}\binom{k+2}{2l+1}(2l+1)^{n+1} ((2l+1)^{2^{m-6}}-1) \times 2l \\ & \equiv 2^{m-4}\sum_{k=0}^{2^m-3}(-1)^{k+1} \sum_{l=1}^{\lfloor (k+1)/2 \rfloor} \binom{k+2}{2l+1}(2l+1)^{n+1} \left(\frac{(2l+1)^{2^{m-6}}-1}{2^{m-5}}\right) l \\ & \equiv 2^{m-4}\sum_{k=0}^{2^m-3}(-1)^{k+1} \sum_{l=1}^{\lfloor (k+1)/2 \rfloor} \binom{k+2}{2l+1}(2l+1)^{n+1} \sum_{i=1}^{2^{m-6}}l^i2^{i-1} \left(\frac{(2^{m-6}-1)!}{i!(2^{m-6}-i)!}\right)\\ & \times l \pmod {2^m}. \end{align*} The last expression contains $m-4$ factors of 2, so it is sufficient to prove that the last summation is divisible by 16. This summation is denoted by $\mathcal{S}$. Simplify the summation $\sum_{i=1}^{2^{m-6}}l^i2^{i-1}\frac{(2^{m-6}-1)!}{i!(2^{m-6}-i)!}$ and using Lemma \ref{appendix} gives \begin{align*} & \sum_{i=1}^{2^{m-6}} l^i 2^{i-1} \left(\frac{(2^{m-6}-1)!}{i!(2^{m-6}-i)!}\right) \equiv \sum_{i=1}^{4}l^i2^{i-1} \left(\frac{(2^{m-6}-1)!}{i!(2^{m-6}-i)!}\right) \equiv l+ l^2(2^{m-6}-1)\\ & +\frac{l^3\times 2(2^{m-6}-1)(2^{m-6}-2)}{3} + \frac{l^4(2^{m-6}-1)(2^{m-6}-2)(2^{m-6}-3)}{3} \pmod {16}. \end{align*} Assume $m \geq 10$ (the case $7 \leq m \leq 9$ is studied at the end of the proof). So $16 \mid 2^{m-6}$. Let $3a= 2(2^{m-6}-1)(2^{m-6}-2)$ and $3b= (2^{m-6}-1)(2^{m-6}-2)(2^{m-6}-3)$. Then $3a \equiv 4$ (mod 16) and $3b \equiv -6$ (mod 16). Therefore $a \equiv -4$ (mod 16) and $b \equiv -2$ (mod 16). So the proof continues as follows: \begin{align*} \mathcal S & \equiv \sum_{k=0}^{2^m-3}(-1)^{k+1}\left(\sum_{l=1}^{\lfloor (k+1)/2 \rfloor} \binom{k+2}{2l+1}(2l+1)^{n+1} (l-l^2-4l^3-2l^4) l \right) \pmod {16}\\ \mathcal S & \equiv \sum_{k=0}^{2^m-3}(-1)^{k+1} \sum_{l=1}^{\lfloor (k+1)/2 \rfloor} \binom{k+2}{2l+1}(2l+1)^{n+1} \left( \frac{l(l+1)}{2} \right) (-2l^2-2l+1) l \pmod 8. \end{align*} Let $P(l)$ and $A(k,r,n)$ be the remainder of $\frac{1}{2}(2l+1)^{n+1} (l(l+1)) (-2l^2-2l+1) l$ and $\sum_{l=-\infty}^{\infty}\binom{k+2}{2l+r}P(l)$ divided by 8, respectively. By Pascal's identity, we have $\binom{k+2}{2l+r}=\binom{k+1}{2l+r}+\binom{k+1}{2l+r-1}$ and therefore \begin{align*} \sum_{l=-\infty}^{\infty}\binom{k+2}{2l+r}P(l)=\sum_{l=-\infty}^{\infty}\binom{k+1}{2l+r}P(l)+ \sum_{l=-\infty}^{\infty}\binom{k+1}{2l+r-1}P(l), \end{align*} so \begin{eqnarray}\label{11} A(k,r,n)=A(k-1,r,n)+A(k-1,r-1,n). \end{eqnarray} We can write \begin{align*} A(k,r+32,n)\equiv \sum_{l=-\infty}^{\infty}\binom{k+2}{2l+r+32}P(l) \pmod 8. \end{align*} The sequence $\left(P(l)\right)_{l=-\infty}^{\infty}$ has period 16, so $P(l+16)=P(l)$. Set $l'=l+16$, then \begin{eqnarray}\label{12} A(k,r+32,n)\equiv\sum_{l'=-\infty}^{\infty}\binom{k+2}{2l'+r}P(l') \equiv A(k,r,n) \pmod 8. \end{eqnarray} Since $\gcd(2l+1,16)=1$, Euler's theorem implies $(2l+1)^{8} \equiv 1 \ (\bmod\ 16)$ and therefore $(2l+1)^{n+1+8} \equiv (2l+1)^{n+1} $ (mod 16). The quantity $A(6,r,n)$ vanishes for $1\leq r \leq 32$ and $9 \leq n \leq 24$, by enumeration, then by \eqref{11} and \eqref{12}, we deduce that \begin{eqnarray} \label{13} A(k,r,n)=0, \text{ for } k\geq 6. \end{eqnarray} Therefore \begin{align*} A(k,1,n) & \equiv \sum_{l=-\infty}^{\infty}\binom{k+2}{2l+1}(2l+1)^{n+1} \left(\frac{l(l+1)}{2}\right) (-2l^2-2l+1) l \\ & \equiv \sum_{l=1}^{\lfloor (k+1)/2 \rfloor}\binom{k+2}{2l+1}(2l+1)^{n+1} \left(\frac{l(l+1)}{2}\right) (-2l^2-2l+1) l \equiv 0 \pmod 8, \end{align*} for $k\geq 6$. If $1 \leq k \leq 5$, $9 \leq n \leq 24$ and $1 \leq r \leq 32$ we have $\sum_{k=1}^{5}(-1)^{k+1}A(k,r,n) \equiv 0\ (\bmod\ 8)$. The period length of $A(k,r,n)$ with respect to $r$ and $n$ implies that \beq \sum_{k=1}^{5}(-1)^{k+1}A(k,1,n) \equiv 0\ (\bmod\ 8), \text{ for } n \geq 9. \eeq Combining this with \eqref{13} we have \begin{align*} \mathcal S\equiv \sum_{k=1}^{2^m-3}(-1)^{k+1}A(k,1,n)\equiv 0 \pmod 8, \text{ for } n \geq 0. \end{align*} So the result follows in the case of $n\geq 2^m-3$. If $m-1 \leq n <2^m-3$ we can write \begin{align*} F_{n+2^{m-6},2} - F_{n,2} & = \sum_{k=0}^{n+2^{m-6}}(k+2)!\rs{n+2^{m-6}+2}{k+2}_{2}-\sum_{k=0}^{n}(k+2)!\rs{n+2}{k+2}_{2} \\ & = \sum_{k=0}^{2^m-3}(k+2)! \left(\rs{n+2^{m-6}+2}{k+2}_{2}-\rs{n+2}{k+2}_{2}\right)\\ & - \sum_{k=n+2^{m-6}+1}^{2^m-3}(k+2)!\rs{n+2^{m-6}+2}{k+2}_{2}+\sum_{k=n+1}^{2^m-3}(k+2)!\rs{n+2}{k+2}_{2}\\ & \equiv \sum_{k=0}^{2^m-3}\sum_{j=1}^{k+2}(-1)^{k+2-j} \binom{k+2}{j} j^{n+1} (j^{2^{m-6}}-1) (j-1) \pmod {2^m}. \end{align*} When $j$ is even, then $j^{n+1}=(2c)^{m+h}$, for some $h \geq 0$, so $2^m \mid j^{n+1}$. Since $m\geq 10$, for odd $j$ we have \begin{align*} & \sum_{k=0}^{2^m-3}\sum_{j=1}^{k+2} (-1)^{k+2-j}\binom{k+2}{j}j^{n+1} (j^{2^{m-6}}-1)(j-1)\\ & \equiv 2^{m-4}\sum_{k=0}^{2^m-3}(-1)^{k+1} \sum_{l=1}^{\lfloor (k+1)/2 \rfloor} \binom{k+2}{2l+1}(2l+1)^{n+1} (l -l^2-4l^3-2l^4) l \pmod {2^m}. \end{align*} The last summation is exactly the $\mathcal S$ and the proof will be similar as above. Combine with the previous case we have the following congruence relation \begin{eqnarray} \label{14} F_{n+2^{m-6},2} \equiv F_{n,2} \pmod {2^m}, \text{ for } m \geq 10. \end{eqnarray} In the case where $7 \leq m \leq 9$, the remainder value of the sum \beq \sum_{k=0}^{2^m-3}(-1)^{k+1} \sum_{l=1}^{\lfloor (k+1)/2 \rfloor} \binom{k+2}{2l+1} (2l+1)^{n+1} \left(\sum_{i=1}^{4}l^i2^{i-1}\frac{(2^{m-6}-1)!}{i!(2^{m-6}-i)!}\right) l \eeq modulo 16 is computed for $m-1 \leq n \leq m+14$. Divisibility of all these values by $16$ implies that the recent sum is divisible by $16$, and therefore \begin{eqnarray} \label{15} F_{n+2^{m-6},2} \equiv F_{n,2} \pmod {2^m}, \text{ for } 7 \leq m \leq 9. \end{eqnarray} Summing up the congruence relations \eqref{14} and \eqref{15} gives \begin{align*} \omega(A_{2,2^m})=2^{m-6}, \text{ for } m \geq 7. \end{align*} \end{proof} \bth \label{thmrfubini4,8} For $m=1$ and $m=2$, the sequence $A_{r,2^m}$ is periodic from the first term and the period length is $\omega({A_{r,2^m}})=1$. \end{theorem} \begin{proof} The proof of this theorem is divided into three cases. For $r=2$ we have \begin{align*} F_{n+1,2} - F_{n,2}& = \sum_{k=0}^{n+1}(k+2)!\rs{n+3}{k+2}_{2}-\sum_{k=0}^{n}(k+2)!\rs{n+2}{k+2}_{2}\\ & \equiv 2\left(\rs{n+3}{2}_{2}-\rs{n+2}{2}_{2}\right)+6\left(\rs{n+3}{3}_{2}-\rs{n+2}{3}_{2}\right)\pmod 4\\ &= 2\left(2^{n+1}-2^n\right)+6\left(3^{n+1}-2^{n+1}-(3^n-2^n)\right)\\ &= 2^{n+1}+6(2 \times 3^n-2^n)=4(2^{n-1}+3^{n+1}-3\times 2^{n-1})\\ &= 4(3^{n+1}-2^n) \equiv 0\ (\bmod\ 4). \end{align*} So we can deduce that $\omega(A_{2,4})=1$ and obviously $\omega(A_{2,2})=1$. For $r=3$ we can write \begin{align*} F_{n+1,3}-F_{n,3}= & \sum_{k=0}^{n+1}(k+3)!\rs{n+4}{k+3}_{3}-\sum_{k=0}^{n}(k+3)!\rs{n+3}{k+3}_{3}\\ & \equiv 6\left(\rs{n+4}{3}_{3}-\rs{n+3}{3}_{3}\right) \pmod 4\\ = & 6\left(3^{n+1}-3^n\right)=6 \times 2 \times 3^n=4 \times 3^{n+1} \equiv 0\ (\bmod\ 4). \end{align*} Therefore we have $\omega(A_{3,4})=1$ and $\omega(A_{3,2})=1$. Finally if $r \geq 4$, let $r=4+h$, for some $h \geq 0$, then \begin{align*} F_{n+1,r}-F_{n,r}= & \sum_{k=0}^{n+1}(k+r)!\rs{n+1+r}{k+r}_{r}-\sum_{k=0}^{n}(k+r)!\rs{n+r}{k+r}_{r}. \end{align*} Since $4 \mid (k+r)!$, for all $k \geq 0$, we can write $F_{n+1,r}-F_{n,r} \equiv 0\ (\bmod\ 4)$. Therefore $\omega(A_{r,4})=1$ and $\omega(A_{r,2})=1$. \end{proof} \bth \label{thmrfubini8to64} If $3 \leq m \leq 6$, after the $(m-1)$th term, the sequence $A_{r,2^m}$ has a period with length $\omega(A_{r,2^m})=2$. \end{theorem} \begin{proof} The proof of this theorem is similar to the proof of Theorem \ref{thm2fubini8to64}. It is enough to prove the theorem for $m=6$; then the result follows for $m=3,4$ and 5. Since $n\geq m-1$, then for $m=6$ we have $n \geq 5$. For $3 \leq r \leq 7$ we have \begin{align*} F_{n+2,r} - F_{n,r} & = \sum_{k=0}^{n+2}(k+r)!\rs{n+2+r}{k+r}_{r}-\sum_{k=0}^{n}(k+r)!\rs{n+r}{k+r}_{r}\\ & \equiv \sum_{k=0}^{7-r}\sum_{j=r}^{k+r}(-1)^{k+r-j}\binom{k+r}{j} j^{n+1} (j^2-1) \left(\frac{(j-1)!}{(j-r)!}\right) \\ & \equiv \sum_{k=0}^{7-r}\sum_{j=r}^{k+r}(-1)^{k+r-j}\binom{k+r}{j}j^{n+1} (j^2-1) (j-1) \left(\frac{(j-2)!}{(j-r)!}\right) \pmod {64}. \end{align*} When $j$ is even, then $j^{n+1}=(2c)^{6+h}$, for some $h \geq 0$, and so $64 \mid j^{n+1}$. For odd $j$ we have $\gcd(j,64)=1$ and Euler's theorem gives $j^{32} \equiv 1\ (\bmod\ 64)$. Therefore $j^{n+1+32} \equiv j^{n+1}$ (mod 64), and we can write \begin{align*} & \sum_{k=0}^{7-r}\sum_{j=r}^{k+r} (-1)^{k+r-j} \binom{k+r}{j}j^{n+1} (j^2-1) (j-1) \frac{(j-2)!}{(j-r)!} \\ &\equiv \sum_{k=0}^{7-r}\sum_{l=\lfloor r/2 \rfloor}^{\lfloor (k+r-1)/2 \rfloor}(-1)^{k+r-(2l+1)} \binom{k+r}{2l+1} (2l+1)^{n+1} ((2l+1)^2-1) \times 2l \left(\frac{(2l-1)!}{(2l+1-r)!}\right) \\ & \equiv 16\sum_{k=0}^{7-r}(-1)^{k+r-1}\sum_{l=\lfloor r/2 \rfloor}^{\lfloor (k+r-1)/2 \rfloor} \binom{k+r}{2l+1} (2l+1)^{n+1} \left(\frac{l(l+1)}{2}\right) l \left(\frac{(2l-1)!}{(2l+1-r)!}\right) \pmod {64}. \end{align*} By computation we see that the recent summation is divisible by 4, for $2\leq n \leq 33$. So the proof for $3 \leq r \leq 7$ is completed. If $r \geq 8$, since $64 \mid 8!$, then $64 \mid (k+r)!$, and \begin{align*} F_{n+2,r}-F_{n,r} =\sum_{k=0}^{n+2}(k+r)!\rs{n+2+r}{k+r}_{r}-\sum_{k=0}^{n}(k+r)!\rs{n+r}{k+r}_{r} \equiv 0\ (\bmod\ 64), \end{align*} so $\omega(A_{r,2^6})=2$, for $r \geq 8$, and the proof is completed. \end{proof} \bth \label{thmrfubini128} If $m \geq 7$, after the $(m-1)$th term, the sequence $A_{r,2^m}$ has a period with length $\omega(A_{r,2^m})=2^{m-6}$. \end{theorem} \begin{proof} The proof of this theorem is similar to the proof of Theorem \ref{thm2fubini128}. In the case of $n \geq 2^m-r-1$ and $r \geq 8$ we have \begin{align*} F_{n+2^{m-6},r}- F_{n,r} & = \sum_{k=0}^{n+2^{m-6}}(k+r)!\rs{n+2^{m-6}+r}{k+r}_{r}-\sum_{k=0}^{n}(k+r)!\rs{n+r}{k+r}_{r}\\ &\equiv \sum_{k=0}^{2^m-r-1} (k+r)!\left(\rs{n+2^{m-6}+r}{k+r}_{r}-\rs{n+r}{k+r}_{r}\right)\\ &\equiv \sum_{k=0}^{2^m-r-1} \sum_{j=r}^{k+r} (-1)^{k+r-j}\binom{k+r}{j} j^{n+1} (j^{2^{m-6}}-1) \left(\frac{(j-1)!}{(j-r)!}\right) \pmod {2^m}. \end{align*} In the case of $2^m > r > 2^m-m$, since $m\geq 7$ this implies that $r>2^m-m\geq 2^{m-1}$, so \beq 2^m \mid (2^{m-1})! \mid (k+r)!, \text{ for each } k\geq 0. \eeq Therefore both summations in the above first equation are zero modulo $2^m$ and in this case $\omega(A_{r,2^m})=2^{m-6}$. When $r \leq 2^m -m$, if $j$ is even then $j^{n+1}=(2c)^{2^m-r+h}$, for some $h \geq 0$. So $2^m \mid j^{n+1}$. For odd $j$ we have $(j,2^{m-5})=1$, and $2^{m-5} \mid j^{2^{m-6}}-1$ by Euler's theorem. Since $r \geq 8$ we can write $\frac{(j-1)!}{(j-r)!}= \left(\frac{(j-8)!}{(j-r)!} \right) \prod_{i=1}^{7} (j-i)$. Therefore $32 \mid \frac{(j-1)!}{(j-r)!}$ and $2^m \mid (j^{2^{m-6}}-1)\left(\frac{(j-1)!}{(j-r)!} \right)$. In the case of $m-1 \leq n < 2^m-r-1$ and $r \geq 8$ we have \begin{align*} F_{n+2^{m-6},r}-F_{n,r} &= \sum_{k=0}^{n+2^{m-6}}(k+r)!\rs{n+2^{m-6}+r}{k+r}_{r}-\sum_{k=0}^{n}(k+r)!\rs{n+r}{k+r}_{r}\\ & \equiv \sum_{k=0}^{2^m-r-1}(k+r)!\left(\rs{n+2^{m-6}+r}{k+r}_{r}-\rs{n+r}{k+r}_{r}\right)\\ & - \sum_{k=n+2^{m-6}+1}^{2^m-r-1}(k+r)!\rs{n+2^{m-6}+r}{k+r} + \sum_{k=n+1}^{2^m-r-1}(k+r)!\rs{n+r}{k+r} \pmod {2^m}\\ & =\sum_{k=0}^{2^m-r-1}(k+r)!\left(\rs{n+2^{m-6}+r}{k+r}_{r}-\rs{n+r}{k+r}_{r}\right) + 0, \end{align*} and the proof proceeds as in the previous case. In the case of $3 \leq r \leq 7$ one can deduce similarly to the proof of Theorem \ref{thm2fubini128} that \begin{align*} F_{n+2^{m-6},r}-F_{n,r} \equiv \sum_{k=0}^{2^m-r-1}\sum_{j=r}^{k+r}(-1)^{k+r-j}\binom{k+r}{j} j^{n+1} (j^{2^{m-6}}-1) \left(\frac{(j-1)!}{(j-r)!}\right) \pmod {2^m}. \end{align*} Exactly the same as Theorem \ref{thm2fubini128}, the terms with even $j$ vanish and only the terms with odd $j$ remain. So we have \begin{align*} F_{n+2^{m-6},r}- F_{n,r} & \equiv \sum_{k=0}^{2^m-r-1} \sum_{l=\lfloor r/2 \rfloor}^{\lfloor (k+r-1)/2 \rfloor}(-1)^{k+r-(2l+1)} \binom{k+r}{2l+1} (2l+1)^{n+1} ((2l+1)^{2^{m-6}}-1) \\ & \times \left(\frac{((2l+1)-1)!}{((2l+1)-r)!}\right)\\ & \equiv 2^{m-5} \sum_{k=0}^{2^m-r-1}(-1)^{k+r-1} \sum_{l=\lfloor r/2 \rfloor}^{\lfloor (k+r-1)/2 \rfloor} \binom{k+r}{2l+1} (2l+1)^{n+1} \\ & \times \left(\sum_{i=1}^{2^{m-6}}l^i2^{i-1} \left(\frac{(2^{m-6}-1)!}{i!(2^{m-6}-i)!}\right)\right) \left(\frac{(2l)!}{(2l-r+1)!}\right) \pmod {2^m}. \end{align*} Since $\gcd(2l+1,16)=1$, Euler's theorem shows that $(2l+1)^{n+1+8} \equiv (2l+1)^{n+1}$ (mod 16). If $m \geq 10$, we have \begin{align*} F_{n+2^{m-6},r} - F_{n,r} & \equiv 2^{m-4}\sum_{k=0}^{2^m-r-1}(-1)^{k+r-1} \sum_{l=\lfloor r/2 \rfloor}^{\lfloor (k+r-1)/2 \rfloor} \binom{k+r}{2l+1} (2l+1)^{n+1} \left(\frac{l(l+1)}{2}\right)\\ & \times (-2l^2-2l+1)\left(\frac{(2l)!}{(2l-r+1)!}\right) \pmod {2^m}. \end{align*} Therefore it is sufficient to compute the above summation (without factor $2^{m-4}$) for $3 \leq r \leq 7$ and $9 \leq n \leq 16$ to show that it is divisible by 16. For $7 \leq m \leq 9$ we evaluate the sum \begin{align*} \sum_{k=0}^{2^m-r-1}(-1)^{k+r-1} \sum_{l=\lfloor r/2 \rfloor}^{\lfloor (k+r-1)/2 \rfloor} \binom{k+r}{2l+1} (2l+1)^{n+1} \sum_{i=1}^{2^{m-6}}l^i2^{i-1}\frac{(2^{m-6}-1)!}{i!(2^{m-6}-i)!} \left(\frac{(2l)!}{(2l-r+1)!}\right) \end{align*} for $m-1 \leq n \leq m+6$ to show that it is divisible by 32. Then it follows that $\omega(A_{r,2^m})=2^{m-6}$, for all $m \geq 7$. \end{proof} \section{The conclusion} We now state the final theorem, which shows how to compute $\omega(A_{r,s})$ for any $s \in \mathbb{N}$. \bth Let $s \in \mathbb{N}$ and $s>1$ with the prime factorization $s=2^{m}p_1^{{m}_1}p_2^{{m}_2} \cdots p_k^{{m}_k}$ and let $D=\{ p_{i}^{m_{i}} \mid p_{i}^{m_{i}}>r, 1\leq i \leq k \}$. Define $E=\{ m_{i}-1 \mid p_{i}^{m_{i}} \in D \}$, $F=\{ \varphi(p_{i}^{m_{i}}) \mid p_{i}^{m_{i}} \in D \}$ and $a=\max(E \cup \{m-1\})$ and let $b$ be the least common multiple $(\lcm)$ of the elements of $F$. Then \begin{eqnarray} \label{final} \omega(A_{r,s}) = \begin{cases} b, & \text{if $0 \leq m \leq 2$ or $2^m \leq r$;}\\ \lcm(2,b), & \text{if $3 \leq m \leq 6$ and $2^m > r$ ;}\\ \lcm(2^{m-6},b), & \text{if $m \geq 7$ and $2^m > r$,} \end{cases} \end{eqnarray} and periodicity of the sequence $A_{r,s}$ is seen after the $a$-th term. \end{theorem} \begin{proof} Let $l$ be the right hand side of \eqref{final}. For each $d \in D \cup \{2^m\}$, $\omega(A_{r,d}) \mid l$ and for each $p_{j}^{m_{j}} \not\in D$ such that $1\leq j \leq k$, we have $1=\omega(A_{r,p_j^{m_j}}) \mid l$, so \begin{align*} F_{n+l,r} &\equiv F_{n,r} \pmod {2^m}\\ F_{n+l,r} &\equiv F_{n,r} \pmod {p_{i}^{m_i}}, \text{ for } i=1,2,\ldots,k. \end{align*} Since $\gcd(2^m,p_1^{m_1},p_2^{m_2},\ldots,p_k^{m_k})=1$, the multiplication of all above congruence relations gives the required result. \end{proof} \section{Acknowledgments} The authors would like to thank the anonymous referee for his/her valuable comments and guides. \begin{appendix} \section{Proof of Lemma \ref{appendix}} After simplifying the lemma's relation we have \begin{eqnarray}\label{factorial} \frac{2^{i-5}\binom{2^{m-6}-1}{i}}{2^{m-6}-i}=\frac{2^{i-5}(2^{m-6}-1)(2^{m-6}-2)\cdots(2^{m-6}-i+1)}{i!}. \end{eqnarray} It is sufficient to show that the right hand side of \eqref{factorial} is integer. We know that $\binom{2^{m-6}}{i} \in \N$, i.e., \begin{eqnarray*} i! \mid 2^{m-6}(2^{m-6}-1)\cdots (2^{m-6}-i+1). \end{eqnarray*} If $O_i$ denotes the product of the odd factors of $i!$, since $(O_i,2^{m-6})=1$, then $O_i \mid (2^{m-6}-1)\cdots (2^{m-6}-i+1)$. So in \eqref{factorial} we only need to prove that \begin{align*} \nu_2 (2^{i-5}(2^{m-6}-1)(2^{m-6}-2)\cdots(2^{m-6}-i+1)) \geq \nu_2 (i!), \end{align*} where by $\nu_2(x)$ we mean that $2^{\nu_2(x)}\mid x$, but $2^{\nu_2(x)+1} \nmid x$. Let $A=\nu_2 ((2^{m-6}-1)(2^{m-6}-2) \cdots (2^{m-6}-i+1))$ and $B=\nu_2 (i!)$. Let $e$ be the unique integer such that $2^e\leq i < 2^{e+1}$. So \begin{align}\label{def} A=\sum_{k=1}^{e} \lfloor \frac{i-1}{2^k} \rfloor, \hskip 0.5 cm B=\sum_{k=1}^{e} \lfloor \frac{i}{2^k} \rfloor. \end{align} If we show that \begin{eqnarray}\label{claim} B-A\leq e \end{eqnarray} then the lemma is concluded if it is proved that \begin{eqnarray}\label{conclusion} i+A \geq B+5. \end{eqnarray} It can easily be shown that $B=\nu_2 (i!)$ and $A=\nu_2 ((i-1)!)$, so $B-A=\nu_2 (i)$. Since $2^e \leq i < 2^{e+1}$, therefore $\nu_2 (i) \leq e$ and \eqref{claim} follows. For $e=2$, integer possibilities for inequality \eqref{conclusion} are as follows: \begin{center} \makebox[12cm]{ \begin{tabular}[b]{c|c|c} $i$ & $A$ & $B$\\ \cline{1-3} 5 & 3 & 3 \\ \cline{1-3} 6 & 3 & 4 \\ \cline{1-3} 7 & 4 & 4 \\ \end{tabular} } \end{center} For $e \geq 3$ one can deduce by simple induction that \begin{align*} 2^e\geq e+5, \end{align*} so $i\geq 2^e \geq e+5$. Add $B-e$ to these inequalities and use \eqref{claim} demonstrates \eqref{conclusion} for $i\geq 8$. \end{appendix} \begin{thebibliography}{9} \bibitem{B} A. Z. Broder, The $r$-Stirling numbers, {\em Discrete Math.} {\bf 49} (1984), 241--259. \bibitem{C} A. Cayley, On the analytical forms called trees, {\em Amer. J. Math.} {\bf 4} (1881), 266--268. \bibitem{CC} C. Chuan-Chong and K. Khee-Meng, {\em Principles and Techniques in Combinatorics}, World Scientific, 1992. \bibitem{M} I. Mez\H{o}, Periodicity of the last digits of some combinatorial sequences, {\em J. Integer Sequences} {\bf 17} (2014), \href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Mezo/mezo19.html}{Article 14.1.1}. \bibitem{MR} I. Mez\H{o} and J. L. Ram\'irez, Some identities of the $r$-Whitney numbers, {\em Aequationes Math.} {\bf 90} (2016), 393--406. \bibitem{P} B. Poonen, Periodicity of a combinatorial sequence, {\em Fibonacci Quart.} {\bf 26} (1988), 70--76. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B50; Secondary 11B75, 05A10, 11B73, 11Y55. \noindent \emph{Keywords:} residue modulo prime power factors, $r$-Fubini number, $r$-Stirling number of the second kind, periodic sequence. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000670}, \seqnum{A008277}, \seqnum{A143494}, \seqnum{A143495}, \seqnum{A143496}, \seqnum{A232472}, \seqnum{A232473}, and \seqnum{A232474}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received March 18 2017; revised version received April 16 2017; April 1 2018; April 12 2018; April 21 2018. Published in {\it Journal of Integer Sequences}, May 8 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}