The general Albertson irregularity index of graphs

Zhen Lin; Ting Zhou; Xiaojing Wang; Lianying Miao; Zhen Lin; Ting Zhou; Xiaojing Wang; Lianying Miao

doi:10.3934/math.2022002

AIMS Mathematics

2022, Volume 7, Issue 1: 25-38. doi: 10.3934/math.2022002

Previous Article Next Article

Research article

The general Albertson irregularity index of graphs

1.
School of Mathematics and Statistics, Qinghai Normal University, Xining, 810008, Qinghai, China
2.
School of Mathematics, China University of Mining and Technology, Xuzhou, 221116, Jiangsu, China

Received: 19 August 2021 Accepted: 22 September 2021 Published: 29 September 2021
MSC : 05C05, 05C07, 05C09, 05C35

We introduce the general Albertson irregularity index of a connected graph $G$ and define it as $A_{p}(G) = (\sum_{uv\in E(G)}|d(u)-d(v)|^p)^{\frac{1}{p}}$ , where $p$ is a positive real number and $d(v)$ is the degree of the vertex $v$ in $G$ . The new index is not only generalization of the well-known Albertson irregularity index and $\sigma$ -index, but also it is the Minkowski norm of the degree of vertex. We present lower and upper bounds on the general Albertson irregularity index. In addition, we study the extremal value on the general Albertson irregularity index for trees of given order. Finally, we give the calculation formula of the general Albertson index of generalized Bethe trees and Kragujevac trees.

Keywords:

Citation: Zhen Lin, Ting Zhou, Xiaojing Wang, Lianying Miao. The general Albertson irregularity index of graphs[J]. AIMS Mathematics, 2022, 7(1): 25-38. doi: 10.3934/math.2022002

Related Papers:

[1]	Zhimin Liu, Ripeng Huang, Songtao Shao . Data-driven two-stage fuzzy random mixed integer optimization model for facility location problems under uncertain environment. AIMS Mathematics, 2022, 7(7): 13292-13312. doi: 10.3934/math.2022734
[2]	Fei Yu . Multiperiod distributionally robust portfolio selection with regime-switching under CVaR risk measures. AIMS Mathematics, 2025, 10(4): 9974-10001. doi: 10.3934/math.2025456
[3]	Shuai Huang, Youwu Lin, Jing Zhang, Pei Wang . Chance-constrained approach for decentralized supply chain network under uncertain cost. AIMS Mathematics, 2023, 8(5): 12217-12238. doi: 10.3934/math.2023616
[4]	Chang-Jun Wang, Zi-Jian Gao . Two-stage stochastic programming with imperfect information update: Value evaluation and information acquisition game. AIMS Mathematics, 2023, 8(2): 4524-4550. doi: 10.3934/math.2023224
[5]	Ruiping Wen, Wenwei Li . An accelerated alternating directional method with non-monotone technique for matrix recovery. AIMS Mathematics, 2023, 8(6): 14047-14063. doi: 10.3934/math.2023718
[6]	Ebenezer Fiifi Emire Atta Mills . The worst-case scenario: robust portfolio optimization with discrete distributions and transaction costs. AIMS Mathematics, 2024, 9(8): 20919-20938. doi: 10.3934/math.20241018
[7]	Massoumeh Nazari, Mahmoud Dehghan Nayeri, Kiamars Fathi Hafshjani . Developing mathematical models and intelligent sustainable supply chains by uncertain parameters and algorithms. AIMS Mathematics, 2024, 9(3): 5204-5233. doi: 10.3934/math.2024252
[8]	Yuan-Zhen Li, Lei-Lei Meng, Biao Zhang . Two-stage iterated greedy algorithm for distributed flexible assembly permutation flowshop scheduling problems with sequence-dependent setup times. AIMS Mathematics, 2025, 10(5): 11488-11513. doi: 10.3934/math.2025523
[9]	Yang Chang, Guangyang Liu, Hongyan Yan . Bang-bang control for uncertain random continuous-time switched systems. AIMS Mathematics, 2025, 10(1): 1645-1674. doi: 10.3934/math.2025076
[10]	Zongqi Sun, Peng Yang, Jing Wu, Yunpeng Fan . The defined contribution pension plan after retirement under the criterion of a revised loss considering the economic situation. AIMS Mathematics, 2024, 9(2): 4749-4761. doi: 10.3934/math.2024229

Abstract

1. Introduction

A permutation of a set of elements ranking from one to $n$ is called derangement if none of the elements is left at its original place. The number of derangements of a set of $n$ elements is denoted by $D_n$ throughout this paper. The first few derangement numbers are $D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44$ , with $D_0 = 1$ being defined by convention and the familiar inclusion-exclusion principle giving a closed formula as follows ^[5,16]

$\begin{align} D_n = n!\sum\limits_{k = 0}^n\frac{(-1)^k}{k!} = \sum\limits_{k = 0}^n(-1)^{n-k}{n\choose k}k!, \end{align}$

(1.1)

which can be also obtained by applying the generating function of the derangement numbers ^[6,16]

$\begin{align} \frac{e^{-t}}{1-t} = \sum\limits_{n = 0}^{\infty}D_n\frac{t^n}{n!}. \end{align}$

(1.2)

The derangement numbers satisfy the following recurrence relations

