Números de Stirling de segundo tipo, pero no hay dos números adyacentes en la misma parte.

Question

Actualización: El problema ha sido resuelto. @Phicar y me individualmente dar dos transformación de $h\rightarrow S$ e $S\rightarrow h$, y son inversos el uno del otro. Cualquier otra explicación o bijective todavía es bienvenida!

Sabemos que el número de maneras de poner $n$ distintas bolas (indexado $1,2,\ldots,n$) a $m$ no vacío de no-cajas distintas ($m\leq n$) es el número de Stirling de segundo tipo $S(n,m)$

Tenemos la fórmula $S(n,m)=S(n-1,m-1)+mS(n-1,m)$ así como el valor inicial $S(n,n)=S(n,1)=1$

Ahora se añade la restricción de que las bolas adyacentes no debe ser puesto en el mismo cuadro（aquí definimos $1$ e $n$ es no-adyacentes）,y el número de maneras es $h(n,m)$

Así mismo, se $h(n,m)=h(n-1,m-1)+(m-1)h(n-1,m)$ e $h(n,n)=1,h(n,2)=1​$. La única cosa que cambia aquí es el coeficiente del segundo término.

De hecho, podemos fácilmente obtener el resultado que $h(n,m)=S(n-1,m-1)$

Pero no puedo encontrar una explicación más intuitiva o una bijective para mostrar un equivalente de esta relación. Aquí me aporta ejemplo

$h(4,3)=S(3,2)=3​$，$\{13|2|4\},\{14|2|3\},\{1|24|3\}​$ e $\{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\}$ y

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

Answer 1

Voy a denotar ${[n]\brace k}=\{\pi \vdash [n]:|\pi|=k\}$ las particiones de $[n]$ a $k$ bloques y voy a denotar $\mathbb{H}(n,k)=\{\pi \in {[n]\brace k}: \pi \text{ has no adjacent elements}\}$ , de modo que $|\mathbb{H}(n,k)|=h(n,k).$
Considere la siguiente función $$\varphi :{[n-1]\brace k-1}\longrightarrow \mathbb{H}(n,k),$$ dado por $\varphi (\pi)=\gamma$ donde si $\pi = \{B_1,\cdots ,B_k\}$luego $\gamma$ está tomando cada bloque $B$ de $\pi$ y aplicando el algoritmo de encontrar mayor $i\in B$ tal que $i,i-1 \in B$ tome $B\setminus \{i-1\}$ y agregar $i$ a un nuevo bloque que contiene a$n.$ en otras palabras, usted enviar los elementos que contradicen su asunción de estar al lado de un bloque que contiene a$n.$
Ejemplo: $$\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}$$ Muestran que este y el tuyo son inversos el uno del otro.


Edit: veo que quieres de otra manera. Creo que el siguiente. $$\mathbb{H}(n,k)={[n]\brace k}\setminus \bigcup _{i=1}^{n-1}A_i,$$ donde $A_i = \{\pi \in {[n]\brace k}:i,i+1\text{ share block}\}$ Así que el uso de la inclusión-exclusión en el principio, usted puede terminar para arriba con $$h(n,k)=\sum _{i = 0}^{n-1}(-1)^i\binom{n-1}{i}{n-i\brace k}.$$ Esto último debido a que $|A_i|={n-1\brace k}$ por el colapso de $i$ e $i+1$ a un elemento. A continuación, $|A_i\cap A_j|={n-2\brace k}$ y así sucesivamente.

Independientemente muestran que $${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 en su bloque. Aviso que este es un binomio de transformación y así que usted puede invertir como $${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\llave de k-1}.$

Answer 2

Voy a ilustrar Phicar del bijection en más detalle y explique por qué es invertible.

Usted comienza con una partición de $[n-1]$ a $m-1$ no-partes bien diferenciadas. Vamos a centrarnos en una sola parte. Por ejemplo, cuando se $n=12$, una parte podría ser $$ \{1,2,3,5,6,8,9,10,11\} $$ Ahora, romper esta en las cadenas de enteros consecutivos. $$ \{ 1,2,3\quad 5,6\quad 8,9,10,11 \} $$ Dentro de cada cadena, vamos a mantener los más altos elemento, eliminar el segundo más alto, mantiene la tercera más alta, retire el cuarto más alto, etc. La quita de los elementos será condenado a una nueva parte con el elemento añadido, $n$. $$ \{ 1,\color{rojo}2,3\quad \color{rojo}5,6\quad \color{rojo}8,9,\color{red}{10},11 \}\\\Downarrow\\\{1,3\quad6\quad 9,11\}\quad\quad \{2,5,8,10,12\}$$ Hacemos esto para cada parte. Es fácil ver que el resultado no tiene números enteros consecutivos en la misma parte.

Ahora, ¿por qué esto es invertible? Dada una partición de $[n]$ a $m$ partes distintas, y no hay dos elementos adyacentes en la misma parte, mirar a la parte que contiene la $n$. Todo lo que en esa parte fue trasladado allí desde otra parte. Pero es fácil ver de donde fue trasladado desde; el número de $k$ debe provenir de la parte que contiene la $k+1$. Después de mover todos estos elementos, y la eliminación de $n$, se obtiene una partición de $[n-1]$ a $[m-1]$ partes.

Answer 3

Mi amigo HHT da una transformación.

Yo uso el código en python para comprobar que mi construcción y @Phicar 's de la construcción es bijective. Pero yo todavía no puede proporcionar la prueba ahora

En $h(n,m)$, considere las cajas con $n^{\text{th}}$ pelota. La caja contiene $a_1^{\text{th}},a_2^{\text{th}}\ldots,n^{\text{th}}$. Mover toda la bola de $a_i^{\text{th}}$ a la caja que contiene a$a_{i+1}^{\text{th}}$ hasta que la caja contiene $n^{\text{th}}$ el balón. A continuación, retire la caja así como el $n^{\text{th}}$ pelota.

Pero todavía no puedo probar que es un bijective aún

El ejemplo:

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

Mover las bolas:

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

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