Derivative with two fractional orders: New door of investigation toward
revolution in fractional calculus

Abdon Atangana

Institute for Groundwater studies, Faculty of Natural and Agricultural
Sciences, University of the Free State, 9300, South Africa,

email<EMAIL_ADDRESS>

Abstract: In order to describe more complex problem using the concept of
fractional derivative, we introduce in this paper a derivative with two
fractional orders. Each order therefore plays an important rule while modeling
for instance problems with two layers with different properties. This is the
case for instance in thermal science for a reaction diffusion within a media
with two different layers with different properties. Another case of this
study can be used in the study of groundwater flowing with an aquifer where
the ground has layers with different properties. The paper presents some basic
definitions and properties.

Keywords: New concept of fractional derivative, bi-order, generalized Mittag-
Leffler function.

##  1 Introduction

The concept of fractional calculus was introduced by mathematicians to solve
problems that could not be handled by local derivative, the fractional order
alpha that appears in the concept of fractional derivative can be used to
represent some physical parameters. Nevertheless it is not possible for the
fractional derivative to be used in order to describe the movement of for
instance heat via material with different layers where each layer possesses
different material from each other. Riemann-Liouville introduced the
fractional derivative as a derivative with convolution of a given function and
the power law function [1-5]. Caputo introduced the fractional derivative as
convolution of derivative of a given function with power law function. Caputo
and Fabrizio introduced the fractional derivative as convolution of derivative
of a given function with exponential [2-4]. Atangana and Goufo independently
with Caputo and Fabrizio introduced another one as derivative of a convolution
of a given function with the exponential function. Atangana and Dumitru
introduced fractional derivative as a both convolution of a derivative of a
given function and the Mittag-Leffler function [4-5]. These concepts of
fractional derivative so far has been used with great success and misused
also. Nevertheless they are not able to handle the concept of heterogeneity
with great success. The concept of Brownian motion was introduced using
fractional derivative to describe to choice that a particle has when moving
via heterogeneous media, however, this concept failed due to the fact that,
the particle does not chose where to move within a given heterogeneous media,
but it condition by the properties of the media [6-7]. For instance, the drop
of water is moving via a given geological formation under the influence of the
properties of the soul. It is therefore important to introduce a suitable
derivative that can used to handle this type of physical problem. In this
paper, we introduce the concept of fractional order with two orders alpha and
beta.

##  2 New concept of fractional derivatives

In this section, some new definitions of fractional derivatives with bi-order
are presented.

Definition 1 : Let $f(x)$ defined in $[a,X]$ necessary differentiable such
that for all $x\in[a,X]$ the convolution of
$x^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}x^{\beta+\alpha}\right\\}$
with the function $\frac{d^{n}f(x)}{dx^{n}}$ exists, then the fractional
derivative of the function $f$ with order $\alpha,\beta\in(0,1)$ is given as:

${}_{a}^{AC}D_{x}^{\alpha,\beta}f(x)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{a}^{x}\frac{d^{n}f(t)}{dt^{n}}(x-t)^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-t)^{\beta+\alpha}\right\\}dt,$
$\displaystyle 0$ $\displaystyle<$ $\displaystyle\beta<1,\text{ \ \
}n-1<\alpha<n.$

Definition 2 : Let $f(x)$ defined in $[a,X]$ not necessary differentiable such
that for all $x\in[a,X]$ the convolution of
$x^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}x^{\beta+\alpha}\right\\}$
with the function $f(x)$ exists, then the fractional derivative of the
function $f$ with order $\alpha,\beta\in(0,1)$ is given as:

${}_{a}^{AR}D_{x}^{\alpha,\beta}f(x)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\frac{d^{n}}{dx^{n}}\int\limits_{a}^{x}f(t)(x-t)^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-t)^{\beta+\alpha}\right\\}dt,$
$\displaystyle 0$ $\displaystyle<$ $\displaystyle\beta<1,\text{ \ \
}n-1<\alpha<n.$

Definition 3 : Let $f(x)$ defined in $[X,\infty]$ not necessary differentiable
such that for all $x\in[0,\infty]$ the convolution of
$x^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}x^{\beta+\alpha}\right\\}$
with the function $\frac{d^{n}f(x)}{dx^{n}}$ exists, then the fractional
derivative of the function $f$ with order $\alpha,\beta\in(0,1)$ is given as:

${}_{a}^{AR}D_{x}^{\alpha,\beta}f(x)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\frac{d^{n}}{dx^{n}}\int\limits_{x}^{\infty}f(t)(t-x)^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-t)^{\beta+\alpha}\right\\}dt,$
$\displaystyle 0$ $\displaystyle<$ $\displaystyle\beta<1,\text{ \ \
}n-1<\alpha<n.$ (3)

Definition 4 : Let $f(x)$ defined in $[X,\infty]$ necessary differentiable
such that for all $x\in[0,\infty]$ the convolution of
$x^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}x^{\beta+\alpha}\right\\}$
with the function $f(x)$ exists, then the fractional derivative of the
function $f$ with order $\alpha,\beta\in(0,1)$ is given as:

${}_{a}^{AC}D_{x}^{\alpha,\beta}f(x)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{x}^{\infty}\frac{d^{n}f(t)}{dt^{n}}(t-x)^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-t)^{\beta+\alpha}\right\\}dt,$
$\displaystyle 0$ $\displaystyle<$ $\displaystyle\beta<1,\text{ \ \
}n-1<\alpha<n.$

Definition 5 : Let $f(x)$ defined in $[-\infty,X]$ not necessary
differentiable such that for all $x\in[-\infty,X]$ the convolution of
$x^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}x^{\beta+\alpha}\right\\}$
with the function $f(x)$ exists, then the fractional derivative of the
function $f$ with order $\alpha,\beta\in(0,1)$ is given as:

${}_{a}^{AR}D_{x}^{\alpha,\beta}f(x)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\frac{d^{n}}{dx^{n}}\int\limits_{-\infty}^{x}f(t)(x-t)^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-t)^{\beta+\alpha}\right\\}dt,$
$\displaystyle 0$ $\displaystyle<$ $\displaystyle\beta<1,\text{ \ \
}n-1<\alpha<n.$

Definition 6 : Let $f(x)$ defined in $[-\infty,X]$ necessary differentiable
such that for all $x\in[-\infty,X]$ the convolution of
$x^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}x^{\beta+\alpha}\right\\}$
with the function $f(x)$ exists, then the fractional derivative of the
function $f$ with order $\alpha,\beta\in(0,1)$ is given as:

${}_{a}^{AC}D_{x}^{\alpha,\beta}f(x)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{-\infty}^{x}\frac{d^{n}f(t)}{dt^{n}}(x-t)^{1-\alpha-n}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-t)^{\beta+\alpha}\right\\}dt,$
$\displaystyle 0$ $\displaystyle<$ $\displaystyle\beta<1,\text{ \ \
}n-1<\alpha<n.$

##  3 New properties of the A.R and A.C derivatives

Some properties of the A.R and A.C derivatives with two order $\alpha,\beta$
are given below:

The Laplace transform of A.R:

The Laplace transform of A.R derivative is obtained via Laplace transform
definition below:

$\displaystyle L\left\\{{}_{a}^{AR}D_{x}^{\alpha,\beta}f(x)\right\\}$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{\infty}e^{-pt}\frac{d}{dt}\int\limits_{0}^{t}f(\tau)(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau
dt$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{p}{\Gamma\left\\{1-\alpha\right\\}}L\left\\{t^{-\alpha}E_{\beta}\left(-\frac{\beta}{1-\beta}t^{\beta+\alpha}\right)\right\\}L\left\\{f(t)\right\\}$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{p}{\Gamma\left\\{1-\alpha\right\\}}L\left\\{t^{1-\alpha-1}E_{\beta}\left(-\frac{\beta}{1-\beta}t^{\beta+\alpha}\right)\right\\}F(p)$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{p}{\Gamma\left\\{1-\alpha\right\\}}L\left\\{t^{p-1}E_{\beta}\left(-\frac{\beta}{1-\beta}t^{\sigma}\right)\right\\}F(p)$

However we have from the literature that

$L\left\\{t^{p-1}E_{\beta,\Psi}^{\delta}\left(at^{\alpha}\right)\right\\}=\frac{s^{-p}}{\Gamma(\delta)}\text{
}_{2}\Psi_{1}\left[\begin{array}[]{c}(\delta,1),(\Psi,\alpha);\\\
(\gamma,\beta)\text{ \ \ \ \ \ \ \
;}\end{array}\begin{array}[]{c}\frac{a}{s^{\alpha}}\end{array}\right]$ (8)

for $\alpha,p,\delta,\beta,\gamma>0$ thus if we take $\delta=\Psi=1,$
$a=-\frac{\beta}{1-\beta},$ and $\sigma=\alpha+\beta$ then we obtain the
following

$\displaystyle
L\left\\{t^{p-1}E_{\beta}\left(-\frac{\beta}{1-\beta}t^{\sigma}\right)\right\\}$
(12) $\displaystyle=$ $\displaystyle s_{\text{ \ \ \ \ \ \
}2}^{\alpha-1}\Psi_{1}\left[\begin{array}[]{c}(1,1),(1-\alpha,\alpha+\beta);\\\
(1,\beta)\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
;}\end{array}\begin{array}[]{c}-\frac{\beta}{1-\beta}.\frac{1}{s^{\alpha+\beta}}\end{array}\right]$

Where the function ${}_{p}\Psi_{q}$ is the wright’s generalized hyper-
geometric function defined by means of the similar representation in the
following form [8-9]:

${}_{p}\Psi_{q}(z)=\sum\limits_{r=0}^{\infty}\frac{\left\\{\prod\limits_{j=1}^{p}r(a_{j}+A_{j}r)\right\\}}{\left\\{\prod\limits_{j=1}^{q}r(b_{j}+B_{j}r)\right\\}}\frac{z^{r}}{r!},$
(13)

therefore replacing the above we obtain

$\displaystyle L\left\\{{}_{a}^{AR}D_{t}^{\alpha,\beta}f(t)\right\\}$ (14)
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}s_{\text{
\ \ \ \ \ \
}2}^{\alpha}\Psi_{1}\left[\begin{array}[]{c}(1,1),(1,\alpha+\beta);\\\
(1,\beta)\text{ \ \ \ \ \ \ \ \ \ \ \ \ \
;}\end{array}\begin{array}[]{c}-\frac{\beta}{1-\beta}.\frac{1}{s^{\alpha+\beta}}\end{array}\right]$
(18)

Existence of A.C:

Theorem 1 : Let $f$ be continuous in $[0,T]$ and $\alpha,\beta\in(0,1)$ then
the following inequality is obtained if

$\left\|\frac{df(t)}{dt}\right\|\leq\Theta\left\|f(t)\right\|_{C}$ (19)

Proof :

$\displaystyle\left\|{}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)\right\|_{C}$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\left\|\int\limits_{0}^{t}\frac{df(\tau)}{d\tau}(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau\right\|$
$\displaystyle\leq$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{t}\left\|\frac{df(\tau)}{d\tau}\right\|\left\|(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}\right\|d\tau$
$\displaystyle\leq$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\Theta\left\|f(t)\right\|_{C}\int\limits_{0}^{t}(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau$
$\displaystyle\leq$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\Theta\left\|f\right\|_{C}\int\limits_{0}^{t}(t-\tau)^{1-\alpha-1}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau$
$\displaystyle\leq$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\Theta\left\|f\right\|_{C}\int\limits_{0}^{t}(t-\tau)^{p-1}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau.$

Let $y=t-\tau$ and $p=1-\alpha$ then

$\int\limits_{0}^{t}(t-\tau)^{p-1}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau=\int\limits_{0}^{t}y^{p-1}E_{\beta}\left\\{-\frac{\beta}{1-\beta}y^{\beta+\alpha}\right\\}dy.$
(21)

However

$\int\limits_{0}^{t}y^{p-1}E_{\beta}\left\\{-\frac{\beta}{1-\beta}y^{\beta+\alpha}\right\\}dy=t^{p}E_{\beta,2}\left\\{-\frac{\beta}{1-\beta}t^{\beta+\alpha}\right\\}$
(22)

then

$\displaystyle\left\|{}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)\right\|_{C}$
$\displaystyle\leq$ $\displaystyle\left\|f\right\|_{C}K\text{ ,}$ (23)
$\displaystyle K$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\Theta
T^{1-\alpha}E_{\beta,2}\left\\{-\frac{\beta}{1-\beta}T^{\beta+\alpha}\right\\}$

Test of the Lipschitz continuity:

Let $f$ and $g$ be two defined function on $[0,T]$ such that their A.C
derivatives exist then

$\displaystyle\left\|{}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)-_{0}^{AC}D_{t}^{\alpha,\beta}g(t)\right\|_{C}$
$\displaystyle=$
$\displaystyle\left\|\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{t}\frac{d(f-g)(\tau)}{d\tau}(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau\right\|$
$\displaystyle\leq$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{t}\Theta_{1}\left\|f-g\right\|_{C}\left\|(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}\right\|d\tau$
$\displaystyle\leq$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{\Theta_{1}}{\Gamma\left\\{1-\alpha\right\\}}\left\|f-g\right\|_{C}\int\limits_{0}^{t}(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau$
$\displaystyle\leq$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{\Theta_{1}}{\Gamma\left\\{1-\alpha\right\\}}T^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}T^{\beta+\alpha}\right\\}\left\|f-g\right\|_{C}$
$\displaystyle\leq$ $\displaystyle L\left\|f-g\right\|_{C}$

Thus

$\left\|{}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)-_{0}^{AC}D_{t}^{\alpha,\beta}g(t)\right\|_{C}\leq
L\left\|f(t)-g(t)\right\|_{C}.$ (25)

This implies A.C has Lipschitz continuity condition.

Theorem 2 : Let $f$ be a continuous function defined in $[0,T]$ such that
${}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)$ and
${}_{0}^{AR}D_{t}^{\alpha,\beta}f(t)$ exists, then the following relation is
established.

${}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)=-G(t)+_{0}^{AR}D_{t}^{\alpha,\beta}f(t).$
(26)

Proof : We achieve this using the Laplace transform

$\displaystyle L\left\\{{}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)\right\\}$
$\displaystyle=$ $\displaystyle
L\left\\{\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{t}\frac{df(\tau)}{d\tau}(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau\right\\}$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}L\left\\{\frac{df(\tau)}{d\tau}\right\\}L\left\\{t^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}t^{\beta+\alpha}\right\\}\right\\}$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\left\\{pF(p)-f(0)\right\\}L\left\\{t^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}t^{\beta+\alpha}\right\\}\right\\}$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{p}{\Gamma\left\\{1-\alpha\right\\}}\text{
}_{2}\Psi_{1}\left[\begin{array}[]{c}(1,1),(1-\alpha,\alpha+\beta);\\\
(1,\beta)\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
;}\end{array}\begin{array}[]{c}-\frac{\beta}{1-\beta}.\frac{1}{s^{\alpha+\beta}}\end{array}\right]F(p)$
(35)
$\displaystyle-\frac{A(\beta)}{1-\beta}\frac{p^{\alpha-1}}{\Gamma\left\\{1-\alpha\right\\}}_{2}\Psi_{1}\left[\begin{array}[]{c}(1,1),(1-\alpha,\alpha+\beta);\\\
(1,\beta)\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
;}\end{array}\begin{array}[]{c}-\frac{\beta}{1-\beta}.\frac{1}{s^{\alpha+\beta}}\end{array}\right]f(0).$

Therefore the inverse Laplace transform applied on the above yields,

