# On permutations avoiding partially ordered patterns defined by bipartite
graphs

Sergey Kitaev111Department of Mathematics and Statistics, University of
Strathclyde, 26 Richmond Street, Glasgow G1 1XH, United Kingdom. Email:
<EMAIL_ADDRESS>and Artem Pyatkin222Sobolev Institute of
Mathematics, Koptyug ave, 4, Novosibirsk, 630090, Russia. Email:
<EMAIL_ADDRESS>
###### Abstract

Partially ordered patterns (POPs) generalize the notion of classical patterns
studied in the literature in the context of permutations, words, compositions
and partitions. In this paper, we give a number of general, and specific
enumerative results for POPs in permutations defined by bipartite graphs,
substantially extending the list of known results in this direction. In
particular, we completely characterize the Wilf-equivalence for patterns
defined by the N-shape posets.

Keywords: permutation pattern, partially ordered pattern, bipartite graph,
enumeration, Wilf-equivalence, N-pattern

AMS Subject Classifications: 05A05, 05A15

##  1 Introduction

An occurrence of a (classical) permutation pattern $p=p_{1}\cdots p_{k}$ in a
permutation $\pi=\pi_{1}\cdots\pi_{n}$ is a subsequence
$\pi_{i_{1}}\cdots\pi_{i_{k}}$, where $1\leq i_{1}<\cdots<i_{k}\leq n$, such
that $\pi_{i_{j}}<\pi_{i_{m}}$ if and only if $p_{j}<p_{m}$. For example, the
permutation $364125$ has two occurrences of the pattern 123, namely, the
subsequences 345 and 125, while this permutation avoids (that is, has no
occurrences of) the pattern 4321. Permutation patterns are an active area of
research that attracts much attention in the literature (e.g. see [1, 2, 3, 7]
and references therein).

A partially ordered pattern (POP) $p$ of length $k$ is defined by a
$k$-element partially ordered set (poset) $P$ labeled by the elements in
$[k]:=\\{1,\ldots,k\\}$. An occurrence of such a POP $p$ in a permutation
$\pi=\pi_{1}\cdots\pi_{n}$ is a subsequence $\pi_{i_{1}}\cdots\pi_{i_{k}}$,
where $1\leq i_{1}<\cdots<i_{k}\leq n$, such that $\pi_{i_{j}}<\pi_{i_{m}}$ if
$j<m$ in $P$. Thus, a classical pattern of length $k$ corresponds to a
$k$-element chain. For example, the POP $p=$ ${\small 3}$${\small 2}$${\small
1}$ occurs four times in the permutation 41253, namely, as the subsequences
412, 413, 423, and 453, as in each of these subsequences the element in
position 1 is bigger than that in position 3. Clearly, avoiding the pattern
$p$ is the same as avoiding the patterns 312, 321 and 231 at the same time, so
POPs provide a convenient language to deal with larger sets of permutation
patterns. Moreover, the notion of a POP provides a uniform notation for
several combinatorial structures such as peaks, valleys, modified maxima and
minima, $p$-descents in permutations, and many others [6].

A POP is bipartite if the underlying graph of the poset defining it is a
bipartite graph. Clearly, a POP is bipartite if and only if in the Hasse
diagram of the poset defining it the longest increasing chain has length 1.

Permutations of length $n$ are called $n$-permutations, and $S_{n}$ denotes
the set of all $n$-permutations. For an $n$-permutation $\pi$, the complement
$c(\pi)$ of $\pi$ is obtained from $\pi$ by replacing each element $x$ by
$n+1-x$. For example, $c(3142)=2413$. The same operation is well-defined on
labels in $[n]$ of an $n$-element poset. Also, the reverse $r(\pi)$ of $\pi$
is obtained by writing the elements of $\pi$ in the reverse order. For
example, $r(52413)=31425$. The complement, reverse, and usual group
theoretical inverse are known as trivial bijections from $S_{n}$ to $S_{n}$.
Finally, for a sequence $s$ of numbers, the reduced form red($s$) of $s$ is
obtained from $s$ by replacing in it the $i$-th smallest element by $i$ for
$i=1,2,\ldots$. For example, red$((2,6,9,1,4))=(2,4,5,1,3)$ and in the context
of this paper, commas and brackets will be omitted.

Denote by $S_{n}(p)$ the set of $n$-permutations avoiding $p$. Patterns
$p_{1}$ and $p_{2}$ are Wilf-equivalent if $|S_{n}(p_{1})|=|S_{n}(p_{2})|$ for
every $n\geq 0$. Throughout this paper, the notation $a(n)$ is used for the
number of $n$-permutations avoiding the pattern $p$ in question, that is,
$a(n)=|S_{n}(p)|$.

POPs were introduced in [5], and they were studied in the context of
permutations, words, compositions and partitions (see references in [4]). A
systematic search for connections between sequences in the Online Encyclopedia
of Integer Sequences (OEIS) [8] and permutations avoiding POPs of length 4 and
5 was conducted in [4], which resulted in 13 new enumerative results for
classical patterns of length 4 and 5. Five out of 15 open problems stated in
[4] were answered in [9]. The most relevant to our paper are the following
general results about bipartite POPs obtained in [4], where “g.f.” stands for
“generating function”.

$x_{2}$$x_{3}$$x_{4}$$x_{k}$$x_{1}$$a)$$b)$$2$$3$$k-1$$1$$k$ Figure 1: The
POPs in Theorems 1.1 and 1.2.

######  Theorem 1.1 ([4]).

Let $p$ be the POP in Figure 1a, where $\\{x_{1},\ldots,x_{k}\\}=[k]$ and
$k\geq 1$. Then,