$\begin{align} D_n = (n-1)(D_{n-1}+D_{n-2}), \; n\geq 2 \end{align}$

(1.3)

and

$\begin{align} D_{n} = nD_{n-1}+(-1)^n, \; n\geq 1, \end{align}$

(1.4)

with $D_0 = 1$ and $D_1 = 0$ . The above two recursion formulae allow us fast evaluation of $D_n$ . Moreover, Qi, Wang and Guo ^[15] established a new recurrence relation

$\begin{align} D_n = \sum\limits_{k = 0}^{n-2}{n\choose k}(n-k-1)D_k, \; n\geq 2. \end{align}$

(1.5)

A short proof was given by Fonseca ^[9].

Let $B_n$ denote the $n$ th Bell number, defined as the number of partitions of a set of cardinality $n$ (with $B_0 = 1$ ). The Bell number $B_n$ can be represented by the sum of Stirling numbers of the second kind, as follows

$\begin{align} B_n = \sum\limits_{k = 0}^n S(n,k), \end{align}$

(1.6)

where $S(n, k)$ are the Stirling numbers of the second kind. The Bell numbers obey the recurrence

$\begin{align} B_{n+1} = \sum\limits_{k = 0}^n{n\choose k}B_k \end{align}$

(1.7)

and satisfy the generating function

$\begin{align} e^{e^t-1} = \sum\limits_{n = 0}^{\infty}B_n\frac{t^n}{n!}. \end{align}$

(1.8)

Both Bell numbers and derangement numbers are important tools in the study of special sequences and combinatorics. In ^[5], an interesting connection between the derangement numbers and the Bell numbers was established by the probabilistic method:

$\begin{align} \sum\limits_{k = 0}^n{n\choose k}k^s D_k = n!\sum\limits_{k = 0}^s{s\choose k}(-1)^kn^{s-k}B_k,\; n\geq s\geq 0. \end{align}$

(1.9)

Recently, Du and Fonseca ^[7] provided a general identity for the derangement numbers and the Bell numbers which includes (1.1), (1.5) and (1.9) as particular cases. They also provided a combinatorial interpretation and established a general determinantal representation in terms of a Hessenberg matrix. For more interesting identities involving the derangement numbers, the Bell numbers and their generalizations, one is referred to ^[13] and the references therein.

The aim of this short note is to establish two kinds of identities involving derangement polynomials and $r$ -Bell polynomials. The identities of the first kind are mainly inspired by the work in ^[5,7], and they are the extensions of (1.9). The identities of the second kind generalize some of the results on derangement polynomials and Bell polynomials in ^[12]. The definitions of the derangement polynomials, the $r$ -Bell polynomials and some necessary properties will be presented in the next section.

2. Preliminaries

We begin by recalling the definition of the derangement polynomials. The derangement polynomials $D_n(x)$ are defined by

$\begin{align} \frac{e^{-t}}{1-t}e^{xt} = \sum\limits_{n = 0}^{\infty}D_n(x)\frac{t^n}{n!}, \end{align}$

(2.1)

which have been considerably investigated in ^[8,10,11,12]. They are natural extensions of the derangement numbers because $D_n(x) = D_n$ when $x = 0$ . The derangement polynomials $D_n(x)$ obey the recursive relation

$\begin{align} D_n(x) = nD_{n-1}(x)+(x-1)^n. \end{align}$

(2.2)

As a direct consequence of (2.1), two closed formulae for the derangement polynomials are

$\begin{align} D_n(x) = \sum\limits_{k = 0}^n{n\choose k}D_kx^{n-k} \end{align}$

(2.3)

and

$\begin{align} D_n(x) = \sum\limits_{k = 0}^n{n\choose k}k!(x-1)^{n-k}, \end{align}$

(2.4)

respectively. The $r$ -Stirling number denoted by $S_r(n, k)$ enumerates the partitions of a set of $n$ elements into $k$ nonempty, disjoint subsets such that the first $r$ elements are in distinct subsets. A systematic treatment on the $r$ -Stirling numbers was given in ^[1] and a different approach was described in ^[2,3]. The $r$ -Stirling numbers have the 'horizontal' generating function

$\begin{align} (x+r)^n = \sum\limits_{k = 0}^nS_r(n+r,k+r)(x)_k, \end{align}$

(2.5)

where the falling factorial of a given real number $x$ is $(x)_k = x(x-1)\cdots(x-k+1)$ . From (2.5), the explicit expressions of $S_r(n+r, k+r)$ are given by

$\begin{align} S_r(n+r,k+r) = \frac{1}{k!}\sum\limits_{j = 0}^k(-1)^{k-j}{k\choose j}(j+r)^n. \end{align}$

(2.6)

In particular, when $r = 0$ , we have $S_r(n+r, k+r) = S(n, k)$ , where $S(n, k)$ are the Stirling numbers of the second kind. In ^[14], $r$ -Bell numbers and $r$ -Bell polynomials are defined by

$\begin{align} B_{n,r} = \sum\limits_{k = 0}^nS_r(n+r,k+r) \end{align}$

(2.7)

and

$\begin{align} B_{n,r}(x) = \sum\limits_{k = 0}^nS_r(n+r,k+r)x^k, \end{align}$

(2.8)