${}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)$ $\displaystyle=$
${}_{0}^{AR}D_{t}^{\alpha,\beta}f(t)-\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}f(0)t^{-\alpha}E_{\beta}\left\\{-t^{\beta+\alpha}\right\\}$
$\displaystyle=$ ${}_{0}^{AR}D_{t}^{\alpha,\beta}f(t)-G(t).$

This completes the proof.

Sumudu Transform of A.C:

The Sumudu transform of A.C is expressed as follows:

$\displaystyle S\left({}_{0}^{AR}D_{t}^{\alpha,\beta}f(t)\right)$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}S\left(\frac{d}{dt}\int\limits_{0}^{t}f(\tau)(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau\right)$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\frac{1}{u}.S\left(\int\limits_{0}^{t}f(\tau)(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau\right)$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\frac{1}{u}S\left(f(t)\right).S\left(t^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}t^{\beta+\alpha}\right\\}\right)$

where

$\displaystyle
S\left(t^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}t^{\beta+\alpha}\right\\}\right)$
$\displaystyle=$
$\displaystyle\int\limits_{0}^{\infty}e^{-t}u^{-\alpha}t^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(ut)^{\beta+\alpha}\right\\}dt$
$\displaystyle=$ $\displaystyle
u^{-\alpha}\int\limits_{0}^{\infty}e^{-t}t^{-\alpha}E_{\beta}\left\\{-\lambda
t^{\beta+\alpha}\right\\}dt,$

where $\lambda=\frac{\beta}{1-\beta}u^{\alpha+\beta}.$

$\displaystyle
S\left(t^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}t^{\beta+\alpha}\right\\}\right)$
$\displaystyle=$ $\displaystyle
u^{-\alpha}\int\limits_{0}^{\infty}e^{-t}t^{-\alpha}E_{\beta}\left\\{-\lambda
t^{\beta+\alpha}\right\\}dt$ $\displaystyle=$ $\displaystyle
u^{-\alpha}\int\limits_{0}^{\infty}e^{-t}t^{-\alpha}\sum\limits_{j=0}^{\infty}\frac{\left(-\lambda
t^{\beta+\alpha}\right)^{j}}{\Gamma\left(\alpha j+1\right)}$

where $\lambda=\frac{\beta}{1-\beta}u^{\alpha+\beta}.$

$\displaystyle=$ $\displaystyle
u^{-\alpha}\sum\limits_{j=0}^{\infty}\frac{\left(-\lambda\right)^{j}}{\Gamma\left(\alpha
j+1\right)}\int\limits_{0}^{\infty}e^{-t}t^{\alpha j+\beta j-\alpha}dt$
$\displaystyle=$ $\displaystyle
u^{-\alpha}\sum\limits_{j=0}^{\infty}\frac{\left(-\lambda\right)^{j}}{\Gamma\left(\alpha
j+1\right)}\int\limits_{0}^{\infty}e^{-t}t^{\alpha j+\beta j-\alpha+1-1}dt$
$\displaystyle=$ $\displaystyle
u^{-\alpha}\sum\limits_{j=0}^{\infty}\frac{\left(-\lambda\right)^{j}}{\Gamma\left(\alpha
j+1\right)}\int\limits_{0}^{\infty}e^{-t}t^{\Theta-1}dt$

where $\Theta=\alpha j+\beta j-\alpha+1.$

$\displaystyle=$ $\displaystyle
u^{-\alpha}\sum\limits_{j=0}^{\infty}\frac{\left(-\lambda\right)^{j}}{\Gamma\left(\alpha
j+1\right)}\Gamma(\Theta)$ $\displaystyle=$ $\displaystyle
u^{-\alpha}\sum\limits_{j=0}^{\infty}\frac{\left(-\lambda\right)^{j}}{\Gamma\left(\alpha
j+1\right)}\Gamma(\alpha j+\beta j-\alpha+1)$ $\displaystyle=$ $\displaystyle
u^{-\alpha}\sum\limits_{j=0}^{\infty}\frac{\left(-\frac{\beta}{1-\beta}u^{\beta+\alpha}\right)^{j}\Gamma(\alpha
j+\beta j-\alpha+1)}{\Gamma\left(\alpha j+1\right)}$

Therefore the Sumudu transform of ${}_{0}^{AR}D_{t}^{\alpha,\beta}f(t)$ is
given as

$\displaystyle S\left({}_{0}^{AR}D_{t}^{\alpha,\beta}f(t)\right)$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}u^{-\alpha-1}\sum\limits_{j=0}^{\infty}\frac{\left(-\frac{\beta}{1-\beta}u^{\beta+\alpha}\right)^{j}\Gamma(\alpha
j+\beta j-\alpha+1)}{\Gamma\left(\alpha j+1\right)}$

##  4 Partial derivative with A.C and A.R

Since one can model many natural occurrence using the space and time, it is
therefore important to propose in this section the partial A.C and A.R
fractional derivative with order $\alpha,\beta.$

Definition 7 : Let $f(x,t)$ be a function differentiable in $x$ or $t$
direction. Let $\alpha,\beta\in(0,1)$ such that the convolution of
$x^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}x^{\beta+\alpha}\right\\}$
and $\frac{\partial f}{\partial x}$ exists than the A.C partial fractional
derivative of $f$ of order $\alpha,\beta$ is given as:

${}_{0}^{AC}D_{x}^{\alpha,\beta}f(x,t)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{x}\frac{\partial
f(\xi,t)}{\partial
t^{n}}(x-\xi)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-\xi)^{\beta+\alpha}\right\\}d\xi.$

Definition 8 : Let $f(x,t)$ be a function not necessary differentiable in $x$
or $t$ direction. Let $\alpha,\beta\in(0,1)$ such that the convolution of
$x^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}x^{\beta+\alpha}\right\\}$
and $\frac{\partial f}{\partial x}$ exists than the A.R partial fractional
derivative of $f$ of order $\alpha,\beta$ is given as:

${}_{0}^{AR}D_{x}^{\alpha,\beta}f(x,t)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\frac{\partial}{\partial
x}\int\limits_{0}^{x}f(\xi,t)(x-\xi)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-\xi)^{\beta+\alpha}\right\\}d\xi.$

Definition 9 : Let $f(x,t)$ be a function such that
$\frac{\partial^{2}f}{\partial x\partial t}$ exists. Let
$\alpha,\beta\in(0,1)$ then A.C partial derivative of $f$ of order
$\alpha,\beta$ is given as:

${}_{0}^{AC}D_{x,t}^{\alpha,\beta}f(x,t)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{x}\int\limits_{0}^{t}\frac{\partial^{2}f(\xi,\lambda)}{\partial\xi\partial\lambda}(x-\xi)^{-\alpha}(t-\lambda)^{-\alpha}$
$\displaystyle.E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-\xi)^{\beta+\alpha}\right\\}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\lambda)^{\beta+\alpha}\right\\}d\xi
d\lambda.$

However if $\frac{\partial^{2}f}{\partial x\partial t}$ does not exist then

${}_{0}^{AR}D_{x,t}^{\alpha,\beta}f(x,t)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\frac{\partial^{2}f}{\partial
x\partial
t}\int\limits_{0}^{x}\int\limits_{0}^{t}f(\xi,\lambda)(x-\xi)^{-\alpha}(t-\lambda)^{-\alpha}$
$\displaystyle.E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-\xi)^{\beta+\alpha}\right\\}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\lambda)^{\beta+\alpha}\right\\}d\xi
d\lambda.$

Theorem 3 : Let $f$ be a function such that $\frac{\partial^{2}f}{\partial
x\partial t}$ and $\frac{\partial^{2}f}{\partial t\partial x}$ exist and
continuous. Let $\alpha,\beta\in(0,1)$ then the following equality holds.

${}_{0}^{AC}D_{x,t}^{\alpha,\beta}f(x,t)=_{0}^{AC}D_{t,x}^{\alpha,\beta}f(x,t)$
(47)

Proof : By definition we have that

${}_{0}^{AC}D_{x,t}^{\alpha,\beta}f(x,t)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{x}\int\limits_{0}^{t}\frac{\partial^{2}f(\xi,\lambda)}{\partial\xi\partial\lambda}(x-\xi)^{-\alpha}(t-\lambda)^{-\alpha}$
$\displaystyle.E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-\xi)^{\beta+\alpha}\right\\}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\lambda)^{\beta+\alpha}\right\\}d\xi
d\lambda.$

Since $\frac{\partial^{2}f}{\partial x\partial t}$ and
$\frac{\partial^{2}f}{\partial t\partial x}$ exist and are continuous then
$\frac{\partial^{2}f}{\partial x\partial t}=\frac{\partial^{2}f}{\partial
t\partial x}$ therefore we have

${}_{0}^{AC}D_{x,t}^{\alpha,\beta}f(x,t)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{x}\int\limits_{0}^{t}\frac{\partial^{2}f(\xi,\lambda)}{\partial\xi\partial\lambda}(x-\xi)^{-\alpha}(t-\lambda)^{-\alpha}$
$\displaystyle.E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-\xi)^{\beta+\alpha}\right\\}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\lambda)^{\beta+\alpha}\right\\}d\xi
d\lambda.$

$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{t}\int\limits_{0}^{x}\frac{\partial^{2}f(\xi,\lambda)}{\partial\lambda\partial\xi}(t-\lambda)^{-\alpha}(x-\xi)^{-\alpha}$
(50)
$\displaystyle.E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\lambda)^{\beta+\alpha}\right\\}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(x-\xi)^{\beta+\alpha}\right\\}d\lambda
d\xi$ $\displaystyle=$ ${}_{0}^{AC}D_{t,x}^{\alpha,\beta}f(x,t)$

Thus

${}_{0}^{AC}D_{x,t}^{\alpha,\beta}f(x,t)=_{0}^{AC}D_{t,x}^{\alpha,\beta}f(x,t).$
(51)

This completes the proof.

##  5 Numerical Approximation

There exist in nature many problems for which mathematical representations are
modeled with strong non-linearity. These kind of mathematical equations can
mostly handled using numerical approximations [8-10]. therefore in order to
accommodate researchers working in the field of numerical analysis. We present
in this section the numerical approximation of the
${}_{0}^{AC}D_{t}^{\alpha,\beta}f(t).$

${}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{t}\frac{df(\tau)}{d\tau}(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\int\limits_{0}^{t}\frac{f(t)-f(t+\Delta
t)}{2\Delta
t}(t-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t-\tau)^{\beta+\alpha}\right\\}d\tau$
${}_{0}^{AC}D_{t}^{\alpha,\beta}f(t)$ $\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\sum\limits_{i=0}^{n}\int\limits_{t_{i}}^{t_{i+1}}\frac{f^{i+1}-f^{i}}{2\left(\Delta
t\right)}(t_{n}-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t_{n}-\tau)^{\beta+\alpha}\right\\}d\tau$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\sum\limits_{i=0}^{n}\frac{f^{i+1}-f^{i}}{2\left(\Delta
t\right)}\int\limits_{t_{i}}^{t_{i+1}}(t_{n}-\tau)^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}(t_{n}-\tau)^{\beta+\alpha}\right\\}d\tau$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\sum\limits_{i=0}^{n}\frac{f^{i+1}-f^{i}}{2\left(\Delta
t\right)}\int\limits_{t_{n}-t_{i}}^{t_{n}-t_{i+1}}y^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}y^{\beta+\alpha}\right\\}dy$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\sum\limits_{i=0}^{n}\frac{f^{i+1}-f^{i}}{2\left(\Delta
t\right)}\int\limits_{t}^{x}y^{-\alpha}E_{\beta}\left\\{-\frac{\beta}{1-\beta}y^{\beta+\alpha}\right\\}dy$
$\displaystyle=$
$\displaystyle\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\sum\limits_{i=0}^{n}\frac{f^{i+1}-f^{i}}{2\left(\Delta
t\right)}\delta_{n,i}.$

Where

$\displaystyle\delta_{n,i}$ $\displaystyle=$
$\displaystyle\left(t_{n}-t_{i+1}\right)^{1-\alpha}E_{\beta,2-\alpha}\left\\{-\frac{\beta}{1-\beta}\left(t_{n}-t_{i+1}\right)^{\beta+\alpha}\right\\}$
$\displaystyle-\left(t_{n}-t_{i}\right)^{1-\alpha}E_{\beta,2-\alpha}\left\\{-\frac{\beta}{1-\beta}\left(t_{n}-t_{i+1}\right)^{\beta+\alpha}\right\\}.$

With the same time of idea we obtain the space approximation as

${}_{0}^{AC}D_{x}^{\alpha,\beta}f(x)=\frac{A(\beta)}{1-\beta}\frac{1}{\Gamma\left\\{1-\alpha\right\\}}\sum\limits_{i=0}^{n}\frac{f^{i+1}-f^{i}}{2\left(\Delta
x\right)}\delta_{n,i}.$ (54)

##  6 Conclusion

In this paper we have broadened the scope of fractional calculus by
introducing fractional derivatives with two orders. The motivation of this is
from the fact that one can find in nature some systems with two different and
parallel layers with different properties, as for instance the movement of
water through aquifer with parallel layers with different properties. This
type of problem can not be portray with existing derivatives with fractional
order. Some properties connected to this new derivatives are presented. The
numerical approximation also presented. This new derivatives will open new
doors for PhD thesis, research and new fields.

## References

  * [1] I. Koca, ”A method for solving differential equations of q-fractional order”, Applied Mathematics and Computation, vo. 266, pp. 1–5, 2015
  * [2] Ozalp, N. and Koca, I. A fractional order nonlinear dynamical model of interpersonal relationships, Advances in Difference Equations 189, pp.510–544 (2012)
  * [3] A. Atangana, I. Koca, Chaos in a simple nonlinear system with Atangana-Baleanu derivatives with fractional order, Chaos, Solitons and Fractals: the interdisciplinary journal of Nonlinear Science, and Nonequilibrium and Complex Phenomena, In press, 10.1016/j.chaos.2016.02.012, 2016
  * [4] A. Atangana, I. Koca, On the new fractional derivative and application to Nonlinear Baggs and Freedman model, J. Nonlinear Sci. Appl. vol. 9 , pp. 2467–2480, 2016
  * [5] I. Koca, N. Ozalp, Analysis of a Fractional-Order Couple Model with Acceleration in Feelings, The Scientific World Journal, Article ID 730736, in press (2013).
  * [6] Chandrasekhar, S.,. ”Stochastic problems in physics and astronomy”. Reviews of Modern Physics 15 (1): 1–89 (1943)
  * [7] Morozov, A. N.; Skripkin, A. V.,. ”Spherical particle Brownian motion in viscous medium as non-Markovian random process”. Physics Letters A 375 (46): 4113–4115(2011).
  * [8] Yang Liu, Zhichao Fang, Hong Li, Siriguleng He. A mixed finite element method for a time-fractional fourth-order partial differential equation; Appl. Math. Comput., 243, pp. 703–717(2014)
  * [9] M.M. Meerschaert, C. Tadjeran; Finite difference approximations for fractional advection dispersion equations; J. Comput. Appl. Math., 172, pp. 65–77 (2004)
  * [10] C.M. Chen, F. Liu, I. Turner, V. Anh; A Fourier method for the fractional diffusion equation describing sub-diffusion; J. Comput. Phys., 227, pp. 886–897(2007)
  * [11] Iyanaga, S. and Kawada, Y. (Eds.). ”Hypergeometric Functions and Spherical Functions.” Appendix A, Table 18 in Encyclopedic Dictionary of Mathematics. Cambridge, MA: MIT Press, pp. 1460-1468, (1980).
  * [12] Kummer, E. E. ”Über die Hypergeometrische Reihe.” J. reine angew. Math. 15, 39-83 and 127-172, (1836).


# On the number of integer non-negative solutions of a linear Diophantine
equation

Eteri Samsonadze

###### Abstract.