$a(n)=\left\\{\begin{array}[]{ll}n!&\mbox{if }n<k\\\
(k-1)!(k-1)^{n-k+1}&\mbox{if }n\geq k.\end{array}\right.$

Also, the respective g.f. is

$\sum_{n\geq
0}a(n)x^{n}=\frac{(k-1)(k-1)!x^{k}}{1-(k-1)x}+\sum_{i=0}^{k-1}i!x^{i}.$

######  Theorem 1.2 ([4]).

Let $p$ be the POP in Figure 1b, where $k\geq 2$ (if $k=2$ then $p$ is two
independent elements). Then,

$a(n)=\left\\{\begin{array}[]{ll}n!&\mbox{if }n<k\\\ 2(k-2)\cdot
a(n-1)-(k-2)(k-3)\cdot a(n-2)&\mbox{if }n\geq k.\end{array}\right.$

Also, the respective g.f. is

$\sum_{n\geq 0}a(n)x^{n}=\frac{A(x)-B(x)+C(x)}{1-2(k-2)x+(k-2)(k-3)x^{2}},$

where

$A(x)=\sum_{i=0}^{k-3}i!x^{i},\
B(x)=2(k-2)\sum_{i=0}^{k-4}i!x^{i+1},C(x)=(k-2)(k-3)\sum_{i=0}^{k-5}i!x^{i+2}.$

The following simple result is also useful.

######  Theorem 1.3 ([4]).

Let $p$ be a POP of length $k$. Also, let $p^{\prime}$ be the POP obtained
from $p$ by applying the complement operation on its labels, that is, by
replacing a label $x$ by $k+1-x$. Moreover, let $p^{\prime\prime}$ be the POP
obtained from $p$ by flipping the poset with respect to a horizontal line.
Then, $|S_{n}(p)|=|S_{n}(p^{\prime})|=|S_{n}(p^{\prime\prime})|$ for any
$n\geq 0$, that is, $p$, $p^{\prime}$ and $p^{\prime\prime}$ are Wilf-
equivalent.

In this paper, we extend the results in Theorems 1.1 and 1.2 to other
bipartite POPs and discuss certain generalizations for some of them. The paper
is organized as follows. In Section 2, we derive enumerative results about
certain classes of POPs defined by complete bipartite graphs, in particular,
enumerating all avoidance classes for such POPs of length at most 5. In
Section 3, we give a complete classification of the Wilf-equivalence for
N-patterns, which are the bipartite POPs of length 4 defined by the posets of
N-shape. We prove that there are three Wilf-equivalence classes for
N-patterns, and enumerate all classes. In Section 4, we discuss enumeration of
so-called DC POPs defined by disjoint chains (including those of length 2).
Finally, in Section 5 we discuss directions for further research.

##  2 POPs defined by complete bipartite graphs

We denote by $p=(A/B)$, where $A\subset[k]$ and $B=[k]\setminus A$, the POP
$p$ of length $k$ in which each element corresponding to a position from $A$
must be larger than all elements that are in positions from $B$. We call such
patterns complete bipartite POPs. We are interested in the number of
$n$-permutations avoiding a given complete bipartite POP $p$ of length $k$.
Clearly, for $n<k$ there are $n!$ $p$-avoiding $n$-permutations, so in our
arguments below we can assume that $n\geq k$. Note that the cases of $|A|=1$
and $A=\\{1,k\\}$ are given by Theorems 1.1 and 1.2, respectively.

In this section, we prove that the number $a(n)$ of $n$-permutations avoiding
POPs with $A\in\\{\\{i,i+1\\},\\{j,j+2\\}\\}$, where $i\in[n-1]$ and
$j\in[n-2]$, satisfies the same recurrence relation as that in Theorem 1.2.

Given an $n$-permutation $\pi$ and $t\in[n]$, denote by
$\pi^{\prime}=\pi\setminus t$ the $(n-1)$\- permutation obtained from $\pi$ by
deleting the element $t$ and decreasing by 1 each element in $\pi$ larger than
$t$. For any POP $p$, we say that $\pi$ and $\pi^{\prime}$ are $p$-equivalent
if either both of the permutations contain an occurrence of $p$, or both of
them are $p$-avoiding. For example, let $p=(A/B)$ be a complete bipartite POP
of length $k$, where $|A|=s$ and $1\in A$. If $\pi=\pi_{1}\cdots\pi_{n}\in
S_{n}$ and $\pi_{1}=t$, where $t\in[k-s]$, then $\pi$ and
$\pi^{\prime}=\pi\setminus t$ are $p$-equivalent, since the first element of
$\pi$ clearly cannot be a part of $p$. It is straightforward to extend the
notion of $p$-equivalence to the situation when more than one element are
removed from a permutation.

Note that for establishing $p$-equivalence, it is sufficient to prove the
implication: “If $\pi$ contains $p$ then $\pi^{\prime}$ contains $p$”, since
the opposite implication is trivial taking into account the hereditary nature
of POP containment.

Our next theorem gives the same recurrence relation, and hence the same g.f.,
as that in Theorem 1.2. In what follows, we use the notation
$[x,y]:=\\{x,x+1,\ldots,y\\}$ and remind that $[x]=[1,x]$.

######  Theorem 2.1.

Let $p=(A/B)$ be a complete bipartite POP of length $k$. If $A=\\{i,i+1\\}$,
where $i\in[k-1]$ for $k\geq 3$, then

$a(n)=\left\\{\begin{array}[]{ll}n!&\mbox{if }n<k\\\ 2(k-2)\cdot
a(n-1)-(k-2)(k-3)\cdot a(n-2)&\mbox{if }n\geq k.\end{array}\right.$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}$ and $\pi_{s}=n$ and $\pi_{t}=n-1$ for
some $s,t\in[n]$. Clearly, if both $s,t\in[i,n-k+i+1]$ then $\pi$ contains
$p$. On the other hand, if $s\in[i-1]\cup[n-k+i+2,n]$ (respectively,
$t\in[i-1]\cup[n-k+i+2,n]$) then $n=\pi_{s}$ (respectively, $n-1=\pi_{t}$)
cannot be a part of $p$, and thus, $\pi$ and $\pi\setminus n$ (respectively,
$\pi\setminus(n-1)$) are $p$-equivalent. In total, there are $2(k-2)\cdot
a(n-1)$ such $p$-avoiding permutations. Among them, there are $(k-2)(k-3)\cdot
a(n-2)$ $p$-avoiding permutations having both $s,t\in[i-1]\cup[n-k+i+2,n]$
that were counted twice (note that in this case both $n$ and $n-1$ cannot be a
part of $p$ and hence $\pi$ and $\pi\setminus\\{n-1,n\\}$ are $p$-equivalent).
In total, we have

$a(n)=2(k-2)\cdot a(n-1)-(k-2)(k-3)\cdot a(n-2),$

as required. ∎

Generalizing the proof of Theorem 2.1 in a straightforward way (using the
principle of inclusion-exclusion) gives the following result.

######  Theorem 2.2.

Let $p=(A/B)$ be a complete bipartite POP of length $k$. For $A=[i,i+j]$,
where $i\in[k-j]$ and $k\geq j+2$, $a(n)=n!$ if $n<k$, and for $n\geq k$,

$a(n)=(j+1)(k-j-1)\cdot a(n-1)-\binom{j+1}{2}(k-j-1)(k-j-2)\cdot a(n-2)$
$+\binom{j+1}{3}(k-j-1)(k-j-2)(k-j-3)\cdot a(n-3)+\cdots$
$+(-1)^{j}(k-j-1)(k-j-2)\cdots(k-2j-1)\cdot a(n-j-1).$

In particular, for $A=\\{i,i+1,i+2\\}$ (the case of $j=2$), we have

$a(n)=3(k-3)\cdot a(n-1)-3(k-3)(k-4)\cdot a(n-2)+(k-3)(k-4)(k-5)\cdot a(n-3).$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}$. Let us say that an element $x\in\pi$
is large if it is among the $j+1$ largest elements, i.e. $x\in[n-j,n]$.
Clearly, if the positions of all large elements in $\pi$ are in $[i,n-k+i+j]$
then $\pi$ contains $p$. On the other hand, any large element whose position
is in $C:=[i-1]\cup[n-k+i+j+1,n]$ cannot be a part of $p$. So, applying the
principle of inclusion-exclusion, we count the number of $p$-avoiding
permutations with one large element in $C$, reduce that number by the number
of $p$-avoiding permutations with two large elements in $C$, add the number of
$p$-avoiding permutations with three large elements in $C$, etc. In order to
count the number of $p$-avoiding permutations with $\ell$ large elements in
$C$, note that there are $\binom{j+1}{\ell}$ ways to choose $\ell$ large
elements. The first of these elements has $(k-j-1)$ possible positions in $C$,
the second one has just $(k-j-2)$ positions, and so on, the $\ell$-th element
has $(k-j-\ell)$ possible positions. Removing these $\ell$ large elements we
obtain a $p$-equivalent permutation of length $n-\ell$. Hence, the total
number of $p$-avoiding permutations with $\ell$ large elements in $C$ is

$\binom{j+1}{\ell}(k-j-1)(k-j-2)\cdots(k-j-\ell)\cdot a(n-\ell).$

Summing up these summands with a multiple of $(-1)^{\ell-1}$ for all $\ell$
from $1$ to $j+1$ gives the required formula. ∎

Note that in the case of $j=0$ in Theorem 2.2, we deal with the POP in Figure
1a, and the recurrence given by Theorem 2.2 in this case, namely,
$a(n)=(k-1)a(n-1)$, can be used to derive the formula in Theorem 1.1.

######  Theorem 2.3.

Let $p=(A/B)$ be a complete bipartite POP of length $k$. If $A=\\{i,i+2\\}$,
where $i\in[k-2]$ and $k\geq 3$, then

$a(n)=\left\\{\begin{array}[]{ll}n!&\mbox{if }n<k\\\ 2(k-2)\cdot
a(n-1)-(k-2)(k-3)\cdot a(n-2)&\mbox{if }n\geq k.\end{array}\right.$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}$ and $n=\pi_{s}$ and $n-1=\pi_{t}$ for
some $s,t\in[n]$. Further, we let $C:=[i-1]\cup[n-k+i+3,n]$. Similarly to the
proof of Theorem 2.1, if $n$ or $n-1$ occurs in $\pi$ in a position from $C$
then it cannot be a part of $p$ and hence there are $2(k-3)\cdot
a(n-1)-(k-3)(k-4)\cdot a(n-2)$ such $p$-avoiding $n$-permutations. Assume
$s,t\not\in C$. Then $s=t\pm 1$ since otherwise $\pi$ contains $p$. Let
$\pi^{\prime}=\pi\setminus n$. We next show that $\pi$ and $\pi^{\prime}$ are
$p$-equivalent. Indeed, assume that $\pi$ contains an occurrence of $p$. Then,
this occurrence cannot involve both $n$ and $n-1$ since they are adjacent in
$\pi$ and hence cannot correspond to $i$ and $i+2$ in $p$. Therefore, if $n$
is involved in an occurrence of $p$ in $\pi$ then substituting it by $n-1$
gives an occurrence of $p$ in $\pi^{\prime}$. Note that $\pi^{\prime}$ has a
property that the position of its maximum element must be in $[i,n-k+i+1]$.
Clearly, there are $a(n-1)-(k-3)\cdot a(n-2)$ such $p$-avoiding
$(n-1)$-permutations $\pi^{\prime}$, and each of them corresponds to two
$p$-avoiding $n$-permutations $\pi$ ($n$ can go straight before or straight
after $n-1$). Thus, we have

$a(n)=2(k-3)\cdot a(n-1)+(k-3)(k-4)\cdot a(n-2)+2[a(n-1)-(k-3)\cdot a(n-2)]$
$=2(k-2)\cdot a(n-1)-(k-2)(k-3)\cdot a(n-2),$

as required. ∎

Note that from Theorems 2.1 and 2.3, all complete bipartite POPs of length 4
with $|A|=2$ are Wilf-equivalent, and their counting sequence begins with 1,
2, 6, 20, 68, 232, 792, 2704, 9232, … (this is the sequence A006012 in [8]
with the g.f. $\sum_{n\geq 0}a(n)x^{n}=\frac{1-3x}{1-4x+2x^{2}}$ and several
combinatorial interpretations, including two related to permutations). As for
length 5, all POPs with $|A|=2$ are also Wilf-equivalent except for
$A\in\\{\\{1,4\\},\\{2,5\\}\\}$, and these two POPs are Wilf-equivalent by
Theorem 1.3. In the “generic case”, the counting sequence begins with 1, 2, 6,
24, 108, 504, 2376, 11232, 53136, … (the sequence A094433 in [8]), and in the
“exceptional cases”, the counting sequence begins with 1, 2, 6, 24, 108, 504,
2364, 11052, 51456, … .

The following theorem completes enumeration of complete bipartite POPs of
length 5, namely, it enumerates avoidance for the POP
$(\\{1,4\\},\\{2,3,5\\})=$ ${\small 1}$${\small 2}$${\small 4}$${\small
3}$${\small 5}$ (equivalently, $(\\{2,5\\},\\{1,3,4\\})=$ ${\small 2}$${\small
1}$${\small 5}$${\small 3}$${\small 4}$ ).

######  Theorem 2.4.

Let $p$ be the POP $(\\{1,4\\},\\{2,3,5\\})=$ ${\small 1}$${\small 2}$${\small
4}$${\small 3}$${\small 5}$ . Then,

$a(n)=\left\\{\begin{array}[]{ll}n!&\mbox{if }n\leq 4\\\
7a(n-1)-12a(n-2)+4a(n-3)+2b(n-2)&\mbox{if }n\geq 5,\end{array}\right.$

where $b(1)=0$, $b(2)=1$ and for $n\geq 3$,

$b(n)=a(n-2)+b(n-1)+2\sum_{i=2}^{n-2}b(i).$

###### Proof.

For $p$-avoiding permutations $\pi_{1}\cdots\pi_{n}$, we let

  * •

$b(n)$ (resp., $b^{\prime}(n)$) be the number of $n$-permutations with
$\pi_{n-1}=n$ (resp., $\pi_{n-1}=n-1$);

  * •

$c(n)$ (resp., $c^{\prime}(n)$) be the number of $n$-permutations with
$\pi_{i-1}=n-1$ and $\pi_{i}=n$ (resp., $\pi_{i-1}=n$ and $\pi_{i}=n-1$) for
$2\leq i<n$;

  * •

$d(n)$ (resp., $d^{\prime}(n)$) be the number of $n$-permutations with
$\pi_{n-3}=n-1$ and $\pi_{n-1}=n$ (resp., $\pi_{n-3}=n$ and $\pi_{n-1}=n-1$);

  * •

$e(n)$ (resp., $e^{\prime}(n)$) be the number of $n$-permutations with
$\pi_{i-2}=n-1$ and $\pi_{i}=n$ (resp., $\pi_{i-2}=n$ and $\pi_{i}=n-1$) for
$3\leq i<n-1$;

  * •

$f(n)$ (resp., $f^{\prime}(n)$) be the number of $n$-permutations with
$\pi_{n}\neq n$ (resp., $\pi_{n}\neq n-1$).

Clearly, for $n<5$, $a(n)=n!$, $f(n)=n!-(n-1)!$, $b(n)=(n-1)!$ except for
$b(1)=0$. Also, for $n<3$, $c(n)=d(n)=e(n)=0$. Moreover, $p$ is symmetric with
respect to $n$ and $n-1$ meaning that swapping $n$ and $n-1$ neither
introduces an extra occurrence of $p$ nor removes an existent occurrence of
$p$ (both $n$ and $n-1$ can only play the role of $1$ or $4$ in $p$). Hence,
$b^{\prime}(n)=b(n)$, $c^{\prime}(n)=c(n)$, $d^{\prime}(n)=d(n)$,
$e^{\prime}(n)=e(n)$ and $f^{\prime}(n)=f(n)$, and therefore in what follows
we can assume that $n$ is to the right of $n-1$, and at the end we multiply
the result by 2.

Since, clearly, there are $a(n-1)$ $n$-permutations $\pi_{1}\cdots\pi_{n}$
with $\pi_{n}=n$, we have

$f(n)=a(n)-a(n-1).$

If $\pi_{i}=n$ for $i<n$ then either $\pi_{i-1}=n-1$ or $\pi_{i-2}=n-1$ (or
else there is an occurrence of $p$ involving $n-1$ and $n$). In the latter
case, we consider separately the case when $\pi_{n-1}=n$. Keeping in mind
doubling the result, we obtain

$a(n)=2(a(n-1)+c(n)+d(n)+e(n)).$ (1)

We now compute $c(n)$. Let $\pi$ be an $n$-permutation counted by $c(n)$.
Then, clearly, removing $n$ from $\pi$ gives a $p$-equivalent permutation.
Hence,

$c(n)=f(n-1)=a(n-1)-a(n-2).$ (2)

Let us compute $e(n)$. If $\pi$ is an $n$-permutation counted by $e(n)$ then
to the right of $n$ in $\pi$ there are at least two elements. Consider
possible positions $j$ for $n-2$. The case of $j<i-3$ is not possible because
then $\pi$ is not $p$-avoiding ($n-2$ and $n$ play the roles of $1$ and $4$ in
$p$, respectively). The case of $i+1<j<n$ is not possible either as then $\pi$
is not $p$-avoiding ($n-1$ and $n-2$ play the roles of $1$ and $4$ in $p$,
respectively). This leaves us with four possible cases for $j$ to consider.

  * •

$j=i-3$. In this case, $\pi$ is $p$-equivalent to the permutation
$\pi^{\prime}$ obtained from $\pi$ by removing $n-2$ and reducing $n-1$ and
$n$ by 1. Indeed, $n-2$ cannot play the role of $2,3,5$ in an occurrence of
$p$ as otherwise $n-1$ and $n$ must play the roles of $1$ and $4$ but there is
only one element in $\pi$ between them. On the other hand, if $n-2$ plays the
role of $1$ or $4$ in an occurrence of $p$ in $\pi$, then the element $n-2$ in
$\pi^{\prime}$ (the former element $n-1$ in $\pi$) plays the same role in an
occurrence of $p$ in $\pi^{\prime}$. Hence, there are $e(n-1)$ such
permutations.

  * •

$j=i-1$. In this case, $\pi$ is $p$-equivalent to the permutation
$\pi^{\prime}$ obtained from $\pi$ by removing $n-1$ and $n$ since only one of
the consecutive elements $n-1$, $n-2$, $n$ can be involved in an occurrence of
$p$. Since in $\pi^{\prime}$ the maximum element $n-2$ is not in the last two
positions, we have $f(n-2)-b(n-2)$ such permutations.

  * •

$j=i+1$ or $j=n$. In both cases, $\pi$ is $p$-equivalent to the permutation
$\pi^{\prime}$ obtained from $\pi$ by removing $n-2$ and reducing $n-1$ and
$n$ by 1. In $\pi^{\prime}$, there is one element between the maximum elements
$n-2$ and $n-1$, and the element $n-1$ is not the rightmost element. Hence, in
each of the two cases, the number of permutations is $d(n-1)+e(n-1)$.

Summarizing the four cases, we obtain

$e(n)=3e(n-1)+2d(n-1)+a(n-2)-a(n-3)-b(n-2).$

Next, we compute $d(n)$. Let $\pi$ be an $n$-permutation counted by $d(n)$.
Similarly to our considerations in the case of $e(n)$, we have three
possibilities fo position $j$ of the element $n-2$.

  * •

$j=n-4$. Removing $n-2$ results in a $p$-equivalent permutation. Hence, there
are $d(n-1)$ permutations in this case.

  * •

$j=n-2$. Removing $n-1$ and $n$ results in a $p$-equivalent permutation.
Hence, there are $b(n-2)$ permutations in this case.

  * •

$j=n$. Removing $n-2$ and $n$ results in a $p$-equivalent permutation. Hence,
there are $b(n-2)$ permutations in this case.

Summarizing the three cases, we obtain

$d(n)=2b(n-2)+d(n-1).$

Finally, we compute $b(n)$. Let $\pi$ be an $n$-permutation counted by $b(n)$
and $\pi_{j}=n-1$. Clearly, to avoid $p$ we must have $j>n-4$. If $j=n$ then
$\pi$ is $p$-equivalent to the permutation obtained by removing $n-1$ and $n$
from $\pi$, and there are $a(n-2)$ such permutations. If $j=n-2$ then $\pi$ is
$p$-equivalent to the permutation obtained by removing $n$ from $\pi$, and
there are $b(n-1)$ such permutations. Finally, if $j=n-3$ then by definition,
there are $d(n)$ such permutations. Hence,

$b(n)=a(n-2)+b(n-1)+d(n).$

As the final step, we simplify the obtained formulas.

$d(n)=2b(n-2)+d(n-1)=2b(n-2)+2b(n-3)+d(n-2)=\cdots=2\sum_{i=2}^{n-2}b(i)$

since $b(1)=0$. But then

$b(n)=a(n-2)+b(n-1)+d(n)=a(n-2)+b(n-1)+2\sum_{i=2}^{n-2}b(i).$

From (1) and (2), $a(n)=2[2a(n-1)-a(n-2)+d(n)+e(n)]$ and hence
$d(n)+e(n)=a(n)/2-2a(n-1)+a(n-2)$. On the other hand,

$d(n)+e(n)=2b(n-2)+d(n-1)+3e(n-1)+2d(n-1)+a(n-2)-a(n-3)-b(n-2)$
$=b(n-2)+a(n-2)-a(n-3)+3(d(n-1)+e(n-1))$
$=b(n-2)+a(n-2)-a(n-3)+3(a(n-1)/2-2a(n-2)+a(n-3))$
$=b(n-2)+3a(n-1)/2-5a(n-2)+2a(n-3).$

Inserting the last expression for $d(n)+e(n)$ into (1), we obtain the desired
result:

$a(n)=2(2a(n-1)-a(n-2)+(b(n-2)+3a(n-1)/2-5a(n-2)+2a(n-3)))$
$=7a(n-1)-12a(n-2)+4a(n-3)+2b(n-2).$

∎

##  3 Wilf-classification for N-pattern avoidance

Note that the minimal connected bipartite graph that is not a complete
bipartite graph is a $4$-path. Due to Theorem 1.3, we may assume that the
corresponding poset defining a bipartite POP of length 4 has the N-shape, and
we call such POPs N-patterns. The following two theorems were obtained in [4].

######  Theorem 3.1 ([4]).

For the N-pattern $2$$1$$3$$4$ , $a(0)=a(1)=1$ and, for $n\geq 2$,
$a(n)=4a(n-1)-3a(n-2)+1$, so that

$a(n)=\frac{3^{n}-2n+3}{4}.$

Also,

$\sum_{n\geq 0}a(n)x^{n}=\frac{(1-2x)^{2}}{(1-3x)(1-x)^{2}}.$

######  Theorem 3.2 ([4]).

For the N-pattern $p=$ $3$$1$$2$$4$ we have $a(0)=a(1)=1$ and, for $n\geq 2$,
$a(n)=4a(n-1)-3a(n-2)+a(n-3)$, so that, for $n\geq 1$,

$a(n)=\sum_{i=0}^{n-1}{n+2i-1\choose 3i}.$

Also,

$\sum_{n\geq 0}a(n)x^{n}=\frac{1-3x+x^{2}}{1-4x+3x^{2}-x^{3}}.$

Reading the labels of an N-pattern through the path starting from the left
lower vertex to the right upper vertex, we can encode such a pattern by a
4-permutation, called N-word, that we record in bold to distinguish from a
classical pattern. For example, the N-pattern  $3$$1$$2$$4$ is encoded by the
N-word 3124. In this section, for the reader’s convenience we indicate
elements of posets in bold in order to distinguish them from elements of
permutations.

N-patterns | Reference
---|---
Wilf-class 1 given by the recurence $a(n)=4a(n-1)-3a(n-2)+1$.
This is the sequence $A111277$ in [8]
($1,2,6,19,59,180,544,1637,4917,\ldots$).
$2$$1$$3$$4$ , $3$$4$$2$$1$ ,  $1$$2$$4$$3$ , $4$$3$$1$$2$ | Theorem 3.1
$2$$1$$4$$3$ , $3$$4$$1$$2$ | Theorem 3.3
$1$$2$$3$$4$ , $4$$3$$2$$1$ | Theorem 3.4
$1$$3$$2$$4$ , $4$$2$$3$$1$ | Theorem 3.5
$1$$4$$3$$2$ , $4$$1$$2$$3$ , $3$$2$$1$$4$ , $2$$3$$4$$1$ | Theorem 3.6
Wilf-class 2 given by the recurrence $a(n)=4a(n-1)-3a(n-2)+a(n-3)$.
This is the sequence $A052544$ in [8]
($1,2,6,19,60,189,595,1873,5896,\ldots$).
$3$$1$$2$$4$ , $2$$4$$3$$1$ , $1$$3$$4$$2$ , $4$$2$$1$$3$ | Theorem 3.2
$1$$4$$2$$3$ , $4$$1$$3$$2$ , $2$$3$$1$$4$ , $3$$2$$4$$1$ | Theorem 3.7
Wilf-class 3 given by the recurrence $a(n)=3a(n-1)+a(n-2)-a(n-3)$.
The sequence begins with $1,2,6,19,61,196,630,2025,6509,\ldots$.
$3$$1$$4$$2$ , $2$$4$$1$$3$ | Theorem 3.8
Table 1: Wilf-equivalence classification for N-patterns where the patterns in
the same row are Wilf-equivalent by Theorem 1.3

There are 24 N-words. By Theorem 1.3, complementing the labels of a poset
gives a Wilf-equivalent pattern, so in the cases to consider we can assume
that in an N-word 1 is to the left of 4. Moreover, by Theorem 1.3, flipping
the poset with respect to a horizontal line then complementing the labels and
reading the word backward (to obtain N-shape with 1 being to the left of 4) we
see that 1423 is equivalent to 2314, 1432 is equivalent to 3214, 1342 is
equivalent to 3124, 1243 is equivalent to 2134, while 1234, 1324, 2143 and
3142 are equivalent to themselves. These observations leave us with eight
cases to consider, two of which are already considered in Theorems 3.1 and
3.2. It turns out that there are three Wilf-equivalence classes for the 24
N-patterns, which are summarized in Table 1.

###  3.1 N-patterns in Wilf-equivalence class 1 in Table 1

######  Theorem 3.3.

For the N-bipartite POP $p=$ $2$$1$$4$$3$ , we have $a(0)=a(1)=1$ and, for
$n\geq 2$, $a(n)=4a(n-1)-3a(n-2)+1$, hence giving the formula for $a(n)$ and
the g.f. in the statement of Theorem 3.1.

###### Proof.

Let $b(n)$ (resp., $c(n)$) be the number of $p$-avoiding $n$-permutations
where $n$ is not the rightmost element (resp., and the elements to the right
of $n$ are in increasing order). Suppose that $\pi_{1}\cdots\pi_{n}\in S_{n}$.
Clearly, if $\pi_{n}=n$ (or, $\pi_{n}=n-1$) then $\pi_{n}$ cannot be involved
in an occurrence of $p$. Hence, removing $\pi_{n}$ one obtains a
$p$-equivalent permutation and therefore $b(n)=a(n)-a(n-1)$.

Let $\pi=\pi_{1}\cdots\pi_{n}$ be $p$-avoiding. One can see that there are
four possibilities to avoid $p$.

  * •

$\pi_{n}=n$. Clearly, there are $a(n-1)$ such permutations.

  * •

$\pi_{n}=n-1$. Clearly, there are $a(n-1)$ such permutations.

  * •

$\pi_{i-1}=n-1$ and $\pi_{i}=n$ for $2\leq i<n$. We have
$b(n-1)=a(n-1)-a(n-2)$ such permutations since removing $n$ from $\pi$ gives a
$p$-equivalent permutation.

  * •

$\pi_{i-1}=n$ and $\pi_{i}=n-1$ for $2\leq i<n$. In this case,
$\pi_{i+1}\cdots\pi_{n}$ must be an increasing permutation or else, there is
an occurrence of $p$ involving the elements $n-1$ and $n$. There are $c(n-1)$
permutations in this case since removing $n$ we obtain a permutation
$\pi^{\prime}$ counted by $c(n-1)$ and $n$ can be inserted back in any such
$\pi^{\prime}$ next to the left of $n-1$ without introducing an occurrence of
$p$.

Summarising all the cases above, we obtain

$a(n)=3a(n-1)-a(n-2)+c(n-1).$ (3)

Next, we find a recurrence relation for $c(n)$. Supposed that
$\pi=\pi_{1}\cdots\pi_{n}$ is an $n$-permutation counted by $c(n)$. We
consider all possibilities for position of $n-1$ in $\pi$.

  * •

$n-1$ is to the left of $n$, in which case $n-1$ must be immediately to the
left of $n$ to avoid $p$. But then, removing $n$ from $\pi$ we obtain a
$p$-equivalent permutation counted by $c(n-1)$. So, there are $c(n-1)$
permutations in this case.

  * •

$\pi_{n-1}\pi_{n}=n(n-1)$. Removing $n(n-1)$ from $\pi$ we obtain a
$p$-avoiding $(n-2)$-permutation, and conversely, we can adjoin $n(n-1)$ to
the right of any permutation counted by $a(n-2)$ without creating an
occurrence of $p$. Hence, we have $a(n-2)$ permutations in this case.

  * •

$\pi_{i}\cdots\pi_{n}=n\pi_{i+1}\cdots\pi_{n-1}(n-1)$ where $i<n-1$ and
$\pi_{i+1}\cdots\pi_{n-1}$ is an increasing permutation. Removing $(n-1)$ we
obtain a permutation counted by $c(n-1)$, and conversely, we can adjoin the
element $n-1$ at the end of any permutation $\pi^{\prime}$ counted by $c(n-1)$
(and replacing $n-1$ in $\pi^{\prime}$ by $n$) without introducing an
occurrence of $p$. Hence, we have $c(n-1)$ permutations in this case.

So, $c(n)=2c(n-1)+a(n-2)$. Now, we will prove by induction by $n$ that
$c(n)=a(n)-2a(n-1)+1$ for $n\geq 1$. The base cases of $c(1)=0$ and $c(2)=1$
are easy to check. Suppose $c(n-1)=a(n-1)-2a(n-2)+1$, then

$c(n)=2c(n-1)+a(n-2)=c(n-1)+a(n-1)-a(n-2)+1=a(n)-2a(n-1)+1$

as desired, where the last equality is obtained by using (3). Finally,

$a(n)=3a(n-1)-a(n-2)+c(n-1)=4a(n-1)-3a(n-2)+1.$

∎

######  Theorem 3.4.

For the N-bipartite POP $p=$ $1$$2$$3$$4$ , we have $a(0)=a(1)=1$ and, for
$n\geq 2$, $a(n)=4a(n-1)-3a(n-2)+1$, hence giving the formula for $a(n)$ and
the g.f. in the statement of Theorem 3.1.

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}$ be a $p$-avoiding permutation. If $\pi_{1}=n$
then there are clearly $a(n-1)$ such permutations. Let $b(n)$ be the number of
$p$-avoiding $n$-permutations $\pi_{1}\cdots\pi_{n}$ with $\pi_{i}=n$ for
$1<i\leq n$. So,

$a(n)=a(n-1)+b(n).$ (4)

Note that in any permutation counted by $b(n)$,
$\pi_{i+1}>\pi_{i+2}>\cdots>\pi_{n}$ because if $\pi_{j}<\pi_{s}$ for some
$i<j<s\leq n$ then the elements $\pi_{1}$, $n$, $\pi_{j}$ and $\pi_{s}$ form
an occurrence of $p$. We claim that

$b(n)=3b(n-1)+1.$ (5)

Indeed, permutations counted by $b(n)$ fall in one of the following four
cases, where we noted that if the element $n-1$ is to the left of $n$ then
either the elements are next to each other, or $\pi_{1}=n-1$ (otherwise, an
occurrence of $p$ involving $n$ and $n-1$ would be created):

  * •

The element $n-1$ is to the right of $n$, and hence $\pi_{i+1}=n-1$. Removing
$n$ we obtain a permutation counted by $b(n-1)$. Vice versa, any permutation
counted by $b(n-1)$ can be extended to a permutation counted by $b(n)$ by
inserting $n$ immediately to the left of the element $n-1$. Thus, we have
$b(n-1)$ permutations in this case.

  * •

$\pi_{1}=n-1$ and $\pi_{2}=n$. There is one such permutation.

  * •

$\pi_{1}=n-1$, $\pi_{2}\neq n$. Removing $n-1$ and replacing $n$ by $n-1$ in
the obtained permutation, we get a permutation counted by $b(n-1)$. This
operation is invertible as $n-1$ in the leftmost position of an
$n$-permutation cannot be involved in an occurrence of $p$. Hence, we have
$b(n-1)$ permutations in this case.

  * •

$\pi_{i-1}\pi_{i}=(n-1)n$ for $i>2$. It is easy to check that removing $n$ we
obtain a $p$-equivalent permutation counted by $b(n-1)$. Thus, we have
$b(n-1)$ permutations in this case completing our proof of (5).

From (4) and (5), to complete the proof of the theorem, clearly we only need
to show that, for $n\geq 2$,

$b(n)=3a(n-1)-3a(n-2)+1.$

Indeed, from (4), $3a(n-1)-3a(n-2)=3b(n-1)$, and hence

$3a(n-1)-3a(n-2)+1=3b(n-1)+1=b(n)$

as desired. ∎

######  Theorem 3.5.

For the POP $p=$ $1$$3$$2$$4$ , we have $a(0)=a(1)=1$ and, for $n\geq 2$,
$a(n)=4a(n-1)-3a(n-2)+1$, hence giving the formula for $a(n)$ and the g.f. in
the statement of Theorem 3.1.

###### Proof.

The base cases are clearly true, so let $n\geq 2$. Let
$\pi=\pi_{1}\cdots\pi_{n}$ be a $p$-avoiding permutation. Clearly,
$\pi_{1}\in\\{n-1,n\\}$ or $\pi_{2}\in\\{n-1,n\\}$ since otherwise the
elements $\pi_{1},\pi_{2},n-1,n$ in $\pi$ form an occurrence of $p$. This
explains the term $4a(n-1)-2a(n-2)$ as we can insert either $n-1$ or $n$ in
either the first or the second position in a $p$-avoiding $(n-1)$-permutation
and subtract the case counted twice when $\\{\pi_{1},\pi_{2}\\}=\\{n-1,n\\}$.
However, some of the $n$-permutations counted by the term $4a(n-1)$ are not
$p$-avoiding, as they contain an occurrence of $p$ with $n-1$ playing the role
of $1$. We say that a permutation is bad if $n-1\in\\{\pi_{1},\pi_{2}\\}$,
$n\not\in\\{\pi_{1},\pi_{2}\\}$, $\pi$ has an instance of $p$ but the
permutation $\pi^{\prime}$ obtained from $\pi$ by removing $n-1$ and reducing
$n$ by $1$ is $p$-avoiding. Let $b(n)$ be the number of bad $n$-permutations.
Then

$a(n)=4a(n-1)-2a(n-2)-b(n).$ (6)

Note that any bad $n$-permutation is of the form
$(n-1)\pi_{2}\cdots\pi_{i}n\pi_{i+2}\cdots\pi_{n}$, where

  * •

$2\leq i\leq n-2$ (that is, $\pi_{2}\neq n$ and $\pi_{n}\neq n$), and

  * •

there exist $x\in\\{\pi_{2},\ldots,\pi_{i}\\}$ and
$y\in\\{\pi_{i+2},\ldots,\pi_{n}\\}$ such that $x<y$.

Indeed, if $\pi_{1}=n-1$ and it plays the role of $1$ in an occurrence of $p$
then the role of $3$ must be played by $n$, so that there exist $x$ and $y$
with the properties described above. On the other hand, if $\pi_{2}=n-1$ and
$\pi_{2}xny$ is an occurrence of $p$ then clearly $x\neq n-2$. But since
$\pi^{\prime}$ is $p$-avoiding, we have $\pi_{1}=n-2$ or $\pi_{3}=n-2$. This
leads to a contradiction with $(n-2)x(n-1)y$ being an occurrence of $p$ in
$\pi^{\prime}$ showing that no bad $n$-permutation with $\pi_{2}=n-1$ exists.

We next show, by induction on $n$, that $b(n)=a(n-2)-1$ (for $n\geq 2$), which
gives us the desired result by (6). The three base cases hold as there are no
bad $n$-permutations for $n=2,3$, and the only bad $4$-permutation is $3142$.
Suppose now that $n\geq 5$ and the statement holds for smaller length
permutations.

Since each bad $n$-permutation begins with $n-1$, we can remove this element,
replace $n$ by $n-1$ in the obtained permutation, and focus on an equivalent
problem of counting $p$-avoiding $(n-1)$-permutations having a subsequence
$x(n-1)y$, $x<y$; we call such $(n-1)$-permutations r-bad (standing for
“reduced bad”). Clearly, removing the element $n-1$ from an r-bad permutation
results in a $p$-avoiding $(n-2)$-permutation, so we will generate all r-bad
permutations from the permutations counted by $a(n-2)$ by inserting the
element $n-1$.

We can see that inserting $n-1$ in the first position does not result in an
r-bad permutation. If $n-1$ is inserted in the second position of a
$p$-avoiding $(n-2)$-permutation $\pi=\pi_{1}\cdots\pi_{n-2}$, then the
obtained permutation is r-bad if and only if $\pi_{1}\neq n-2$ (as only then
we obtain the subsequence $x(n-1)y$; also, note that no occurrence of $p$ can
be introduced in this case). This gives us $a(n-2)-a(n-3)$ r-bad
$(n-1)$-permutations since the number of $p$-avoiding $(n-2)$-permutations
beginning with $n-2$ is clearly $a(n-3)$.

Suppose now that $n-1$ is inserted in position $i$, $3\leq i\leq n-2$. Since
the result of the insertion is a $p$-avoiding permutation
$\pi^{\prime}=\pi^{\prime}_{1}\cdots\pi^{\prime}_{n-1}$, we see that either
$\pi^{\prime}_{1}=n-2$ or $\pi^{\prime}_{2}=n-2$ (otherwise,
$\pi^{\prime}_{1},\pi^{\prime}_{2},n-2,n-1$ form an occurrence of $p$). We
consider these two cases.

  * •

$\pi^{\prime}_{1}=n-2$. $\pi^{\prime}$ must contain a subsequence $x(n-1)y$,
$x<y$, and clearly $x\neq n-2$. But then $(n-2)x(n-1)y$ is an occurrence of
$p$, a contradiction showing that no r-bad permutations can be obtained in
this case.

  * •

$\pi^{\prime}_{2}=n-2$. We claim that removing the element $n-2$ in
$\pi^{\prime}$ and replacing the element $n-1$ by $n-2$, one obtains an r-bad
$(n-2)$-permutation $\pi^{\prime\prime}$. Indeed, $\pi^{\prime}_{2}=n-2$
cannot be involved in an occurrence of $p$, or be the $x$ in the subsequence
$x(n-1)y$, $x<y$. Hence, $\pi^{\prime}$ is r-bad if an only if
$\pi^{\prime\prime}$ is r-bad, and therefore the number of bad permutations
$\pi^{\prime}$ of this type is given by $b(n-1)$, which is $a(n-3)-1$ by the
induction hypothesis.

To summarise the cases above, $b(n)=a(n-2)-a(n-3)+a(n-3)-1=a(n-2)-1$, as
desired. ∎

######  Theorem 3.6.

For the POP $p=$ $1$$4$$3$$2$ , we have $a(0)=a(1)=1$ and, for $n\geq 2$,
$a(n)=4a(n-1)-3a(n-2)+1$, hence giving the formula for $a(n)$ and the g.f. in
the statement of Theorem 3.1.

###### Proof.

Let $b(n)$ be the number of $p$-avoiding permutations $\pi_{1}\cdots\pi_{n}$
such that $\pi_{n}\neq 1$ and each element to the left of the element 1 (if
any) is larger than any element to the right of 1.

Let us compute $a(n)$. Suppose that $\pi=\pi_{1}\cdots\pi_{n}$ is
$p$-avoiding. If $\pi_{n}=1$ or $\pi_{n}=2$ then $\pi_{n}$ cannot be involved
in an occurrence of $p$. Hence there are $2a(n-1)$ such permutations. Further,
if $\pi_{n}\neq 1$ and $\pi_{n}\neq 2$ and the elements 1 and 2 are not next
to each other in $\pi$, then clearly there is an occurrence of $p$ in $\pi$
involving $1$, $2$ and $\pi_{n}$, which is impossible. Consider two cases.

  * •

Suppose that $\pi_{i-1}=1$ and $\pi_{i}=2$ for some $i\in[2,n-1]$. Then the
permutation $\pi^{\prime}=\pi^{\prime}_{1}\cdots\pi^{\prime}_{n-1}$ obtained
from $\pi$ by removing the element 1 and decreasing all other elements by 1 is
$p$-equivalent to $\pi$. Indeed, if the element 1 plays the role of $1$ in an
occurrence of $p$ in $\pi$ then the element $2$ cannot play the role of $2$ in
that occurrence since there are no candidates for an element to play the role
of $3$ in this case. On the other hand, if the element 1 plays the role of $3$
in an occurrence of $p$ in $\pi$ then the element 2 cannot play the role of
$4$ in that occurrence since there is no candidate to play the role of $1$
(which would have to be less than 2). Hence, in both cases, any time the
element 1 is involved in an occurrence of $p$, the element 2 may be involved
in the same occurrence of $p$ in $\pi^{\prime}$. We have $a(n-1)-a(n-2)$ such
permutations since in $\pi^{\prime}_{n-1}\neq 1$.

  * •

Suppose that $\pi_{i-1}=2$ and $\pi_{i}=1$ for $2\leq i<n$. If there exist
$k<i-1$ and $j>i$ such that $\pi_{k}<\pi_{j}$ then the elements $\pi_{k}$,
$2$, $1$ and $\pi_{j}$ would form an occurrence of $p$, which is impossible.
If such $k<i-1$ and $j>i$ do not exist, then the permutation obtained from
$\pi$ by removing the element 1 and reducing every other element by 1 is
$p$-equivalent to $\pi$. Indeed, if the element 1 plays the role of $1$ in an
occurrence of $p$ then 2 also plays the role of $1$ in the same occurrence of
$p$ in $\pi^{\prime}$. Also, 1 cannot play the role of $3$ since there is no
candidate for the role of $1$ in that case (which would have to be less than
the element playing the role of $4$). We have $b(n-1)$ such permutations.

From our considerations above, we see that

$a(n)=3a(n-1)-a(n-2)+b(n-1).$ (7)

Next, we computer $b(n)$. Suppose that $\pi=\pi_{1}\cdots\pi_{n}$ is
$p$-avoiding, $\pi_{i}=1$ for some $i\in[1,n-1]$ and for all $0\leq k<i<j\leq
n$ we have $\pi_{k}>\pi_{j}$ where $\pi_{0}:=\infty$. Let $\pi_{j}=2$ then by
definition $j>i$. We consider three cases.

  * •

$i=n-1$, $j=n$. Clearly, the permutation obtained by removing 1 and 2 from
$\pi$ and reducing every other element by 2 is $p$-equivalent to $\pi$ (none
of 1 and 2 can play the role of $4$ in an occurrence of $p$). Therefore, we
have $a(n-2)$ such permutations.

  * •

$i<n-1$, $j\in[i+2,n-1]$. This case is impossible since then the elements $1$,
$\pi_{i+1}$, $2$, $\pi_{n}$ form an occurrence of $p$.

  * •

$i<n-1$, $j\in\\{i+1,n\\}$. It is easy to see that the permutation obtained by
removing the element 2 from $\pi$ and reducing each element in $[3,n]$ by 1 is
$p$-equivalent to $\pi$. Hence, we have $2b(n-1)$ such permutations.

Summarising the three cases above, we have

$b(n)=2b(n-1)+a(n-2).$

The recursion for $b(n)$ is the same as that for $c(n)$ in the proof of
Theorem 3.3, so we can conclude from that proof that $b(n)=a(n)-2a(n-1)+1$,
which gives us the desired recursion for $a(n)$ from (7). ∎

###  3.2 N-patterns in Wilf-equivalence class 2 in Table 1

######  Theorem 3.7.

For the POP $p=$ $1$$4$$2$$3$ we have $a(0)=a(1)=1$ and, for $n\geq 2$,
$a(n)=4a(n-1)-3a(n-2)+a(n-3)$, hence giving the formula for $a(n)$ and the
g.f. in the statement of Theorem 3.2.

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}$ be a $p$-avoiding $n$-permutation. Clearly,
$\\{\pi_{1},\pi_{2}\\}\cap\\{n-1,n\\}\neq\emptyset$ as otherwise there would
be an occurrence of $p$ in $\pi$. Moreover, if $\pi_{1}=n$ or $\pi_{2}=n$ then
$n$ cannot be involved in an occurrence of $p$ in $\pi$, and hence there are
$2a(n-1)$ such permutations. Also, if $\pi_{2}=n-1$ and $\pi_{1}\neq n$ then
removing $n-1$ from $\pi$ and decreasing $n$ by 1 we obtain a $p$-equivalent
permutation $\pi^{\prime}=\pi^{\prime}_{1}\cdots\pi^{\prime}_{n-1}$, since
$n-1$ cannot play the role of $2$ in an occurrence of $p$, while if $n-1$
plays the role of $1$ in an occurrence of $p$ then $\pi_{1}$ also plays the
role of $1$ in an occurrence of $p$ in $\pi^{\prime}$. Since
$\pi^{\prime}_{1}\neq n-1$ we have $a(n-1)-a(n-2)$ such permutations.

