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](http://oeis.org/A290384) for details.


Motivated by [Question 403336](https://mathoverflow.net/questions/403336/) and [Question 403386](https://mathoverflow.net/questions/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](http://oeis.org/A000670), 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](http://www.mat.univie.ac.at/%7Eslc/opapers/s05barsky.html) for [Fubini numbers](http://oeis.org/A000670).


**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](http://oeis.org/A000670).


**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$.



Set partitions and permanents
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} (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