respectively. The exponential generating function for the $r$ -Bell polynomials is

$\begin{align} \sum\limits_{n = 0}^{\infty}B_{n,r}(x)\frac{t^n}{n!} = e^{x(e^t-1)+rt}. \end{align}$

(2.9)

It is clear that the $r$ -Bell polynomials $B_{n, r}(x)$ reduce to the well-known Bell polynomials $B_n(x)$ ^[6] when $r = 0$ . For more about r-Bell polynomials, especially from an algebraic perspective, one can refer to reference ^[4], in which partial $r$ -Bell polynomials in three combinatorial Hopf algebras are introduced.

3. Main results

In this section, two kinds of identities involving the derangement polynomials and the $r$ -Bell polynomials are established. The following lemma plays an important role.

Lemma 3.1. If both $r$ and $s$ are nonnegative integers, then we have

$\begin{align} \sum\limits_{k = 0}^n{n\choose k}(n-k+r)^sx^{n-k}D_k(1-x) = n!\left\{B_{s,r}(x)-\sum\limits_{j = n+1}^sS_r(s+r,j+r)x^j\right\}. \end{align}$

(3.1)

Proof. From the explicit expression of the derangement polynomials $D_n(x)$ (2.4), we have

$\begin{align*} \sum\limits_{k = 0}^n{n\choose k}(n-k+r)^sx^{n-k}D_k(1-x) & = \sum\limits_{k = 0}^n{n\choose k}(n-k+r)^sx^{n-k}\sum\limits_{j = 0}^k{k\choose j}j!(-x)^{k-j}\\ & = \sum\limits_{j = 0}^nj!x^{n-j}\sum\limits_{k = j}^n(-1)^{k-j}{n\choose k}{k\choose j}(n-k+r)^s\\ & = \sum\limits_{j = 0}^nj!{n\choose j}x^{n-j}\sum\limits_{k = j}^n(-1)^{k-j}{n-j\choose k-j}(n-k+r)^s, \end{align*}$

since

$\begin{align*} {n\choose k}{k\choose j} = {n\choose j}{n-j\choose k-j}. \end{align*}$

We replace $k$ by $k+j$ and obtain

$\begin{align*} &\sum\limits_{j = 0}^nj!{n\choose j}x^{n-j}\sum\limits_{k = j}^n(-1)^{k-j}{n-j\choose k-j}(n-k+r)^s\\ = &\sum\limits_{j = 0}^nj!{n\choose j}x^{n-j}\sum\limits_{k = 0}^{n-j}(-1)^{k}{n-j\choose k}(n-j-k+r)^s\\ = &\sum\limits_{j = 0}^nj!{n\choose j}x^{n-j}\sum\limits_{k = 0}^{n-j}(-1)^{n-j-k}{n-j\choose k}(k+r)^s. \end{align*}$

By (2.6), we have

$\begin{align*} &\sum\limits_{j = 0}^nj!{n\choose j}x^{n-j}\sum\limits_{k = 0}^{n-j}(-1)^{n-j-k}{n-j\choose k}(k+r)^s\\ = &\sum\limits_{j = 0}^nj!{n\choose j}x^{n-j}(n-j)!S_r(s+r,n-j+r)\\ = &n!\sum\limits_{j = 0}^nS_r(s+r,j+r)x^j. \end{align*}$

From (2.8), it is equivalent to the righthand side of (3.1). □

Remark 3.1. For $j > i\geq 0$ , $S_r(i, j) = 0$ . Thus, when $n\geq s$ , it is natural that (3.1) reduces to

$\begin{align} \sum\limits_{k = 0}^n{n\choose k}(n-k+r)^sx^{n-k}D_k(1-x) = n!B_{s,r}(x). \end{align}$

(3.2)

By Lemma 3.1, we have the following theorem.

Theorem 3.1. Let $f(x) = a_sx^s+a_{s-1}x^{s-1}+\cdots+a_0$ be a polynomial of degree $s$ . If $r$ is a nonnegative integer, then

$\begin{align} \sum\limits_{k = 0}^n{n\choose k}f(n-k+r)x^{n-k}D_k(1-x) = n!\left\{\sum\limits_{i = 0}^sa_iB_{i,r}(x)-\sum\limits_{n+1\leq j\leq i\leq s}a_iS_r(i+r,j+r)x^j\right\}. \end{align}$

(3.3)

Proof. Using (3.1), the theorem is easily obtained by linearity. □

Remark 3.2. In fact, here we introduce truncated $r$ -Bell polynomials:

$\begin{align*} B_{s,r}^{(n)}(x) = \sum\limits_{k = 0}^nS_r(s+r,k+r)x^k, \end{align*}$

with the exponential generating function

$\begin{align*} \sum\limits_{s = 0}^{\infty}B_{s,r}^{(n)}(x)\frac{t^s}{s!} = e^{x\left(\sum\limits_{i = 1}^n\frac{t^i}{i!}\right)+rt}. \end{align*}$

For $x = 1$ , we obtain numbers that have a simple combinatorial interpretation: They are partitions of a set of size $s$ into $k\leq n$ disjoint subsets such that the first $r$ elements are in distinct sets. For a fixed $n$ , these polynomials form a generating set of the space of polynomials of degree at most $n$ . As the referee pointed out, we can use this notation to give a simpler form to the statement of Lemma 3.1, which becomes

