Prueba combinatoria de recurrencia del número de Stirling de segunda clase

Estoy trabajando con el problema del número de Stirling del segundo tipo del libro Principios y técnicas en combinatoria de Chen Chuang-Chong y Koh Khee-Meng. Página 73 problema 84: Dado r , norte ∈ Z con 0 ≤ norte ≤ r , el número de Stirling S ( norte , k ) del segundo tipo se define como el número de formas de distribuir r objetos distintos en norte casillas idénticas de modo que ninguna casilla esté vacía. Muestra esa

  • ( yo ) S ( r , 3 ) = 1 2 ( 3 r − 1 + 1 ) − 2 r − 1 ;

  • ( ii ) S ( r , r − 1 ) = ( r 2 ) .

  • Mi respuesta para ( ii ) Exactamente una caja contendrá dos objetos, mientras que todas las demás cajas contienen exactamente una caja. Basta con considerar qué dos elementos pertenecen a la misma caja, y hay ( r 2 ) maneras de hacerlo. Porque ( i ) no sé cómo hacer la prueba combinatoria. Estoy tratando de entender para poder obtener el RHS pero fallé. Cualquier ayuda es muy apreciada. Muchas gracias..

Respuestas (1)

El segundo está bien. Para el primero, asigne un color a los bloques (voy a usar r mi d b yo tu mi gramo r mi mi norte ), por lo que en cada partición está coloreando los números dentro del bloque (suponga que siempre pone 1 en bloque de color r mi d ), así que tienes 3 norte − 1 = | { ∙ ∪ ∙ ∪ ∙ } [ norte ] ∖ { 1 } | posibles colores (funciones) para los elementos restantes.

Ahora sabes que no quieres menos que 3 colores por definición, por lo que sacas cuando tienes exactamente 2 bloques 2 ∗ ( 2 norte − 1 − 2 ) + 2 = 2 norte − 2 (¿ por qué? ) también hay que sacar el estuche cuando cada elemento está coloreado con 1 , y así obtienes

3 norte − 1 − ( 2 norte − 2 ) − 1 = 3 norte − 1 − 2 norte + 2 − 1 = 3 norte − 1 − 2 norte + 1.
Ahora bien, el problema es que los colores no son importantes, es decir, si norte = 3 y tu tienes 1 2 3 es lo mismo que 1 2 3 , por lo que tiene una relación equivalente en este conjunto que produce, a saber π 1 ∼ π 2 si y si π 1 es lo mismo que π 2 hasta números verdes en π 1 son números azules en π 2 y viceversa. Entonces, si divides por la relación de equivalencia y entiendes que las clases equivalentes tienen exactamente 2 elementos, obtienes tu resultado.

Entonces, para probarlo "formalmente" tendrás una función
φ : S norte , 3 ⟶ { ∙ ∪ ∙ ∪ ∙ } [ norte − 1 ]
pero verás que la imagen va a ser una restricción en ese conjunto que te dará los números que obtuviste en el argumento.

Prueba combinatoria de recurrencia del número de Stirling de segunda clase
RespuestasAquíPolítica de privacidad1y, 0v