We deal with the problem to find the number $P(b)$ of integer non-negative
solutions of an equation $\sum_{i=1}^{n}a_{i}x_{i}=b$, where
$a_{1},a_{2},...,a_{n}$ are natural numbers and $b$ is a non-negative integer.
As different from the traditional methods of investigation of the function
$P(b)$, in our study we do not employ the techniques of number series theory,
but use in the main the properties of the Kronecker function and the elements
of combinatorics. The formula is derived to express $P(b)$, for an integer
non-negative $b$, via $P(r),P(r+M),...,P(r+(s-1)M)$ when $s\neq 0$, where
$s=\left[n-\dfrac{\sum_{i=1}^{n}a_{i}+r}{M}\right]$ and takes quite small
values in some particular cases; $M$ is the least common multiple of the
numbers $a_{1},a_{2},\ldots,a_{n}$, and $r$ is the remainder of $b$ modulo
$M$. Also, the recurrent formulas are derived to calculate $P(b)$, for any
non-negative integer $b$, which, in particular, are used in finding
$P(r),P(r+M),...,P(r+(s-1)M)$. For the case where $s=0$ and
$a_{1},a_{2},...,a_{n}$ are coprime, the explicit formula
$P(b)=\dfrac{M^{n-1}}{a_{1}a_{2}\ldots
a_{n}}C^{n-1}_{\tiny\left[\dfrac{b}{M}\right]+n-1}$ is given. To illustrate
the proposed method, examples of finding the function $P(b)$ for linear
Diophantine equations with $2,3,7$ and $n$ variables are given.

Key words and phrases: linear Diophantine equation; number of solutions;
recurrent formula.

2020 Mathematics Subject Classification: 11D45, 11D04.

##  1\. Introduction

In the present paper we study the problem of finding the number $P(b)$ of
integer non-negative solutions of a linear Diophantine equation

$\sum_{i=1}^{n}a_{i}x_{i}=b,$

where $a_{1},a_{2},...,a_{n}$ are natural numbers and $b$ is a non-negative
integer. To this end we first study the interrelation of the numbers of
integer non-negative solutions of arbitrary linear Diophantine equations with
natural coefficients and one and the same number of variables. Applying the
found interrelation, for the case where the number $s$ defined by

$s=\left[n-\dfrac{\sum_{i=1}^{n}a_{i}+r}{M}\right]$

is different from $0$ we obtain the formula representing the number $P(b)$ via
the numbers

$P(r),P(r+M),\ldots,P(r+(s-1)M),$ (1.1)

where $M$ is the least common multiple of the numbers
$a_{1},a_{2},\ldots,a_{n}$, and $r$ is the remainder of $b$ modulo $M$. It
should be noted that applying a different method the formula representing
$P(b)$ via the numbers

$P(r+M),P(r+2M),\ldots,P(r+nM)$

is given in Riordan’s book [5]. Note also that $s\leq n-1$. Moreover, $s$
takes quite small values in some particular cases.

In the paper we also give the recurrent formulas to calculate $P(b)$, for any
non-negative integer $b$, which, in particular, are applied to find values
(1.1).

For the case where $s=0$ (which holds if, for instance,
$r>(n-1)M-\sum_{i=1}^{n}a_{i}$) and the numbers $a_{1},a_{2},...,a_{n}$ are
coprime (which can always be assumed without loss of generality), we give the
explicit formula for $P(b)$:

$P(b)=\dfrac{M^{n-1}}{a_{1}a_{2}\ldots
a_{n}}C^{n-1}_{\tiny\left[\dfrac{b}{M}\right]+n-1}.$

As different from the traditional methods of investigation of the function
$P(b)$, in our study we do not employ the techniques of number series theory,
but use in the main the properties of the Kronecker function and the elements
of combinatorics. Moreover, the proposed method of finding the function $P(b)$
can be used even in the case where the numbers $a_{1},a_{2},...,a_{n}$ are not
pairwise coprime.

To illustrate the proposed method some examples of finding the number $P(b)$
in the case of linear Diophantine equations with $2,3,4,7$ and $n$ variables
are given.

##  2\. Interrelationship of the numbers of integer non-negative solutions of
some linear Diophantine equations

In this section we consider the problem of determining the relationship
between the numbers of integer non-negative solutions of linear Diophantine
equations with one and the same number of variables.

We denote by the symbol $P(f(x_{1},x_{2},...,x_{n})=m)$ the number of integer
non-negative solutions of an equation $f(x_{1},x_{2},...,x_{n})=m$.

First, we represent the number of integer non-negative solutions
$P^{\prime}(b)=P^{\prime}(\sum_{i=1}^{n}a_{i}x_{i}=b)$ of the system

$\sum_{i=1}^{n}a_{i}x_{i}=b,$ $0\leq x_{i}\leq d_{i}-1~{}(i=1,2,\cdots,n)$

via the values of the function $P(b)=P(\sum_{i=1}^{n}a_{i}x_{i}=b)$, where
$n\geq 2$, $b$ is an integer non-negative number, $a_{i}\in\mathbb{N}$,
$d_{i}\in\mathbb{N}$ $(i=1,2,\cdots,n)$.

######  Lemma 2.1.

We have

$P^{\prime}(b)=P(b)-\sum_{i=1}^{n}P(b-a_{i}d_{i})+\sum_{1\leqslant
i<j\leqslant n}^{n}P(b-a_{i}d_{i}-a_{j}d_{j})-$ $-\sum_{1\leqslant
i<j<m\leqslant
n}P(b-a_{i}d_{i}-a_{j}d_{j}-a_{m}d_{m})+\ldots+(-1)^{n}P(b-\sum_{i=1}^{n}a_{i}d_{i}),$
(2.1)

###### Proof.

It is not difficult to observe that

$P(\sum_{i=1}^{n}a_{i}x_{i}=b)=\sum_{x_{1}}\sum_{x_{2}}...\sum_{x_{n}}\delta(\sum_{i=1}^{n}a_{i}x_{i};b)$
(2.2)

and

$P^{\prime}(\sum_{i=1}^{n}a_{i}x_{i}=b)=\sum_{x_{1}=0}^{d_{1}-1}\sum_{x_{2}=0}^{d_{2}-1}...\sum_{x_{n}=0}^{d_{n}-1}\delta(\sum_{i=1}^{n}a_{i}x_{i};b),$
(2.3)

where $\delta(x;y)$ is the Kronecker symbol, while
$\sum_{x_{1}}\sum_{x_{2}}...\sum_{x_{n}}$ denotes the summation over all
integer non-negative $x_{1},x_{2},...,x_{n}$.

Since

$\sum_{x}\delta(ax;b)=\sum_{x=0}^{d-1}\delta(ax;b)+\sum_{x=d}^{\infty}\delta(ax;b)=$
$\sum_{x=0}^{d-1}\delta(ax;b)+\sum_{x}\delta(a(x+d);b)=$
$\sum_{x=0}^{d-1}\delta(ax;b)+\sum_{x}\delta(ax;b-ad),$

for any natural $d$, we conclude that

$\sum_{x=0}^{d-1}\delta(ax;b)=\sum_{x}\delta(ax;b)-\sum_{x}\delta(ax;b-ad).$

Applying this and the principle of mathematical induction, it is not difficult
to show that

$\sum_{x_{1}=0}^{d_{1}-1}\sum_{x_{2}=0}^{d_{2}-1}...\sum_{x_{n}=0}^{d_{n}-1}\delta(\sum_{i=1}^{n}a_{i}x_{i};b)=$
$\sum_{x_{1}}\sum_{x_{2}}...\sum_{x_{n}}(\delta(\sum_{i=1}^{n}a_{i}x_{i};b)-\Sigma_{k=1}^{n}\delta(\sum_{i=1}^{n}a_{i}x_{i};b-a_{k}d_{k})+$
$\sum_{1\leq k<j\leq
n}\delta(\sum_{i=1}^{n}a_{i}x_{i};b-a_{k}d_{k}-a_{j}d_{j})-$ $\sum_{1\leq
k<j<m\leq
n}\delta(\sum_{i=1}^{n}a_{i}x_{i};b-a_{k}d_{k}-a_{j}d_{j}-a_{m}d_{m})+...+$
$(-1)^{n}\delta(\sum_{i=1}^{n}a_{i}x_{i};b-\sum_{i=1}^{n}a_{i}d_{i})),$

for any natural $d_{1},d_{2},...,d_{n}$. Therefore (2.2) and (2.3) imply that

$P^{\prime}(b)=\sum_{\beta_{1}=0}^{1}\sum_{\beta_{2}=0}^{1}...\sum_{\beta_{n}=0}^{1}(-1)^{\beta_{1}+\beta_{2}+\ldots\beta_{n}}P(b-\sum_{i=1}^{n}\beta_{i}a_{i}d_{i}).$

∎

######  Theorem 2.2.

The following equality holds:

$P(\sum_{i=1}^{n}a_{i}x_{i}=b)=\sum_{k=0}^{\overline{s}}m_{k}P(\sum_{i=1}^{n}c_{i}x_{i}=\left[\dfrac{b}{M}\right]-k),$
(2.4)

where $n\geqslant 2$; $a_{i},c_{i}\in\mathbb{N}$ $(i=1,2,...,n)$; $b$ is a
non-negative integer, $M$ is the least common multiple of
$a_{1},a_{2},...a_{n}$; $r$ is the remainder of $b$ modulo $M$,

$\overline{s}=\left[\sum_{i=1}^{n}c_{i}-\dfrac{\sum_{i=1}^{n}a_{i}+r}{M}\right],$
(2.5) $m_{0}=P(r),m_{k}=P(r+kM)-\Sigma_{i=1}^{n}P(r+kM-Mc_{i})+$ $\sum_{1\leq
i<j\leq n}P(r+kM-M(c_{i}+c_{j}))-\ldots+$ $(-1)^{k}\sum_{1\leq
i_{1}<i_{2}<\ldots<i_{k}\leq
n}P(r+kM-M(c_{i_{1}}+c_{i_{2}}+\ldots+c_{i_{k}}))$ (2.6)

($k=1,2,\ldots,\overline{s}$), and

$P(l)=P(\sum_{i=1}^{n}a_{i}x_{i}=l).$

###### Proof.

It is not difficult to observe that

$\sum_{x}\delta(ax;b)=\sum_{x}\sum_{t=0}^{d-1}\delta(a(dx+t);b),$

for any natural $d$. Hence we have

$\sum_{x_{1}}\sum_{x_{2}}...\sum_{x_{n}}\delta(\sum_{i=1}^{n}a_{i}x_{i};b)=$
$\sum_{x_{1}}\sum_{x_{2}}...\sum_{x_{n}}\sum_{t_{1}=0}^{d_{1}-1}\sum_{t_{2}=0}^{d_{2}-1}...\sum_{t_{n}=0}^{d_{n}-1}\delta(\sum_{i=1}^{n}a_{i}(d_{i}x_{i}+t_{i});b),$
(2.7)

for any natural $d_{1},d_{2},...,d_{n}$. Therefore (2.2) and (2.3) imply that

$P(\sum_{i=1}^{n}a_{i}x_{i}=b)=$
$\sum_{t_{1}=0}^{d_{1}-1}\sum^{d_{2}-1}_{t_{2}=0}...\sum^{d_{n}-1}_{t_{n}=0}P(\sum_{i=1}^{n}d_{i}a_{i}x_{i}=b-\sum_{i=1}^{n}a_{i}t_{i}),$
(2.8)

for any natural $d_{i}$ $(i=1,2,...,n)$. Applying this equality for
$d_{i}=\dfrac{M}{a_{i}}c_{i}$ $(i=1,2,...,n)$, we obtain

$P(\sum_{i=1}^{n}a_{i}x_{i}=b)=$
$\sum_{t_{1}=0}^{\alpha_{1}}\sum^{\alpha_{2}}_{t_{2}=0}...\sum^{\alpha_{n}}_{t_{n}=0}P(\sum_{i=1}^{n}c_{i}x_{i}=\dfrac{b-\sum^{n}_{i=1}a_{i}t_{i}}{M}).$
(2.9)

where $\alpha_{i}=\dfrac{Mc_{i}}{a_{i}}-1$ $(i=1,2,...,n)$.

Since $\dfrac{b-\sum^{n}_{i=1}a_{i}t_{i}}{M}$ is an integer if and only if
$\sum^{n}_{i=1}a_{i}t_{i}=r+Mk$, for some integer $k$, and using
$0\leq\sum^{n}_{i=1}a_{i}t_{i}\leqslant
M\sum^{n}_{i=1}c_{i}-\sum^{n}_{i=1}a_{i}$, we have

$0\leq k\leqslant\sum^{n}_{i=1}c_{i}-\dfrac{\sum^{n}_{i=1}a_{i}+r}{M}.$

Further, since $\dfrac{b-(r+Mk)}{M}=\left[\dfrac{b}{M}\right]-k$, (2.9)
implies (2.4), where $m_{k}$ $(k=0,1,2,...,\overline{s})$ is the number of
integer non-negative solutions of the system:

$\sum_{i=1}^{n}a_{i}t_{i}=r+Mk,~{}~{}0\leqslant
t_{i}\leqslant\dfrac{M}{a_{i}}c_{i}-1~{}~{}(i=1,2,...n).$

Applying Lemma 2.1 for $d_{i}=\dfrac{M}{a_{i}}c_{i}$ $(i=1,2,...n)$, we obtain

$m_{k}=\sum_{\beta_{1}=0}^{1}\sum_{\beta_{2}=0}^{1}...\sum_{\beta_{n}=0}^{1}(-1)^{\beta_{1}+\beta_{2}+\ldots\beta_{n}}P(r+Mk-M\sum_{i=1}^{n}\beta_{i}c_{i}),$

for any $k$ $(k=0,1,...,\overline{s})$.

Since $c_{i}\geq 1$ $(i=1,2,...n)$ and $P(b)=0$ for $b<0$, we obtain (2.6). ∎

##  3\. On the function $P(b)=P(\sum_{i=1}^{n}a_{i}x_{i}=b)$

Theorem 2.1 generalizes our earlier result [6], where the number $P(b)$ of
integer non-negative solutions of an equation $\sum_{i=1}^{n}a_{i}x_{i}=b$
$(a_{1},a_{2},...,a_{n}\in\mathbb{N}$, $b$ is a non-negative integer) was
represented via the numbers of integer non-negative solutions of certain
linear Diophantine equations where all coefficients of variables are 1.

Applying (2.4), (2.5) and (2.6) with $c_{i}=1$ $(i=1,2,...,n)$ we obtain

$P(\sum_{i=1}^{n}a_{i}x_{i}=b)=\sum_{k=0}^{s}l_{k}P(\sum_{i=1}^{n}x_{i}=\left[\dfrac{b}{M}\right]-k),$
(3.1)

where

$s=\left[n-\dfrac{\sum_{i=1}^{n}a_{i}+r}{M}\right],$ (3.2)
$l_{0}=P(r),~{}l_{k}=P(r+kM)-C_{n}^{1}P(r+(k-1)M)+C_{n}^{2}P(r+(k-2)M)+$
$...+(-1)^{k}C_{n}^{k}P(r),~{}(k=1,2,..,s).$ (3.3)

.

Since, for any integer $d$, we have