$\begin{align*} B_{s,r}^{(n)}(x) = \frac{1}{n!}\sum\limits_{k = 0}^n{n\choose k}(n-k+r)^sx^{n-k}D_k(1-x). \end{align*}$

Theorem 3.1 can then be rewritten as follows:

$\begin{align*} \sum\limits_{i = 0}^sa_iB_{s,r}^{(n)}(x) = \frac{1}{n!}\sum\limits_{k = 0}^n{n\choose k}f(n-k+r)x^{n-k}D_k(1-x). \end{align*}$

We therefore have an equality between two linear combinations of families of polynomials. Suppose that $f(x) = \sum_{k = 0}^\infty a_kx^k$ has an infinite radius of convergence. Passing to the limit, the equality becomes

$\begin{align*} \sum\limits_{i = 0}^\infty a_iB_{s,r}^{(n)}(x) = \frac{1}{n!}\sum\limits_{k = 0}^n{n\choose k}f(n-k+r)x^{n-k}D_k(1-x). \end{align*}$

The identity relates the values of a function and the coefficients of its Taylor expansion.

Remark 3.3. The referee also pointed out that using the truncated $r$ -Bell polynomials and generating series, the proof of Lemma 3.1 can be simplified. Now, we present his (her) proof. Lemma 3.1 is equivalent to

$\begin{align*} \sum\limits_{n = 0}^\infty B_{s,r}^{(n)}(x)t^n = \sum\limits_{n = 0}^\infty(n+r)^s\frac{(xt)^n}{n!}\sum\limits_{n = 0}^\infty D_n(1-x)\frac{t^n}{n!}. \end{align*}$

The left hand side is

$\begin{align*} \sum\limits_{n = 0}^\infty B_{s,r}^{(n)}(x)t^n = \sum\limits_{n = 0}^\infty\sum\limits_{k = 0}^nS_r(s+r,k+r)x^kt^n = \sum\limits_{k = 0}^\infty x^kS_r(s+r,k+r)\frac{t^k}{1-t} = \frac{B_{s,r}(xt)}{1-t}. \end{align*}$

By Dobinski's formula for $r$ -Bell polynomials ^[14]

$\begin{align*} B_{n,r}(x) = e^{-x}\sum\limits_{k = 0}^\infty\frac{(k+r)^n}{k!}x^k, \end{align*}$

we obtain the righthand side

$\begin{align*} \sum\limits_{n = 0}^\infty(n+r)^s\frac{(xt)^n}{n!}\sum\limits_{n = 0}^\infty D_n(1-x)\frac{t^n}{n!} = B_{s,r}(xt)e^{xt}\frac{e^{-xt}}{1-t}. \end{align*}$

The two expressions are equal and Lemma 3.1 is proved.

When $r = 0$ , we establish the relationship between the derangement polynomials and the Bell polynomials.

Corollary 3.1. Let $f(x) = a_sx^s+a_{s-1}x^{s-1}+\cdots+a_0$ be a polynomial of degree $s$ , then

$\begin{align} \sum\limits_{k = 0}^n{n\choose k}f(n-k)x^{n-k}D_k(1-x) = n!\left\{\sum\limits_{i = 0}^sa_iB_{i}(x)-\sum\limits_{n+1\leq j\leq i\leq s}a_iS(i,j)x^j\right\}. \end{align}$

(3.4)

Remark 3.4. Theorem 4 in ^[7] describes a relationship between the derangement numbers and the Bell numbers, while Corollary 3.1 in our paper is extended to the case of the derangement polynomials and the Bell polynomials. When $x = 1$ , (3.4) reduces to

$\begin{align} \sum\limits_{k = 0}^n{n\choose k}f(n-k)D_k = n!\left\{\sum\limits_{i = 0}^sa_iB_{i}-\sum\limits_{n+1\leq j\leq i\leq s}a_iS(i,j)\right\}. \end{align}$

(3.5)

In (3.4), when $f(x) = 1$ , we get

$\begin{align} \sum\limits_{k = 0}^n{n\choose k}x^{n-k}D_k(1-x) = n!; \end{align}$

(3.6)

equivalently, by the binomial inversion formula we have

$\begin{align} D_n(x) = \sum\limits_{k = 0}^n{n\choose k}k!(x-1)^{n-k}. \end{align}$

(3.7)

In fact, if we rewrite (2.1) as

$\begin{align*} \frac{1}{1-t} = e^{xt}\sum\limits_{n = 0}^\infty D_n(1-x)\frac{t^n}{n!}, \end{align*}$

we can easily find that (3.6) is a direct consequence of the above identity. When $f(x) = x-1$ , we get

$\begin{align} \sum\limits_{k = 0}^n{n\choose k}(n-k-1)x^{n-k}D_k(1-x) = n!\left\{B_1(x)-B_0(x)\right\} = n!(x-1), \; n\geq 2. \end{align}$

(3.8)

It can be rewritten as

$\begin{align} D_n(x) = \sum\limits_{k = 0}^{n-2}{n\choose k}(n-k-1)(1-x)^{n-k}D_k(x)+n!x, \; n\geq 2. \end{align}$

(3.9)

When $x = 0$ , (3.9) reduces to (1.5).

