Número de conjunto pedido especial

Un conjunto ordenado es un conjunto tal que el orden en que aparecen los objetos en el conjunto es significativo.

Por ejemplo, (1, 2, 3) y (2, 1, 3) son dos conjuntos diferentes de números enteros ordenados.

Se dice que un conjunto ordenado de enteros es un conjunto especial si para cada elemento X del conjunto, el conjunto no contiene el elemento X+1.

Determine el número de conjuntos especiales para el número N, cuyo elemento más grande no es mayor que N.

Para N = 3, hay 5 conjuntos especiales que son (1), (2), (3), (1, 3), (3, 1).

Probé por mi cuenta contando todo el conjunto ordenado tomando la diferencia de elementos más de >=2 pero al final, observo que se cuenta para algunos de los subconjuntos de tamaño superior a >=2.

¿Alguien podría explicar esto, cómo contarlo correctamente?

Gracias de antemano.

¿Se exige que los conjuntos especiales no estén vacíos?
sí, todo el conjunto especial no debe estar vacío.
Debería editar eso en su pregunta, para aclarar las cosas.
Creo que aquí no tiene sentido un conjunto vacío, está claro en el ejemplo dado en la pregunta.
Por ejemplo, el caso norte = 3 el conjunto ∅ evidentemente satisface (vacuamente) la condición de que para cada elemento X en el conjunto el elemento X + 1 no está en el conjunto. También el conjunto está ordenado por la relación vacía.
pero aquí tengo una duda si no estamos seleccionando ningún elemento del conjunto, ¿cómo asumimos que X + 1 no está presente en el conjunto nulo? ya que no tenemos ningún elemento en el conjunto. podrías explicarlo por favor
Cualquier declaración de la forma ∀ X ∈ ∅ [ pag ] o equivalente ∀ X [ X ∈ ∅ ⟹ pag ] es cierto (no importa qué pag estados). Para entender esto obsérvese que su negación, es decir, ∃ X [ X ∈ ∅ ∧ ¬ pag ] es falso porque X ∈ ∅ es falso para cada X .

Respuestas (2)

Supongamos que hay metro elementos en un conjunto especial. parece claro que metro ≤ ⌊ ( norte + 1 ) / 2 ⌋ . Un resultado bien conocido en combinatoria (ver más abajo) es que hay ( norte − metro + 1 metro ) subconjuntos de 1 , 2 , 3 , … , norte de tamaño metro sin elementos adyacentes. Cada uno de estos juegos se puede pedir en metro ! maneras. Así que el número total de conjuntos especiales es

∑ metro = 1 ⌊ ( norte + 1 ) / 2 ⌋ ( norte − metro + 1 metro ) metro !
Los primeros valores, por 1 ≤ norte ≤ 10 , son 1 , 2 , 5 , 10 , 23 , 50 , 121 , 290 , 755 , 1978 . Hice una búsqueda en OEIS sin encontrar esta secuencia.

Para aquellos que no están familiarizados con la fórmula para el número de formas de seleccionar k elementos no adyacentes de n, aquí hay una derivación. Supongamos que queremos seleccionar k enteros no adyacentes a 1 , a 2 , a 3 , … , a k del conjunto { 1 , 2 , 3 , … , norte } . Para que las opciones no sean adyacentes, debemos tener 1 ≤ a 1 , a 1 < a 2 − 1 , a 2 < a 3 − 1 , a 3 < a 4 − 1 , ..., a k − 1 < a k − 1 , y a k ≤ norte . Un conjunto equivalente de desigualdades es

1 ≤ a 1 < a 2 − 1 < a 3 − 2 < a 4 − 3 < ⋯ < a k − k + 1 ≤ norte − k + 1
Así que podemos elegir de manera equivalente los valores a 1 , a 2 − 1 , a 3 − 2 , a 4 − 3 , … , a k − k + 1 de { 1 , 2 , 3 , … , norte − k + 1 } , y esto se puede hacer en ( norte − k + 1 k ) maneras.

Un método iterativo

El número de juegos especiales para norte es 1 menor que la suma de los elementos de la norte + 1 columna de la matriz METRO . por ejemplo, para norte = 4 el número de juegos especiales es 4 + 6 = 10 .

METRO = ( 1 1 1 1 1 1 1 1 . . . 0 1 2 3 4 5 6 7 . . . 0 0 0 2 6 12 20 30 . . . 0 0 0 0 0 6 24 60 . . . 0 0 0 0 0 0 0 24 . . . . . . . . . . . . . . . . . . . . . . )

La matriz se calcula mediante la fórmula

metro i + 1 , j + 2 = metro i + 1 , j + 1 + i metro i , j

y es fácil de implementar en Excel. Esta relación se demuestra de la siguiente manera.

El elemento metro i + 1 , j + 2 cuenta el número de juegos especiales para j + 1 de tamaño i . Considere estos conjuntos según contengan o no j + 1 .

no contiene j + 1 . Hay metro i + 1 , j + 1 de estos.

que contiene j + 1 . Tal conjunto es uno de los metro i , j conjuntos para j − 1 de tamaño i − 1 con j + 1 añadido en uno de j posiciones posibles.

Número de conjunto pedido especial
RespuestasAquíPolítica de privacidad1y, 0v