We let $b(n)$ be the number of $p$-avoiding $n$-permutations $\pi$ such that
$\pi_{1}=n-1$ and $\pi_{2}\neq n$. Then

$a(n)=3a(n-1)-a(n-2)+b(n).$

Let us compute $b(n)$. Suppose that $\pi$ is a permutation counted by $b(n)$
such that $\pi_{1}=n-1$, $\pi_{i}=n$ for $i>2$ and $\pi_{j}=n-2$. We consider
five possible cases.

  * •

If $j=2$ and $i=3$ then removing from $\pi$ the elements $n-2$, $n-1$, $n$, we
obtain a $p$-equivalent permutation (none of these elements can play the role
of $1$ in an occurrence of $p$). Hence, we have $a(n-3)$ permutations in this
case.

  * •

If $j=2$ and $i>3$ then the permutation $\pi^{\prime}$ obtained from $\pi$ by
removing $n-1$ and decreasing $n$ by 1 is $p$-equivalent to $\pi$. Indeed, if
the element $n-1$ plays the role of $1$ in an occurrence of $p$ in $\pi$ then
the element $n-2$ cannot play the role of $2$, and therefore $n-2$ may play
the role of $1$ in the same occurrence of $p$ in $\pi^{\prime}$. Since $i>3$,
we have $b(n-1)$ such permutations.

  * •

