Let $a(n)=$ Number of ordered set partitions of $[n]$ such that the smallest element of each block is odd.
Example:
a(3) = 3: 123, 12|3, 3|12.
a(4) = 5: 1234, 124|3, 3|124, 12|34, 34|12.
See A290384 for details.
Motivated by Question 403336 and Question 403386, I consider the permanents $\operatorname{per}(A)$ where
$$A=\left[\left\lceil \frac{2j-k}{n+\cos^2(\frac{n\pi}{2})}\right\rceil \right]_{1\le j,k\le n}$$ and $\lceil \cdot\rceil$ is the ceil function.
When $n=1,2,3,4,5,6$, $A=$
$$\left[ \begin {array}{c} 1\end {array} \right] ,$$
$$\left[ \begin {array}{cc} 1&0\\ 1&1\end {array} \right], $$
$$ \left[ \begin {array}{ccc} 1&0&0\\ 1&1&1
\\ 2&2&1\end {array} \right]
,$$
$$ \left[ \begin {array}{cccc} 1&0&0&0\\ 1&1&1&0
\\ 1&1&1&1\\ 2&2&1&1\end {array}
\right]
,$$
$$ \left[ \begin {array}{ccccc} 1&0&0&0&0\\ 1&1&1&0&0
\\ 1&1&1&1&1\\ 2&2&1&1&1
\\ 2&2&2&2&1\end {array} \right]
,$$
$$\left[ \begin {array}{cccccc} 1&0&0&0&0&0\\ 1&1&1&0
&0&0\\ 1&1&1&1&1&0\\ 1&1&1&1&1&1
\\ 2&2&1&1&1&1\\ 2&2&2&2&1&1
\end {array} \right]
$$
respectively.
Numerical computation indicates that
$$\operatorname{per}(A)=a(n)$$
for $1≤n≤21$.
n per(A)
1 1
2 1
3 3
4 5
5 23
6 57
7 355
8 1165
9 9135
10 37313
11 352667
12 1723605
13 19063207
14 108468169
15 1374019539
16 8920711325
17 127336119839
18 928899673425
19 14751357906571
20 119445766884325
21 2088674728868631
Thus, we obtain the following
Conjecture 1. For any positive integer $n$,$$\operatorname{per}(A) = a(n).$$
Question 1. Is this identity correct? How to prove it?
EDIT
Let
$$B=\left[\left\lceil \frac{j+k}{n+\cos^2(\frac{n\pi}{2})}\right\rceil \right]_{1\le j,k\le n}$$
where $\lceil \cdot\rceil$ is the ceil function.
When $n=1,2,3,4,5,6$, $B=$
$$ \left[ \begin {array}{c} 2\end {array} \right], $$
$$\left[ \begin {array}{cc} 1&1\\ 1&2\end {array}
\right], $$
$$\left[ \begin {array}{ccc} 1&1&2\\ 1&2&2
\\ 2&2&2\end {array} \right] ,$$
$$ \left[ \begin {array}{cccc} 1&1&1&1\\ 1&1&1&2
\\ 1&1&2&2\\ 1&2&2&2\end {array}
\right] ,$$
$$ \left[ \begin {array}{ccccc} 1&1&1&1&2\\ 1&1&1&2&2
\\ 1&1&2&2&2\\ 1&2&2&2&2
\\ 2&2&2&2&2\end {array} \right] ,$$
$$ \left[ \begin {array}{cccccc} 1&1&1&1&1&1\\ 1&1&1&1
&1&2\\ 1&1&1&1&2&2\\ 1&1&1&2&2&2
\\ 1&1&2&2&2&2\\ 1&2&2&2&2&2
\end {array} \right]
$$
respectively.
We have the following
Conjecture 2. For any positive integer $n$,
$$\operatorname{per}(B)=\frac{3-(-1)^n}{2}F(n)$$
where $F(n)$ is the Fubini numbers, i.e. the number of ordered partitions of $[n]$.
It is equivalent to
Conjecture 3. For any positive integer $n$,
$$\operatorname{per}(C)=F(n),$$
where $$C=\left[\left\lceil\frac{j+k}{n+1}\right\rceil\right]_{1\le j,k\le n}.$$
Numerical computation indicates that it is true for $1≤n≤21$.
Question 2. Are these new results? How to prove them?
A2: By @Peter Taylor's comments, Conjectures 2 and 3 are known results.
ADDED
Today (2021-9-24), I discovered the following interesting arithmetic properties of $a(n)$
Conjecture 4. For any prime $p$,
$$a(n) \equiv a(n+p(p-1)) \pmod p.$$
Noting that $a(1)=a(2)=1$, we have
Conjecture 5. For any prime $p$ ,
$$a(p^2-p+1) \equiv 1 \pmod p,$$
$$a(p^2-p+2) \equiv 1 \pmod p.$$
Numerical computation indicates that it is true for $2≤p≤19$.
Moreover
Conjecture 6. For any prime $p$ and positive integer $n\geq h \geq 1$,
$$a(n) \equiv a(n+p^h(p-1)) \pmod{p^h}.$$
It is similar to Daniel Barsky's congruence for Fubini numbers.
Daniel Barsky's Congruence. For any prime $p$ and positive integer $n\geq h \geq 1$,
$$F(n) \equiv F(n+p^{h-1}(p-1)) \pmod{p^h},$$
where $F(n)$ is the Fubini numbers.
Question 3. Are these congruences correct? How to prove them?
ADDED (2021-9-27)
Claim. Conjecture 4 is true for $2 \leq p \leq 5$.
Proof. Obviously, we have $a(n)\equiv 1 \pmod{2}$.
For $3\leq p \leq 5$, we use the following generating function
$$\sum_{n\geq 1} a(n)x^n = \sum_{k\geq 1} \frac{(-1)^{k-1}}{\binom{-\frac1x-1}{k-1}\binom{\frac1x-1}k},$$
which is proved by Max Alekseyev.
When $p=3$,
\begin{align}
\sum_{n\geq 1} a(n)x^n
&\equiv \sum_{1 \leq k \leq 2} \frac{(-1)^{k-1}}{\binom{-\frac1x-1}{k-1}\binom{\frac1x-1}k}\\
&=-\frac{x}{x-1}+2\,{\frac {{x}^{3}}{ \left( x+1 \right) \left( 2\,{x}^{2}-3\,x+1
\right) }}\\
&= \sum _{n=0}^{\infty } \left( -{\frac { \left( -1 \right) ^{n}}{3}}+{
\frac {{2}^{n}}{3}} \right) {x}^{n}
\pmod{3}
\end{align}
and $-{\frac { \left( -1 \right) ^{n}}{3}}+{\frac {{2}^{n}}{3}} \pmod{3}$ is a periodic sequence with least period $6$: repeat in the pattern $$1, 1, 0, 2, 2, 0.$$
This leads to $a(n) \equiv a(n+6) \pmod 3.$
Similarly, we have
\begin{align}
\sum_{n\geq 1} a(n)x^n
&\equiv \sum_{1 \leq k \leq 4} \frac{(-1)^{k-1}}{\binom{-\frac1x-1}{k-1}\binom{\frac1x-1}k}\\
&=\sum _{n=0}^{\infty } \left( {\frac {13\,{2}^{n}}{30}}+{\frac {{4}^{n}
}{35}}+{\frac { \left( -2 \right) ^{n}}{10}}-{\frac { \left( -3
\right) ^{n}}{35}}-{\frac {13\, \left( -1 \right) ^{n}}{30}}-{\frac {
{3}^{n}}{10}} \right) {x}^{n}
\pmod{5},
\end{align}
so $a(n) \pmod{5}$ is a periodic sequence with least period $20$: repeat in the pattern $$1, 1, 3, 0, 3, 2, 0, 0, 0, 3, 2, 0, 2, 4, 4, 0, 4, 0, 1, 0.$$
This leads to $a(n) \equiv a(n+20) \pmod 5.$ QED
Moreover, we have the following
Conjecture 7. For any odd prime $p$,
\begin{equation}
\sum_{n=1}^{p(p-1)}a(n) \equiv
\begin{cases}
p \pmod{p^2} &\mbox{if $p \equiv 1 \pmod 4$ }\\
0 \pmod{p^2} &\mbox{if $p \equiv 3 \pmod 4$ }
\end{cases}.
\end{equation}
It is true for $3 \leq p \leq 19$.
ADDED (2021-10-04)
Conjecture 8. For any prime $p$,
$$\sum_{n=1}^{p(p-1)}\left(\frac{a(n)}{p}\right)\equiv 0 \pmod p,$$
where $\left(\frac{\cdot}p\right)$ is the Legendre symbol.
It is true for $2 \leq p \leq 19$.
Best 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
Hence, $\mathrm{per}(A+B) = a(n)$. QED