# Stirling numbers of second kind, but no two adjacent numbers in same part.

Update: The problem has been solved. @Phicar and I individually give two transformation from $$h\rightarrow S$$ and $$S\rightarrow 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 ($$m\leq 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​$$$$\{13|2|4\},\{14|2|3\},\{1|24|3\}​$$ and $$\{12|3\},\{13|2\},\{1|23\}​$$

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

$$\{135|2|4\},\{13|25|4\},\{14|25|3\},\{14|2|35\},\{15|24|3\},\{1|24|35\},\{13|24|5\}$$ and

$$\{124|3\},\{12|34\},\{134|2\},\{13|24\},\{14|23\},\{1|234\},\{123|4\}$$

• i have added another way. You might enjoy it as well. – Phicar Apr 15 at 23:25

I will denote $${[n]\brace k}=\{\pi \vdash [n]:|\pi|=k\}$$ the partitions of $$[n]$$ into $$k$$ blocks and i will denote $$\mathbb{H}(n,k)=\{\pi \in {[n]\brace k}: \pi \text{ has no adjacent elements}\}$$ so that $$|\mathbb{H}(n,k)|=h(n,k).$$
Consider the following function $$\varphi :{[n-1]\brace k-1}\longrightarrow \mathbb{H}(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 $$i\in B$$ such that $$i,i-1 \in B$$ take $$B\setminus \{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 ({\color{red}{1}24|3})=\color{red}{15}|24|3$$ $$\varphi ({\color{red}{1}2|\color{red}{3}4})=\color{red}{135}|2|4$$ $$\varphi ({1\color{red}{3}4|2})=14|2|\color{red}{35}$$ $$\varphi({1\color{red}{2}3|4})=13|\color{red}{25}|4$$ $$\varphi({1|2\color{red}{3}4})=1|24|\color{red}{35}$$ Show that this and yours are inverse of each other.

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

Independently show that $${n\brace k}=\sum _{i = 0}^{n-1}\binom{n-1}{i}{n-1-i\brace 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)^i\binom{n-1}{i}{n-i\brace k}.$$ And so $$h(n,k)={n-1\brace k-1}.$$

• Yes, we can use the binomial transform to get the result directly – VicaYang Apr 16 at 1:45

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,3\quad 5,6\quad 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,\color{red}2,3\quad \color{red}5,6\quad \color{red}8,9,\color{red}{10},11 \}\\\Downarrow\\\{1,3\quad6\quad 9,11\}\quad,\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.

• Yes, I realize that Phicar’s construction and mine are mutually inverse to each other. – VicaYang Apr 15 at 16:52

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^{\text{th}}$$ ball. The box contains $$a_1^{\text{th}},a_2^{\text{th}}\ldots,n^{\text{th}}$$. Move all the ball $$a_i^{\text{th}}$$ to the box containing $$a_{i+1}^{\text{th}}$$ until the box contains $$n^{\text{th}}$$ ball only. Then remove the box as well as the $$n^{\text{th}}$$ ball.

But I still cannot prove it is a bijective yet

The example:

$$\{135|2|4\},\{13|25|4\},\{14|25|3\},\{14|2|35\},\{15|24|3\},\{1|24|35\},\{13|24|5\}$$

Move balls:

$$\{5|12|34\},\{123|5|4\},\{14|5|23\},\{134|2|5\},\{5|124|3\},\{1|234|5\},\{13|24|5\}$$

Remove $$5$$

$$\{12|34\},\{123|4\},\{14|23\},\{134|2\},\{124|3\},\{1|234\},\{13|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

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)
$$$$
`