Una versión generalizada del principio de exclusión de inclusión usando una identidad binomial

Question

Una versión generalizada del principio de exclusión de inclusión usando una identidad binomial

Matemáticas
combinatoria
exclusión inclusión
Matemáticas discretas
funciones generadoras

mateo7k5b

Estoy tratando de encontrar una manera de derivar un principio de exclusión de inclusión generalizado para la cantidad de elementos que se encuentran en la intersección de al menos $s$ conjuntos de $A_1,A_2,...,A_n$ usando esta identidad:

dejar $k$ y $s$ sean enteros positivos y sean $k\ge s\ge 1$

\sum_{i = 0}^{k - s} (- 1)^{i} (\binom{s - 1 + i}{s - 1}) (\binom{k}{s + i}) = 1

$\sum_{i=0}^{k-s} (-1)^i{s-1+i \choose s-1}{k \choose s+i} = 1$

Vengo de esta pregunta: prueba de que la suma binomial es igual a 1

De la suma se desprende que lo que determina si sumamos o restamos el producto del coeficiente binomial es si tiene un número par o impar de elementos y se puede aplicar a cada subconjunto de $s.

Pero no entiendo muy bien el concepto de la forma generalizada del principio de exclusión de inclusión.

Respuestas (1)

Una versión generalizada del principio de exclusión de inclusión usando una identidad binomial

robarjohn · Answer 1

Para un teorema de inclusión-exclusión generalizado, vea esta respuesta . En esa respuesta, el Teorema dice que el número de artículos en exactamente $k$ de los conjuntos es

\sum_{j = 0}^{metro} (- 1)^{j - k} (\binom{j}{k}) norte (j)

$\sum_{j=0}^m(-1)^{j-k}\binom{j}{k}N(j)$ El corolario 2 dice que el número de artículos en al menos

k

$k$ de los conjuntos es

\sum_{j = k}^{metro} (- 1)^{j - k} (\binom{j - 1}{j - k}) norte (j)

$\bbox[5px,border:2px solid #C0A000]{\sum_{j=k}^m(-1)^{j-k}\binom{j-1}{j-k}N(j)}$ dónde

(\binom{- 1}{n}) =

$\binom{-1}{n}=$

(- 1)^{n} (\binom{n}{n})

$(-1)^n\binom{n}{n}$

= (- 1)^{n}

$=(-1)^n$

[n \geq 0]

$[n\ge0]$ .

Prueba de identidad

Si $k\ge s$ , entonces

\begin{aligned} (1) & \sum_{i = 0}^{k - s} (- 1)^{i} (\binom{s - 1 + i}{s - 1}) (\binom{k}{s + i}) & = \sum_{i = 0}^{k - s} (- 1)^{i} (\binom{s - 1 + i}{i}) (\binom{k}{k - s - i}) \\ (2) & = \sum_{i = 0}^{k - s} (\binom{- s}{i}) (\binom{k}{k - s - i}) \\ (3) & = (\binom{k - s}{k - s}) \\ (4) & = 1 \end{aligned}

$\begin{align} \sum_{i=0}^{k-s}(-1)^i\binom{s-1+i}{s-1}\binom{k}{s+i} &=\sum_{i=0}^{k-s}(-1)^i\binom{s-1+i}{i}\binom{k}{k-s-i}\tag{1}\\ &=\sum_{i=0}^{k-s}\binom{-s}{i}\binom{k}{k-s-i}\tag{2}\\ &=\binom{k-s}{k-s}\tag{3}\\[8pt] &=1\tag{4} \end{align}$ Explicación:

(1)

$(1)$ :

(\binom{n}{k}) = (\binom{n}{n - k})

$\binom{n}{k}=\binom{n}{n-k}$ para

n \geq 0

$n\ge0$ y

n \in Z

$n\in\mathbb{Z}$

(2)

$(2)$ :

(\binom{- n}{k}) = (- 1)^{k} (\binom{n + k - 1}{k})

$\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}$

(3)

$(3)$ : Identidad de Vandermonde

(4)

$(4)$ :

(\binom{n}{n}) = 1

$\binom{n}{n}=1$ para

n \geq 0

$n\ge0$ y

n \in Z

$n\in\mathbb{Z}$

Una versión generalizada del principio de exclusión de inclusión usando una identidad binomial

mateo7k5b

Respuestas (1)

robarjohn

¿Inclusión/exclusión, al menos y exactamente arreglos?

nnn invitados, cada invitado trae un premio, ¿de cuántas maneras se pueden repartir los premios para que nadie reciba el premio que trajeron?

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

4 parejas y 4 personas solas sentadas en 3 mesas redondas

Sobre el número de Stirling de segunda clase

Parejas sentadas en una mesa redonda

Una pregunta relacionada con el teorema del binomio de Newton en la que no puedo pensar

Ordenar objetos distintos en líneas y un círculo.

sentar parejas casadas alrededor de una mesa circular

Extraer coeficientes para resolver la relación de recurrencia