If $2<j<i$ then the elements $n-1$, $\pi_{2}$, $n-2$, $n$ form an occurrence
of $p$, so this case is impossible.

  * •

If $3<i<j$ then the elements $\pi_{2}$, $\pi_{3}$, $n$, $n-2$ form an
occurrence of $p$, so this case is impossible.

  * •

If $i=3$ and $j>i$ then removing the elements $n-1$ and $n$ we obtain a
$p$-equivalent permutation
$\pi^{\prime}=\pi^{\prime}_{1}\cdots\pi^{\prime}_{n-1}$. Indeed, $n-1$ cannot
play the role of $1$ in an occurrence of $p$ in $\pi$ because $n$ cannot play
the role of $4$, and since $n-1$ is not involved in an occurrence of $p$ then
$n$ also cannot be involved in an occurrence of $p$. Since
$\pi^{\prime}_{1}\neq n-2$, we have $a(n-2)-a(n-3)$ such permutations.

Summarizing the cases, we have

$b(n)=a(n-3)+b(n-1)+a(n-2)-a(n-3)=b(n-1)+a(n-2)$
$=b(n-2)+a(n-2)+a(n-3)=\cdots=\sum_{i=1}^{n-2}a(i).$

Hence,

$a(n)=3a(n-1)-a(n-2)+b(n)=3a(n-1)+\sum_{i=1}^{n-3}a(i)$

