\section{Introduction}

Conservation of the spin angular momentum plays an essential role in the interaction between light and electron spin in solids.
The optical selection rule, \textit{i.e.}, the Fermi's golden rule, sets the transition rate of electrons from the ground state to the excited state upon light irradiation.
Exploiting the selection rule, one can excite spin polarized carriers in semiconductors\cite{zutic2002prl,ganichev2004prl,ando2010apl,endres2013ncomm} or in systems with spin-momentum locked bands\cite{mciver2012nnano,yuan2014nnano,okada2016prb,pan2017ncomm,ma2017nphys,puebla2019prl}.
It is generally understood that the efficiency to excite such carriers is the largest when the light energy is close to the energy band gap of the system.

Significant light induced effects have also been observed in metals, where there is no band gap.
For example, application of ultrashort polarized laser pulses to magnetic thin films allows manipulation of the magnetization\cite{beaurepaire1996prl,kimel2005nature,satoh2010prl} and can lead to light induced magnetization switching\cite{stanciu2007prl,lambert2014science}.
In many cases, the orientation of the magnetization is defined by the helicity of circularly polarized light.
Recent studies have shown that irradiation of ultrashort laser pulses to ferromagnetic metal/heavy metal bilayers results in emission of electromagnetic waves in the THz range\cite{kampfrath2013nnano,huisman2016nnano,seifert2016nphoton}.
In this case, linearly polarized light is typically used to generate THz signals.
Although the underlying mechanism of all optical switching and THz emission is under debate, two different processes are considered to contribute to the effects\cite{berritta2016prl,qaiumzadeh2016prb,freimuth2016prb,tokman2020prb}.
The optical spin transfer torque is a direct transfer of spin angular momentum from light to electrons\cite{choi2015nphys}, while the inverse Faraday effect (IFE) can be considered equivalent to applying an effective magnetic field associated with circularly polarized light\cite{kimel2005nature,stanciu2007prl,lambert2014science,john2017scirep}.
As the light intensity required to observe these effects are extremely large, means to increase their efficiencies are being sought.

Here we show, from helicity dependent photocurrent measurements, that irradiation of circularly polarized light to Bi-based Dirac semimetals\cite{murakami2006prl,li2008science,fuseya2009prl} induces a giant effective magnetic field along the light spin angular momentum.
The experimental results suggest that the effective magnetic field peaks at the Dirac point with its maximum being significantly larger than that of typical transition metals induced by the IFE.
We consider the giant IFE is due to the unique characteristics of carriers in Dirac semimetals.

Semimetal thin films are deposited on SiO$_2$ substrates using RF magnetron sputtering.
Here we show representative results from Bi, Bi$_{1-x}$Sb$_x$ alloy, Sn- or Te-doped Bi thin films with a thickness of $t$ (see supplementary material for the details of sample preparation and device characterization).
A seed layer of 0.5 Ta/2 Cu (thickness in nm) is inserted for the Bi$_{1-x}$Sb$_x$ alloy film.
The influence of the seed layer on the photocurrent will be discussed elsewhere.
A metal shadow mask is inserted between the substrate and the sputtering target to form a wire\cite{hirose2018apl}.

Schematic illustration of the experimental setup and the coordinate axis are shown in Fig.~\ref{fig:1}(a).
We measure the photocurrent of the wire made of semimetal thin films while illuminating light through a quarter wave plate.
A continuous wave semiconductor laser light with wavelength $\lambda$ and power $P$ is used as the light source.
$\theta$ and $\phi$ are the polar and azimuthal angles of the light incidence.
The quarter wave plate is rotated to change the light helicity. The incident light is linearly polarized when $\alpha=0^{\circ}, 90^{\circ}, 180^{\circ}, 270^{\circ}$ and circularly polarized when $\alpha=45^{\circ}, 225^{\circ}$ (left handed) and $135^{\circ}, 315^{\circ}$ (right handed). The left (right) handed circularly polarized light has an angular momentum of $\hbar$ against (along) the light propagation direction, where $\hbar$ is the reduced Planck constant.

\begin{figure}[t]
 \begin{center}
  \includegraphics[scale=0.7]{Figs_082920_mac_1.eps}
  \caption{

  (a) Schematic illustration of the experimental setup and definition of the coordinate axis. The yellow line on the substrate represents the wire made of the film. Light is irradiated from an angle ($\theta$, $\phi$) as defined in the image.

  (b,c) Bottom panels: The quarter wave plate optical axis angle ($\alpha$) dependence of the photocurrent ($I$) for Bi thin film with $t\sim70$ nm. $\phi\sim90^\circ$ (b) and  $\phi\sim 0^\circ$ (c). $\theta$ is fixed to $\sim45^\circ$. The solid circles represent experimental data, the orange solid line shows fit to the data with Eq.~(\ref{eq:fitting}). The red solid, purple dotted and green dashed lines show contributions from the $C$, $L_1$, and $L_2$ terms, respectively.

  (b,c) Data are obtained using $\lambda=405$ nm and $P\sim2.5$ mW.

  }
  \label{fig:1}
 \end{center}
\end{figure}

Representative results of the photocurrent are plotted in Figs.~\ref{fig:1}(b) and \ref{fig:1}(c) as a function of $\alpha$ for Bi thin film ($t\sim$70 nm).
The incident angle $\theta$ is fixed to $\sim45^{\circ}$ and $\phi\sim90^\circ$ for Fig.~\ref{fig:1}(b) and $\phi\sim0^{\circ}$ for Fig.~\ref{fig:1}(c). A large helicity dependent photocurrent (period of 180$^\circ$) is found when $\phi\sim90^\circ$ whereas the effect is negligibly small when $\phi\sim 0^\circ$.
The $\alpha$ dependence of the photocurrent is fitted with the following function\cite{mciver2012nnano,okada2016prb}:
\begin{equation}
\begin{aligned}
    I=&C\sin{2(\alpha + \alpha_0)}\\
    &+L_1\sin{4(\alpha + \alpha_0)}+L_2\cos{4(\alpha + \alpha_0)}+I_\mathrm{0}
\label{eq:fitting}
\end{aligned}
\end{equation}
where $C$ represents the difference in the photocurrent when left and right handed polarized light are illuminated.
$L_1$ and $L_2$ are the changes in the photocurrent under illumination of circularly and linearly polarized light.
The last term $I_\mathrm{0}$ is a constant term that is independent of $\alpha$.
$\alpha_0$ is an offset angle associated with the optical setup and is $\sim-1^{\circ}$ here.
The fitting results are shown using the orange solid line in Figs.~\ref{fig:1}(b) and \ref{fig:1}(c).
Large contribution from the $C$ term (red solid line) is found for $\phi\sim90^\circ$ whereas the $L_2$ term (green dashed line) dominates for $\phi\sim 0^\circ$.
We focus on the characteristics of $C$, obtained using $\phi\sim90^\circ$, hereafter.

\begin{figure}[t]
\centering
\includegraphics[scale=0.7]{Figs_082920_mac_2.eps}
\caption{
(a) The light incident angle ($\theta$) dependence of the helicity dependent photocurrent $C$ with $\phi\sim90^\circ$ for $\sim30$ nm thick Bi thin film. $C$ is normalized by its maximum value obtained at $\theta\sim\pm45^{\circ}$. The solid line shows the calculated $\theta$ dependence of $P_\mathrm{a}\sin{\theta}$. (b) The Bi layer thickness ($t$) dependence of $C$ for Bi thin film. The inset shows the corresponding $t$ dependence of the transmission coefficient ($T$). (c) $C$ vs. $t$ for Cu-seeded Bi$_{1-x}$Sb$_x$ thin films. The Sb concentration ($x$) is denoted in the box. (b,c) The lines are guides to the eye. Data are obtained using $\theta\sim45^\circ$, $\phi\sim90^\circ$. (d) $x$ dependence of maximum $C$ ($C_\mathrm{max}$) obtained from (c). (a-d) Laser with $\lambda=405$ nm and $P\sim2.5$ mW is used to obtain the data.}
\label{fig:2}
\end{figure}