Lemma 3.2. If both $r$ and $s$ are nonnegative integers, then we have

$\begin{align} &\sum\limits_{k = 0}^n{n\choose k}(k-r)^sx^{n-k}D_k(1-x)\\ & = n!\left\{\sum\limits_{j = 0}^s(-1)^j{s\choose j}n^{s-j}B_{j,r}(x)-\sum\limits_{n+1\leq i\leq j\leq s}(-1)^j{s\choose j}n^{s-j}S_r(j+r,i+r)x^i\right\}. \end{align}$

(3.10)

Proof. We have

$\begin{align*} \sum\limits_{k = 0}^n{n\choose k}(k-r)^sx^{n-k}D_k(1-x)& = \sum\limits_{k = 0}^n{n\choose k}(n-(n-k+r))^sx^{n-k}D_k(1-x)\\ & = \sum\limits_{k = 0}^n{n\choose k}x^{n-k}D_k(1-x)\sum\limits_{j = 0}^s(-1)^j{s\choose j}n^{s-j}(n-k+r)^j\\ & = \sum\limits_{j = 0}^s(-1)^j{s\choose j}n^{s-j}\sum\limits_{k = 0}^n{n\choose k}(n-k+r)^jx^{n-k}D_k(1-x). \end{align*}$

By Lemma 3.1, we immediately obtain Lemma 3.2. □

Remark 3.5. When $n\geq s$ , (3.10) reduces to

$\begin{align} \sum\limits_{k = 0}^n{n\choose k}(k-r)^sx^{n-k}D_k(1-x) = n!\sum\limits_{j = 0}^s(-1)^j{s\choose j}n^{s-j}B_{j,r}(x), \end{align}$

(3.11)

which is a generalized identity of (1.9).

By Lemma 3.2 and simple calculations, we have the following theorem.

Theorem 3.2. Let $f(x) = a_sx^s+a_{s-1}x^{s-1}+\cdots+a_0$ be a polynomial of degree $s$ . If $r$ is a nonnegative integer, then

$\begin{align} &\sum\limits_{k = 0}^n{n\choose k}f(k-r)x^{n-k}D_k(1-x)\\ & = n!\left\{\sum\limits_{0\leq j\leq i\leq s}(-1)^ja_i{i\choose j}n^{i-j}B_{j,r}(x) -\sum\limits_{n+1\leq t\leq j\leq i\leq s}(-1)^ja_i{i\choose j}n^{i-j}S_r(j+r,t+r)x^t\right\}. \end{align}$

(3.12)

Remark 3.6. As discussed in Remark 3.2, we can have the same approach for Theorem 3.2 with the formula

$\begin{align*} \sum\limits_{i = 0}^s a_i\sum\limits_{j = 0}^i(-1)^j{i\choose j}n^{i-j}B_{j,r}^{(n)}(x) = \frac{1}{n!}\sum\limits_{k = 0}^n{n\choose k}f(k-r)x^{n-k}D_k(1-x). \end{align*}$

In particular, suppose that $f(x) = \sum_{k = 0}^\infty a_kx^k$ has an infinite radius of convergence. Passing to the limit we obtain

$\begin{align*} \sum\limits_{i = 0}^\infty a_i\sum\limits_{j = 0}^i(-1)^j{i\choose j}n^{i-j}B_{j,r}^{(n)}(x) = \frac{1}{n!}\sum\limits_{k = 0}^n{n\choose k}f(k-r)x^{n-k}D_k(1-x). \end{align*}$

The identity also relates the values of a function and the coefficients of its Taylor expansion.

In particular, when $r = 0$ , we have

Corollary 3.2. Let $f(x) = a_sx^s+a_{s-1}x^{s-1}+\cdots+a_0$ be a polynomial of degree $s$ , then

$\begin{align} &\sum\limits_{k = 0}^n{n\choose k}f(k)x^{n-k}D_k(1-x)\\ & = n!\left\{\sum\limits_{0\leq j\leq i\leq s}(-1)^ja_i{i\choose j}n^{i-j}B_{j}(x) -\sum\limits_{n+1\leq t\leq j\leq i\leq s}(-1)^ja_i{i\choose j}n^{i-j}S(j,t)x^t\right\}. \end{align}$

(3.13)

If we take $x = 1$ in Corollary 3.2, we recover Corollary 5 in ^[7].

In the following theorems, we establish the identities of the second kind involving the derangement polynomials and the $r$ -Bell polynomials.

Theorem 3.3. If both $r$ and $s$ are nonnegative integers, then we have

$\begin{align} B_{n,r}(x) = \sum\limits_{j = 0}^n\sum\limits_{k = 0}^{j}{n\choose j}(r+1)^{n-j}(-1)^kS(j,k)D_k(1-x). \end{align}$

(3.14)

Proof. If we let $u = 1-e^t$ , then

$\begin{align*} e^{x(e^t-1)+rt}& = \frac{e^{-xu}}{1-u}\cdot e^{(r+1)t} = \sum\limits_{k = 0}^{\infty}D_k(1-x)\frac{u^k}{k!}\sum\limits_{k = 0}^{\infty}(r+1)^k\frac{t^k}{k!}. \end{align*}$

Since

