Mrthdrb

Update: The problem has been solved. @Phicar and I individually give two transformation from $hrightarrow S$ and $Srightarrow h$, and they are inverse of each other. Any other explanation or bijective is still welcomed!

We know that the number of ways to put $n$ distinct balls (indexed $1,2,ldots,n$) into $m$ non-empty non-distinct boxes ($mleq n$) is the Stirling number of second type $S(n,m)$

We have the formula $S(n,m)=S(n-1,m-1)+mS(n-1,m)$ as well as the initial value $S(n,n)=S(n,1)=1$

Now we add the restriction that the adjacent balls should not be put into the same box（here we define $1$ and $n$ is non-adjacent）,and the number of ways is $h(n,m)$

Similarly, we have $h(n,m)=h(n-1,m-1)+(m-1)h(n-1,m)$ and $h(n,n)=1,h(n,2)=1​$. The only thing change here is the coefficient of the second term.

In fact, we can easily get the result that $h(n,m)=S(n-1,m-1)$

But I cannot figure out a more intuitive explanation or a bijective to show this equivalent relationship. Here I provides some basic example

$h(4,3)=S(3,2)=3​$，$2,14,1​$ and $3,13,1​$

$h(5,3)=S(4,2)=7$,

$135,13,14,14,15,35,13$ and

$124,12,2,24,23,234,4$

I will denote $[n]brace k=pi vdash [n]:$ the partitions of $[n]$ into $k$ blocks and i will denote $mathbbH(n,k)=pi in [n]brace k: pi text has no adjacent elements$ so that $|mathbbH(n,k)|=h(n,k).$
Consider the following function
$$varphi :[n-1]brace k-1longrightarrow mathbbH(n,k),$$
given by $varphi (pi)=gamma$ where if $pi = B_1,cdots ,B_k$ then
$gamma$ is taking each block $B$ of $pi$ and applying the algorithm find biggest $iin B$ such that $i,i-1 in B$ take $Bsetminus i-1$ and add $i$ to a new block that contains $n.$
in other words you send the elements that contradict your assumption of being adjacent to a block that contains $n.$
Example:
$$varphi (3)=colorred15|24|3$$
$$varphi (colorred12)=colorred135|2|4$$
$$varphi (2)=14|2|colorred35$$
$$varphi(1colorred23)=13|colorred25|4$$
$$varphi(2colorred34)=1|24|colorred35$$
Show that this and yours are inverse of each other.



Edit: I see you want another way. Think the following. $$mathbbH(n,k)=[n]brace ksetminus bigcup _i=1^n-1A_i,$$
where $A_i = pi in [n]brace k:i,i+1text share block$
So using inclusion-exclusion principle, you end up with
$$h(n,k)=sum _i = 0^n-1(-1)^ibinomn-1in-ibrace k.$$
This last thing because $|A_i|=n-1brace k$ by collapsing $i$ and $i+1$ to one element. Then $|A_icap A_j|=n-2brace k$ and so on.


Independently show that $$nbrace k=sum _i = 0^n-1binomn-1in-1-ibrace k-1,$$ by choosing the elements that go with $n$ in its block. Notice that this is a binomial transformation and so you can invert it as
$$n-1 brace k-1=sum _i = 0^n-1(-1)^ibinomn-1in-ibrace k.$$ And so $h(n,k)=n-1brace k-1.$

I will illustrate Phicar's bijection in more detail and explain why it is invertible.

You start with a partition of $[n-1]$ into $m-1$ non-distinct parts. Let us focus on a single part. For example, when $n=12$, one part could be
$$
1,2,3,5,6,8,9,10,11
$$
Now, break this into chains of consecutive integers.
$$

1,2,3quad 5,6quad 8,9,10,11

$$
Within each chain, we will keep the highest element, remove the second highest, keeps the third highest, remove the fourth highest, etc. The removed elements will all be put into a new part with the added element, $n$.
$$