The incident angle $\theta$ dependence of $C$ is shown in Fig.~\ref{fig:2}(a).
$C$ is normalized by its maximum absolute value obtained at $\theta\sim\pm45^{\circ}$.
The $\theta$ dependence of the normalized $C$ can be accounted for with a functional form $P_\mathrm{a}\sin{\theta}$, which is shown by the solid line in Fig.~\ref{fig:2}(a).
$P_\mathrm{a}$ is the absorbance of the circularly polarized light calculated for a Bi thin film in contact with air (the optical constants of Bi are obtained experimentally that are consistent with previous report\cite{werner2009jpcrd}).
$\sin{\theta}$ represents the in-plane component of the light spin angular momentum.
These results show that the in-plane component of the light spin angular momentum plays an essential role in setting the helicity dependent photocurrent.
From hereon, we discuss results obtained using $\theta\sim45^\circ$.

The Bi layer thickness ($t$) dependence of $C$ is shown in Fig.~\ref{fig:2}(b).
We find $C$ increases with $t$ and tends to saturate at larger $t$.
Such thickness dependence suggests that a large part of the photocurrent is generated within the bulk of the film.
To highlight the unique characteristics of Bi, we have studied photocurrent in Bi$_{1-x}$Sb$_x$ thin films.
Although Bi-rich Bi$_{1-x}$Sb$_x$ alloy is known as a three-dimensional topological insulator\cite{hsieh2008nature}, we consider it unlikely that the films grown by sputtering host topological surface states given the polycrystalline structure of the films\cite{chi2020sciadv}.
The $t$ dependence of $C$ for Bi$_{1-x}$Sb$_x$ thin films are presented in Fig.~\ref{fig:2}(c).
In all structures except for $x\sim0.75$, whose $C$ is nearly zero, $C$ increases with $t$ until it saturates.
The maximum value of $C$ for each structure is defined as $C_\mathrm{max}$: $C_\mathrm{max}$ is plotted as a function of $x$ in Fig.~\ref{fig:2}(d).
$C_\mathrm{max}$ decreases with increasing $x$.
Interestingly, the $x$ dependence of $C_\mathrm{max}$ resembles that of the spin Hall conductivity of Bi$_{1-x}$Sb$_x$ alloy\cite{chi2020sciadv,sahin2015prl}.
These results thus suggest that spin current plays an important role in the generation of helicity dependent photocurrent.

Based on the results presented in Fig.~\ref{fig:2}, we consider the generation of helicity dependent photocurrent involves two processes: (1) light induced generation of spin density and (2) conversion of the spin density to charge current.
A schematic illustration of the two processes is sketched in Fig.~\ref{fig:3}(a).
In the first process, a circularly polarized light induces spin density, an imbalance in the electron population with spin angular momentum pointing parallel and antiparallel to the light propagation direction.
Assuming that the spin density scales with the light absorbance, the finite penetration depth ($\lambda_\mathrm{p}$) of light into the semimetal causes a gradient in the spin density along the film normal.
See Fig.~\ref{fig:2}(b) inset for a representative thickness dependence of the transmission coefficient ($T$) of Bi thin film, which is roughly proportional to the light absorbance.
We find $\lambda_\mathrm{p} \sim 10$ nm for Bi.
The spin density gradient induces a spin current along the film normal, which in the second process is converted to charge current via the inverse spin Hall effect (ISHE)\cite{saitoh2006apl}.
Under the ISHE, the charge current along $i$ ($j_i$) is expressed as
\begin{equation}
\begin{aligned}

	j_i = \theta_\mathrm{SH} e n ( \bm{v}_\sigma \times \bm{\sigma} )_i,
\label{eq:ishe}
\end{aligned}
\end{equation}
where $\theta_\mathrm{SH}$ is the spin Hall angle, $e$ is the elementary charge ($e>0$), $n$ is the carrier density, $\bm{\sigma}$ is a vector that represents the spin angular momentum of the carriers and $\bm{v}_\sigma$ is the velocity of the carriers with spin $\bm{\sigma}$. $\bm{v}_\sigma$ is defined as $\displaystyle{\bm{v}_\sigma = - \mu \nabla ( \frac{u_\sigma}{2e}} )$, where $\mu$ is the carrier mobility and $u_\sigma$ is the chemical potential of carriers with spin $\bm{\sigma}$.
For a reason that will be discussed later, we assume that $\bm{\sigma}$ points along, or against, the light propagation direction ($\bm{l}$).
Since $\bm{v}_\sigma$ is parallel to the light intensity gradient (along $z$ in Fig.~\ref{fig:3}(a)), $|j_x|$ scales with the in-plane component of $\bm{l}$ and takes a maximum when the $y$-component of $\bm{l}$ is the largest (i.e. when $\phi=90, 270^\circ$).
These features are consistent with the $\theta$ and $\phi$ dependences of $C$.

\begin{figure}[h]
 \begin{center}
  \includegraphics[scale=0.7]{Figs_082920_win_3.eps}

  \caption{

  (a,b) Schematic illustration of light induced spin density. The in-plane component of the spin angular momentum ($\bm{\sigma}$) of the electrons (a) and holes (b) is sketched using the arrows that thread the yellow spheres when a right-handed circularly polarized light is irradiated to the film. The gradient in the spin density causes carriers to diffuse along the film normal with velocity ($\bm{v}_\sigma$) and generates a spin current $\bm{j}_\mathrm{s}$. $\bm{j}_\mathrm{s}$ is converted to charge current ($\bm{j}$) via the ISHE. $h_{\mathrm{eff}}$ represents the $y$-component of the light induced effective magnetic field ($\bm{h}_\mathrm{eff}$). (c,d) Doping concentration ($x$) dependence of the difference of the electron density ($n_e$) and hole density ($n_h$), $\Delta n \equiv n_e - n_h$ (c), and the mobility ($\mu$) (d) of Sn-doped Bi (Bi$_{1-x}$Sn$_x$) and Te-doped Bi (Bi$_{1-x}$Te$_x$) thin films with $t\sim65-70$ nm. Red squares: Bi$_{1-x}$Sn$_x$, blue circles: Bi$_{1-x}$Te$_x$, black diamond: Bi. The open symbols represent results from thin films with lightly doped Bi. (e) $C/P$ plotted against $\Delta n$ for all the structures shown in (c,d). The solid line is guide to the eye. The inset shows the $x$ dependence of $C/P$. Laser with $\lambda=405$ nm and $P\sim2.5$ mW is used to obtain the data. (f) Wavelength dependence of $C/P$ for Bi thin film with $t\sim65$ nm ($P\sim2.5$ mW). (e,f) Data are obtained using $\theta\sim45^\circ$, $\phi\sim90^\circ$. }

  \label{fig:3}
 \end{center}
\end{figure}

To clarify how the electronic structure of Bi influences the generation of helicity dependent photocurrent, we have doped Bi with Sn and Te to vary the carrier concentration and change the position of the Fermi level with respect to the Dirac point\cite{liu1995prb,fuseya2009prl}.
Figure~\ref{fig:3}(c) shows the nominal doping concentration ($x$) dependence of the difference of the electron density ($n_e$) and hole density ($n_h$), $\Delta n \equiv n_e - n_h$, of Sn-doped Bi (Bi$_{1-x}$Sn$_x$) and Te-doped Bi (Bi$_{1-x}$Te$_x$) thin films.
Note that for pure Bi, the number of electrons and holes are equal due to the charge neutrality condition and the carrier concentration ($n = n_e + n_h$) of the films is $\sim1.1-1.2 \times 10^{25}$ m$^{-3}$.
The majority carrier type of Sn- and Te-doped Bi is holes and electrons, respectively.
For both systems, $|\Delta n|$ decreases with decreasing $x$.
In contrast, the mobility ($\mu$), shown in Fig.~\ref{fig:3}(d), sharply increases as $x$ is reduced, taking a peak at $x\sim0$.