and $a(n)-a(n-1)=3a(n-1)-3a(n-2)+a(n-3)$ giving the desired result. ∎

###  3.3 N-patterns in Wilf-equivalence class 3 in Table 1

######  Theorem 3.8.

For the N-bipartite POP $p=$ $3$$1$$4$$2$ , we have $a(n)=n!$ for $n\leq 3$
and, for $n\geq 4$, $a(n)=3a(n-1)+a(n-2)-a(n-3)$.

###### Proof.

Suppose that $\pi=\pi_{1}\cdots\pi_{n}$ is a $p$-avoiding $n$-permutation.
Clearly, at least one of $\pi_{n-1}$ and $\pi_{n}$ is $n-1$ or $n$, since
otherwise there is an occurrence of $p$ involving $n-1$ and $n$. There are
$2a(n-1)$ permutations in question in which $\pi_{n}\in\\{n-1,n\\}$. Hence,
letting $b(n)$ (resp., $c(n)$) be the number of $p$-avoiding $n$-permutations
with $\pi_{n}<n-1$ and $\pi_{n-1}=n$ (resp., $\pi_{n-1}=n-1$), we have

$a(n)=2a(n-1)+b(n)+c(n).$

Let us compute $b(n)$. Clearly, removing $n$ from $\pi$ we obtain a
$p$-equivalent permutation in which the maximum element $n-1$ is not the
rightmost. Hence, there are $a(n-1)-a(n-2)$ such permutations.

