4
$\begingroup$

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

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

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

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

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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.