The inset of Fig.~\ref{fig:3}(e) shows the $x$ dependence of $C$ divided by the laser power $P$.
We find that the sign of $C$ reverses as the majority carrier type is changed from electrons to holes.
The sign change in $C$ across $x\sim0$ can be understood if we assume the inverse Faraday effect (IFE) is responsible for the generation of light induced spin density.
In this process, circularly polarized light acts as an effective magnetic field ($\bm{h}_\mathrm{eff}$), which is parallel (antiparallel) to $\bm{l}$ for right (left)-handed circularly polarized light.
Application of $\bm{h}_\mathrm{eff}$ will align the magnetic moment ($\bm{m}$) of the carriers along $\bm{h}_\mathrm{eff}$.
Consequently, the spin angular momentum ($\bm{\sigma}$) of the electrons will point opposite to $\bm{h}_\mathrm{eff}$ whereas that of the holes will be parallel to $\bm{h}_\mathrm{eff}$.
Theoretical study shows that the sign of $\theta_\mathrm{SH}$ for electron and hole doped Bi is the same\cite{sahin2015prl}.
Thus change in the majority carrier from electrons to holes causes $\bm{\sigma}$ in Eq.~(\ref{eq:ishe}) to reverse its direction, resulting in $C$ with opposite sign (see Figs.~\ref{fig:3}(a) and \ref{fig:3}(b) for a schematic illustration).
(For the Te-doped Bi thin films, the sign of $C$ changes at $x\sim 0.04$, which coincides with $x$ where a rapid increase in the carrier concentration is found.
We consider the system becomes degenerate and contributions from other bands influence $C$ in this regime ($x \geq 0.04$).)

From the magnitude of $C$, we first provide a rough estimate of the light induced spin density per unit volume ($n_\mathrm{s}$).
$n_\mathrm{s}$ can be obtained from $N_\mathrm{F}$, the density of states at the Fermi level, and $u_\mathrm{s}$, the difference in the chemical potential of carriers with $\bm{\sigma}$ parallel and antiparallel to the in-plane component of $\bm{l}$, via the relation $n_\mathrm{s} = N_\mathrm{F} u_\mathrm{s}$.
As a first order estimation, we assume that $u_\mathrm{s}$ varies linearly from $u_\mathrm{s,max}$ at the surface of the semimetal to 0 over a distance ($\lambda_\mathrm{s,p}$) set either by the larger of the spin diffusion length ($\lambda_\mathrm{s}$) and the light penetration length ($\lambda_\mathrm{p}$).
Consequently, a spin current of $\displaystyle{j_\mathrm{s} = \frac{\sigma_{xx} u_\mathrm{s,max}}{2 e \lambda_\mathrm{s,p}}}$\cite{chen2013prb} flows along the film normal, where $\sigma_{xx}$ is the electrical conductivity of the semimetal.
The resulting charge current due to the ISHE (Eq.~(\ref{eq:ishe})), equivalent to $C$ obtained in the experiments, is calculated by multiplying $j_\mathrm{s}$ with $\lambda_\mathrm{s,p} w \theta_\mathrm{SH}$, where $w$ is the width of the wire.
The maximum $n_\mathrm{s}$ induced at the surface of the semimetal layer ($n_\mathrm{s,max}$) therefore reads
\begin{equation}
\begin{aligned}

	n_\mathrm{s,max} \sim \frac{2 e N_\mathrm{F} C}{\sigma_{xx} \theta_\mathrm{SH} w}.
\label{eq:ns}
\end{aligned}
\end{equation}
Substituting $C \sim 1$ nA, $w \sim 0.4$ mm, $\sigma_{xx} \sim 1.3 \times 10^5$ ($\Omega^{-1}$ m$^{-1}$) and $N_\mathrm{F} \sim 1.4 \times 10^{28}$ (eV$^{-1}$ m$^{-3}$)\cite{gonze1990prb} for Bi, we find $\frac{n_\mathrm{s,max}}{P/S} \sim \frac{4.5 \times 10^{13}}{\theta_\mathrm{SH}}$ (W$^{-1}$ m$^{-1}$), where $S$ is the laser irradiation area.
Even with a spin Hall angle of $\sim1$\cite{chi2020sciadv}, $\frac{n_\mathrm{s,max}}{P/S}$ is three to four orders of magnitude larger than that of typical transition metals\cite{berritta2016prl,freimuth2016prb,huisman2016nnano}.

The $\Delta n$ dependence of $C$ is presented in Fig.~\ref{fig:3}(e).
Clearly, $C$ takes a maximum at $\Delta n \sim 0$.
As the electron and hole densities are the same for Bi, however, $C$ should be zero at $\Delta n \sim 0$ if the scenario sketched in Figs.~\ref{fig:3}(a,b) applies.
To account for these results, we develop a toy model (a rigid band model is assumed under Sn/Te doping).
As illustrated in Fig.~\ref{fig:4}(a), the Fermi level of Bi ($\Delta n \sim 0$) lies above the Dirac point at the $L$ valley.
The $L$ valley supplies electrons that contribute to transport whereas the $T$ valley provides holes\cite{liu1995prb,fuseya2015jpsj}.
Assuming that carriers in each valley contribute to $C$ independently, we obtain $C$ by summing all contributions (and taking into account that the signs of $C$ due to electrons and holes are opposite):
\begin{equation}
\begin{aligned}

	C \sim C_{L,e^-} - C_{L,h^+} - C_{T,h^+},

\label{eq:Call}
\end{aligned}
\end{equation}
where $C_{v, c}$ represents $C$ due to carrier type $c$ ($e^-$: electrons. $h^+$: holes) at valley $v$ ($L$ or $T$).
(Note that the $T$ valley only accommodates holes).
We assume that the spin density is equal to the product of the Zeeman energy and $N_\mathrm{F}$ for each valley, \textit{i.e.}, $n_\mathrm{s,max} \sim \mu_\mathrm{B} g_\mathrm{eff} h_\mathrm{eff} N_\mathrm{F}$, where $\mu_\mathrm{B}$, $g_\mathrm{eff}$ and $h_\mathrm{eff}$ are the Bohr magneton, the effective $g$-factor and the $y$-component of $\bm{h}_\mathrm{eff}$, respectively.
Using Eq.~(\ref{eq:ns}), $C_{v,c}$ can be expressed as
\begin{equation}
\begin{gathered}
	C_{v, c} \sim \frac{\mu_\mathrm{B} w}{2 e} \big(h_\mathrm{eff} g_\mathrm{eff} \sigma_\mathrm{SH} \big)\big|_{v,c},
\label{eq:CLTeh}
\end{gathered}
\end{equation}
where $\sigma_\mathrm{SH} \equiv \sigma_{xx} \theta_\mathrm{SH}$ is the spin Hall conductivity.

\begin{figure}[t]
 \begin{center}
    \includegraphics[scale=0.7]{Figs_082920_win_4.eps}
  \caption{

  (a) Schematic illustration of the electronic band structure of Bi at the $L$ valley. $E_\mathrm{F}$ denotes the Fermi level of Bi. (b-d) Fermi level position dependence of the product of the light induced effective magnetic field ($h_\mathrm{eff}$) and the $g$-factor ($g_\mathrm{eff}$), $h_\mathrm{eff} g_\mathrm{eff}$ (b), spin Hall conductivity $\sigma_\mathrm{SH}$ (c) and the helicity dependent photocurrent $C$ (d) calculated using Eqs.~(\ref{eq:Call}) and (\ref{eq:CLTeh}). Red and blue solid lines in (c,d) indicate contribution from electrons and holes in the $L$ valley. $\Delta$ indicates the width of the $h_\mathrm{eff} g_\mathrm{eff}$ peak.}

  \label{fig:4}
 \end{center}
\end{figure}

Theoretical calculations suggest that $\sigma_\mathrm{SH}$ is larger for the electrons in the $L$ valley than that of the holes in the $T$ valley\cite{sahin2015prl,fuseya2015jpsj}.
Such difference breaks the electron-hole symmetry of $C$ at $\Delta n \sim 0$: we neglect contribution from $C_{T,h^+}$ hereafter.
Calculations also indicate that $\sigma_\mathrm{SH}$ of the carriers in the $L$ valley is nearly constant across the Dirac point\cite{sahin2015prl}.
We thus assume $\sigma_\mathrm{SH}$ is constant for the majority carriers and scales with the carrier density for the minority carriers, as shown in Fig.~\ref{fig:4}(c) (see supplementary material for the details).
The calculated $\Delta n$ dependence of $C$ is presented in Fig.~\ref{fig:4}(d).
We find the experimental results are best described if $h_\mathrm{eff} g_\mathrm{eff}$ takes a peak at the Dirac point and its width is close to the energy difference between the Dirac point and the Fermi level of Bi, as sketched in Fig.~\ref{fig:4}(b).
Note that the peak width of $h_\mathrm{eff} g_\mathrm{eff}$, defined as $\Delta$ in Fig.~\ref{fig:4}(b), roughly defines the position of $C$ maximum; see Fig.~\ref{fig:4}(d).

In the calculation, we adjust the peak value of $h_\mathrm{eff} g_\mathrm{eff}$ so that the maximum $C$ at $\Delta n \sim 0$ is $\sim 1$ nA ($\theta_\mathrm{SH} \sim 1$ is assumed), in accordance with the experiments.
Past studies have shown that the electrons in the $L$ valley possess large $g_\mathrm{eff}$, of the order of $\sim$100 to $\sim$1000\cite{fuseya2015prl} owing to its small effective mass and large spin orbit coupling.
Even with $g_\mathrm{eff} \sim 1000$, which is unlikely given the poly-crystal texture of the films used here, the estimated $h_\mathrm{eff}$ ($\sim 4 \times 10^{-9}$ T under light intensity of $\sim 1.3 \times 10^4$ W/m$^2$) is one to two orders of magnitude larger than that of typical transition metals caused by the IFE\cite{berritta2016prl,freimuth2016prb,huisman2016nnano}.
Thus the large $h_\mathrm{eff} g_\mathrm{eff}$ at the Dirac point is likely due to contributions from both $h_\mathrm{eff}$ and $g_\mathrm{eff}$.
$g_\mathrm{eff}$ may follow the $\Delta n$ dependence of mobility $\mu$ (Fig.~\ref{fig:3}(d)) via changes in the carrier effective mass.
Similarly, $h_\mathrm{eff}$ may scale with the inverse of the carrier effective mass, as recent calculations suggest\cite{tokman2020prb}.
We thus consider the unique characteristics of the Dirac semimetals with strong spin orbit coupling, \textit{i.e.}, small effective mass and large $g$-factor, cause the giant IFE in Bi.
Note that in the experiments, we find a dip in $C$ right above $\Delta n \sim 0$, which cannot be accounted for with this model.
To fully describe the experimental results, we infer that influence of carrier density on $C$ must also be taken into account.

Theoretical calculations show that the strength of IFE increases with increasing light wavelength ($\lambda$)\cite{berritta2016prl,freimuth2016prb}.
Figure.~\ref{fig:3}(f) shows the $\lambda$ dependence of $C$ for Bi thin film ($\Delta n \sim 0$).
As the light power ($P$) depends on $\lambda$ (see supplementary material), $C$ is normalized by $P$.
Although the range of $\lambda$ studied here is limited, $C/P$ tends to increase with increasing $\lambda$.
It remains to be seen whether $C$ will further increase when the light energy becomes close to band gap of Bi.
See supplementary material for discussion on contributions to the photocurrent from other sources.

In summary, we have shown that a giant light induced effective magnetic field emerges in Dirac semimetals.
A spin density that scales with the light intensity is created by the IFE, causing a spin current along the film normal.
The spin current is converted to charge current via the ISHE, giving rise to HDP.
The carrier transport characteristics of Dirac semimetals with strong spin orbit coupling are responsible for the giant IFE.
These results demonstrate the unique optical response of Dirac semimetals that can be exploited to develop systems with strong light-spin coupling.

\begin{acknowledgments}
This work was partly supported by JST CREST (JPMJCR19T3), JSPS Grant-in-Aids (JP15H05702,JP16H03853), Yamada Science Foundation and the Center of Spintronics Research Network of Japan. Y.-C.L. is supported by JSPS International Fellowship for Research in Japan (JP17F17064). H.H. and Z.C. acknowledge financial support from Materials Education program for the future leaders in Research, Industry, and Technology (MERIT).
\end{acknowledgments}