Next, we compute $c(n)$. We have $\pi_{n-1}=n-1$ and we let $\pi_{j}=n-2$ and
$\pi_{i}=n$ for $i\neq n$ and $j\leq n$. We consider three cases.

  * •

$j=n$. In this case, removing $n-1$ and $n-2$ from $\pi$ and reducing $n$ by
2, we get a $p$-equivalent permutation. Indeed, if $n-2$ plays the role of $4$
in an occurrence of $p$ in $\pi$ then $n$ and $n-1$ must play the roles of $1$
and $2$, but there is no candidate for the role of $3$. Also, clearly, $n-1$
cannot play the role of $4$ in an occurrence of $p$ in $\pi$. Hence, there are
$a(n-2)$ permutations in this case.

  * •

$i=n-2$ and $j<n-2$. In this case, removing $n$ from $\pi$ we get a
$p$-equivalent permutation
$\pi^{\prime}=\pi^{\prime}_{1}\cdots\pi^{\prime}_{n-1}$. Indeed, $n$ cannot
play the roles of $3$ or $4$ in an occurrence of $p$ in $\pi$, and if $n$
plays the role of $2$, then $n-1$ must play the role of $3$, but we have no
candidate for the role of $1$. Also, $\pi^{\prime}_{n-2}=n-1$ and
$\pi^{\prime}_{n-1}\neq n-2$, so we have $b(n-1)=a(n-2)-a(n-3)$ permutations
in this case.

  * •

$i<n-2$ and $j<n-1$. In this case $\pi$ contains an occurrences of $p$.
Indeed, if $i<j$ then $n$, $n-2$, $n-1$, $\pi_{n}$ form an occurrence of $p$,
while if $j<i$ then $n-2$, $n$, $\pi_{n-2}$, $\pi_{n}$ form an occurrence of
$p$.

Summarising the cases above, $c(n)=2a(n-2)-a(n-3)$ and

$a(n)=2a(n-1)+b(n)+c(n)=2a(n-1)+a(n-1)-a(n-2)+2a(n-2)-a(n-3)$
$=3a(n-1)+a(n-2)-a(n-3),$

as desired. ∎

##  4 POPs defined by disjoint chains

The minimal disconnected non-trivial bipartite graph $K_{2}\cup K_{1}$
corresponds, up to complementing the labels and taking the mirror image with
respect to a horizontal line, to two non-Wilf-equivalent POPs $p_{1}=$
$1$$2$$3$ and $p_{2}=$ $1$$3$$2$ for which the avoidance formulas $a_{1}(n)=n$
and $a_{2}(n)=F_{n}$, the $n$-th Fibonacci number, are well-known and easy to
derive.

