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

Question

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\}$

Answer 1

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

Answer 2

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

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

Answer 3

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.

Answer 4

I think this problem is worth re-visiting. We will use PIE. The underlying poset for PIE consists of nodes $Q \subseteq [n-1]$ ordered by set inclusion representing set partitions of $[n]$ into $k$ non-empty subsets where $q\in Q$ implies that $q$ and $q+1$ are in the same subset. These partitions could have additional elements in the same subset as their successor. The weight of the partitions represented at $Q$ will be $(-1)^{|Q|}.$ Now a partition having exactly $P$ as the set of elements who are in the same subset as their successor where $P\ne \emptyset$ will be included in all nodes $Q\subseteq P.$ This means the total weight contributed by the partition every time it appears, is

$$\sum_{Q\subseteq P} (-1)^{|Q|} = \sum_{q=0}^{|P|} {|P|\choose q} (-1)^q = 0.$$

On the other hand a partition having no adjacent elements in the same subset will only be included in $Q=\emptyset$ for a total weight of $(-1)^{|\emptyset|} = 1.$ Hence these weights produce exactly what we mean to count. We have now counted one way, computing the total weight of each partition. This same count can be obtained another way, by computing the number of elements represented at each node $Q$ and multiplying by the weight $(-1)^{|Q|}.$ What is the cardinality of the set of partitions represented at $Q$? Ordering the elementsof $[n]$ covered by $Q$ we obtain a sequence of blocks when we fuse adjacent values (values next to their successor). Suppose there are $m$ blocks of length $b_1, b_2, \ldots b_m$ where $1\le m\le |Q|$ and $b_j\ge 2$ (the upper bound may not be attained as it could happen that $3|Q|-1\gt n$, we must always have $3m-1\le n$). We remove the constitutents of these blocks from $[n]$ for a change of $-b_1-b_2-\ldots -b_m$ and replace them by their fused version (which may no longer be separated and acquires a unique identity), for a change of $+m$. This means the net change in the number of elements is $-(b_1-1)-(b_2-1)-\ldots-(b_m-1).$ But this is precisely $-|Q|$ as a fused block of length $b$ is produced by $b-1$ adjacent elements of $Q.$ Therefore the number of partitions represented at $Q$ is ${n-|Q|\brace k}$ and we get by applying PIE the closed form

$$H_{n,k} = \sum_{Q\subseteq [n-1]} (-1)^{|Q|} {n-|Q|\brace k} = \sum_{q=0}^{n-1} {n-1\choose q} (-1)^q {n-q\brace k}.$$

We then have by basic EGFs that this is

$$\sum_{q=0}^{n-1} {n-1\choose q} (-1)^q (n-q)! [z^{n-q}] \frac{(\exp(z)-1)^k}{k!} \\ = \sum_{q=0}^{n-1} {n-1\choose q} (-1)^q (n-1-q)! [z^{n-1-q}] \exp(z) \frac{(\exp(z)-1)^{k-1}}{(k-1)!}.$$

Now apply convolution of EGFs to obtain

$$(n-1)! [z^{n-1}] \exp(-z) \exp(z) \frac{(\exp(z)-1)^{k-1}}{(k-1)!} \\ = (n-1)! [z^{n-1}] \frac{(\exp(z)-1)^{k-1}}{(k-1)!}.$$

We have shown that

$$\bbox[5px,border:2px solid #00A000]{ H_{n,k} = {n-1\brace k-1}.}$$