Return to Answer

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 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. Furthermore, our matrices have the shape of Ferrers boards, 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, 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

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 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. Furthermore, our matrices have the shape of Ferrers boards, 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, 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} (1+\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} (1+\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

Let me outline an approach for computing permanents in these conjectures. For the sake of concreteness, I consider Conjecture 1 for an odd $n$. The matrix here is the sum of the following two 0-1 matrices (using 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)$.

The crucial observation is that 0-1 matrices can be viewed as boards on which permanent enumerates non-attacking rook placements. Furthermore, our matrices have the shape of Ferrers boards, 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, 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\atop p_i=0}^{(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 become 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=i}^{\frac{n-1}2} p_j$ accounts for assignment of $2i+1$ to one of $1+\sum_{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=i}^{\frac{n-1}2} p_j$ accounts for assignment of $2i$ to one of $1+\sum_{j=1}^{i-1} p_j$ parts (whose smallest elements are smaller than $2i$).

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

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 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. Furthermore, our matrices have the shape of Ferrers boards, 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, 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

Let me outline an approach for computing permanents in these conjectures. For the sake of concreteness, I consider Conjecture 1 for an odd $n$. The matrix here is the sum of the following two 0-1 matrices (using 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)$.

The crucial observation is that 0-1 matrices can be viewed as boards on which permanent enumerates non-attacking rook placements. Furthermore, our matrices have the shape of Ferrers boards, 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, 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).$$

This can surely be simplified further and linked to sequence $a(n)$ - will do that when I have time.

Let me outline an approach for computing permanents in these conjectures. For the sake of concreteness, I consider Conjecture 1 for an odd $n$. The matrix here is the sum of the following two 0-1 matrices (using 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)$.

The crucial observation is that 0-1 matrices can be viewed as boards on which permanent enumerates non-attacking rook placements. Furthermore, our matrices have the shape of Ferrers boards, 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, 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\atop p_i=0}^{(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 become 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=i}^{\frac{n-1}2} p_j$ accounts for assignment of $2i+1$ to one of $1+\sum_{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=i}^{\frac{n-1}2} p_j$ accounts for assignment of $2i$ to one of $1+\sum_{j=1}^{i-1} p_j$ parts (whose smallest elements are smaller than $2i$).

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