Olimpiada India IMO Training Camp 2009 Problema 12

Sea $ G$ un grafo simple con conjunto de vértices $ V=\{0,1,2,3,\cdots ,n+1\}$. $ j$ y $ j+1$ están conectados por una arista para $ 0\le j\le n$. Sea $ A$ un subconjunto de $ V$ y $ G(A)$ el subgrafo inducido asociado con $ A$. Sea $ O(G(A))$ el número de componentes de $ G(A)$ que tienen un número impar de vértices. Sea $ T(p,r)=\{A\subset V \mid 0.n+1 \notin A,|A|=p,O(G(A))=2r\}$ para $ r\le p \le 2r$. Demuestra que $ |T(p,r)|={n-r \choose{p-r}}{n-p+1 \choose{2r-p}}$.

5

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados