Let me outline an approach for computing permanents in these conjectures. For the sake of concreteness, I will prove Conjecture 1 for an odd $n$. The matrix here is the sum of the following two 0-1 matrices (using [Iverson bracket](https://en.wikipedia.org/wiki/Iverson_bracket) notation):
$$A:=\big([2j-k \geq 1]\big)_{j,k=1}^n$$
and
$$B:=\big([2j-k \geq n+1]\big)_{j,k=1}^n$$
(notice that I intentionally redefine matrices $A$ and $B$). For example, for $n=5$, we have
$$A=\begin{bmatrix} 1&0&0&0&0\\ 1&1&1&0&0
\\ 1&1&1&1&1\\ 1&1&1&1&1
\\ 1&1&1&1&1\end{bmatrix}
\quad\text{and}\quad
B=\begin{bmatrix} 0&0&0&0&0\\ 0&0&0&0&0
\\ 0&0&0&0&0\\ 1&1&0&0&0
\\ 1&1&1&1&0\end{bmatrix}
$$
Our goal is to compute $\mathrm{per}(A+B)$ and show that it's equal to $a(n)$.

The crucial observation is that 0-1 matrices can be viewed as boards on which permanent enumerates [non-attacking rook placements](https://en.wikipedia.org/wiki/Rook_polynomial). Furthermore, our matrices have the shape of [Ferrers boards](https://en.wikipedia.org/wiki/Partition_(number_theory)#Ferrers_diagram), and the one for $B$ is a sub-board for that of $A$. From now on, I will not distinguish matrices $A$ and $B$ from the corresponding Ferrers boards. 

I will use the notation and machinery from my [other answer](https://mathoverflow.net/q/386804), which computes the number of non-attacking rook placements (i.e., the permanent) for the *difference* of a Ferrers board with its sub-board. In the current problem, we need to compute the number of placements of $n$ non-attacking rooks in $A$, where each placement comes with multiplicity $2^t$, where $t$ in the number of rooks in $B\subset A$.

Board $A$ has row lengths 
$$a:=(1,3,5,\dots,n-2,\underbrace{n,n,\dots,n}_{(n+1)/2}),$$
while board $B$ has row lengths
$$b:=(\underbrace{0,0,\dots,0}_{(n+1)/2},2,4,\dots,n-1).$$

By inclusion-exclusion here, we have
$$\mathrm{per}(A+B) = \sum_{T\subseteq[n]} r_n(A_{\bar T}\| B_T),$$
where $\bar T := [n] \setminus T$ is the complement of $T$. The analog of formula $(\star)$ here gives the following expression:
$$\mathrm{per}(A+B) = \sum_{p\in\{0,1\}^n} \prod_{i=1}^n \big(p_i(a_i-\sum_{j=1}^{\tau_A(i)-1} \delta_j) + q_i(b_i-\sum_{j=1}^{\tau_B(i)-1} \delta_j)\big),$$
where $q_i:=1-p_i$ and
$$\sigma:=\big(\underbrace{0,0,\dots,0}_{(n+1)/2},1,2,\dots,n-1,\underbrace{n,n,\dots,n}_{(n+1)/2}\big),$$
$$\delta:=\big(q_1,q_2,\dots,q_{\frac{n+1}2},p_1,q_{\frac{n+1}2+1},p_2,q_{\frac{n+1}2+2},\dots,p_{\frac{n-1}2},q_n,p_{\frac{n+1}2},p_{\frac{n+1}2+1},\dots,p_n\big),$$
$$\tau_A:=\big( \frac{n+3}2,\frac{n+7}2, \dots, \frac{3n+1}2, \frac{3n+3}2,\frac{3n+5}2,\dots,2n\big),$$
$$\tau_B:=\big(1,2,\dots,\frac{n+1}2,\frac{n+1}2+2,\frac{n+1}2+4,\dots,\frac{3n-1}2\big).$$

Correspondingly, we have
$$\sum_{j=1}^{\tau_A(i)-1} \delta_j =
\begin{cases} 
i-1 + \sum_{j=i}^{\frac{n-1}2+i}q_j, & \text{if}\ i\leq\frac{n-1}2;\\
n - \sum_{j=i}^{n}p_j, & \text{if}\ i\geq\frac{n+1}2.
\end{cases}$$
and
$$\sum_{j=1}^{\tau_B(i)-1} \delta_j =
\begin{cases} 
\sum_{j=1}^{i-1} q_j & \text{if}\ i\leq\frac{n-1}2;\\
i-1 - \sum_{j=i-\frac{n-1}2}^{i-1}p_j, & \text{if}\ i\geq\frac{n+1}2.
\end{cases}$$


The formula then becomes
$$\mathrm{per}(A+B) = \sum_{p\in\{0,1\}^n} \prod_{i=1}^{(n-1)/2} \big(p_i(i - \sum_{j=i}^{\frac{n-1}2+i}q_j) - q_i \sum_{j=1}^{i-1} q_j)\big)
\prod_{i=(n+1)/2}^n \big(p_i\sum_{j=i}^{n}p_j + q_i(i-n + \sum_{j=i-\frac{n-1}2}^{i-1}p_j)\big).$$

We can see that if $\min\{i\,:\,q_i=1\}\leq\frac{n-1}2$, then the corresponding summand is zero. Hence, we can restrict summation to $(p_i,q_i)=(1,0)$ for all $i\leq\frac{n-1}2$, and further the same holds for $i=\frac{n+1}2$. Shifting indices $i\to \frac{n+1}2+i$, we get the formula:
\begin{split}
&\mathrm{per}(A+B) = \sum_{p\in\{0,1\}^{\frac{n-1}2}} (1 + \sum_{j=1}^{\frac{n-1}2} p_i) \prod_{i=1}^{(n-1)/2} \big(p_i\sum_{j=i}^{\frac{n-1}2} p_j + q_i (1+\sum_{j=1}^{i-1} p_j)\big)(1+\sum_{j=1}^{i-1} p_j) \\
&=\sum_{p\in\{0,1\}^{\frac{n-1}2}} 
\bigg( (1 + \sum_{j=1}^{\frac{n-1}2} p_i) \prod_{i=1\atop p_i=1}^{(n-1)/2} \sum_{j=i}^{\frac{n-1}2} p_j\bigg) \cdot
\bigg( \prod_{i=1\atop p_i=0}^{(n-1)/2} (1+\sum_{j=1}^{i-1} p_j) \bigg) \cdot
\bigg( \prod_{i=1}^{(n-1)/2} (1+\sum_{j=1}^{i-1} p_j) \bigg)
\end{split}

---

Now, let's show that this is exactly $a(n)$. More specifically, if we restrict summation to fixed $1 + \sum_{j=1}^{\frac{n-1}2} p_i =: k$, then the sum gives the number of ordered set partitions with $k$ parts.

Think of constructing a set partition by assigning elements $1,2,\dots,n$ in order to some part, and of $p_i$ as the indicator for $2i+1$ being a smallest element in its part (element $1$ has to be the smallest in its part, and this where "$1+$ in the formula comes from). Then

 - $(1 + \sum\limits_{j=1}^{\frac{n-1}2} p_i) \prod\limits_{i=1\atop p_i=1}^{(n-1)/2} \sum\limits_{j=i}^{\frac{n-1}2} p_j = k!$ accounts for the order of parts;
 - $\prod\limits_{i=1\atop p_i=0}^{(n-1)/2} \sum\limits_{j=1}^{i-1} p_j$ accounts for assignments of $2i+1$ to one of $1+\sum\limits_{j=1}^{i-1} p_j$ parts, whose smallest elements are smaller than $2i+1$;
- $\prod\limits_{i=1}^{(n-1)/2} \sum\limits_{j=1}^{i-1} p_j$ accounts for assignments of $2i$ to one of $1+\sum\limits_{j=1}^{i-1} p_j$ parts (whose smallest elements are smaller than $2i$).

Hence, $\mathrm{per}(A+B) = a(n)$. QED