$\begin{align*} \frac{u^k}{k!} = (-1)^k\frac{(e^t-1)^k}{k!} = (-1)^k\sum\limits_{n\geq k}S(n,k)\frac{t^n}{n!}, \end{align*}$

we have

$\begin{align*} e^{x(e^t-1)+rt}& = \sum\limits_{p = 0}^{\infty}\frac{t^p}{p!}\sum\limits_{k = 0}^{p}(-1)^kS(p,k)D_k(1-x)\cdot\sum\limits_{q = 0}^{\infty}(r+1)^q\frac{t^q}{q!}\\ & = \sum\limits_{n = 0}^{\infty}\frac{t^n}{n!}\sum\limits_{j = 0}^n{n\choose j}(r+1)^{n-j}\sum\limits_{k = 0}^{j}(-1)^kS(j,k)D_k(1-x). \end{align*}$

From (2.9), we arrive at

$\begin{align*} \sum\limits_{n = 0}^{\infty}\frac{t^n}{n!}\sum\limits_{j = 0}^n{n\choose j}(r+1)^{n-j}\sum\limits_{k = 0}^{j}(-1)^kS(j,k)D_k(1-x) = \sum\limits_{n = 0}^{\infty}B_{n,r}(x)\frac{t^n}{n!}. \end{align*}$

By comparing the coefficients of $t^n/n!$ , we get

$\begin{align*} B_{n,r}(x) = \sum\limits_{j = 0}^n{n\choose j}(r+1)^{n-j}\sum\limits_{k = 0}^{j}(-1)^kS(j,k)D_k(1-x), \end{align*}$

which leads to Theorem 3.3. □

Taking $x = 1$ in (3.14), we obtain the explicit expression of the $r$ -Bell numbers $B_{n, r}$ in terms of the derangement numbers $D_k$ .

Corollary 3.3. If both $r$ and $s$ are nonnegative integers, then we have

$\begin{align} B_{n,r} = \sum\limits_{j = 0}^n\sum\limits_{k = 0}^{j}{n\choose j}(r+1)^{n-j}(-1)^kS(j,k)D_k. \end{align}$

(3.15)

When $r = 0$ in (3.14), we have the relationship between the derangement polynomials and the Bell polynomials.

Corollary 3.4. ^[12] For $n\geq 0$ , we have

$\begin{align} B_{n}(x) = \sum\limits_{j = 0}^n\sum\limits_{k = 0}^{j}{n\choose j}(-1)^kS(j,k)D_k(1-x). \end{align}$

(3.16)

Remark 3.7. By the binomial inversion formula, we can rewrite (3.14) as

$\begin{align} \sum\limits_{k = 0}^n(-1)^kS(n,k)D_k(1-x) = \sum\limits_{j = 0}^n(-1)^{n-j}{n\choose j}(r+1)^{n-j}B_{j,r}(x). \end{align}$

(3.17)

By (3.17), we obtain the explicit expression of the derangement polynomials $D_n(x)$ in terms of the $r$ -Bell polynomials.

Theorem 3.4. If both $r$ and $s$ are nonnegative integers, then we have

$\begin{align} D_n(x) = \sum\limits_{k = 0}^n\sum\limits_{j = 0}^k(-1)^{n-k-j}s(n,k){k\choose j}(r+1)^{k-j}B_{j,r}(1-x), \end{align}$

(3.18)

where $s(n, k)$ are the Stirling numbers of the first kind.

Proof. Let $T_n = \sum_{j = 0}^n(-1)^{n-j}{n\choose j}(r+1)^{n-j}B_{j, r}(x)$ in (3.17). By the orthogonal relationship between two kinds of Stirling numbers ^[6],

$\begin{align*} \sum\limits_{j = k}^ns(n,j)S(j,k) = \delta_{n,k}, \end{align*}$

where $\delta_{n, k}$ is the Kronecker symbol defined by $\delta_{n, k} = 1$ if $n = k$ and $\delta_{n, k} = 0$ otherwise, and one can obtain

$\begin{align*} D_n(1-x) = (-1)^n\sum\limits_{k = 0}^ns(n,k)T_k. \end{align*}$

Replacing $x$ by $1-x$ , we arrive at (3.18). □

Taking $x = 1$ in (3.14), we obtain the explicit expression of the derangement numbers $D_n$ in terms of the $r$ -Bell numbers $B_{j, r}$ .

Corollary 3.5. For $n\geq 0$ , we have

$\begin{align} D_n = \sum\limits_{k = 0}^n\sum\limits_{j = 0}^k(-1)^{n-k-j}s(n,k){k\choose j}(r+1)^{k-j}B_{j,r}, \end{align}$

(3.19)

where $s(n, k)$ are the Stirling numbers of the first kind.

Taking $r = 0$ in (3.14), we have the following corollary.

Corollary 3.6. ^[12] For $n\geq 0$ , we have

$\begin{align} D_n(x) = \sum\limits_{k = 0}^n\sum\limits_{j = 0}^k(-1)^{n-k-j}s(n,k){k\choose j}B_{j}(1-x), \end{align}$

(3.20)

where $s(n, k)$ are the Stirling numbers of the first kind.

Remark 3.8. In ^[12], Kim et al. obtained Corollaries 3.4 and 3.6 by using the generating function method. Their method provides us with a good idea to prove Theorems 3.3 and 3.4. In the proof of Theorem 3.4, we use the binomial inversion formula and the orthogonal relationship of two kinds of Stirling numbers, which seems more direct.