In this section we prove some interesting results concerning a generalization
of the POP $p_{1}$. We introduce the notion of a disjoint chains POP, or DC
POP, that is a POP defined by disjoint chains. DC POPs extend the notion of
multi-patterns introduced in [5] to the case of non-consecutive patterns. A DC
POP $[\sigma_{1},\ldots,\sigma_{m}]$ of length $k$, where red$(\sigma_{i})\in
S_{k_{i}}$ and $\sum_{i=1}^{m}k_{i}=k$, is defined by $m$ disjoint chains so
that the $i$-th path is labeled by
$\\{1+\sum_{j=1}^{i-1}k_{j},\ldots,\sum_{j=1}^{i}k_{j}\\}$ giving the
permutation $\sigma_{i}$ when reading from top to bottom. For example,
[12,43,65] and [231,54,678,(11)9(10)] correspond, respectively, to the POPs

${\small 1}$${\small 2}$${\small 4}$${\small 3}$${\small 6}$${\small 5}$ |  and |  ${\small 3}$${\small 2}$${\small 1}$${\small 5}$${\small 4}$${\small 6}$${\small 7}$${\small 8}$${\small 11}$${\small 9}$${\small 10}$
---|---|---

Clearly, a DC POP with each $\sigma_{i}$ being of length 2 is a bipartite POP.

In this section we deal with the exponential generating function (e.g.f.) for
a sequence $a(n)$, which is $A(x)=\sum_{n\geq 0}a(n)\frac{x^{n}}{n!}$. A
permutation $\pi=\pi_{1}\cdots\pi_{n}$ quasi-avoids a POP $p$ if it contains
at least one occurrence of $p$ but the permutation
red($\pi_{1}\cdots\pi_{n-1}$) contains no occurrences of $p$. For example, the
permutation $\pi=416532$ quasi-avoids the complete bipartite POP
$p=(\\{1,2\\}/\\{3,4\\})$ since $\pi$ contains three occurrences of $p$ while
the permutation red(41653)=31542 avoids $p$. We let $a^{\star}(n)$ denote the
number of $n$-permutations quasi-avoiding the pattern in question and
$A^{\star}(x)$ is the respective e.g.f.. The notion of quasi-avoidance was
first introduced in [5] for so-called consecutive patterns (that is, patterns
whose occurrences form contiguous subsequences in permutations). Essentially
copy/pasting the arguments from [5] for consecutive patterns, we can derive
the following results.

######  Proposition 4.1.

Let $p$ be a POP and $A(x)$ (resp. $A^{\star}(x)$) is the e.g.f. for the
number of permutations that avoid (resp. quasi-avoid) $p$. Then,

$A^{\star}(x)=(x-1)A(x)+1.$

###### Proof.

We first show that

$a^{\star}(n)=n\cdot a(n-1)-a(n).$ (8)

Indeed, extending, in all possible ways, each $(n-1)$-permutation avoiding $p$
to the right by adjoining an element gives $n\cdot a(n-1)$ $n$-permutations.
The set of these permutations is a disjoint union of the set of all
$n$-permutations that avoid $p$ and the set of all $n$-permutations that
quasi-avoid $p$, which gives (8). Multiplying both sides of (8) by $x^{n}/n!$
and summing over all $n$, as well as observing that $a^{\star}(0)=0$, we
obtain the desired result. ∎

######  Theorem 4.2.

Let $p$ be an arbitrary POP, and the POP $p^{\prime}$ is obtained from $p$ by
increasing each label by $k$ and adding a disjoint path labeled by a
permutation $\sigma$ of $\\{1,\ldots,k\\}$ (from top to bottom). Let $C(x)$
(resp., $A(x)$, $B(x)$) be the e.g.f. for the number of permutations avoiding
$p^{\prime}$ (resp., $\sigma$, $p$). Then,

$C(x)=A(x)+B(x)A^{\star}(x).$

###### Proof.

Let $a(n)$, $b(n)$, $c(n)$ be the number of $n$-permutations avoiding the
patterns $\sigma$, $p$ and $p^{\prime}$, respectively. If a permutation
$\pi=\pi_{1}\cdots\pi_{n}$ avoids $\sigma$ then it avoids $p^{\prime}$.
Otherwise, $\pi_{1}\cdots\pi_{i}$ quasi-avoids $\sigma$ for a unique $i$,
$k\leq i\leq n$. But then $\pi_{i+1}\pi_{i+2}\cdots\pi_{n}$ must avoid $p$.
Hence,

$c(n)=a(n)+\displaystyle\sum_{i=0}^{n}{n\choose i}a^{\star}(i)b(n-i)$ (9)

since $a^{\star}(i)=0$ for $i=0,\ldots,k-1$. Multiplying both sides of (9) by
$x^{n}/n!$ and taking the sum over all $n$ we get the desired result. ∎

The following corollary of Theorem 4.2 shows that all DC bipartite POPs are
Wilf-equivalent.

######  Corollary 4.3.

Let $p=[\sigma_{1},\ldots,\sigma_{m}]$ be a bipartite POP of length $2m$ and
$C(x)$ is the e.g.f. for the number of $p$-avoiding permutations. Then,

$C(x)=\frac{1-(1+(x-1)e^{x})^{m}}{1-x}.$

###### Proof.

We use Theorem 4.2, induction on $m$ and the fact that $A(x)=e^{x}$ (there is
only one $\sigma_{i}$-avoiding $n$-permutation for each $n\geq 0$) and thus by
Proposition 4.1, $A^{\star}(x)=1+(x-1)e^{x}$. ∎

Corollary 4.3 can be generalized as follows.

######  Theorem 4.4.

Let $p=[\sigma_{1},\ldots,\sigma_{m}]$ be a DC POP and $A_{i}(x)$ is the
e.g.f. for the number of ${\sigma}_{i}$-avoiding permutations. Then, the
e.g.f. $A(x)$ for the number of $p$-avoiding permutations is

$A(x)=\displaystyle\sum_{i=1}^{m}A_{i}(x)\displaystyle\prod_{j=1}^{i-1}((x-1)A_{j}(x)+1).$

###### Proof.

We use Theorem 4.2 and prove by induction on $k$ that

$A(x)=\displaystyle\sum_{i=1}^{m}A_{i}(x)\displaystyle\prod_{j=1}^{i-1}A^{\star}_{j}(x).$

The rest is given by an application of Proposition 4.1. ∎

##  5 Concluding remarks

There is of a host of research directions that can be taken based on our
paper, and we will briefly discuss here just some of them.

Can one generalize/extend Theorems 2.1 and 2.3 dealing with $A=\\{i,i+1\\}$
and $A=\\{i,i+2\\}$, respectively, to the case of $A=\\{i,i+s\\}$ for any
$s\geq 1$?

The Wilf-equivalent classes in Table 1 raise a number of interesting
questions. Indeed, while some of our proofs for the same recurrence relation
look quite similar (e.g. those of Theorems 3.3 and 3.6), some others are
rather different (e.g. those of Theorems 3.4 and 3.5). That would be
interesting to find direct (simple) bijections (rather than recursive
bijections) explaining (some of) Wilf-equivalences from different rows in
Table 1.

Another natural research direction is in extending our classification and/or
enumerative results for N-patterns to POPs defined by paths of the forms

$\cdots$ |  | and |  |  $\cdots$ .
---|---|---|---|---

In particular, the next natural step is in studing such POPs of length 5 that
we call $M$-patterns. For example, the avoidance sequence for the M-pattern
$2$$1$$4$$3$$5$ begins with 1, 2, 6, 24, 104, 448, 1888, 7808, 31872, … and
this sequence is not in [8]. For another example, the avoidance sequence for
the M-pattern $1$$3$$2$$4$$5$ begins with 1, 2, 6, 24, 104, 448, 1888, 7808,
31872, … and this sequence is also not in [8].

Finally, that could be interesting to obtain (general) enumerative/Wilf-
equivalence results for POPs defined by bipartite graphs of some regular
shapes, e.g. such as

$\cdots$

.

## References

  * [1] M. Albert, M.-L. Lackner, M. Lackner, V. Vatter. The complexity of pattern matching for 321-avoiding and skew-merged permutations. Discrete Math. & Theor. Comp. Sci. 18 (2016) 2, #11.
  * [2] D. Bevan, R. Brignall, A. Elvey Price, J. Pantone. A structural characterisation of Av(1324) and new bounds on its growth rate. European J. Combin. 88 (2020), 103115.
  * [3] A. Conway, A. Guttmann, P. Zinn-Justin. 1324-avoiding permutations revisited. Advances in Appl. Math. 96 (2018), 312–333.
  * [4] A. Gao, S. Kitaev. On Partially Ordered Patterns of Length 4 and 5 in Permutations. Electronic J. Combin. 26 (2019) 3, 31pp.
  * [5] S. Kitaev. Partially ordered generalized patterns. Discrete Math. 298 (2005), 212–229.
  * [6] S. Kitaev. A survey on partially ordered patterns. In Permutation Patterns (2010), S. Linton, N. Ruskuc, and V. Vatter, Eds., vol. 376 of London Mathematical Society Lecture Note Series, Cambridge University Press, 115–135.
  * [7] D. Marchant. 2413-balloon permutations and the growth of the Möbious function. Electronic J. Combin. 27 (2020) 1, P1.7.
  * [8] N. J. A. Sloane. The Online Encyclopedia of Integer Sequences. Published electronically at http://oeis.org.
  * [9] K. T. K. Yap, D. L. Wehlau, I. Zaguia. Permutations avoiding certain partially-ordered patterns. Electron. J. Comb. 28 (2021) 3, 41pp..


# Bot Detection in GitHub Repositories

Natarajan Chidambaram  0000-0002-2295-8928<EMAIL_ADDRESS>Software Engineering Lab, University of MonsMonsBelgium and  Pooya Rostami
Mazrae  1234-1234-1234-1234<EMAIL_ADDRESS>Software
Engineering Lab, University of MonsMonsBelgium

(2022)

###### Abstract.

Contemporary social coding platforms like GitHub promote collaborative
development. Many open-source software repositories hosted in these platforms
use machine accounts (bots) to automate and facilitate a wide range of effort-
intensive and repetitive activities. Determining if an account corresponds to
a bot or a human contributor is important for socio-technical development
analytics, for example, to understand how humans collaborate and interact in
the presence of bots, to assess the positive and negative impact of using
bots, to identify the top project contributors, to identify potential bus
factors, and so on. Our project aims to include the trained machine learning
(ML) classifier from the BoDeGHa bot detection tool as a plugin to the
GrimoireLab software development analytics platform.

