Some ideas about parking functions and integer partitions

Question

We know that a integer partition of $\lambda=(\lambda_1, ..., \lambda_m)$ of $n$ satisfying $\lambda_1\geq \cdots \geq \lambda_m$ and $\sum_{i=1}^m\lambda_i=n$. Let $\mathcal{P}(n)$ be the set of patitions $\lambda$ of $n$, and $\mathcal{P}_m(n)$ be the set of partitions $\lambda$ of $n$ with $m$ parts. Define a parking function of length $n$ to be a sequence $\alpha=(a_1, a_{2}, ..., a_n)\in \{0, 1, 2, ...\}^n$ satisfying the following condition: if $b_1\leq \cdots \leq b_n$ is the rearrangement of the terms of $\alpha$, then $b_i\leq i-1$.

Now we will connect parking functions with integer partitions. Given $\lambda\in \mathcal{P}(n)$, define a parking function with type $\lambda$ to be a parking function $\alpha_{\lambda}$ satisfying that $\{a_1, ..., a_n\}=\{0^{\lambda_1}, ..., (m-1)^{\lambda_m}\}$. Easily see that it is well-defined since the decreasing property of parts of $\lambda$ and naturally contain the condition that its length is $n$. Let $pf_{\lambda}(n)$ be the number of parking function with type $\lambda$, and $pf(n)=\sum_{\lambda\in \mathcal{P}(n)}pf_{\lambda}(n)$. We easily know that $pf(n)$ is $A005651(n)$ in OEIS.

Now we consider the "insert". That is, insert $1^{\lambda_1}$ into $0^{\lambda_1}$, and insert $2^{\lambda_3}$ into $0^{\lambda_1}1^{\lambda_2}$ etc. So we obtain a parking function with type $\lambda$. Consider the separate on this parking function, i.e., the repeated numbers more than one are not allowed to be adjacent.

Given $\lambda\in \mathcal{P}(n)$, we say that a parking function with type $\lambda$ is separated, if it satisfies the condition that the repeated numbers more than one are not allowed to be adjacent. Let $sp_{m}(n)$ be the number of separated parking function with type $\lambda$ where $\lambda=(\lambda_1, ..., \lambda_m)$, and $sp(n)=\sum_{m=1}^nsp_m(n)$.

So the first seven terms: 1, 2, 7, 32, 171, 1110, 8148. And $sp(n)$ is $A321688(n)$ in OEIS. Then we have the following problems:

(1). Can we study the enumeration of separated parking functions with type $\lambda$? And how?

(2). We can consider the set of restricted partitions, such as $\mathcal{D}(n)$, the set of partitions of $n$ with distinct parts. And $pf^*(n)=\sum_{\lambda\in \mathcal{D}(n)}pf_{\lambda}(n)$. The first ten terms: 1, 1, 4, 5, 16, 82, 169, 541, 2272, 17966. It is $A007837(n)$ in OEIS.

Answer 1

(1). Can we study the enumeration of separated parking functions with type $\lambda$? And how?

Clear["Global`*"];
NonAdjacentDuplicatesQ[p_List] := 
  Module[{counts, duplicates, positions}, 
   counts = Tally[p];(*Get counts of each element*)
   duplicates = 
    Select[counts, #[[2]] > 1 &][[All, 
      1]];(*Elements appearing more than once*)
   positions = 
    Position[p, #] & /@ duplicates;(*Get positions of duplicates*)
   AllTrue[positions, 
    AllTrue[Partition[#, 2, 1], 
      Part[#[[2]] - #[[1]], 1] > 1 &] &] (*Check non-adjacency*)];
testTheSocalledSeparatedParkingFunction[n_] := 
 Module[{}, ps = IntegerPartitions[n]; 
  bs = Table[
    Apply[Join, 
     Table[ConstantArray[i - 1, p[[i]]], {i, 1, Length@p}]], {p, 
     ps}];
  Count[Flatten[Permutations /@ bs, 1], 
   x_ /; NonAdjacentDuplicatesQ[x]]
  ]
testTheSocalledSeparatedParkingFunction /@ Range[1, 7, 1]

So the first seven terms: 1, 2, 7, 32, 171, 1110, 8148. And $sp(n)$ is A321688 in OEIS.

     

---

     

(2). We can consider the set of restricted partitions, such as $\mathcal{D}(n)$, the set of partitions of $n$ with distinct parts. And $pf^*(n)=\sum_{\lambda\in \mathcal{D}(n)}pf_{\lambda}(n)$.

Clear["Global`*"];
DistinctPartitions[n_] := 
  Select[IntegerPartitions[n], DuplicateFreeQ[#] &];
Table[Apply[Plus, Multinomial @@ # & /@ IntegerPartitions[n]], {n, 1, 10}]
Table[Apply[Plus, Multinomial @@ # & /@ DistinctPartitions[n]], {n, 1, 10}]

So the first ten terms: 1, 1, 4, 5, 16, 82, 169, 541, 2272, 17966. It is A007837 in OEIS.