Remark 3.9. Theorems 3.3 and 3.4 have a common feature, which is that the lefthand member of the equality is a combinatorial number, while the righthand member of the equality is a somewhat complicated double sum. For algorithmic motivation, these results show that either derangement polynomials or $r$ -Bell polynomials can be calculated using the other one. Furthermore, these results may well have combinatorial consequences, as double sums involve combinatorial numbers, binomial coefficients, signs and so on. It would therefore be interesting to look for an interpretation of these two identities from the point of view of combinatorial objects. We will continue our research in the following paper.

4. Conclusions

We have obtained two kinds of identities involving derangement polynomials and $r$ -Bell polynomials. The identities of the first kind presented a relation between two linear combinations of families of polynomials. They also related the values of a function and the coefficients of its Taylor expansion. The identities of the second kind extended some of the results on derangement polynomials and Bell polynomials due to Kim et al and had a common feature, which is that the lefthand member of the equality is a combinatorial number, while the righthand member of the equality is a somewhat complicated double sum.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

We are grateful to the referees for their careful reading and helpful comments that have improved the presentation substantially from the initial submission. The work was supported by Zhejiang Provincial Natural Science Foundation of China (Grant No. LTGY23H240002), Zhejiang Province Higher Education Teaching Reform Project (Grant No. jg20220457) and Ningbo Municipal Natural Science Foundation (Grant No. 2023J302).

Conflict of interest

The authors declare that they have no competing interests.

References

[1]	M. O. Albertson, The irregularity of a graph, Ars Combin., 46 (1997), 219–225.
[2]	H. Abdo, S. Brandt, D. Dimitrov, The total irregularity of a graph, DMTCS, 16 (2014), 201–206.
[3]	H. Abdoa, N. Cohenb, D. Dimitrov, Graphs with maximal irregularity, Filomat, 28 (2014), 1315–1322. doi: 10.2298/FIL1407315A. doi: 10.2298/FIL1407315A
[4]	H. Abdo, D. Dimitrov, The irregularity of graphs under graph operations, Discuss. Math. Graph T., 34 (2014), 263–278. doi: 10.7151/dmgt.1733. doi: 10.7151/dmgt.1733
[5]	H. Abdo, D. Dimitrov, I. Gutman, Graphs with maximal $\sigma$ irregularity, Discrete Appl. Math., 250 (2018), 57–64. doi: 10.1016/j.dam.2018.05.013. doi: 10.1016/j.dam.2018.05.013
[6]	B. Bollobás, P. Erdős, Graphs of extremal weights, Ars Combin., 50 (1998), 225–233.
[7]	X. D. Chen, Y. P. Hou, F. G. Lin, Some new spectral bounds for graph irregularity, Appl. Math. Comput., 320 (2018), 331–340. doi: 10.1016/j.amc.2017.09.038. doi: 10.1016/j.amc.2017.09.038
[8]	D. Dimitrov, T. Réti, Graphs with equal irregularity indices, Acta Polytech. Hung., 11 (2014), 41–57.
[9]	E. Estrada, Quantifying network heterogeneity, Phys. Rev. E Stat. Nonlin. Soft Matter Phys., 82 (2010), 066102. doi: 10.1103/PhysRevE.82.066102. doi: 10.1103/PhysRevE.82.066102
[10]	I. Gutman, Geometric approach to degree-based topological indices: Sombor indices, MATCH Commun. Math. Comput. Chem., 86 (2021), 11–16.
[11]	I. Gutman, Some basic properties of Sombor indices, Open J. Discret. Appl. Math., 4 (2021), 1–3. doi: 10.30538/psrp-odam2021.0047. doi: 10.30538/psrp-odam2021.0047
[12]	I. Gutman, P. Hansen, H. Mélot, Variable neighborhood search for extremal graphs. 10. comparison of irregularity indices for chemical trees, J. Chem. Inf. Model., 45 (2005), 222–230. doi: 10.1021/ci0342775. doi: 10.1021/ci0342775
[13]	I. Gutman, M. Togan, A. Yurttas, A. S. Cevik, I. N. Cangul, Inverse problem for sigma index, MATCH Commun. Math. Comput. Chem., 79 (2018), 491–508.
[14]	I. Gutman, Y.N. Yeh, S.L. Lee, J.C. Chen, Wiener numbers of dendrimers, MATCH Commun. Math. Comput. Chem., 30 (1994), 103–115.
[15]	S. A. Hosseini, M. B. Ahmadi, I. Gutman, Kragujevac trees with minimal atom-bond connectivity index, MATCH Commun. Math. Comput. Chem., 71 (2014), 5–20.
[16]	O. J. Heilmann, E. H. Lieb, Theory of monomer-dimer systems, Commun. Math. Phys., 25 (1972), 190–232. doi: 10.1007/BF01877590. doi: 10.1007/BF01877590
[17]	M. A. Henninga, D. Rautenbach, On the irregularity of bipartite graphs, Discrete Math., 307 (2007), 1467–1472. doi: 10.1016/j.disc.2006.09.038. doi: 10.1016/j.disc.2006.09.038
[18]	X. L. Li, J. Zheng, A unifled approach to the extremal trees for difierent indices, MATCH Commun. Math. Comput. Chem., 54 (2005), 195–208.
[19]	M. Ostilli, Cayley trees and Bethe lattices: A concise analysis for mathematicians and physicists, Physica A, 391 (2012), 3417–3423. doi: 10.1016/j.physa.2012.01.038. doi: 10.1016/j.physa.2012.01.038
[20]	I. Rivin, Counting cycles and finite dimensional $L^p$ norms, Adv. Appl. Math., 29 (2002), 647–662. doi: 10.1016/S0196-8858(02)00037-4. doi: 10.1016/S0196-8858(02)00037-4
[21]	T. Réti, On some properties of graph irregularity indices with a particular regard to the $\sigma$ -index, Appl. Math. Comput., 344–345 (2019), 107–115. doi: 10.1016/j.amc.2018.10.010. doi: 10.1016/j.amc.2018.10.010
[22]	O. Rojo, R. D. J. Alarcón, Line graph of combinations of generalized Bethe trees: Eigenvalues and energy, Linear Algebra Appl., 435 (2011), 2402–2419. doi: 10.1016/j.laa.2010.10.008. doi: 10.1016/j.laa.2010.10.008
[23]	O. Rojo, M. Robbiano, An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree, Linear Algebra Appl., 427 (2007), 138–150. doi: /10.1016/j.laa.2007.06.024. doi: 10.1016/j.laa.2007.06.024
[24]	T. Réti, R. Sharafdini, H. Haghbin, Á. Drégelyi-Kiss, Graph irregularity indices used as molecular descriptors in QSPR studies, MATCH Commun. Math. Comput. Chem., 79 (2018), 509–524.
[25]	M. Robbianoa, V. Trevisan, Applications of recurrence relations for the characteristic polynomials of Bethe trees, Comput. Math. Appl., 59 (2010), 3039–3044. doi: 10.1016/j.camwa.2010.02.023. doi: 10.1016/j.camwa.2010.02.023
[26]	L. A. Székely, L. H. Clark, R. C. Entringer, An inequality for degree sequences, Discrete Math., 103 (1992), 293–300. doi: 10.1016/0012-365X(92)90321-6. doi: 10.1016/0012-365X(92)90321-6
[27]	M. K. Siddiqui, M. Imran, M. A. Iqbal, Molecular descriptors of discrete dynamical system in fractal and Cayley tree type dendrimers, J. Appl. Math. Comput., 61 (2019), 57–72. doi: 10.1007/s12190-019-01238-1. doi: 10.1007/s12190-019-01238-1
[28]	T. Vetrík, M. Masre, General eccentric connectivity index of trees and unicyclic graphs, Discrete Appl. Math., 284 (2020), 301–315. doi: 10.1016/j.dam.2020.03.051. doi: 10.1016/j.dam.2020.03.051
[29]	Y. Wu, F. Y. Wei, B. L. Liu, Z. Jia, The generalized (terminal) Wiener polarity index of generalized Bethe trees and coalescence of rooted trees, MATCH Commun. Math. Comput. Chem., 70 (2013), 603–620.
[30]	K. X. Xu, K. C. Das, A. D. Maden, On a novel eccentricity-based invariant of a graph, Acta Math. Sin., 32 (2016), 1477–1493. doi: 10.1007/s10114-016-5518-z. doi: 10.1007/s10114-016-5518-z
[31]	B. Zhou, N. Trinajstić, On general sum-connectivity index, J. Math. Chem., 47 (2010), 210–218. doi: 10.1007/s10910-009-9542-4. doi: 10.1007/s10910-009-9542-4