In this work, we present the procedure to form a pipeline for retrieving
contribution and contributor data using Perceval, distinguishing bots from
humans using BoDeGHa, and visualising the results using Kibana.

††journalyear: 2022††copyright: acmcopyright††conference: 19th International
Conference on Mining Software Repositories; May 23–24, 2022; Pittsburgh, PA,
USA††booktitle: 19th International Conference on Mining Software Repositories
(MSR ’22), May 23–24, 2022, Pittsburgh, PA, USA††price: 15.00††doi:
10.1145/3524842.3528520††isbn: 978-1-4503-9303-4/22/05

##  1\. Introduction

Social coding platforms like GitHub promote collaboration and interaction
between developers (Dabbish et al., 2012). Along with this opportunity for
engagement, developers also face some workload in performing error-prone,
time-intensive or repetitive tasks such as conducting quality checks, testing,
code reviewing, merging, building, deploying, and so on (Wessel et al., 2018).
Thus, the developer overload increases as the frequency of these tasks
increases (Young et al., 2021). Bots (machine accounts that act with as
minimal human intervention as possible) are therefore frequently used to face
this ever-increasing complexity in software development (Erlenhov et al.,
2019).

There are many bot accounts that are built by software developers and are used
only in a specific set of repositories. For instance, the _highfive_ account
is responsible for greeting and assigning issues to contributors in
_servo/servo_ , one of the largest packages distributed through the Cargo
package manager. Similarly, the _bors-diem_ bot is managing the merging of
pull requests (PR) in the _diem/diem_ Cargo package. However, they are not
evidently identified as bots as they neither have bot in their name nor their
GitHub description/bio111https://github.com/bors-servo and
https://github.com/libra-action conveys this explicitly. The challenge of
identifying bot accounts makes it difficult to conduct socio-technical
analysis that need to distinguish human from bot behaviour, while doing so
would be valuable for researchers to better understand the positive and
negative impact of bots in software development, as well as for practitioners
and organizations that want to accredit human project contributors (Golzadeh
et al., 2022).

The GrimoireLab software development analytics
toolkit222https://chaoss.github.io/grimoirelab/ provides _data retrieval_
capability with tools such as Perceval and Graal, _data enrichment_ using
tools such as HatStall and SortingHat (for merging duplicate contributor
identities), and _data visualisation_ using tools such as Kidash and KiBiter
(based on Kibana dashboards for visualising Elasticsearch data). Adding a bot
identification model as one of GrimoireLab’s data enrichment components would
enable GrimoireLab users to collect data from GitHub repositories, identify
the bot accounts, and visualise/analyse socio-technical collaborative
development activities using a single platform.

As part of the MSR 2021 Hackathon333Team: NAP; repository:
https://github.com/pooya-rostami/Hackathon-21, we propose the creation of such
an end-to-end pipeline (illustrated in Figure 1) that integrates BoDeGHa
(Golzadeh et al., 2021), a tool to identify bots in GitHub repositories on the
basis of their PR and issue commenting activities. BoDeGHa comes with a
trained machine learning classifier that could be added as a part of the
GrimoireLab pipeline.

Figure 1. Integrating BoDeGHa in the GrimoireLab pipeline

##  2\. Approach and Preliminary Results

Since we aim to improve GrimoireLab’s bot detection capability by integrating
BoDeGHa’s trained machine learning classifier (hereafter addressed as
BoDeGHa), we need to execute the pipeline of Figure 1 with a set of GitHub
repositories. This section presents a step-by-step process that needs to be
followed to query, predict and visualise the number of contributors along with
their type.

In the first step, we pass the GitHub repository and owner name along with the
GitHub API token as an argument to Perceval for querying issues and pull
requests (PRs) in the corresponding repository. The tool returns the comments
present in each issue and PR along with user- and repository-specific
information. Next, we extract the fields _issue/PR number_ , _comments_ ,
_created at_ , and _corresponding author names_ and save them in a CSV file to
execute BoDeGHa bot identification tool. The ML model predicts the type of
contributor (_bot_ or _human_) in the corresponding repository based on
repetition and patterns in the comments made by the contributors in issues and
PRs. The contributor names along with their predicted type (_bot_ or _human_)
are stored in a CSV file. In the last step, we use Kibana (an open user
interface that is used for visualising Elasticsearch data) to present
BoDeGHa’s prediction results.

Figure 2. Number of contributors present in each repository

To illustrate this process of integrating BoDeGHa into the GrimoireLab
pipeline, we use four large GitHub repositories of Cargo packages, namely,
_diem/diem_ , _servo/servo_ , _SergioBenitez/Rocket_ , and
_paritytech/substrate_. Due to their size and popularity, these repositories
are likely to use bots in their collaborative software development process.

Figure 2 shows, without using the integrated bot prediction tool, the number
of contributors that were actively posting comments in each repository between
December 2021 and January 2022. In contrast, Figure 3 provides a fine-grained
view by taking into account the type of contributor (_human_ or _bot_) in each
repository. We observe a proportionally high number of bots in three of the
considered repositories: 6 out of 37 contributors are bots in
_paritytech/substrate_ , 8 out of 24 in _diem/diem_ and 2 out of 6 in
_servo/servo_. Also, it can be observed that all the issue and PR comments in
_tokio-rs/tokio_ were made by human contributors.

##  3\. Going Further

Knowing the types of contributors within a repository could be leveraged for
many other types of visualisation through the Kibana dashboard. For example,
it would be useful to come up with visualisations that reveal whether bots are
among the most active contributors within a given software repository.
Similarly, one could provide visualisations involving data from multiple
repositories, in order to understand how widespread specific bots are being
used.

Given that BoDeGHa can occasionally produce incorrect classifications, it
would also be useful to provide an interface in the BoDeGHa plugin to allow an
operator to rectify misclassified contributor types (in a CSV file that has
the predictions) before visualising the results.

In a similar way, the BoDeGHa plugin could be integrated with SortingHat,
GrimoireLab’s component in charge of managing contributors’ data (including
the flag to mark them as bot) and of adding contributors’ details in the data
shown in Kibiter (Moreno et al., 2019).

Figure 3. Number and type of contributors present in each repository

##  4\. Conclusion

Bots are being prevalently used in collaborative software development on
GitHub to face ever-increasing complexity, by automating effort-intensive and
repetitive activities. Identifying these bots is valuable for researchers
performing socio-technical analysis in software development, as well as for
practitioners and organizations that want to accredit human contributors.
BoDeGHa is one such tool that identifies bot accounts based on their
commenting activity in issues and pull requests. As part of the MSR 2022
Hackathon, we integrated BoDeGHa’s trained machine learning classifier into
the GrimoireLab pipeline, by extracting repository data with Perceval,
identifying bot contributors with BoDeGHa, and visualising the results with
Kibana dashboard.

###### Acknowledgements.

This work is supported by DigitalWallonia4.AI research project ARIAC (grant
number 2010235), as well as by the ARC-21/25 UMONS3 Action de Recherche
Concertée financée par le Ministère de la Communauté française – Direction
générale de l’Enseignement non obligatoire et de la Recherche scientifique

## References

  * (1)
  * Dabbish et al. (2012) Laura Dabbish, Colleen Stuart, Jason Tsay, and Jim Herbsleb. 2012\.  Social Coding in GitHub: Transparency and Collaboration in an Open Software Repository. In _International Conference on Computer Supported Cooperative Work_. 1277–1286.  https://doi.org/10.1145/2145204.2145396
  * Erlenhov et al. (2019) Linda Erlenhov, Francisco Gomes de Oliveira Neto, Riccardo Scandariato, and Philipp Leitner. 2019.  Current and Future Bots in Software Development. In _International Workshop on Bots in Software Engineering (BotSE)_. IEEE, 7–11.  https://doi.org/10.1109/BotSE.2019.00009
  * Golzadeh et al. (2022) Mehdi Golzadeh, Alexandre Decan, and Natarajan Chidambaram. 2022\.  On the accuracy of bot detection techniques. In _International Workshop on Bots in Software Engineering (BotSE)_. IEEE.
  * Golzadeh et al. (2021) Mehdi Golzadeh, Alexandre Decan, Damien Legay, and T. Mens. 2021\.  A ground-truth dataset and classification model for detecting bots in GitHub issue and PR comments.  _Journal of Systems and Software_ 175 (2021).  https://doi.org/10.1016/j.jss.2021.110911
  * Moreno et al. (2019) David Moreno, Santiago Dueñas, Valerio Cosentino, Miguel Angel Fernandez, Ahmed Zerouali, Gregorio Robles, and Jesus M. Gonzalez-Barahona. 2019.  SortingHat: Wizardry on Software Project Members. In _International Conference on Software Engineering: Companion Proceedings (ICSE-Companion)_. IEEE, 51–54.  https://doi.org/10.1109/ICSE-Companion.2019.00036
  * Wessel et al. (2018) Mairieli Wessel, Bruno Mendes De Souza, Igor Steinmacher, Igor S. Wiese, Ivanilton Polato, Ana Paula Chaves, and Marco A. Gerosa. 2018.  The power of bots: Understanding bots in OSS projects.  _The ACM International Conference on Human-Computer Interaction_ (2018).  https://doi.org/10.1145/3274451
  * Young et al. (2021) Jean-Gabriel Young, Amanda Casari, Katie McLaughlin, Milo Z. Trujillo, Laurent Hébert-Dufresne, and James P. Bagrow. 2021.  Which contributions count? Analysis of attribution in open source.  _International Conference on Mining Software Repositories (MSR)_ (2021), 242–253.  https://doi.org/10.1109/MSR52588.2021.00036