$P(\sum_{i=1}^{n}x_{i}=d)=\left\\{\begin{array}[]{llllllll}C_{d+n-1}^{n-1}&if&d\geq
0,\\\ 0&otherwise,\end{array}\right.$ (3.4)

we obtain the following statement.

######  Theorem 3.1.

We have the equality

$P(\sum_{i=1}^{n}a_{i}x_{i}=b)=\sum_{k=0}^{s}l_{k}\overline{C}_{\left[\dfrac{b}{M}\right]+n-1-k}^{n-1},$
(3.5)

where $n\geq 2$, $a_{i}\in\mathbb{N}$ $(i=1,2,...,n)$, $b$ is a non-negative
integer, $M$ is the least common multiple of the numbers
$a_{1},a_{2},...,a_{n}$, $r$ is a remainder of $b$ modulo $M$, $s$ and $l_{k}$
$(k=0,1,...,s)$ are respectively given by (3.2) and (3.3), while

$\overline{C}_{k}^{m}=\left\\{\begin{array}[]{llllllll}C_{k}^{m}&if&k\geq
m,\\\ 0&otherwise,\end{array}\right.$ (3.6)

Formulas (3.5), (3.2) and (3.3) imply:

$P(b)=c_{0}\left[\dfrac{b}{M}\right]^{n-1}+c_{1}\left[\dfrac{b}{M}\right]^{n-2}+\ldots+c_{n-2}\left[\dfrac{b}{M}\right]+c_{n-1},$
(3.7)

where $c_{0}$, $c_{1}$,…,$c_{n-1}$ are numbers which do not depend on
$\left[\dfrac{b}{M}\right]$. In this way we obtain the known result from [1]
by which the function $P(b)=P(\sum_{i=1}^{n}a_{i}x_{i}=b)$ is a polynomial of
degree $(n-1)$ with respect to $\left[\dfrac{b}{M}\right]$.

Formula (3.7) implies that

$c_{n-1}=P(r).$ (3.8)

Without loss of generality one can assume that the coefficients $a_{1},a_{2},$
$\ldots,a_{n}$ in the equation $\sum_{i=1}^{n}a_{i}x_{i}=b$ are coprime. In
that case, according to [4], we have

$\lim_{b\rightarrow\infty}\dfrac{P(b)}{b^{n-1}}=\dfrac{1}{a_{1}a_{2}\ldots
a_{n}(n-1)!}.$ (3.9)

Since $\left[\dfrac{b}{M}\right]=\dfrac{b-r}{M}$, equality (3.7) implies that

$\lim_{b\rightarrow\infty}\dfrac{P(b)}{b^{n-1}}=\dfrac{c_{0}}{M^{n-1}}.$

Hence from (3.9) we obtain the value of the leading coefficient of polynomial
(3.7)

$c_{0}=\dfrac{M^{n-1}}{a_{1}a_{2}\ldots a_{n}(n-1)!},$ (3.10)

for the case of coprime $a_{1},a_{2},$ $\ldots,a_{n}$.

Formulas (3.7), (3.8), (3.10) imply

######  Proposition 3.2.

If $b\equiv 0$ $(mod$ $M)$ and $a_{1},a_{2},\ldots,a_{n}$ are coprime, then
the function $P(b)=P(\sum_{i=1}^{n}a_{i}x_{i}=b)$ is a polynomial of degree
$(n-1)$ with respect to $b$ with the leading coefficient
$\dfrac{1}{a_{1}a_{2}\ldots a_{n}(n-1)!}$ and the free coefficient $1$.

Since (3.5) implies that $c_{0}=\dfrac{\sum_{i=0}^{n}l_{i}}{(n-1)!}$, from
(3.10) we obtain that if $a_{1},a_{2},\ldots,a_{n}$ are coprime, we have

$\sum_{i=0}^{s}l_{i}=\dfrac{M^{n-1}}{a_{1}a_{2}\ldots a_{n}}.$ (3.11)

This implies that for calculating $P(b)$ by formula (3.5), it suffices to know
the values of $l_{0},l_{1},\ldots,l_{s-1}$.

From (3.3) we obtain

$\sum_{i=0}^{s}l_{i}=P(r+sM)+P(r+(s-1)M)(1-C_{n}^{1})+$
$P(r+(s-2)M)(1-C_{n}^{1}+C_{n}^{2})+...+$
$P(r)(1-C_{n}^{1}+C_{n}^{2}+...+(-1)^{s}C_{n}^{s}).$ (3.12)

As is well known (see, e.g. [3]),

$C_{n}^{0}-C_{n}^{1}+C_{n}^{2}+...+(-1)^{m}C_{n}^{m}=\left\\{\begin{array}[]{lll}(-1)^{m}C_{n-1}^{m}&if&m\leq
n-1,\\\ 0&otherwise.\end{array}\right.$

Therefore (3.11) and (3.12) imply that if $a_{1},a_{2},\ldots a_{n}$ are
coprime, then we have

$P(r+sM)-C_{n-1}^{1}P(r+(s-1)M)+C_{n-1}^{2}P(r+(s-2)M)+$
$...+(-1)^{s}C_{n-1}^{s}P(r)=\dfrac{M^{n-1}}{a_{1}a_{2}\ldots a_{n}}.$ (3.13)

Since the function $P(b)$ is a polynomial of degree $(n-1)$ with respect to
$\left[\dfrac{b}{M}\right]$, it can be found applying the interpolation
formula provided that its values at $n$ different points are known. In this
manner the formula which represents the value of $P(b)$ via the values of

$P(r+M),P(r+2M),\ldots P(r+nM).$

was obtained in [5].

However if $s\neq 0$, then (3.5), (3.2), and (3.11) enables us to represent
$P(b)$ via

$P(r),P(r+M),P(r+2M),\ldots P(r+(s-1)M),$

where $s\leqslant n-1$; at that the value of $s$ is quite small in some
particular cases (for instance, if $\sum_{i=1}^{n}a_{i}>>M$).

For instance, for the equation

$2x_{1}+3x_{2}+3x_{3}+3x_{4}+6x_{5}+6x_{6}+6x_{7}+6x_{8}+6x_{9}+6x_{10}=6005$

we have $s=\left[10-\dfrac{47+5}{6}\right]=1$.

But if $s=0$ and the numbers $a_{1},a_{2},...,a_{n}$ are coprime, then from
(3.5) and (3.11) we obtain

$P(b)=l_{0}C_{\left[\dfrac{b}{M}\right]+n-1}^{n-1},$

where $l_{0}=\dfrac{M^{n-1}}{a_{1}a_{2}\ldots a_{n}}$, and since according to
(3.3), $l_{0}=P(r)$, we obtain the following statement.

######  Theorem 3.3.

If $\left[n-\dfrac{\sum_{i=1}^{n}a_{i}+r}{M}\right]=0$ and the numbers
$a_{1},a_{2},...,a_{n}$ are coprime, then

$P(\sum_{i=1}^{n}a_{i}x_{i}=r)=\dfrac{M^{n-1}}{a_{1}a_{2}\ldots a_{n}}.$
(3.14)

and

$P(\sum_{i=1}^{n}a_{i}x_{i}=b)=\dfrac{M^{n-1}}{a_{1}a_{2}\ldots
a_{n}}C^{n-1}_{\left[\dfrac{b}{M}\right]+n-1}$ (3.15)

Since $r>(n-1)M-\sum_{i=1}^{n}a_{i}$ implies that
$s=\left[n-\dfrac{\sum_{i=1}^{n}a_{i}+r}{M}\right]=0$, from Theorem 3.3 we
obtain the following assertion.

######  Corollary 3.4.

If $r>(n-1)M-\sum_{i=1}^{n}a_{i}$ and the numbers $a_{1},a_{2},...,a_{n}$ are
coprime, then the values of $P(\sum_{i=1}^{n}a_{i}x_{i}=b)$ and
$P(\sum_{i=1}^{n}a_{i}x_{i}=r)$ can be found by formulas (3.15) and (3.14).

Consider now the case where $n=2$. Formulas (3.7), (3.8) and (3.10) imply the
Ehrhart’s result [2] by which we have that

$P(a_{1}x_{1}+a_{2}x_{2}=b)=\left[\dfrac{b}{M}\right]+P(r)$ (3.16)

if $(a_{1},a_{2})=1$ and $r$ is the remainder of $b$ modulo $M$, and,
moreover, that $P(r$) is equal to either $0$ or $1$.

At that [2]

$P(r)=\left\\{\begin{array}[]{llllllll}0&if&r<a_{1}+a_{2},&a_{1}\nmid
r,&and&a_{2}\nmid r;\\\ 1&if&r=a_{1}+a_{2},&or&a_{1}\mid r&or&a_{2}\mid
r.\end{array}\right.$ (3.17)

Moreover, as follows from Corollary 3.4,

$P(r)=1$ (3.18)

if $r>a_{1}a_{2}-(a_{1}+a_{2})$.

The equality

$(a_{1}a_{2}-(a_{1}+a_{2}))-(a_{1}+a_{2})=a_{1}(a_{2}-2)-2a_{2}$

implies that if either $a_{1}\geqslant 4$ and $a_{2}\geqslant 4$, or $a_{1}=3$
and $a_{2}>6$, then $a_{1}+a_{2}\leqslant a_{1}a_{2}-(a_{1}+a_{2})$. As is not
difficult to verify, in all other cases
$a_{1}a_{2}-(a_{1}+a_{2})<a_{1}+a_{2}$, and if
$r\in(a_{1}a_{2}-(a_{1}+a_{2}),a_{1}+a_{2}]$, then $P(r)=1$. Therefore (3.16),
(3.17) and (3.18) imply

######  Proposition 3.5.

Let $(a_{1},a_{2})=1$ and $1<a_{1}<a_{2}$. If either $a_{1}=2$, or $a_{1}=3$
and $a_{2}<6$, then we have

$P(a_{1}x_{1}+a_{2}x_{2}=b)=\left\\{\begin{array}[]{llllllll}\left[\dfrac{b}{a_{1}a_{2}}\right]+1,&if&r>a_{1}a_{2}-(a_{1}+a_{2});\\\
&or&r=a_{1}+a_{2};\\\ &or&a_{1}\mid r;\\\ &or&a_{2}\mid r;\\\
\left[\dfrac{b}{a_{1}a_{2}}\right],&otherwise.\end{array}\right.$ (3.19)

where $r$ is the remainder of $b$ modulo $a_{1}a_{2}$.

##  4\. Recurrent formulas for the number of integer non-negative solutions of
a linear Diophantine equation

Applying the formulas given in Sections 2-3, we obtain

######  Theorem 4.1.

We have

$\sum_{k=0}^{a_{1}+a_{2}+...+a_{n}-n}l^{\prime}_{k}P(\sum_{i=1}^{n}a_{i}x_{i}=b-k)=C^{n-1}_{b+n-1}$
(4.1)

where

$l^{\prime}_{0}=1,~{}l^{\prime}_{k}=C_{n-1+k}^{n-1}-\sum_{i=1}^{n}\overline{C}_{n-1+k-a_{i}}^{n-1}+\sum_{1\leq
i<j\leq n}\overline{C}_{n-1+k-a_{i}-a_{j}}^{n-1}-$

$\sum_{1\leq i<j<m\leq n}\overline{C}_{n-1+k-a_{i}-a_{j}-a_{m}}^{n-1}+...$
$(-1)^{n}\overline{C}_{n-1+k-\sum_{i=1}^{n}a_{i}}^{n-1},$ (4.2)

$(k=1,2,...,\sum_{i=1}^{n}a_{i}-n)$ and $\overline{C}^{m}_{k}$ is given by
(3.6).

###### Proof.

Using formula (2.8) for $a_{i}=1$ $(i=1,2,\ldots,n)$, we obtain

$P(\sum_{i=1}^{n}x_{i}=b)=\sum_{t_{1}=0}^{d_{1}-1}\sum_{t_{2}=0}^{d_{2}-1}\ldots\sum_{t_{n}=0}^{d_{n}-1}P(\sum_{i=1}^{n}d_{i}x_{i}=b-\sum_{i=1}^{n}t_{i}),$

for any natural $d_{1},d_{2},...,d_{n}$. This combined with formula (3.4)
implies

$\sum_{t_{1}=0}^{a_{1}-1}\sum_{t_{2}=0}^{a_{2}-1}\ldots\sum_{t_{n}=0}^{a_{n}-1}P(\sum_{i=1}^{n}a_{i}x_{i}=b-\sum_{i=1}^{n}t_{i})=C_{b+n-1}^{n-1},$
(4.3)

whence we obtain (4.1), where $l^{\prime}_{k}$
$(k=0,1,...,\sum_{i=1}^{n}a_{i}-n)$ is the number of integer non-negative
solutions of the system

$\sum_{i=1}^{n}t_{i}=k,$ $0\leqslant t_{i}\leqslant a_{i}-1,(i=1,2\ldots,n).$

Equality (2.1) implies that

$l^{\prime}_{k}=\sum_{\beta_{1}=0}^{1}\sum_{\beta_{2}=0}^{1}\ldots\sum_{\beta_{n}=0}^{1}(-1)^{\beta_{1}+\beta_{2}+\ldots+\beta_{n}}P(\sum_{i=1}^{n}x_{i}=k-\sum_{i=1}^{n}\beta_{i}a_{i}),$

for all $k=0,1,...,s$. This together with formula (3.4) gives:

$l^{\prime}_{k}=\sum_{\beta_{1}=0}^{1}\sum_{\beta_{2}=0}^{1}\ldots\sum_{\beta_{n}=0}^{1}(-1)^{\beta_{1}+\beta_{2}+\ldots+\beta_{n}}\overline{C}^{n-1}_{k-\sum_{i=1}^{n}\beta_{i}a_{i}+n-1}.$

∎

Formula (4.1) implies the recurrent formula for
$P(b)=P(\sum_{i=}^{n}a_{i}x_{i}=b),$ for any non-negative integer $b$. Namely,
we have

######  Corollary 4.2.

$P(\sum_{i=1}^{n}a_{i}x_{i}=b)=C_{b+n-1}^{n-1}-\sum_{k=1}^{a_{1}+a_{2}+...+a_{n}-n}l^{\prime}_{k}P(\sum_{i=1}^{n}a_{i}x_{i}=b-k),$
(4.4)

where $l^{\prime}_{k}$ $(k=1,2,...,\Sigma_{i=1}^{n}a_{i}-n)$ can be found by
formula (4.2).

In a similar manner one can prove the following recurrent formula for $P(b)$.

######  Theorem 4.3.

We have

$P(b)=\sum_{k=0}^{s^{*}}l^{*}_{k}P(\left[\dfrac{b}{m}\right]-k),$ (4.5)

where $m$ is an arbitrary natural number,

$s^{*}=\left[\dfrac{(m-1)\sum_{i=1}^{n}a_{i}-r)}{m}\right],$

$r$ is the remainder of $b$ modulo $m$, and $l^{*}_{k}$ $(k=0,1,2,\ldots,s*)$
is the number of integer non-negative solutions of the system

$\sum_{i=1}^{n}a_{i}t_{i}=r+km,$ $0\leqslant t_{i}\leqslant
m-1,(i=1,2,\ldots,n).$

###### Proof.

Applying (2.8) for $d_{i}=m$ $(i=1,2,...,n)$ we obtain:

$P(\sum_{i=1}^{n}a_{i}x_{i}=b)=\sum_{t_{1}=0}^{m-1}\sum_{t_{2}=0}^{m-1}\ldots\sum_{t_{n}=0}^{m-1}P(\sum_{i=1}^{n}a_{i}x_{i}=\dfrac{b-\sum_{i=1}^{n}a_{i}t_{i}}{m}).$
(4.6)

Since $\dfrac{b-\sum_{i=1}^{n}t_{i}}{m}$ is an integer if and only if
$\sum_{i=1}^{n}a_{i}t_{i}=r+km$ for some integer $k$, we obtain that

$0\leqslant r+km\leq\sum_{i=1}^{n}a_{i}(m-1)$

and

$0\leq k\leq\dfrac{(m-1)\sum_{i=1}^{n}a_{i}-r}{m}.$

And since

$\dfrac{b-(r+mk)}{m}=\left[\dfrac{b}{m}\right]-k,$

equality (4.6) implies (4.5). ∎

In particular, from (4.5) for $m=2$ we obtain the following statement.

######  Corollary 4.4.

We have

$P(b)=\left\\{\begin{array}[]{lllll}\sum_{k=0}^{s_{1}}P^{*}(2k)P(\dfrac{b}{2}-k)&if&b&is&even,\\\
\\\
\sum_{k=0}^{s_{2}}P^{*}(2k+1)P(\left[\dfrac{b}{2}\right]-k)&if&b&is&odd,\end{array}\right.$
(4.7)

where

$s_{1}=\left[\dfrac{\sum_{i=1}^{n}a_{i}}{2}\right],~{}s_{2}=\left[\dfrac{\sum_{i=1}^{n}a_{i}-1}{2}\right],$

and $P^{*}(d)$ denotes the number of integer non-negative solutions of the
system

$\sum_{i=1}^{n}a_{i}t_{i}=d,$ $0\leqslant t_{i}\leqslant 1,(i=1,2,\ldots,n).$

To calculate $P^{*}(d)$ $(d\in\mathbb{N})$ one can apply the following
recurrent formula

$P^{*}_{n}(d)=P^{*}_{n-1}(d)+P^{*}_{n-1}(d-a_{n}),$ (4.8)

where $P^{*}_{n}(d)=P^{*}(d)$ and $P^{*}_{n-1}(c)$ $(c\in\mathbb{Z})$ denotes
the number of integer non-negative solutions of the system

$\sum_{i=1}^{n-1}a_{i}t_{i}=c,$ $0\leq t_{i}\leq 1,~{}(i=1,2,\ldots,n-1),$

and also take into account the fact that if $c>\sum_{i=1}^{n-1}a_{i}$ or
$c<0$, then $P^{*}_{n-1}(c)=0$.

##  5\. Examples

In this section, employing the method described above we give examples of
finding the number of integer non-negative solutions of a linear Diophantine
equation.

Note that for a Diophantine equation $\sum_{i=1}^{3}a_{i}x_{i}=b$ with
pairwise coprime coefficients $a_{1},a_{2},a_{3}$, the formula is given in [2]
which represents the number $P(b)$ via $P(r)$, where $r$ is the remainder of
$b$ modulo $a_{1}a_{2}a_{3}$. In this paper we deal with Diophantine equations
where coefficients are not necessarily pairwise coprime.

######  Example 5.1.

Find the number $P(b)$ of integer non-negative solutions of the equation

$2x_{1}+4x_{2}+5x_{3}=b,$

where $b$ is an integer non-negative number.

To this end we apply formulas (3.5), (3.2) and (3.3). Here $n=3$,
$\sum_{i=1}^{3}a_{i}=11$, $M=20$,

$s=\left[3-\dfrac{11+r}{20}\right]=\left\\{\begin{array}[]{llllllll}2&if&r\leq
9,\\\ 1&if&r\geq 10.\end{array}\right.$

where $r$ is the remainder of $b$ modulo $20$.

Since the coefficients of the equation are coprime, according to formula
(3.11), $\sum_{i=0}^{2}l_{i}=10$ (at that, if $r\geqslant 10$, then
$l_{2}=0$). Therefore,

$P(b)=l_{0}C_{b^{\prime}+2}^{2}+l_{1}\overline{C}_{b^{\prime}+1}^{2}+l_{2}\overline{C}_{b^{\prime}}^{2},$
(5.1)

where $b^{\prime}=\left[\dfrac{b}{20}\right]$,

$l_{0}=P(r),~{}l_{1}=P(r+20)-3P(r),~{}l_{2}=10-l_{0}-l_{1}.$ (5.2)

To find $P(r)$ and $P(r+20)$ we apply formulas (4.4) and (4.2). We have
$\Sigma_{i=1}^{n}a_{i}-n=8$. Moreover, $\overline{C}_{l}^{3}=0$ for $l<3$.
Therefore, for any non-negative integer $d$ we obtain:

$P(d)=C_{d+2}^{2}-\sum_{k=1}^{8}l^{\prime}_{k}P(d-k),$

where

$l^{\prime}_{k}=C_{k+2}^{2}-(\overline{C}_{k}^{2}+\overline{C}_{k-2}^{2}+\overline{C}_{k-3}^{2})+(\overline{C}_{k-4}^{2}+\overline{C}_{k-5}^{2}),~{}(k=1,2,...,s).$

We get

$l^{\prime}_{1}=3,l^{\prime}_{2}=5,l^{\prime}_{3}=7,l^{\prime}_{4}=8,l^{\prime}_{5}=7,l^{\prime}_{6}=5,l^{\prime}_{7}=3,l^{\prime}_{8}=1,$
$P(1)=0,P(2)=1,P(3)=0,P(4)=2,P(5)=1,P(6)=2,P(7)=1,$
$P(8)=3,P(9)=2,P(10)=4,P(11)=2,P(12)=5,P(13)=3,$
$P(14)=6,P(15)=4,P(16)=7,P(17)=5,P(18)=8,P(19)=6,$
$P(20)=10,P(21)=7,P(22)=11,P(23)=8,P(24)=13,P(25)=10,$
$P(26)=14,P(27)=11,P(28)=16,P(29)=13.$

Substituting these values in formula (5.2), one can find, for each
$r=0,1,...,19$, the corresponding values of $l_{0},l_{1}$ and $l_{2}$. The
found values are given by the table below.

$r$ | 0;5 | 1 | 2;7 | 3 | 4;9 | 6;11 | 8;13 | 10;15 | 12;17 | 14;19 | 16 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---
$l_{0}$ | 1 | 0 | 1 | 0 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8
$l_{1}$ | 7 | 7 | 8 | 8 | 7 | 8 | 7 | 6 | 5 | 4 | 3 | 2
$l_{2}$ | 2 | 3 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0

Substituting these values in formula (5.1), one can find the value of the
function $P(b)$, for any integer non-negative $b$.

For instance, $P(214)=616$, since $\left[\dfrac{214}{20}\right]=10$, $r=14$,
$l_{0}=6$, $l_{1}=4$, $l_{2}=0$, and $P(214)=6C_{12}^{2}+4C_{11}^{2}$.

######  Example 5.2.

Find the number $P(826)$ of integer non-negative solutions of the equation

$2x_{1}+3x_{2}+4x_{3}+6x_{4}=826.$

We apply formulas (3.5), (3.2), (3.3), and (3.11).

Here $n=4$, $\sum_{i=1}^{4}a_{i}=15$, $M=12$, $b=826$,
$\left[\dfrac{b}{M}\right]=68$, $r=10$,
$s=\left[4-\dfrac{15+10}{12}\right]=1$, $l_{0}+l_{1}=12$. Hence

$P(826)=l_{0}C_{71}^{3}+l_{1}C_{70}^{3},$ (5.3)

where

$l_{0}=P(10),~{}l_{1}=12-P(10).$

As it is not difficult to observe, $P(10)=7$. Therefore $l_{0}=7$, $l_{1}=5$.
From (5.3) we obtain

$P(826)=7C_{71}^{3}+5C_{70}^{3}=673785.$

######  Example 5.3.

Find the number $P(b)$ of integer non-negative solutions of the equation

$2x_{1}+2x_{2}+3x_{3}+3x_{4}+3x_{5}+6x_{6}+6x_{7}=b,$

where $b$ is an integer non-negative number.

To this end we apply formulas (3.5), (3.3), (3.2), and (3.11). Here $n=7$,
$\sum_{i=1}^{7}a_{i}=25$, $M=6$, $s=\left[7-\dfrac{25+r}{6}\right]=2$, $r$ is
the remainder of $b$ modulo $6$, $\sum_{i=0}^{2}l_{i}=12$. Hence

$P(b)=l_{0}C_{b^{\prime}+6}^{6}+l_{1}\overline{C}_{b^{\prime}+5}^{6}+l_{2}\overline{C}_{b^{\prime}+4}^{6},$
(5.4)

where $b^{\prime}=\left[\dfrac{b}{6}\right]$ and

$l_{0}=P(r),~{}l_{1}=P(r+6)-7P(r),~{}l_{2}=12-l_{0}-l_{1}.$ (5.5)

Since $r+6\leq 11$, for finding $l_{0}$, $l_{1}$ and $l_{2}$ it suffices to
find $P(c)$ for all $c\leq 11$.

To calculate $P(r)$ and $P(r+6)$ we apply recurrent formulas (4.7) and (4.8).
As a result we obtain:

$P^{*}(0)=1,P^{*}(1)=0,P^{*}(2)=2,P^{*}(3)=3,P^{*}(4)=1,P^{*}(5)=6,P^{*}(6)=5,P^{*}(7)=3,P^{*}(8)=10,P^{*}(9)=7,P^{*}(10)=5,P^{*}(11)=14.$Therefore,
taking the fact that $P(c)=0$ for $c<0$ into account, we obtain that for even
$c$ we have

$P(c)=P(c^{\prime})+2P(c^{\prime}-1)+P(c^{\prime}-2)+5P(c^{\prime}-3)+10P(c^{\prime}-4)+5P(c^{\prime}-1),$

while for odd $c$ we have

$P(c)=3P(c^{\prime}-1)+6P(c^{\prime}-2)+3P(c^{\prime}-3)+7P(c^{\prime}-4)+14P(c^{\prime}-5),$

where $c^{\prime}=\left[\dfrac{c}{2}\right]$.

Since $P(0)=1$, we obtain:
$P(1)=0,P(2)=2,P(3)=3,P(4)=3,P(5)=6,P(6)=12,P(7)=9,P(8)=21,P(9)=28,P(10)=30,P(11)=47.$Substituting
these values in equality (5.4) we can find $l_{0}$, $l_{1}$, and $l_{2}$ for
$r=0,1,2,3,4,5$.

Next, substituting, for each $r=0,1,...,5$, the corresponding values of
$l_{0}$, $l_{1}$ and $l_{2}$ in formula (5.4), we obtain:

$P(b)=\left\\{\begin{array}[]{llllllll}C_{b^{\prime}+6}^{6}~{}+~{}5\overline{C}_{b^{\prime}+5}^{6}+6\overline{C}_{b^{\prime}+4}^{6}&if&r=0,\\\
9\overline{C}_{b^{\prime}+5}^{6}+3\overline{C}_{b^{\prime}+4}^{6}&if&r=1,\\\
2C_{b^{\prime}+6}^{6}+7\overline{C}_{b^{\prime}+5}^{6}+3\overline{C}_{b^{\prime}+4}^{6}&if&r=2,\\\
3C_{b^{\prime}+6}^{6}+7\overline{C}_{b^{\prime}+5}^{6}+2\overline{C}_{b^{\prime}+4}^{6}&if&r=3,\\\
3C_{b^{\prime}+6}^{6}+9\overline{C}_{b^{\prime}+5}^{6}&if&r=4,\\\
6C_{b^{\prime}+6}^{6}+5\overline{C}_{b^{\prime}+5}^{6}+\overline{C}_{b^{\prime}+4}^{6}&if&r=5.\end{array}\right.$

For instance,

$P(49)=9C_{13}^{6}+3C_{12}^{6}=18216.$

######  Example 5.4.

Find the number $P(b)$ of integer non-negative solutions of the equation

$x_{1}+2x_{2}+3x_{3}+4x_{4}+5x_{5}+6x_{6}+7x_{7}=101.$

Apply the recurrent formulas (4.7) and (4.8). Since $\sum_{i=1}^{7}a_{i}=28$,
we need to find $P^{*}(c)$ for all $c\leq 28$. Applying formula (4.8), we
obtain:

$P^{*}(0)=1$, $P^{*}(1)=1$, $P^{*}(2)=1$, $P^{*}(3)=2$, $P^{*}(4)=2$,
$P^{*}(5)=3$, $P^{*}(6)=4$, $P^{*}(7)=5$, $P^{*}(8)=5$, $P^{*}(9)=6$,
$P^{*}(10)=7$, $P^{*}(11)=7$, $P^{*}(12)=8$, $P^{*}(13)=8$, $P^{*}(14)=8$,
$P^{*}(15)=8$, $P^{*}(16)=8$, $P^{*}(17)=7$, $P^{*}(18)=7$, $P^{*}(19)=6$,
$P^{*}(20)=5$, $P^{*}(21)=5$, $P^{*}(22)=4$, $P^{*}(23)=3$, $P^{*}(24)=2$,
$P^{*}(25)=2$, $P^{*}(26)=1$, $P^{*}(27)=1$, $P^{*}(28)=1$.

Therefore from (4.7) we can conclude that if $c$ is even, then

$P(c)=P(c^{\prime})+P(c^{\prime}-1)+2P(c^{\prime}-2)+4P(c^{\prime}-3)+$
$5P(c^{\prime}-4)+7P(c^{\prime}-5)+8P(c^{\prime}-6)+8P(c^{\prime}-7)+8P(c^{\prime}-8)+7P(c^{\prime}-9)+$
$5P(c^{\prime}-10)+4P(c^{\prime}-11)+2P(c^{\prime}-12)+P(c^{\prime}-13)+P(c^{\prime}-14).$

But if $c$ is odd, then

$P(c)=P(c^{\prime})+2P(c^{\prime}-1)+3P(c^{\prime}-2)+5P(c^{\prime}-3)+$
$6P(c^{\prime}-4)+7P(c^{\prime}-5)+8P(c^{\prime}-6)+8P(c^{\prime}-7)+7P(c^{\prime}-8)+6P(c^{\prime}-9)+$
$5P(c^{\prime}-10)+3P(c^{\prime}-11)+2P(c^{\prime}-12)+P(c^{\prime}-13),$
(5.6)

where $c^{\prime}=\left[\dfrac{c}{2}\right]$.

Hence

$P(101)=P(50)+2P(49)+3P(48)+5P(47)+6P(46)+7P(45)+8P(44)+$
$8P(43)+7P(42)+6P(41)+5P(40)+3P(39)+2P(38)+P(37).$

In a similar manner, representing $P(50)$, $P(49)$,…, $P(37)$ via $P(25)$,
$P(24)$, …, $P(0)$ with the aid of (5.6), we obtain that

$P(101)=P(25)+6P(24)+20P(23)+47P(22)+91P(21)+$
$154P(20)+230P(19)+312P(18)+389P(17)+445P(16)+471P(15)+$
$463P(14)+420P(13)+352P(12)+272P(11)+190P(10)+120P(9)+$
$67P(8)+31P(7)+12P(6)+3P(5).$ (5.7)

Taking the fact that $P(0)=1$ into account, from formula (5.6) we obtain:

$P(1)=1$, $P(2)=2$, $P(3)=3$, $P(4)=5$, $P(5)=7$, $P(6)=11$, $P(7)=15$,
$P(8)=21$, $P(9)=28$, $P(10)=38$, $P(11)=49$, $P(12)=65$, $P(13)=82$,
$P(14)=105$, $P(15)=131$, $P(16)=164$, $P(17)=201$, $P(18)=248$, $P(19)=300$,
$P(20)=364$, $P(21)=436$, $P(22)=522$, $P(23)=618$, $P(24)=733$, $P(25)=860$.

Substituting these values in formula (5.7), we obtain

$P(101)=628998.$

######  Example 5.5.

Find the number $P(9005)$ of integer non-negative solutions of the equation

$x_{1}+5x_{2}+10x_{3}+10x_{4}+...+10x_{n}=9005,$

where $n\geq 3$.

Here $\sum_{i=1}^{n}a_{i}=6+10(n-2)$, $M=10$,
$M(n-1)-\sum_{i=1}^{n}a_{i}=10(n-1)-6-10(n-2)=4$, $r=5$ is the remainder of
$9005$ modulo $10$. Since $r>M(n-1)-\sum_{i=1}^{n}a_{i}$, Corollary 3.4
implies

$P(9005)=\dfrac{M^{n-1}}{a_{1}a_{2}\ldots
a_{n}}C^{n-1}_{\left[\dfrac{9005}{10}\right]+(n-1)}$

Since $\dfrac{M^{n-1}}{a_{1}a_{2}\ldots a_{n}}=2$, we obtain

$P(9005)=2C_{900+n-1}^{n-1}.$

For instance, for $n=4$ we obtain $P(9005)=2C_{903}^{3}=244623302$.

######  Example 5.6.

Find the number $P(b)$ of integer non-negative solutions of the equation

$x_{1}+kx_{2}+kx_{3}+\ldots+kx_{n}=b,$

where $k,n\in\mathbb{N}$, $n\geq 2$, $b$ is a non-negative integer. Here we
have $\sum_{i=1}^{n}a_{i}=1+k(n-1)$, $M=k$, $s=0$. Therefore (3.14) implies

$P(x_{1}+kx_{2}+kx_{3}+\ldots+kx_{n}=b)=C^{n-1}_{\left[\dfrac{b}{k}\right]+(n-1)}.$
(5.8)

######  Example 5.7.

Find the number $P(b)$ of integer non-negative solutions of the equation

$ax_{1}+2x_{2}+2ax_{3}+2ax_{4}+\ldots+2ax_{n}=b,$ (5.9)

where $n\geq 2$, $a$ is a natural odd number which is different from $1$, and
$b$ is a non-negative integer.

To investigate the function $P(b)$ we apply equalities (3.5), (3.2), (3.3),
and (3.11). We have

$s=\left[n-\dfrac{a+2+2a(n-2)+r}{2a}\right]=\left[2-\dfrac{a+2+r}{2a}\right],$

where $r$ is the remainder of $b$ modulo $2a$.

This implies that if $r>a-2$, we have $s=0$, and according to Theorem 3.3, we
obtain that

$P(b)=C^{n-1}_{\left[\dfrac{b}{2a}\right]+n-1}.$ (5.10)

in that case.

If $r\leqslant a-2$, then $s=1$. Moreover, formula (3.11) implies that
$l_{0}+l_{1}=1$. Therefore we can conclude that either $l_{0}=1$ and
$l_{1}=0$, or $l_{0}=0$ and $l_{1}=1$. Since $l_{0}=P(r)$, from (3.5) we
obtain that if $r\leqslant a-2$, then

$P(b)=\left\\{\begin{array}[]{lll}C_{\left[\dfrac{b}{2a}\right]+n-1}^{n-1}&if&P(r)=1,\\\
\\\
\overline{C}_{\left[\dfrac{b}{2a}\right]+n-2}^{n-1}&if&P(r)=0.\end{array}\right.$
(5.11)

Since $P(r)=P(ax_{1}+2x_{2}=r)$, formulas (3.19), (3.16), (3.17), (3.18) and
(5.11) imply that

$P(b)=\left\\{\begin{array}[]{llllllll}C^{n-1}_{\left[\dfrac{b}{2a}\right]+n-1}&if&r>a-2,\\\
&or&r&is&even,\\\ \\\
\overline{C}^{n-1}_{\left[\dfrac{b}{2a}\right]+n-2}&otherwise.\end{array}\right.$

## References

  * [1] E. T. Bell, Interpolated denumerants and Lambert series, Amer. J. Math. 65(1943), 382-386.
  * [2] E. Ehrhart, Sur un probléme de géometrie diophantienne linéare II. Journal fur reine und angewanandte Mathematik. 227(1967), 25-49.
  * [3] I. I. Ezhov, A. V. Skorokhod, I. I. Yadrenko, Elements of combinatorics, ”Nauka”, 1977.
  * [4] G. Polya, G. Szego, Aufgaben und Lehrsa̋tze aus der Analysis. Springer-Verlag, New York, 1964.
  * [5] J. Riordan, An introduction to combinatorial analysis. John Willey Sons, Inc., New York, 1958.
  * [6] E. T. Samsonadze, The formulas for the number of integer non-negative solutions of linear equations and inequalities. Proc. Tbilisi State University, 239 (1983), 36-42.

Author’s address:

Eteri Samsonadze, Retd., I. Javakhishvili Tbilisi State University,

1 Tchavchavadze Av., Tbilisi, 0179, Georgia,

e-mail<EMAIL_ADDRESS>


# A stability result for almost perfect matchings111Supported by National Key
R&D Program of China under grant No. 2023YFA1010203 and the National Natural
Science Foundation of China under grant No.12271425

Mingyang Guo, Hongliang Lu222Corresponding email<EMAIL_ADDRESS>
School of Mathematics and Statistics
Xi’an Jiaotong University
Xi’an, Shaanxi 710049, China

###### Abstract

Let $n,k,s$ be three integers and $\beta$ be a sufficiently small positive
number such that $k\geq 3$, $0<1/n\ll\beta\ll 1/k$ and $ks+k\leq
n\leq(1+\beta)ks+k-2$. A $k$-graph is called non-trivial if it has no isolated
vertex. In this paper, we determine the maximum number of edges in a non-
trivial $k$-graph with $n$ vertices and matching number at most $s$. This
result confirms a conjecture proposed by Frankl (On non-trivial families
without a perfect matching, _European J. Combin._ , 84 (2020), 103044) for the
case when $s$ is sufficiently large.

##  1 Introduction

For integers $n>k\geq 1$, let $[n]:=\\{1,2,\cdots,n\\}$ be the standard $n$
element set and $\binom{[n]}{k}=\\{T\subseteq[n]:|T|=k\\}$ be the collection
of all its $k$-subsets. A $k$-uniform hypergraph defined on $[n]$ is a family
$\mathcal{F}$ such that $\mathcal{F}\subseteq\binom{[n]}{k}$. A $k$-uniform
hypergraph is also called a _$k$ -graph_. For a $k$-graph
$\mathcal{F}\subseteq\binom{[n]}{k}$, let $\nu(\mathcal{F})$ denote the
matching number of $\mathcal{F}$, that is, the maximum number of pairwise
disjoint members of $\mathcal{F}$.

Let $n,s,k$ be three positive integers such that $k\geq 2$ and $n\geq ks+k-1$.
For each $i\in[k]$, define

$\mathcal{A}_{i}(n,k,s):=\left\\{A\in\binom{[n]}{k}:|A\cap[(s+1)i-1]|\geq
i\right\\}.$

In 1965, Erdős [5] asked for the determination of the maximum possible number
of edges that can appear in any $k$-graph $\mathcal{F}$ with
$\nu(\mathcal{F})\leq s$. He conjectured that $\mathcal{A}_{1}(n,k,s)$ and
$\mathcal{A}_{k}(n,k,s)$ are the two extremal constructions of this problem.

######  Conjecture 1.1 (Erdős Matching Conjecture [5]).

Let $n,s,k$ be three positive integers such that $k\geq 2$ and $n\geq
k(s+1)-1$. If $\mathcal{F}$ is a $k$-graph on $[n]$ and $\nu(\mathcal{F})\leq
s$, then

$|\mathcal{F}|\leq\max\left\\{\binom{n}{k}-\binom{n-s}{k},\binom{k(s+1)-1}{k}\right\\}.$

There have been recent activities on the Erdős Matching Conjecture, see [1, 2,
4, 3, 5, 8, 9, 10, 11, 12, 14, 18, 21, 20, 7, 19]. The Erdős Matching
Conjecture was verified by Erdős and Gallai [3] for $k=2$. For $k\geq 3$, it
was proved by Bollobás, Daykin and Erdős [2] for $n>2k^{3}s$. Subsequently,
Huang, Loh and Sudakov [18] settled the conjecture for $n>3k^{2}(s+1)$. In
2013, Frankl [8] verified the conjecture for $n\geq(2s+1)k-s$. Recently,
Frankl and Kupavskii [14] proved the conjecture for
$n\geq\frac{5}{3}sk-\frac{2}{3}s$ and sufficiently large $s$. As for the
special case of $k=3$, Frankl, Rödl and Ruciński [7] proved the conjecture for
$n\geq 4s$. In particular, the Erdős Matching Conjecture was settled for $k=3$
and sufficiently large $n$ in [21], and finally, it was completely resolved
for $k=3$ in [10].

A _vertex cover_ in a $k$-graph $\mathcal{F}$ is a set of vertices which
intersects all edges of $\mathcal{F}$. We use $\tau(\mathcal{F})$ to denote
the minimum size of a vertex cover in $\mathcal{F}$. Bollobás, Daykin and
Erdős [2] proved a stability result of Conjecture 1.1 for $n>2k^{3}s$.

######  Theorem 1.1 (Bollobás, Daykin and Erdős [2]).

Let $n,s,k$ be three positive integers such that $k\geq 2$ and $n>2k^{3}s$. If
$\mathcal{F}$ is a $k$-graph on $[n]$ and $\nu(\mathcal{F})\leq
s<\tau(\mathcal{F})$, then

$|\mathcal{F}|\leq\binom{n}{k}-\binom{n-s}{k}-\binom{n-s-k}{k-1}+1.$ (1)

Remark: The condition (1) is tight. Define

$\mathcal{B}(n,k,s):=\left\\{B\in\binom{[n]}{k}:B\cap[s-1]\neq\emptyset\right\\}\cup\left\\{S\right\\}\cup\left\\{B\in\binom{[n]}{k}:s\in
B,B\cap S\neq\emptyset\right\\},$

where $S:=\\{s+1,\ldots,s+k\\}$. Note that
$|\mathcal{B}(n,k,s)|=\binom{n}{k}-\binom{n-s}{k}-\binom{n-s-k}{k-1}+1$,
$\nu(\mathcal{B}(n,k,s))=s$ and $\tau(\mathcal{B}(n,k,s))=s+1$.

Theorem 1.1 shows that if $\nu(\mathcal{F})\leq s$ and
$|\mathcal{F}|>|\mathcal{B}(n,k,s)|$, then $\tau(\mathcal{F})\leq s$. That is,
$\mathcal{F}$ is a subgraph of $\mathcal{A}_{1}(n,k,s)$.

Frankl and Kupavskii [12] improved the result in Theorem 1.1 by proving that
for $k\geq 3$ and either $n\geq(s+\max\\{25,2s+2\\})k$ or $n\geq(2+o(1))sk$,
where $o(1)$ is with respect to $s\rightarrow\infty$, if $\mathcal{F}$ is a
$k$-graph with $\nu(\mathcal{F})=s$ and $\tau(\mathcal{F})>s$, then
$|\mathcal{F}|\leq\binom{n}{k}-\binom{n-s}{k}-\binom{n-s-k}{k-1}+1$. For the
case $s=1$, a classical result of Hilton and Milner [17] shows that for a
$k$-graph $\mathcal{F}$, if $\nu(\mathcal{F})=1$ and $\tau(\mathcal{F})>1$,
then $|\mathcal{F}|\leq\binom{n-1}{k-1}-\binom{n-k-1}{k-1}+1$ for $n>2k$. This
can be seen as a stability result of the famous Erdős-Ko-Rado theorem [4].

Frankl and Kupavskii [12] conjectured there are several different extremal
graphs for the stability problem and proposed the following conjecture.

######  Conjecture 1.2 (Frankl and Kupavskii [12]).

Suppose that $\mathcal{F}$ is a $k$-graph on vertex set $[n]$. If
$\nu(\mathcal{F})=s$ and $\tau(\mathcal{F})>s$, then

$\mathcal{F}\leq\max\\{|\mathcal{A}_{2}(n,k,s)|,\ldots,|\mathcal{A}_{k}(n,k,s)|,|\mathcal{B}(n,k,s)|\\}.$

Guo, Lu and Mao [15] confirm Conjecture 1.2 for $k=3$ and sufficiently large
$n$.

A majority of the works on Erdős Matching Conjecture deal with the regimes
when $\mathcal{A}_{1}(n,k,s)$ is larger than $\mathcal{A}_{k}(n,k,s)$. Frankl
[9] proved that if a $k$-graph $\mathcal{F}$ on $[n]$ satisfies
$\nu(\mathcal{F})\leq s$, then $|\mathcal{F}|\leq|\mathcal{A}_{k}(n,k,s)|$ for
$k(s+1)\leq n\leq(k+k^{-2k-1}/2)(s+1)$. This is the first result proving Erdős
Matching Conjecture for a range where $\mathcal{A}_{k}(n,k,s)$ is larger than
$\mathcal{A}_{1}(n,k,s)$. Recently, Kolupaev and Kupavskii [19] improved the
bounds by proving that Erdős Matching Conjecture holds for $k(s+1)\leq
n\leq(k+1/(100k))(s+1)$.

Define

$\begin{split}\mathcal{E}_{0}(n,k,s):=\binom{[ks+k-2]}{k}\cup\left\\{A\in\binom{[n]}{k}:A\setminus[ks+k-2]=\\{ks+k-1\\},A\cap[k-1]\neq\emptyset\right\\}\\\
\cup\left\\{[k-1]\cup\\{x\\}:ks+k\leq x\leq n\right\\}\end{split}$

and

$\begin{split}\mathcal{E}_{1}(n,k,s):=\binom{[ks+k-2]}{k}\cup\left(\bigcup_{x\in[ks+k-1,n]}\left\\{A\in\binom{[n]}{k}:A\setminus[ks+k-2]=\\{x\\},1\in
A\right\\}\right).\end{split}$

We followed the notation of [13]. A $k$-graph $\mathcal{F}$ called non-trivial
if there is no isolated vertex in $\mathcal{F}$. Frankl [13] proved the
following theorem.

######  Theorem 1.2 (Frankl [13]).

For any integer $k\geq 2$, there exists a positive integer $s_{0}$ such that
the following holds. Let $s$ be a positive integer such that $s>s_{0}$.
Suppose that $\mathcal{F}$ is a non-trivial $k$-graph on $(ks+k)$ vertices. If
$\nu(H)\leq s$, then

$|\mathcal{F}|\leq|\mathcal{E}_{0}(ks+k,k,s)|.$

This result shows that if a $k$-graph $\mathcal{F}$ with $(ks+k)$ vertices
satisfies $\nu(\mathcal{F})\leq s$ and
$|\mathcal{F}|>|\mathcal{E}_{0}(ks+k,k,s)|$, then $\mathcal{F}$ is a subgraph
of $\mathcal{A}_{k}(ks+k,k,s)$. Thus the result can be seen as a stability
result on Erdős Matching Conjecture for the case when $\mathcal{A}_{k}(n,k,s)$
is larger than $\mathcal{A}_{1}(n,k,s)$. For $n>ks+k$, Frankl [13] proposed
the following conjecture.

######  Conjecture 1.3 (Frankl [13]).

For any integer $\ell\geq 1$, there exists a positive integer $k_{0}$ such
that the following holds. Let $n,s,k$ be integers such that $s\geq 5$,
$k>k_{0}$ and $n=k(s+1)+\ell$. Suppose that
$\mathcal{F}\subseteq\binom{[n]}{k}$. If $\mathcal{F}$ is non-trivial and
$\nu(\mathcal{F})\leq s$, then

$|\mathcal{F}|\leq|\mathcal{E}_{0}(n,k,s)|.$

In this paper, we focus on the stability problem on Erdős Matching Conjecture
for a range where $\mathcal{A}_{k}(n,k,s)$ is larger than
$\mathcal{A}_{1}(n,k,s)$. By $x\ll y$ we mean that for any $y>0$ there exists
$x_{0}>0$ such that for any $x<x_{0}$ the following statement holds. We omit
the floor and ceiling functions when they do not affect the proof. The
following theorem is our main result.

######  Theorem 1.3.

For any integer $k\geq 3$, there exist $\beta>0$ and a positive integer
$s_{0}$ such that the following holds. Let $n,s$ be two integers such that
$s>s_{0}$ and $ks+k\leq n\leq(1+\beta)ks+k-2$. Suppose that
$\mathcal{F}\subseteq\binom{[n]}{k}$. If $\mathcal{F}$ is non-trivial and
$\nu(\mathcal{F})\leq s$, then

$|\mathcal{F}|\leq\max\\{|\mathcal{E}_{0}(n,k,s)|,|\mathcal{E}_{1}(n,k,s)|\\}.$

Theorem 1.3 implies the following result, which confirms Conjecture 1.3 for
sufficiently large $s$.

######  Corollary 1.4.

For any integers $k\geq 3$ and $\ell\geq 1$, there exists a positive integer
$s_{0}$ such that the following holds. Let $n,s$ be two integers such that
$s>s_{0}$ and $n=k(s+1)+\ell$. Suppose that
$\mathcal{F}\subseteq\binom{[n]}{k}$. If $\mathcal{F}$ is non-trivial and
$\nu(\mathcal{F})\leq s$, then

$|\mathcal{F}|\leq\left\\{\begin{aligned} &|\mathcal{E}_{0}(n,k,s)|,\
\text{if}\ k>\ell+3;\\\ &|\mathcal{E}_{1}(n,k,s)|,\ \text{if}\
k\leq\ell+3.\end{aligned}\right.$

Proof. By Theorem 1.3, there exists a positive integer $s_{0}^{\prime}$ such
that $|\mathcal{F}|\leq\max_{i\in\\{0,1\\}}\\{|\mathcal{E}_{i}(n,k,s)|\\}$ for
$s>s_{0}^{\prime}$. Note that

$|\mathcal{E}_{0}(n,k,s)|=\binom{ks+k-2}{k}+\binom{ks+k-2}{k-1}-\binom{ks-1}{k-1}+\ell+1$

and

$|\mathcal{E}_{1}(n,k,s)|=\binom{ks+k-2}{k}+(\ell+2)\binom{ks+k-3}{k-2}.$

For $k>\ell+3$, one can see that there exists an integer
$s_{0}^{\prime\prime}$ such that for $s>s^{\prime\prime}_{0}$,

$\begin{split}|\mathcal{E}_{0}(n,k,s)|-|\mathcal{E}_{1}(n,k,s)|&=\binom{ks+k-2}{k-1}-\binom{ks-1}{k-1}+\ell+1-\left(\ell+2\right)\binom{ks+k-3}{k-2}\\\
&>(k-1)\binom{ks-1}{k-2}-\left(\ell+2\right)\binom{ks+k-3}{k-2}\\\
&=\binom{ks-1}{k-2}-\left((\ell+2)\binom{ks+k-3}{k-2}-(k-2)\binom{ks-1}{k-2}\right)\\\
&\geq\binom{ks-1}{k-2}-(k-2)\left(\binom{ks+k-3}{k-2}-\binom{ks-1}{k-2}\right)\\\
&>\binom{ks-1}{k-2}-(k-2)^{2}\binom{ks+k-3}{k-3}\\\ &>0.\end{split}$

For $k\leq\ell+3$, one can see that

$\begin{split}&|\mathcal{E}_{1}(n,k,s)|-|\mathcal{E}_{0}(n,k,s)|\\\
=&(\ell+2)\binom{ks+k-3}{k-2}-\left(\binom{ks+k-2}{k-1}-\binom{ks-1}{k-1}+\ell+1\right)\\\
=&(\ell+2)\binom{ks+k-3}{k-2}-\left(\sum_{i=1}^{k-1}\binom{ks+k-2-i}{k-2}+\ell+1\right)\\\
=&((\ell+2)-(k-1))\left(\binom{ks+k-3}{k-2}-1\right)+\sum_{i=1}^{k-1}\left(\binom{ks+k-3}{k-2}-\binom{ks+k-2-i}{k-2}\right)-(k-2)\\\
\geq&0\end{split}$

holds for all $k\geq 3$ and $s\geq 1$. Let
$s_{0}=\max\\{s_{0}^{\prime},s_{0}^{\prime\prime}\\}$, then

$|\mathcal{F}|\leq\left\\{\begin{aligned} &|\mathcal{E}_{0}(n,k,s)|,\
\text{if}\ k>\ell+3;\\\ &|\mathcal{E}_{1}(n,k,s)|,\ \text{if}\
k\leq\ell+3.\end{aligned}\right.$

for $s>s_{0}$. ∎

The following corollary can be seen as a stability result on Erdős Matching
Conjecture for a range where $\mathcal{A}_{k}(n,k,s)$ is larger than
$\mathcal{A}_{1}(n,k,s)$. Let $\mathcal{F}\subset\binom{[n]}{k}$ be a
$k$-graph. For a subset $S\subseteq[n]$, we use $\mathcal{F}[S]$ to denote the
sub-hypergraph with vertex set $S$ and edge set $\\{F\in\mathcal{F}:F\subseteq
S\\}$.

######  Corollary 1.5.

For any integer $k\geq 3$, there exist $\beta>0$ and a positive integer
$s_{0}$ such that the following holds. Let $n,s$ be two integers such that
$s>s_{0}$ and $ks+k\leq n\leq(1+\beta)ks+k-2$. Suppose that
$\mathcal{F}\subseteq\binom{[n]}{k}$. If $\nu(\mathcal{F})\leq s$ and

$|\mathcal{F}|>\max\\{|\mathcal{E}_{0}(n,k,s)|,|\mathcal{E}_{1}(n,k,s)|\\},$

then $\mathcal{F}$ is a subgraph of $\mathcal{A}_{k}(n,k,s)$.

Proof. Let $I$ be the set of isolated vertices in $\mathcal{F}$ and
$S=[n]\setminus I$. Suppose that $\mathcal{F}$ is not a subgraph of
$\mathcal{A}_{k}(n,k,s)$, then $|I|\leq n-(ks+k)$. Thus $\mathcal{F}[S]$ is a
non-trivial $k$-graph on $S$ with $n\geq|S|\geq ks+k$. By Theorem 1.3, there
exists an integer $s_{0}$ such that

$|\mathcal{F}|=|\mathcal{F}[S]|\leq\max_{i\in\\{0,1\\}}\\{|\mathcal{E}_{i}(|S|,k,s)|\\}\leq\max_{i\in\\{0,1\\}}\\{|\mathcal{E}_{i}(n,k,s)|$

for $s>s_{0}$, a contradiction. ∎

##  2 shifting

Let $\mathcal{F}$ be a $k$-graph on vertex set $[n]$. For vertices $1\leq
x<y\leq n$, we define the _$(x,y)$ -shift_ $S_{x,y}$ by
$S_{x,y}(\mathcal{F})=\\{S_{x,y}(F):F\in\mathcal{F}\\}$, where

$S_{x,y}(F)=\begin{cases}F\setminus\\{y\\}\cup\\{x\\},&\text{if $y\in F$,
$x\notin F$ and $F\setminus\\{y\\}\cup\\{x\\}\notin\mathcal{F}$;}\\\
F,&\text{otherwise.}\end{cases}$

The following well-known result can be found in [6].

######  Lemma 2.1.

The $(x,y)$-shift satisfies the following properties.

  1. $($i$)$

$|\mathcal{F}|=|S_{x,y}(\mathcal{F})|$ and $|F|=|S_{x,y}(F)|$ for any
$F\in\mathcal{F}$,

  2. $($ii$)$

$\nu(S_{x,y}(\mathcal{F}))\leq\nu(\mathcal{F})$.

For a $k$-graph $\mathcal{F}$, define
$N_{\mathcal{F}}(x)=\\{F\setminus\\{x\\}:x\in F\in\mathcal{F}\\}$,
$N_{\mathcal{F}}(x,y)=\\{F\setminus\\{x,y\\}:x,y\in F\in\mathcal{F}\\}$ and
$N_{\mathcal{F}}(x,\overline{y})=\\{F\setminus\\{x\\}:x\in
F\in\mathcal{F},y\notin F\\}$.

######  Proposition 2.2 (Frankl [13]).

Suppose that $\mathcal{F}\subseteq\binom{[n]}{k}$, then the following hold.

  1. $($i$)$

If $|N_{\mathcal{F}}(x)|\geq|N_{\mathcal{F}}(y)|$ and
$\widetilde{\mathcal{F}}:=S_{x,y}(\mathcal{F})\neq\mathcal{F}$, then

$\sum_{i\in[n]}|N_{\widetilde{\mathcal{F}}}(i)|^{2}>\sum_{i\in[n]}|N_{\mathcal{F}}(i)|^{2}.$
(2)

  2. $($ii$)$

If $\mathcal{F}$ is non-trivial and
$\widetilde{\mathcal{F}}=S_{x,y}(\mathcal{F})$ has isolated vertex, then
$|N_{\mathcal{F}}(x,y)|=\emptyset$ and
$|N_{\mathcal{F}}(x,\overline{y})|+|N_{\mathcal{F}}(y,\overline{x})|\leq\binom{n-2}{k-1}$.

Let us say that the $(x,y)$-shift $S_{x,y}$ is _meaningful_ if (2) holds.
Noting the obvious upper bound

$\sum_{x\in[n]}|N_{\mathcal{F}}(x)|^{2}\leq n|\mathcal{F}|^{2},$

one concludes that there can be only a _limited_ number of successive
meaningful shifts. For a subset $Y\subset[n]$, we say that
$\mathcal{F}\subseteq\binom{[n]}{k}$ is _shifted_ on $Y$ if
$S_{i,j}(\mathcal{F})=\mathcal{F}$ holds for all $1\leq i<j\leq n$,
$\\{i,j\\}\subset Y$. It is not difficult to see that if $\mathcal{F}$ is
shifted on $Y$, then for any subsets
$\\{u_{1},\ldots,u_{k}\\},\\{v_{1},\ldots,v_{k}\\}\subset Y$ such that
$u_{i}\leq v_{i}$ for $i\in[k]$, $\\{v_{1},\ldots,v_{k}\\}\in\mathcal{F}$
implies $\\{u_{1},\ldots,u_{k}\\}\in\mathcal{F}$. Let $\omega(\mathcal{F})$ be
the number of vertices in the largest complete subgraph of $\mathcal{F}$.

######  Lemma 2.3.

For any integer $k\geq 3$ and positive real $\varepsilon<1/k$, there exists
$s_{0}(k,\varepsilon)$ such that the following holds. Let
$0<\eta<\frac{\varepsilon^{k}}{3^{k+2}k!}$ and $n,s$ be positive integers such
that $s>s_{0}$ and $(1-\eta)ks\leq n\leq(1+\eta)ks+k-2$. Suppose that
$\mathcal{F}\subseteq\binom{[n]}{k}$ and
$|\mathcal{F}|>\binom{ks+k-2}{k}-3\eta(ks)^{k}$. If $\mathcal{F}$ is shifted
on $[n]$, then $\omega(\mathcal{F})\geq(1-\varepsilon)ks$.

Proof. Suppose that $\omega(\mathcal{F})<(1-\varepsilon)ks$. Let
$S=[n]\setminus[(1-\varepsilon)ks]$, then $\mathcal{F}[S]=\emptyset$ since
$\mathcal{F}$ is shifted on $[n]$. Thus
$|\mathcal{F}|<\binom{n}{k}-\binom{|S|}{k}$. Note that $|S|\geq
n-(1-\varepsilon)ks>(\varepsilon-\eta)ks\geq\varepsilon ks/2$. Combining with
$|\mathcal{F}|>\binom{ks+k-2}{k}-3\eta(ks)^{k}$, we have
$\binom{n}{k}-\binom{|S|}{k}>\binom{ks+k-2}{k}-3\eta(ks)^{k}$. That is

$\binom{n}{k}-\binom{ks+k-2}{k}+3\eta(ks)^{k}>\binom{|S|}{k}.$ (3)

Since

$\begin{split}\binom{n}{k}-\binom{ks+k-2}{k}\leq&\binom{(1+\eta)ks+k-2}{k}-\binom{ks+k-2}{k}\\\
\leq&\eta ks\binom{(1+\eta)ks+k-2}{k-1}\\\ \leq&\eta
ks\binom{(1+2\eta)ks}{k-1}\\\
\leq&\frac{(1+2\eta)^{k-1}\eta(ks)^{k}}{(k-1)!}\\\
\leq&\frac{2^{k-1}\eta(ks)^{k}}{(k-1)!}\end{split}$

and

$\binom{|S|}{k}\geq\frac{(\varepsilon
ks/2-k)^{k}}{k!}\geq\frac{\varepsilon^{k}(ks)^{k}}{3^{k}k!},$

inequality (3) implies

$\frac{\varepsilon^{k}}{3^{k}k!}\leq\frac{2^{k-1}\eta}{(k-1)!}+3\eta\leq
5\eta,$

a contradiction. ∎

Using some ideas from [13], we prove that if the number of edges in
$\mathcal{F}$ is large enough, then we can perform shifts on most of vertices
without destroying non-triviality.

######  Lemma 2.4.

For any integer $k\geq 3$ and positive real $\beta\leq\frac{1}{9k}$, there
exists $s_{0}(k,\beta)$ such that the following holds. Let $n,s$ be integers
such that $s>s_{0}$ and $ks+k\leq n\leq(1+\beta)ks+k-2$. Suppose that
$\mathcal{F}\subseteq\binom{[n]}{k}$, $|\mathcal{F}|\geq\binom{ks+k-2}{k}$ and
$\mathcal{F}$ is non-trivial. Then there is a $k$-graph
$\mathcal{F}^{*}\subseteq\binom{[n]}{k}$ obtained from $\mathcal{F}$ via
successive shifts such that $\mathcal{F}^{*}$ is non-trivial and shifted on
$[n-3\beta ks]$.

Proof. We try and find $1\leq x<y\leq n-3\beta ks$ such that the $(x,y)$-shift
$S_{x,y}$ is meaningful and we rename the elements of $[n]$ after
$(x,y)$-shift $S_{x,y}$ so that the new family $\widetilde{\mathcal{F}}$
satisfies
$|N_{\widetilde{\mathcal{F}}}(1)|\geq\cdots\geq|N_{\widetilde{\mathcal{F}}}(n)|.$
After that, by abuse of notation we denote $\widetilde{\mathcal{F}}$ by
$\mathcal{F}$ and continue to find another meaningful
$(x^{\prime},y^{\prime})$-shift $S_{x^{\prime},y^{\prime}}$. After
$(x^{\prime},y^{\prime})$-shift we denote the new family
$\widetilde{\mathcal{F}}$ by $\mathcal{F}$ and rename the elements such that
$|N_{\mathcal{F}}(1)|\geq\cdots\geq|N_{\mathcal{F}}(n)|$. In view of
Proposition 2.2 this process is going to terminate after a finite number of
steps. The only thing that we have to show is that
$\widetilde{\mathcal{F}}=S_{x,y}(\mathcal{F})$ is non-trivial for $1\leq
x<y\leq n-3\beta ks$.

If $N_{\widetilde{\mathcal{F}}}(y)=\emptyset$, then
$|N_{\mathcal{F}}(x,y)|=\emptyset$ and
$|N_{\mathcal{F}}(x,\overline{y})|+|N_{\mathcal{F}}(y,\overline{x})|<\binom{n-2}{k-1}$
by Proposition 2.2. It follows that

$|N_{\mathcal{F}}(x)|+|N_{\mathcal{F}}(y)|=2|N_{\mathcal{F}}(x,y)|+|N_{\mathcal{F}}(x,\overline{y})|+|N_{\mathcal{F}}(y,\overline{x})|<\binom{n-2}{k-1}.$

Thus

$N_{\mathcal{F}}(v)\leq N_{\mathcal{F}}(y)<\frac{1}{2}\binom{n-2}{k-1}$ (4)

for each $v\in\\{y+1,\ldots,n\\}$.

Suppose that $y\leq n-3\beta ks$ and
$N_{\widetilde{\mathcal{F}}}(y)=\emptyset$, we are going to get a
contradiction. To this end we introduce the notation

$\alpha_{j}=\binom{n-1}{k-1}-|N_{\mathcal{F}}(j)|.$

Note that $\alpha_{x}$ counts the number of missing sets in
$N_{\mathcal{F}}(x)$, namely the sets $G\in\binom{[n]}{k}$ with $x\in
G\notin\mathcal{F}$. Let $W=\\{n-3\beta ks+1,\ldots,n\\}$. By inequality (4),
for each $v\in W$

$\alpha_{v}>\binom{n-1}{k-1}-\frac{1}{2}\binom{n-2}{k-1}>\frac{1}{2}\binom{n-1}{k-1}.$
(5)

Let $\alpha$ denote the total number of missing sets for $\mathcal{F}$. On the
one hand,

$\alpha=\binom{n}{k}-|\mathcal{F}|<\beta ks\binom{n-1}{k-1}$ (6)

since $|\mathcal{F}|\geq\binom{ks+k-2}{k}$. On the other hand, by inclusion-
exclusion principle and inequality (5), we have

$\begin{split}\alpha>&\sum_{i\in
W}\alpha_{i}-\binom{|W|}{2}\binom{n-2}{k-2}\\\
\geq&\frac{|W|}{2}\binom{n-1}{k-1}-\binom{|W|}{2}\binom{n-2}{k-2}\\\
=&\left(\frac{|W|}{2}\frac{n-1}{k-1}-\binom{|W|}{2}\right)\binom{n-2}{k-2}\\\
>&\frac{|W|}{2}\left(\frac{n-1}{k-1}-|W|\right)\binom{n-2}{k-2}\\\
=&\frac{3\beta ks}{2}\left(\frac{n-1}{k-1}-3\beta ks\right)\binom{n-2}{k-2}\\\
\geq&\frac{3\beta ks}{2}\cdot\frac{2(n-1)}{3(k-1)}\cdot\binom{n-2}{k-2}\\\
=&\beta ks\binom{n-1}{k-1},\end{split}$ (7)

a contradiction.

∎

##  3 Proof of Theorem 1.3

In order to prove Theorem 1.3, we need the following results. Two families
$\mathcal{A},\mathcal{B}$ are called _cross-intersecting_ if $A\cap
B\neq\emptyset$ for all $A\in\mathcal{A}$, $B\in\mathcal{B}$. Let
$\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{t}\subseteq\binom{[n]}{k}$.
$\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{t}$ are called _cross-
intersecting_ if $\mathcal{A}_{i}$ and $\mathcal{A}_{j}$ are cross-
intersecting for any
$\mathcal{A}_{i},\mathcal{A}_{j}\in\\{\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{t}\\}$
with $i\neq j$.

######  Theorem 3.1 (Shi, Frankl and Qian [22]).

Let $n,k,t$ be positive integers with $n\geq 2k$ and $t\geq 2$. If
$\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{t}\subseteq\binom{[n]}{k}$
are non-empty cross-intersecting families, then

$\sum_{i=1}^{t}|\mathcal{A}_{i}|\leq\max\left\\{\binom{n}{k}-\binom{n-k}{k}+t-1,t\binom{n-1}{k-1}\right\\}$

and the equality holds if and only if, up to isomorphism, one of the following
holds:

  1. $($i$)$

$n>2k$, $\mathcal{A}_{i}=\\{A\in\binom{[n]}{k}:1\in A\\}$ for every
$i\in\\{1,2,\ldots,t\\}$ if $\binom{n}{k}-\binom{n-k}{k}+t-1\leq
t\binom{n-1}{k-1}$, or $\mathcal{A}_{1}=\\{A\in\binom{[n]}{k}:[k]\cap
A\neq\emptyset\\}$ and $\mathcal{A}_{j}=\\{[k]\\}$ for every
$j\in\\{2,\ldots,t\\}$ (up to rearrangement of families) if
$\binom{n}{k}-\binom{n-k}{k}+t-1\geq t\binom{n-1}{k-1}$;

  2. $($ii$)$

$n=2k$, $t=2$, $\mathcal{A}_{1}\subseteq\binom{[n]}{k}$ with
$0<|\mathcal{A}_{1}|<\binom{n}{k}$ and
$\mathcal{A}_{2}=\binom{[n]}{k}\setminus\overline{\mathcal{A}_{1}}$;

  3. $($iii$)$

$n=2k$, $t\geq 3$, $\mathcal{A}_{1}\subseteq\binom{[n]}{k}$ is intersecting
with $|\mathcal{A}_{1}|=\binom{n-1}{k-1}$ and
$\mathcal{A}_{2}=\cdots=\mathcal{A}_{t}=\mathcal{A}_{1}$.

Similar to Lemma 2 in [21], Guo, Lu and Peng [16] prove the following result.
We say that $\mathcal{F}$ is _s-saturated_ , if $\nu(\mathcal{F})\leq s$, but
$\nu(\\{F\\}\cup\mathcal{F})=s+1$ for every $F\notin\mathcal{F}$.

######  Theorem 3.2.

For any integer $k\geq 3$, there exist $\varepsilon>0$ and a positive integer
$n_{0}$ such that the following holds. Let $\mathcal{F}$ be a s-saturated
$k$-graph on $n>n_{0}$ vertices and $s$ be an integer with
$n(1/k-1/(2k^{2}))-1<s\leq(n-k+1)/k$. If $\nu(\mathcal{F})\leq s$, and
$(1-\varepsilon)ks\leq\omega(\mathcal{F})\leq ks+k-3$, then

$|\mathcal{F}|\leq\binom{ks+k-1}{k}-3.98\binom{(1-\varepsilon)ks}{k-1}+(2+8\varepsilon
k^{4})\binom{n}{k-1}.$

###### Proof of Theorem 1.3.

Suppose that
$|\mathcal{F}|>\max_{i\in\\{0,1\\}}\\{|\mathcal{E}_{i}(n,k,s)|\\}>\binom{ks+k-2}{k}$,
we will get a contradiction. Let $\varepsilon$ be a sufficiently small
constant as in Theorem 3.2 and $\beta$ be a constant such that
$3\beta<\frac{\varepsilon^{k}}{3^{k+2}k!}$. By Lemma 2.4, there is a $k$-graph
$\mathcal{F}^{\prime}$ such that $\mathcal{F}^{\prime}$ is non-trivial and
shifted on $[n-3\beta ks]$. According to Lemma 2.1,
$|\mathcal{F}^{\prime}|=|\mathcal{F}|$ and
$\nu(\mathcal{F}^{\prime})\leq\nu(\mathcal{F})$. So we may assume that
$\mathcal{F}$ is non-trivial and shifted on $[n-3\beta ks]$ in our proof.
Since $|\mathcal{F}|>\binom{ks+k-2}{k}$, we have

$\begin{split}\left|\mathcal{F}[n-3\beta ks]\right|>&\binom{ks+k-2}{k}-3\beta
ks\binom{n-1}{k-1}\\\
>&\binom{ks+k-2}{k}-3\beta\cdot\frac{(1+2\beta)^{k-1}(ks)^{k}}{(k-1)!}\\\
>&\binom{ks+k-2}{k}-6\beta(ks)^{k}.\end{split}$ (8)

Note that $(1-3\beta)ks+k\leq n-3\beta ks\leq(1-2\beta)ks+k-2$. By Lemma 2.3,
$\omega(\mathcal{F})>(1-\varepsilon)ks$. Since we can turn a $k$-graph without
a matching of size $s+1$ to an $s$-saturated graph by adding edges, we may
assume that $\mathcal{F}$ is $s$-saturated in the following proof.

We first claim that $\omega(\mathcal{F})\leq ks+k-2$. Otherwise, suppose that
there is a clique $U$ of size $ks+k-1$, then there is an edge $F$ not
contained in $U$ since $\mathcal{F}$ is non-trivial. But there is a matching
of size $s+1$ in $\mathcal{F}[U\cup F]$, a contradiction. For the case
$\omega(\mathcal{F})\leq ks+k-3$, by Theorem 3.2,

$\begin{split}|\mathcal{F}|\leq&\binom{ks+k-1}{k}-3.98\binom{(1-\varepsilon)ks}{k-1}+\left(2+8\varepsilon
k^{4}\right)\binom{n}{k-1}\\\
<&\binom{ks+k-1}{k}-1.5\binom{(1-\varepsilon)ks}{k-1}\\\
<&\binom{ks+k-1}{k}-\binom{ks+k-2}{k-1}\\\ =&\binom{ks+k-2}{k}\end{split}$ (9)

for sufficiently large $s$ and small $\varepsilon$, a contradiction.

Now let us consider the case $\omega(\mathcal{F})=ks+k-2$. Let $U$ be the
largest clique in $\mathcal{F}$ such that $|U|=ks+k-2$. Next we focus on
vertices in $[n]\setminus U$. We claim that for any vertex $x\in[n]\setminus
U$, $N_{\mathcal{F}}(x)\subset\binom{U}{k-1}$. Indeed, if there is an edge
$F\in\mathcal{F}$ such that $x,y\in F$ and $x,y\in[n]\setminus U$, then
$\mathcal{F}[U\setminus F]$ contains a matching $M$ of size $s$ since
$|U\setminus F|=ks$. Thus $M\cup\\{F\\}$ is a matching of size $s+1$ in
$\mathcal{F}$, which contradicts that $\nu(\mathcal{F})\leq s$.

Let $U=[ks+k-2]$. So
$N_{\mathcal{F}}(ks+k-1),\ldots,N_{\mathcal{F}}(n)\subseteq\binom{U}{k-1}$.
Since $\nu(H)\leq s$, one can see that $N_{\mathcal{F}}(i),N_{\mathcal{F}}(j)$
are cross-intersecting for $ks+k-1\leq i<j\leq n$. Indeed, if there exist
$i,j$ such that $ks+k-1\leq i<j\leq n$ and
$N_{\mathcal{F}}(i),N_{\mathcal{F}}(j)$ are not cross-intersecting, then there
exist $F_{i}\in N_{\mathcal{F}}(i)$ and $F_{j}\in N_{\mathcal{F}}(j)$ such
that $F_{i}\cap F_{j}=\emptyset$. Thus
$M_{1}:=\\{F_{i}\cup\\{i\\},F_{j}\cup\\{j\\}\\}$ is a matching of size two in
$\mathcal{F}$. Since $|U\setminus V(M_{1})|=k(s-1)$, $\mathcal{F}[U\setminus
V(M_{1})]$ contains a matching $M_{2}$ of size $s-1$. Thus $M_{1}\cup M_{2}$
is a matching of size $s+1$ in $\mathcal{F}$, which contradicts that
$\nu(H)\leq s$.

Recall that $\mathcal{F}$ is non-trivial, then $N_{\mathcal{F}}(i)$ is non-
empty for each $i\in\\{ks+k-1,\ldots,n\\}$. By Theorem 3.1,

$\begin{split}\sum_{i=ks+k-1}^{n}|N_{\mathcal{F}}(i)|\leq\max\left\\{\binom{ks+k-2}{k-1}-\binom{ks-1}{k-1}+n-ks-k+1,(n-ks-k+2)\binom{ks+k-3}{k-2}\right\\}.\end{split}$

Thus

$\begin{split}|\mathcal{F}|&=\binom{ks+k-2}{k}+\sum_{i=ks+k-1}^{n}|N_{\mathcal{F}}(i)|\\\
&\leq\binom{ks+k-2}{k}+\max\left\\{\binom{ks+k-2}{k-1}-\binom{ks-1}{k-1}+n-ks-k+1,(n-ks-k+2)\binom{ks+k-3}{k-2}\right\\}\\\
&=\max_{i\in\\{0,1\\}}\\{|\mathcal{E}_{i}(n,k,s)|\\},\end{split}$

a contradiction.

∎

## References

  * [1] N. Alon, P. Frankl, H. Huang, V. Rödl, A. Ruciński and B. Sudakov,  Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels,  J. Combin. Theory Ser. A, 119 (2012), 1200–1215.
  * [2] B. Bollobás, D. E. Daykin and P. Erdős,  Sets of independent edges of a hypergraph,  Quart. J. Math. Oxford Ser., 27 (1976), 25–32.
  * [3] P. Erdős and T. Gallai,  On maximal paths and circuits of graphs,  Acta Math. Acad. Sci. Hungar., 10 (1959), 337–356.
  * [4] P. Erdős, C. Ko and R. Rado,  Intersection theorems for systems of finite sets,  Quart. J. Math. Oxford Ser., 12 (1961), 313–320.
  * [5] P. Erdős,  A problem of independent $r$-tuples,  Annales Univ. Budapest, 8 (1965), 93–95.
  * [6] P. Frankl,  Extremal set systems, in: Handbook of Combinatorics,  Elsevier, Amsterdam, 1995.
  * [7] P. Frankl, V. Rödl and A. Ruciński, On the maximum number of edges in a triple system not containing a disjoint family of a given size, _Combin. Probab. Comput._ , 21 (2012), 141–148.
  * [8] P. Frankl,  Improved bounds for Erdős Matching Conjecture,  J. Combin. Theory Ser. A, 120 (2013), 1068–1072.
  * [9] P. Frankl, Proof of the Erdős matching conjecture in a new range, _Israel J. Math._ , 222 (2017), 421-430.
  * [10] P. Frankl, On maximum number of edges in a hypergraph with given matching number, _Discrete Appl. Math._ , 216 (2017), 562-581.
  * [11] P. Frankl, T. Łuczak and K. Mieczkowska, On matchings in hypergraphs, _Electron. J. Combin._ , 19 (2012), #R42.
  * [12] P. Frankl and A. Kupavskii,  Two problems on matchings in set families - in the footsteps of Erdős and Kleitman,  J. Combin. Theory ser. B, 138 (2019), 286–313.
  * [13] P. Frankl, On non-trivial families without a perfect matching, _European J. Combin._ , 84 (2020), 103044.
  * [14] P. Frankl and A. Kupavskii,  The Erdős matching conjecture and concentration inequalities, _J. Combin. Theory ser. B_ , 157 (2022), 366-400.
  * [15] M. Guo, H. Lu and D. Mao, A stability result on matchings in $3$-uniform hypergraphs, _SIAM J. Discrete Math._ , 36 (2022), 2339–2351.
  * [16] M. Guo, H. Lu and X. Peng. Anti-Ramsey number of matchings in 3-uniform hypergraphs. _SIAM J. Discrete Math._ , 37 (2023), 1970–1987.
  * [17] A. J. W. Hilton and E. C. Milner,  Some intersection thorems for systems of finite sets,  Quart. J. Math. Oxford Ser., 18 (1967), 369–384.
  * [18] H. Huang, P. Loh and B. Sudakov,  The size of a hypergraph and its matching number,  Combin. Probab. Comput., 21 (2012), 442–450.
  * [19] D. Koluaev and A. Kupavskii,  Erdős matching conjecture for almost perfect matchings,  Discrete Math., 346 (2023), 113304.
  * [20] H. Lu, X. Yu and X. Yuan,  Nearly perfect matchings in uniform hypergraphs,  SIAM J. Discrete Math., 35 (2021), 1022–1049.
  * [21] T. Łuczak and K. Mieczkowska,  On Erdős extremal problem on matchings in hypergraphs,  J. Combin. Theory Ser. A, 124 (2014), 178–194.
  * [22] C. Shi, P. Frankl and J. Qian,  On non-empty cross-intersecting famlies,  Combinatorica, 42 (2022), 1513–1525.