This article has been cited by:

1.	Shuai Huang, Youwu Lin, Jing Zhang, Pei Wang, Chance-constrained approach for decentralized supply chain network under uncertain cost, 2023, 8, 2473-6988, 12217, 10.3934/math.2023616
2.	Tareq Oshan, Nuha Hamada, Mahmoud Sharkawi, 2024, Optimizing Facility Location Under Disruptions: A Big Data-Driven Approach, 979-8-3503-5475-1, 225, 10.1109/IDSTA62194.2024.10746991

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

AIMS Mathematics

1.8 3.4

Metrics

Article views(3144) PDF downloads(221) Cited by(2)

Preview PDF

Download XML

Export Citation

Article outline

Show full outline

Figures and Tables

Figures(4)

AIMS Mathematics

The general Albertson irregularity index of graphs

Related Papers:

Abstract

1. Introduction

2. Preliminaries

3. Main results

4. Conclusions

Use of AI tools declaration

Acknowledgments

Conflict of interest

References

This article has been cited by:

Reader Comments

通讯作者: 陈斌, bchen63@163.com

Metrics

Figures and Tables

Other Articles By Authors

Catalog

AIMS Mathematics

The general Albertson irregularity index of graphs

Related Papers:

Abstract

1. Introduction

2. Preliminaries

3. Main results

4. Conclusions

Use of AI tools declaration

Acknowledgments

Conflict of interest

References

This article has been cited by:

Reader Comments

通讯作者: 陈斌, bchen63@163.com

Metrics

Figures and Tables

Other Articles By Authors

Related pages

Tools

Export File

Citation

Format

Content

Catalog