1,colorred2,3quad colorred5,6quad colorred8,9,colorred10,11
\Downarrow\1,3quad6quad
9,11quad,quad 2,5,8,10,12$$
We do this for every part. It is easy to see the result will have no consecutive integers in the same part.

Now, why is this invertible? Given a partition of $[n]$ into $m$ distinct parts with no two adjacent elements in the same part, look at the part containing $n$. Everything in that part was moved there from a different part. But it is easy to see where it was moved from; the number $k$ must have come from the part containing $k+1$. After moving all these elements back, and deleting $n$, we get a partition of $[n-1]$ into $[m-1]$ parts.

My friend HHT gives a transformation.

I use the python code to verify that my construction and @Phicar 's construction is bijective. But I still cannot provide the proof now

In $h(n,m)$, consider the boxes with $n^textth$ ball. The box contains $a_1^textth,a_2^textthldots,n^textth$. Move all the ball $a_i^textth$ to the box containing $a_i+1^textth$ until the box contains $n^textth$ ball only. Then remove the box as well as the $n^textth$ ball.

But I still cannot prove it is a bijective yet

The example:

$135,13,14,14,15,35,13$

Move balls:

$12,4,23,134,5,1,13$

Remove $5$

$12,4,23,2,124,234,24$

# assert n <= 10 for convenience, otherwise the str will be too long
# and my brute force algorithm will be too slow

import copy

def sort(arr):
 for elem in arr:
 elem = sorted(elem)
 arr = sorted(arr, key=lambda x:x[0])
 return arr

def is_valid_S(arr):
 return all(arr)

def is_valid_H(arr):
 if not is_valid_S(arr):
 return False
 for elem in arr:
 for i in range(len(elem)-1):
 if elem[i] + 1 == elem[i+1]:
 return False
 return True

# generate(5, 3, is_valid_H) or generate(4, 2, is_valid_S)
def generate(n, m, is_valid):
 res = []
 for i in range(m**n):
 val = i
 tmp = []
 for i in range(m):
 tmp.append([])
 for idx in range(n):
 tmp[val % m].append(idx+1)
 val //= m
 if is_valid(tmp) and sort(tmp) not in res:
 res.append(sort(tmp))
 return res


def H2S(m_h_arr):
 h_arr = copy.deepcopy(m_h_arr)
 n = max(map(max, h_arr))
 idx = 0
 while n not in h_arr[idx]:
 idx += 1
 h_arr[idx].remove(n)
 for elem in h_arr[idx]:
 _idx = 0
 while elem + 1 not in h_arr[_idx]:
 _idx += 1
 h_arr[_idx].insert(h_arr[_idx].index(elem+1),elem)
 del h_arr[idx]
 return h_arr

def remove_adjacent(elem):
 idx = len(elem) - 2
 removed = []
 while idx != -1:
 if elem[idx] + 1 == elem[idx + 1]:
 removed.append(elem[idx])
 del elem[idx]
 idx -= 1
 return elem, removed

def S2H(m_s_arr):
 s_arr = copy.deepcopy(m_s_arr)
 n = max(map(max, s_arr))
 removed = []
 for i in range(len(s_arr)):
 e, r = remove_adjacent(s_arr[i])
 s_arr[i] = e
 for val in r:
 removed.append(val)
 removed.append(n+1)
 s_arr.append(sorted(removed))
 return sort(s_arr)

def is_bijective(n, m, H2S, S2H):
 if n > 9:
 print("please set n < 10")
 return 
 hs = generate(n, m, is_valid_H)
 ss = generate(n-1, m-1, is_valid_S)
 ss_ = list(map(H2S, hs))
 hs_ = list(map(S2H, ss))
 return all(map(lambda x:x in hs, hs_)) 
 and all(map(lambda x:x in hs_, hs)) 
 and all(map(lambda x:x in ss, ss_)) 
 and all(map(lambda x:x in ss_, ss))

is_bijective(8,4,H2S,S2H)
```