MathDB

Let

G

be a simple graph with vertex set V\equal{}\{0,1,2,3,\cdots ,n\plus{}1\} .

j

and j\plus{}1 are connected by an edge for

0\le j\le n

. Let

A

be a subset of

V

and

G(A)

be the induced subgraph associated with

A

. Let

O(G(A))

be number of components of

G(A)

having an odd number of vertices. Let T(p,r)\equal{}\{A\subset V \mid 0.n\plus{}1 \notin A,|A|\equal{}p,O(G(A))\equal{}2r\} for

r\le p \le 2r

. Prove That |T(p,r)|\equal{}{n\minus{}r \choose{p\minus{}r}}{n\minus{}p\plus{}1 \choose{2r\minus{}p}}.

Problem Statement