\section{Introduction}\label{intro}
The interplay between words and graphs has been investigated in the literature repeatedly, as discussed in \cite{KitLoz} focusing on {\em word-representable graphs} that are also surveyed in \cite{Kit2017}. Various ways to encode graphs in terms of words often allow to reveal and describe various useful properties of graphs, such as classes where difficult algorithmic problems become easy. The {\em Pr\"{u}fer sequence} giving a fascinating relationship between labelled trees with $n$ vertices and sequences of length $n-2$ made of the elements of the set $[n]:=\{1,2,\ldots,n\}$, is a classical example showing the importance of words for graph enumeration.

In this paper we study encoding of so-called labelled $p$-Riordan graphs by certain words, and also consider encoding a particular important case of $p=2$ (labelled Riordan graphs) by certain pattern-avoiding permutations extensively studied in the literature \cite{Kit2011}. We consider only labelled graphs, so the word ``labelled'' is omitted throughout this paper.

We begin with introducing the notions of interest.\\

\noindent
{\bf Riordan graphs.} A {\em
Riordan matrix} \cite{shap} $L=[\ell_{ij}]_{i,j\ge0}$ generated by two formal
power series $g=\sum_{n=0}^\infty g_nt^n$ and $f=\sum_{n=1}^\infty
f_nt^n$ in ${\mathbb Z}[[t]]$ is denoted as $(g,f)$ and defined as
an infinite lower triangular matrix whose $j$-th column generating
function is $gf^j$, {\it i.e.} $\ell_{ij}=[t^i]gf^j$ where
$[t^k]\sum_{n\ge0}a_nt^n=a_k$. If $g_0\ne0$ and $f_1\ne
 0$ then the Riordan matrix is called {\it proper}.

A simple graph $G$ of order $n$ is said to be a {\em Riordan graph}
if the adjacency matrix $A(G)$ can be expressed as
\begin{equation} A(G) \equiv (tg,f)_n + (tg,f)_n^T \pmod{2} \label{riordandef}\end{equation}
for some generating functions $g$ and $f$ over $\mathbb Z$ where
$(tg,f)_n$ is the $n\times n$ leading principle matrix of the
Riordan matrix $(tg,f)$. A Riordan graph $G$ on $n$ vertices with
the adjacency matrix $A(G)$ given by (\ref{riordandef}) is denoted
as $G=G_n(g,f)$. If we let $A(G)=(a_{i,j})_{1\le i,j\le n}$, then, by (\ref{riordandef}),
for $i\ge j$,
\begin{align*}
a_{i,j}=a_{j,i}\equiv [t^{i-2}]gf^{j-1} \pmod{2}.
\end{align*}
In particular, if $[t^0]g \equiv [t^1]f \equiv 1 \pmod{2}$, then the graph $G_n(g,f)$ is called {\it proper}. We denote the set of Riordan graphs with $n$ vertices by $\mathcal{RG}_n$. When defining Riordan graphs we assume, without loss the generality, that $g$ and $f$ have binary coefficients. The number $r_n$ of Riordan graphs of order $n\ge1$ is known from  \cite{CJKM} to be
\begin{eqnarray}\label{Riord-rn}
r_n={4^{n-1}+2\over 3}.
\end{eqnarray}

Riordan graphs were introduced in \cite{CJKM,CJKM2} and they are a far-reaching
generalization of the well-known and well studied Pascal graphs and
Toeplitz graphs, and also some other families of graphs. The Riordan
graphs are proved to have a number of interesting (fractal)
properties  \cite{CJKM}, and  spectral properties of Riordan graphs were studied in~\cite{CJKM2}.

There are several naturally defined classes/families of Riordan
graphs~\cite{CJKM,CJKM2}. A Riordan graph $G_n(g,t)$ is said to be of the
{\em Appell type}. Riordan graphs of the Appell type are also
known as {\em Toeplitz graphs}.
Toeplitz graphs have been studied in \cite{CJKM,DTTVZZ,NP}.  A Riordan graph $G_n(g,tg)$ is said to be of the {\em Bell type} and
it has been studied in \cite{CJKM,J1}. The well-known {\em Pascal graph} $G_n\left(\frac{1}{1-t},\frac{t}{1-t}\right)$ is a particular example of a Bell type Riordan graph, and it is the only such graph of type $(1+f,f)$, also considered in our paper. Finally, a Riordan graph $G_n(f',f)$ is said to be of the {\em derivative type} and it has been studied in \cite{CJKM}. \\

\noindent
{\bf Oriented Riordan graphs and $p$-Riordan graphs.} There is a natural generalization of the notion of a Riordan graph that was introduced in \cite{J}. This notion is obtained by replacing ``mod 2'' by ``mod $p$'' in the definition of a Riordan graph. While the definition makes sense for any integer $p\geq 2$, it is normally assumed that $p$ is a prime number to resolve the invertibility issues preventing us from being able to analyze such graphs. In particular, the number $r^{(p)}_n$ of $p$-Riordan graphs for a prime $p$  was derived in \cite{J}, and it is given by
\begin{eqnarray}\label{mod-p-formula}r^{(p)}_n=\frac{p^{2(n-1)}+p}{p+1},\end{eqnarray}
while no enumeration is known for a non-prime $p$. Setting $p=2$ in (\ref{mod-p-formula}) we recover the number of Riordan graphs given by (\ref{Riord-rn}), while setting $p=3$ in (\ref{mod-p-formula}) we obtain the number $\tilde{r}_n$ of oriented Riordan graphs of order $n$:
\begin{eqnarray}\label{formula-mod-3}\tilde{r}_n=\frac{3^{2(n-1)}+3}{4}.\end{eqnarray}
For $p>3$, $p$-Riordan graphs can be thought of as weighted Riordan graphs.

In the case of a $p$-Riordan graph $G$, in some contexts it is convenient to let the elements of the adjacency matrix $A(G)$ be coming from the set $\{\lfloor
p/2\rfloor,\ldots,-1,0,1,\ldots,\lfloor p/2\rfloor\}$. However, in this paper it is more convenient to let these elements be in the set $\{0,1,\ldots,p-1\}$. In particular, oriented Riordan graphs have adjacency matrices' elements in $\{0,1,2\}$. We denote the set of $p$-Riordan graphs with $n$ vertices by $\mathcal{RG}_{n}^{(p)}$. \\

\noindent
{\bf Patterns in permutations.} We think of permutations to be written in the one-line notation, and a permutation of length $n$ is called an $n$-permutation. The reduce form of a permutation $\pi$ is the permutation red$(\pi)$ obtained from $\pi$ by substituting the $i$-th smallest element by $i$. For example, red(4287)=2143.

A {\em pattern} is a permutation. We say that a pattern $\tau=\tau_1\cdots\tau_k$ {\em occurs} in a permutation $\pi=\pi_1\cdots\pi_n$ if there are indices $1\leq i_1<i_2<\cdots<i_k\leq n$ such that red$(\pi_{i_1}\pi_{i_2}\cdots\pi_{i_k})=\tau$. For example, the permutation $14235$ has four occurrence of the pattern 123, namely, the subsequences 145, 125, 135 and 235, while the permutation 34512 {\em avoids} the pattern 132 (has no occurrences of it). Permutation patterns have been the subject of extensive research in the literature \cite{Kit2011}.

A well-known result \cite{Kit2011} states that the number of $n$-permutations that avoid simultaneously the patterns 123 and 132 is $2^{n-1}$. This can be proved using a bijection $\psi$ from the set of binary words of length $n-1$ to the set of restricted $n$-permutations that is  denoted by $S_n(123,132)$. Think of constructing a permutation in $S_n(123,132)$ by inserting elements $1, 2,\ldots, n$ one by one, starting from 1 and continuing with the least available element, into $n$ empty slots and observing that at each step an element $i$ can only be inserted in one of the two rightmost  empty slots to avoid the patterns 123 and 132; the element $n$ will be inserted in a unique way. Thus, given a binary word $b_1b_2\cdots b_{n-1}$, $\psi$ uses the process of insertion, and  places the element  $i$ to the left (resp., right) available slot if $b_i=0$ (resp., 1). For example, $\psi(011001)=7546312$. \\

\noindent
{\bf $p$-Riordan words.} We define the following set of words that we call {\em $p$-Riordan words} because they will be proved by us in Section~\ref{p-Riordan-sec} to be in 1-to-1 correspondence with $p$-Riordan graphs.  A $p$-Riordan word $w_1w_2\cdots w_n$, $n\geq 1$, is a word over the alphabet $A^{(p)}=\{a_{i,j}:0\leq i,j\leq p-1\}$ such that either it is $a_{0,0}a_{0,0}\cdots a_{0,0}$ or there exist $i$ and $b$, $1\leq i\leq n$, $1\leq b\leq p-1$, such that $w_1\cdots w_i=a_{0,0}a_{0,0}\cdots a_{0,0}a_{b,0}$. By definition, the empty word $\varepsilon$ is a $p$-Riordan word of length $0$. The set of $p$-Riordan words of length $n$ is denoted by $\mathcal{W}_n^{(p)}$. For example, letting $a=a_{0,0}$, $b=a_{1,0}$, $c=a_{0,1}$ and $d=a_{1,1}$, $\mathcal{W}_3^{(2)}=\{aaa,aab,aba,abb,abc,abd,baa,bab,bac,bad,bba,bbb,bbc,bbd,bca,$ \\ $bcb,bcc,bcd,bda,bdb,bdc,bdd\}.$\\

\noindent
{\bf Organization of the paper}. This paper is organized as follows. In Section~\ref{p-Riordan-sec} we present our main result, namely, encoding  $p$-Riordan graphs by $p$-Riordan words. In Section~\ref{pattern-avoiding-sec} we consider encoding Riordan graphs by pattern-avoiding permutations. In Section~\ref{orient-Riord-graphs} we encode oriented Riordan graphs by balanced words over the alphabet $\{0,1,2\}$, and provide, as a bi-product, a proof of a known enumerative result related to the formula (\ref{formula-mod-3}). Finally, in Section~\ref{concl-sec} we make concluding remarks and state open problems for further research.

\section{Encoding $p$-Riordan graphs by $p$-Riordan words}\label{p-Riordan-sec}
In this section, we will present a bijective map $\xi:\mathcal{RG}_{n+1}^{(p)}\rightarrow\mathcal{W}_{n}^{(p)}$ for $n\geq 0$ and discuss its applications in the case of Riordan graphs (the case $p=2$).

\begin{theorem}\label{thm-xi}
There is bijection between $\mathcal{RG}_{n+1}^{(p)}$ and $\mathcal{W}_{n}$.
\end{theorem}
\begin{proof}
By definition, a $p$-Riordan graph $G=G^{(p)}_n(g,f)$ of order $n$ can be determined by the coefficients $g_{b^*},g_{b^*+1},\ldots,g_{n-2},f_1,f_2,\ldots,f_{n-b^*-2}$ where $b^*$ is the smallest $i\in\{0,1,\ldots,n-2\}$ such that $g_i\neq 0$; if no such $i$ exists then $G$ is an empty graph (a graph with no edges). Thus, $G^{(p)}_n(g,f)=G^{(p)}_n(\tilde{g},\tilde{f})$ where $\tilde{g}$ and $\tilde{f}$ are the following polynomials:
\begin{itemize}
\item $\tilde{g}:=\displaystyle\sum_{i=b^*}^{n-2}g_{i}t^i$ and $\displaystyle\tilde{f}:=\sum_{i=1}^{n-2-b^*}f_{i}t^i$ if $b^*$ is defined;
\item $\tilde{g}=\tilde{f}=0$ if $b^*$ does not exist.
\end{itemize}

If $s^{(p)}_n=|\mathcal{W}_n^{(p)}|$ then $s^{(p)}_1=p$ and
\begin{eqnarray}\label{spn-formula} s^{(p)}_{n+1}=p^2(s^{(p)}_n-1)+p.\end{eqnarray}
Indeed, $\mathcal{W}_1^{(p)}=\{a_{0,i}:0\leq i\leq p-1\}$ and to generate all elements in $\mathcal{W}_{n+1}^{(p)}$ we can extend every word in $\mathcal{W}_{n}^{(p)}$ different from $a_{0,0}\cdots a_{0,0}$ by any letter in $A^{(p)}$ (which explains the term $p^2(s^{(p)}_n-1)$), and the remaining $p$ elements in $\mathcal{W}_{n+1}^{(p)}$ are given by $\{a_{0,0}\cdots a_{0,0}a_{b,0}: 0\leq b\leq p-1\}$.

We note that $r^{(p)}_n$ satisfies the same recursion as (\ref{spn-formula}), namely, \begin{eqnarray}\label{rpn-rec-formula} r^{(p)}_{n+1}=p^2(r^{(p)}_n-1)+p\end{eqnarray}
with the initial condition $r^{(p)}_2=p$, which provides an alternative proof of (\ref{mod-p-formula}).  Indeed, the initial condition counts the $p$ graphs on 2 vertices given by $\tilde{g}_0=i$, $0\leq i\leq p-1$. Also, to generate all graphs in $\mathcal{RG}_{n+1}^{(p)}$, we can take any non-empty graph in $\mathcal{RG}_{n}^{(p)}$ given by $\tilde{g}\neq 0$ and $\tilde{f}$, and choose independently $g_{n-1}$ and $f_{n-b^*-1}$ in $\{0,1,\ldots, p-1\}$ ($b^*$ is defined). This explains the term ``$p^2(r^{(p)}_n-1)$'' in (\ref{rpn-rec-formula}). The only uncounted graphs in $\mathcal{RG}_{n+1}^{(p)}$ are those given by $\tilde{g}=it^{n-1}$ where $0\leq i\leq p-1$, which explains the term ``$+p$''.

For the only graph on one vertex, $\xi(G_{1}^{(p)}(0,0))=\varepsilon$, and for $n\geq 2$, $\xi(G_{n}^{(p)}(g,f))$ is defined by \\[-5mm]
$$a_{g_0,f_{n-2}}a_{g_1,f_{n-3}}\cdots a_{g_{b^*-1},f_{n-3-b^*}} a_{g_{b^*},f_0}a_{g_{b^*+1},f_1}a_{g_{b^*+2},f_2}\cdots a_{g_{n-2},f_{n-2-b^*}}=$$
$$a_{0,0}a_{0,0}\cdots a_{0,0} a_{1,0}a_{g_{b^*+1},f_1}a_{g_{b^*+2},f_2}\cdots a_{g_{n-2},f_{n-2-b^*}}$$ where $g_i=[t^i]\tilde{g}$ and $f_j=[t^j]\tilde{f}$. The fact that $\xi$ is well-defined and bijective essentially follows from our proofs of (\ref{spn-formula}) and (\ref{rpn-rec-formula}).
\end{proof}

The bijection $\xi$ given in Theorem~\ref{thm-xi} allows us to encode by words three classes of Riordan graphs (the case $p=2$).  As above, we let $\mathcal{W}_n^{(2)}$ be words over $\{a,b,c,d\}$, where $a=a_{0,0}$, $b=a_{1,0}$, $c=a_{0,1}$ and $d=a_{1,1}$,  Justifications of our encodings are straightforward from the properties of $\xi$.\\

\noindent
{\bf The class $(1+f,f)$.} In this case, $g=1+f$. Since $[t^0]g=1$ and $[t^i]g=[t^i]f$ for each $i\in[n-2]$, we have that $b^*=0$ and the words in $\mathcal{W}_n^{(2)}$  corresponding to these graphs are those of the form $bx_1x_2\cdots x_{n-1}$ where $x_i\in\{a,d\}$.\\

\noindent
{\bf Proper Riordan graphs.} For a proper Riordan graph $g_0= f_1 = 1$, so $b^*=0$ and the words in $\mathcal{W}_n^{(2)}$ corresponding to these graphs are those beginning either with $bc$ or with $bd$ for $n\geq 2$, and $\mathcal{W}_1^{(2)}=\{b\}$.\\

\noindent
{\bf Riordan graphs of the Appel type.} For these graphs $f=t$, and thus the words in $\mathcal{W}_n^{(2)}$ corresponding to these graphs are of the form $aa\cdots a$, $aa\cdots ab$ and $aa\cdots abxw$ for $x\in\{c,d\}$ and $w$ a word over the alphabet $\{a,b\}$. \\

\section{Encoding Riordan graphs by pattern-avoiding permutations}\label{pattern-avoiding-sec}

The sequence $(r_n)_{n\ge0}$  counting Riordan graphs and given by (\ref{Riord-rn}) has various combinatorial interpretations recorded in
A047849 in the {\em On-Line Encyclopedia of Integer Sequences} ({\em OEIS})
\cite{oeis}. Two of these interpretations are related to pattern-avoiding permutations:
\begin{itemize}
\item[(I1)] $r_n$ counts permutations in $S_{2n}(123, 132)$ with two fixed points; the set of such permutations is denoted by $P_{2n}$; see \cite{MR}.
\item[(I2)] $r_n$ counts permutations in $S_n(4321,4123)$, or in $S_n(4321, 3412)$, or in $S_n(4123,3214)$, or in $S_n(4123,2143)$; see \cite{KW}.
\end{itemize}

In this paper, we explain combinatorially a connection between Riordan graphs and (I1). Moreover,  we will show which permutations, under the bijection we will construct, correspond to Riordan graphs of the Appell type, of the Bell type (including the Pascal graph), of the derivative type, as well as of the types given by $(1+f,f)$ and $(g,0)$ (a star graph with a number of isolated vertices), and to proper Riordan graphs. We leave explaining the second bullet point combinatorially as an open problem.

\begin{figure}
\begin{center}
\psscalebox{0.5 0.5}
{
\begin{pspicture}(0,-5.2)(10.56,5.2)
\definecolor{colour0}{rgb}{0.8,0.8,0.8}
\psline[linecolor=black, linewidth=0.04](0.38,2.0)(10.38,2.0)
\psline[linecolor=black, linewidth=0.04](0.38,-1.6)(10.38,-1.6)
\psline[linecolor=black, linewidth=0.04](3.58,5.2)(3.58,-4.8)
\psline[linecolor=black, linewidth=0.04](6.78,5.2)(6.78,-4.8)
\psframe[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour0, dimen=outer](1.98,5.2)(0.38,2.0)
\psframe[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour0, dimen=outer](3.58,2.0)(1.98,-1.6)
\psframe[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour0, dimen=outer](6.78,-1.6)(3.58,-3.2)
\psframe[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour0, dimen=outer](10.38,-3.2)(6.78,-4.8)
\rput[bl](0.02,-4.92){\huge$1$}
\rput{-0.33752647}(0.030576011,0.020646136){\rput[bl](3.52,-5.45){\huge$a$}}
\rput[bl](6.68,-5.45){\huge$b$}
\rput[bl](10.2,-5.45){\huge$2n$}
\rput[bl](-0.1,-1.66){\huge$a$}
\rput[bl](-0.1,1.9){\huge$b$}
\rput[bl](-0.4,4.98){\huge$2n$}
\psframe[linecolor=black, linewidth=0.04, dimen=outer](10.38,5.2)(0.38,-4.8)
\psdots[linecolor=black, dotsize=0.3](3.58,-1.6)
\psdots[linecolor=black, dotsize=0.3](6.78,2.0)
\rput[bl](0.9,3.32){\huge$A$}
\rput[bl](2.5,-0.14){\huge$B$}
\rput[bl](4.9,-2.67){\huge$C$}
\rput[bl](8.2,-4.3){\huge$D$}
\end{pspicture}
}
\end{center}
\caption{The structure of a permutation in $P_{2n}$}\label{fig:P2n}
\end{figure}

\begin{theorem}\label{thm1}
There is a bijection between $\mathcal{RG}_n$ and $P_{2n}$.
\end{theorem}

\begin{proof} Let $\pi=p_1p_2\cdots p_{2n}$ and $a$ and $b$ be the two fixed points in $\pi$ where $1\le a<b\le 2n$. Since $\pi$ avoids the patterns $123$ and $132$, the remaining $2n-2$ elements can only be placed in  the areas $A$, $B$, $C$ and $D$ in Figure~\ref{fig:P2n}, where we show $\pi$ schematically as a permutation diagram. In addition, the elements in $B$ and $C$ must be in decreasing order, while $A$ (resp., $D$) avoids 123 and 132, and is independent from the rest of $\pi$ in the sense that no occurrence of 123 or 132 can start in $A$ (resp., $D$) and end elsewhere. Since the number of elements in $B$ and $C$ is $b-a-1$, we obtain that the number of elements in $D$, which is the same as the number of elements in $A$, is
\begin{align*}
2n-b=a-1-(b-a-1)\quad\Rightarrow\quad a=n.
\end{align*}
Thus, $B$ and $C$ have the same number of elements $b-n-1$, and $\pi$ satisfies
\begin{itemize}
\item $p_1p_2\cdots p_{2n-b}$ and $p_{b+1}p_{b+2}\cdots p_{2n}$ avoid the patterns 123 and 132;
\item $p_{2n-b+i}=b-i$ for each $i=1,2,\ldots,2b-2n-1$.
\end{itemize}
The desired map $\phi:\mathcal{RG}_n\rightarrow P_{2n}$,  is defined as follows where $\phi(G_n(g,f))=p_1p_2\cdots p_{2n}$ and  the function $\psi$ is defined in Section~\ref{intro}:
\begin{itemize}
\item $p_n=n$ and $p_{b}=b$ where $b=b^*+n+1$ and $b^*=\min\{i\mid [t^i]g=1\}$  if $g\neq0$ and $b=2n$ if $g=0$;
\item $p_{2n-b+i}=b-i$ for each $i\in[2b-2n-1]$;
\item $\psi(g_{b^*+1}g_{b^*+2}\cdots g_{n-2})=(p_{1}-b)\cdots (p_{2n-b}-b)$ so that to obtain $p_{1}\cdots p_{2n-b}$ we apply $\psi$ to $g_{b^*+1}g_{b^*+2}\cdots g_{n-2}$ and then increase each element in the obtained permutation by $b$ (lengths are proper here since $b=b^*+n+1$);
\item $\psi(f_1f_2\cdots f_{2n-b-1})=p_{b+1}\cdots p_{2n}$.
\end{itemize}
It is not difficult to see that $\phi$ is well-defined and injective. Thus, since $|\mathcal{RG}_n|=|P_{2n}|$, $\phi$ is bijective. For example, $\phi(G_5(t+t^3,t^2))=(10)896547312$ and $\phi(G_5(t,t+t^2))=98(10)6547321$. In particular, in both cases $n=5$, $2n=10$ and $b^*=1$ so that $b=7$.
\end{proof}

The bijection $\phi$ given in Theorem~\ref{thm1} allows us to describe subclasses of Riordan graphs in terms of pattern-avoiding permutations. In our description we refer to $A$ and $D$ to be the parts of a permutation $\pi=p_1\cdots p_{2n}$ schematically given in Figure~\ref{fig:P2n}. That is, $A=p_1\cdots p_{2n-b}$ and $D=p_{b+1}\cdots p_{2n}$.  Justifications of our descriptions are usually straightforward from the properties of $\phi$, but in some places we still provide various clarifications. In what follows recall that $b=b^*+n+1$.\\

\noindent
{\bf The class $(1+f,f)$.} In this case, $g=1+f$. Since $[t^0]g=1$ and $[t^i]g=[t^i]f$ for each $i\in[n-2]$, we have that $b^*=0$ and the permutations in $P_{2n}$ corresponding to these graphs have the fixed points $n$ and $n+1$, and red$(A)=D$.\\

\noindent
{\bf Proper Riordan graphs.} For a proper Riordan graph $g_0= f_1 = 1$, so $b^*=0$ and the permutations in $P_{2n}$ corresponding to these graphs have two fixed points $n$ and $n+1$,  and the minimal element in $D$ is in the last place.\\

\noindent
{\bf Riordan graphs of the Appel type.} For these graphs $f=t$ and thus the permutations in $P_{2n}$ describing them are those for which $D=(2n-b-1)(2n-b-2)\cdots 32(2n-b)1$. \\

\noindent
{\bf Riordan graphs of the Bell type.} Such graphs are given by $(g,tg)$ where either $g=0$ or $g_0=g_1=\cdots=g_{b^*-1}=0$ and $g_{b^*}=1$ for $b^*\geq 0$. In the former case, we deal with the empty graph corresponding to $(2n-1)(2n-2)\cdots 1(2n)$. For the latter case, since  $\tilde{f}=g_0t+g_1t^2+\cdots +g_{n-2-b^*}t^{n-1-b^*}$, we can conclude that permutations in $P_{2n}$ corresponding to the Riordan graphs of the Bell type are those having the $b^*+1$ rightmost elements of $D$ forming the permutation $b^*(b^*-1)\cdots 21(b^*+1)$. We note that the Pascal graph $\left(\frac{1}{1-z},\frac{z}{1-z}\right)$ is the only graph of the Bell type that belongs to the class $(1+f,f)$. For this graph $b^*=0$, $b=n+1$, and the permutation in $P_{2n}$ corresponding to it is $(2n)(2n-1)\cdots (n+2)n(n+1)(n-1)(n-2)\cdots 1$.\\

\noindent
{\bf Riordan graphs of the derivative type.} This class of graphs is of the form $(f',f)$ so $g=f'=f_1+f_3t^2+f_5t^4+\cdots$. Thus,  permutations corresponding to such graphs can be described algorithmically by imposing the following restrictions on $A$: in implementing the bijection $\psi$ every even step must place the current element into the left out of two valid slots. Thus, if this rule is not violated, the obtained permutation corresponds to a Riordan graph of the derivative type.\\

\section{Encoding oriented Riordan graphs by balanced words over $\{0,1,2\}$}\label{orient-Riord-graphs}

The  sequence $\tilde{r}_n$ counting oriented Riordan graphs $\mathcal{RG}^{(3)}_n$ and given by (\ref{formula-mod-3}) is A054879 in \cite{oeis}, one of whose interpretations is the number of words of length $2n$ on alphabet $\{0,1,2\}$ with an even number (possibly zero) of each letter. We call these words {\em balanced words} and denote the respective set by $\mathcal{B}_n$. Also, let $b_n:=|\mathcal{B}_n|$. The words in $\mathcal{B}_n$ are clearly in 1-to-1 correspondence with closed walks of length $2n$ along the edges of the $3$-cube (cube) starting at the origin. Such walks also mentioned in A054879. The correspondence is given by letting a walk take the $i$-th step in direction $x$, $1\leq x\leq 3$ (that is, swap the $i$-th coordinate from 0 to 1, or vice versa) in the case if the $i$-th letter in the word is $x-1$. The formula for $b_n$ (the same as (\ref{formula-mod-3})) is given in A054879 in \cite{oeis}, but its derivation would involve simplifying a more general result in \cite{Reyzin}
$$\frac{1}{2^n}\sum_{j=0}^{n}{n\choose j}(n-2j)^r$$
after placing $n=3$ there. As a bi-product, in this section we obtain an alternative justification of  (\ref{formula-mod-3}) be valid for $b_n$ after explaining combinatorially the recursion (\ref{rec-2-b}).

To build a recursive encoding in question, we will use an alternative, inductive way to prove formula (\ref{formula-mod-3}) via first explaining combinatorially the recursion
\begin{eqnarray}\label{rec-1-o}\tilde{r}_{n+1}=3\tilde{r}_n+6(\tilde{r}_n-1),\end{eqnarray}
which is a particular case of $p=3$ in (\ref{rpn-rec-formula}) proved above. Next, we explain \begin{eqnarray}\label{rec-2-b}b_{n+1}=3b_n+6(b_n-1),\end{eqnarray} which, again, will provide an alternative proof for the formula (\ref{formula-mod-3}) for $b_n$ given in A054879. \\

\noindent
{\bf Explanation of (\ref{rec-1-o}).} Each graph $G_{n+1}(g,f)$ in  $\mathcal{RG}^{(3)}_{n+1}$ either has
\begin{itemize}
\item $f_{n-b^*-1}=0$ (in the case $b^*$ is not defined we can assume $\tilde{f}=0$),
and there are $3\tilde{r}_n$ ways to select such $G$ , where ``3'' is the number of choices for $g_{n-1}$, or
\item $f_{n-b^*-1}\in\{1,2\}$ and $g_0g_1\ldots g_{n-2}\neq 00\cdots 0$, so that there are 3 choices for $g_{n-1}$ and in total $6(b_n-1)$ ways to select such a $G$.
\end{itemize}
This completes the proof of (\ref{rec-1-o}).\\

\noindent
{\bf Explanation of (\ref{rec-2-b}).} We note that any balanced word either ends with $xx$ or with $xy$, $x\neq y$, $x,y\in\{0,1,2\}$. Clearly, there are $3b_n$ words in $\mathcal{B}_{n+1}$ ending with 00 or 11 or 22. Next, we prove that there are $6(b_n-1)$ words in $\mathcal{B}_{n+1}$ ending with $xy$, $x\neq y$. To generate any such word we use the function $h_{x,y}$ that
\begin{itemize}
\item takes any word $w$ in $\mathcal{B}_{n}$ different from $zz\cdots z$ for $z\neq x,y$, then
\item replaces the leftmost occurrence of an element in $\{x,y\}$ in $w$ by the opposite from the same set, and
\item attaches $xy$ to the obtained word.
\end{itemize}
For example, for $x=0$ and $y=1$, $h_{0,1}(22012120)=2211212001$. Note that $h_{x,y}$ is well-defined because its outcome is a balanced word.

Next note that $h_{x,y}$ is injective. Indeed, different words, say $w_1$ and $w_2$, would either get different endings, and thus will result in different outcomes, or they will have the same ending. In the later case, if such an ending is $xx$ then we clearly have different outcomes. Otherwise, the ending is $xy$ for $x\neq y$. Consider the smallest $i\geq 1$ such that the $i$-th element in $w_1$ is different from the $i$-th element in $w_2$ (such an $i$ exists).  Thus, $w_1=x_1x_2\cdots x_{i-1}a\cdots$ and $w_2=x_1x_2\cdots x_{i-1}b\cdots$ and $a\neq b$. If none of the $a$ and $b$ would be changed by $h_{x,y}$, the outcome words are different. On the other hand if, without loss of generality $a$ will be changed, then $x_1x_2\cdots x_{i-1}=zz\cdots z$ for $z\neq x,y$, and thus either
\begin{itemize}
\item $b=z$ in which case we obtain $h_{x,y}(w_1)\neq h_{x,y}(w_2)$ as $a\neq z$, or
\item $b$ in $w_2$ will be changed as well, so that $h_{x,y}(w_1)$ and $h_{x,y}(w_2)$ differ in position $i$.
\end{itemize}
So, in either case, $h_{x,y}(w_1)\neq h_{x,y}(w_2)$.

We finally prove surjectivity of $h_{x,y}$ that completes our proof of (\ref{rec-2-b}). Given a word $w_1w_2\cdots w_{2n+2}\in\mathcal{B}_{n+1}$ we replace the leftmost occurrence of a letter in $\{w_{2n+1}w_{2n+2}\}$ in $w_1w_2\cdots w_{2n}$ by the opposite from the same set so that the resulting word belongs to $\mathcal{B}_n$. For example, $h_{x,y}^{-1}(0021210202)=20212102$. \\

\begin{theorem}
There is a bijection between $\mathcal{RG}^{(3)}_{n+1}$ and $\mathcal{B}_n$.
\end{theorem}
\begin{proof}
We describe recursively a bijective map $\eta:\mathcal{RG}^{(3)}_{n+1}\rightarrow\mathcal{B}_n$ based on our proofs of relations (\ref{rec-1-o}) and (\ref{rec-2-b}) with the base cases $\eta(G_2(0,0))=00$, $\eta(G_2(1,0))=11$ and $\eta(G_2(2,0))=22$.

Suppose that $\eta$ is already defined for $\mathcal{RG}^{(3)}_{n}$, $n\geq 2$, and $\eta(G_n(g,f))=w_1w_2\cdots w_{2n-2}$. Moreover, we make the following assumptions, which work for the base case and will work for $n+1$ as well:
\begin{itemize}
\item $\eta(G_n(0,0))=00\cdots 0$;
\item  $\eta(G_n(1+t+\cdots + t^{n-2},0))=11\cdots 1$;
\item $\eta(G_n(2+2t+\cdots + 2t^{n-2},0))=22\cdots 2$.
\end{itemize}
Then, adding $g_{n-1}$ and $f_{n-b^*-1}$ into consideration results in a graph $G\in \mathcal{RG}^{(3)}_{n+1}$ obtained from $G_n(g,f)$ by adding one vertex, and we define $\eta(G)$ by the following rules:
\begin{itemize}
\item If $f_{n-b^*-1}=0$ or $\tilde{f}=0$ (in the case $b^*$ is not defined) then $\eta(G)=w_1w_2\cdots w_{2n-2}g_{n-1}g_{n-1}$.
\item If $f_{n-b^*-1}=1$, then we can take any $G_n(g,f)$ except for the one with  $\tilde{g}= 0$ corresponding to $w_1w_2\cdots w_{2n-2}=00\cdots 0$, and consider the following subcases:
\begin{itemize}
\item if $g_{n-1}=0$ then $\eta(G)=h(w_1w_2\cdots w_{2n-2})01$ if $w_1w_2\cdots w_{2n-2}\neq 22\cdots 2$ and $\eta(G)=h(00\cdots 0)01=100\cdots 01$ otherwise; note that this rule is injective, well-defined for any $G_n(g,f)$ different from an empty graph, and covers all words in $\mathcal{B}_n$ ending with 01.
\item if $g_{n-1}=1$ then $\eta(G)=h(w_1w_2\cdots w_{2n-2})12$, which is well-defined since $w_1w_2\cdots w_{2n-2}\neq 00\cdots 0$, injective, and covers all words in $\mathcal{B}_n$ ending with 12.
\item if $g_{n-1}=2$ then $\eta(G)=h(w_1w_2\cdots w_{2n-2})02$ if $w_1w_2\cdots w_{2n-2}\neq 11\cdots 1$ and $\eta(G)=h(00\cdots 0)02=200\cdots 02$ otherwise; note that this rule is injective, well-defined for any $G_n(g,f)$ different from an empty graph, and covers all words in $\mathcal{B}_n$ ending with 02.\end{itemize}
\item If $f_{n-b^*-1}=2$, then we can take any $G_n(g,f)$ except for the one with  $\tilde{g}= 0$ corresponding to $w_1w_2\cdots w_{2n-2}=00\cdots 0$, and consider the following subcases:
\begin{itemize}
\item if $g_{n-1}=0$ then $\eta(G)=h(w_1w_2\cdots w_{2n-2})10$ if $w_1w_2\cdots w_{2n-2}\neq 22\cdots 2$ and $\eta(G)=h(00\cdots 0)10=100\cdots 010$ otherwise; note that this rule is injective, well-defined for any $G_n(g,f)$ different from an empty graph, and covers all words in $\mathcal{B}_n$ ending with 10.
\item if $g_{n-1}=1$ then $\eta(G)=h(w_1w_2\cdots w_{2n-2})21$, which is well-defined since $w_1w_2\cdots w_{2n-2}\neq 00\cdots 0$, injective, and covers all words in $\mathcal{B}_n$ ending with 21.
\item if $g_{n-1}=2$ then $\eta(G)=h(w_1w_2\cdots w_{2n-2})20$ if $w_1w_2\cdots w_{2n-2}\neq 11\cdots 1$ and $\eta(G)=h(00\cdots 0)20=200\cdots 020$ otherwise; note that this rule is injective, well-defined for any $G_n(g,f)$ different from an empty graph, and covers all words in $\mathcal{B}_n$ ending with 020.\end{itemize}
\end{itemize}
The fact that $\eta$ is well-defined and bijective follows from our remarks above. For example, $w=\eta(G_5(1+2t^2+t^3,t^2))$ can be recursively calculated from $\eta(G_4(1+2t^2+t^3,t^2))$ and $g_{n-1}=g_4=0$ and $f_{n-b^*-1}=f_{5-1-1}=f_3=0$ so that $w$ will end with 00. In turn, $w'=\eta(G_4(1+2t^2+t^3,t^2))$ can be recursively calculated from $\eta(G_3(1+2t^2+t^3,t^2))$ and $g_3=1$ and $f_{2}=1$, so that $w'$ will end with 12. And so on. One can check that $w=2100221200$.
\end{proof}

\section{Concluding remarks}\label{concl-sec}
This paper provides a convenient encoding of $p$-Riordan graphs in terms of $p$-Riordan words, and explains combinatorially some links between (oriented) Riordan graphs and balanced words (equivalently, certain closed walks in a cube) and pattern-avoiding permutations.

We leave it as an open question to explain combinatorially that the sequence $(r_n)_{n\ge0}$  counting Riordan graphs and given by (\ref{Riord-rn}) also counts permutations in $S_n(4321,4123)$, or in $S_n(4321, 3412)$, or in $S_n(4123,3214)$, or in $S_n(4123,2143)$ that were enumerated in \cite{KW}; also see A047849 in \cite{oeis}. A natural approach would be to use 2-Riordan words that are in bijection with Riordan graphs to establish a correspondence in question. However, enumeration of pattern-avoiding permutations in \cite{KW} is rather involved (it uses the notion of an {\em active site}) and e.g.\ cannot be translated that easily into recursion (\ref{spn-formula}) for $p=2$.

\section{Acknowledgments} The work of the second author was supported by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education of Korea (NRF-2019R1I1A1A01044161).