Explanation of inclusion and exclusion principle formula

[hajer]

I have a problem understanding this specific formula of inclusion and exclusion. (favorite) I need to know why it is needed. and an example that uses it.

\(\displaystyle \mathbf{Lemma 1. }\, Principle\, of\, inclusion\, and\, exclusion.\)

\(\displaystyle \mbox{Given a set }\, A,\, \mbox{ let }\, f\, \mbox{ be a real valued func}\mbox{tion}\)

\(\displaystyle \mbox{defined for all sets }\, S,\, J\, \subseteq\, A.\, \)

. . .\(\displaystyle \mbox{ If }\displaystyle g(S)\, =\, \sum_{J:J\, \supseteq\, S}\, f(J)\, \)

. . . . .\(\displaystyle \displaystyle \mbox{ then }\, f(S)\, =\, \sum_{J:J\, \supseteq\, S}(-1)^{\vert J\S \vert}\, g(J).\)

 

[tkhunny]

Include Everything
Whoops! Too much. Subtract some.
Whoops! Too much. Add some back.
Whoops! Too much. Subtract some.
Whoops! Too much. Add some back.
Whoops! Too much. Subtract some.
Whoops! Too much. Add some back.
ad infinitum...

The formula is fine, but perhaps irrationally difficult to dissect.

 

[stapel]

I have a problem understanding this specific formula of inclusion and exclusion. (favorite) I need to know why it is needed. and an example that uses it.

\(\displaystyle \mathbf{Lemma 1. }\, Principle\, of\, inclusion\, and\, exclusion.\)

\(\displaystyle \mbox{Given a set }\, A,\, \mbox{ let }\, f\, \mbox{ be a real valued func}\mbox{tion}\)

\(\displaystyle \mbox{defined for all sets }\, S,\, J\, \subseteq\, A.\, \)

. . .\(\displaystyle \mbox{ If }\displaystyle g(S)\, =\, \sum_{J:J\, \supseteq\, S}\, f(J)\, \)

. . . . .\(\displaystyle \displaystyle \mbox{ then }\, f(S)\, =\, \sum_{J:J\, \supseteq\, S}(-1)^{\vert J\S \vert}\, g(J).\)

Did your textbook and instructor provide no examples? If not, then you might want to spend some time studying online lessons, which will include examples.

Or is it your homework exercise that wants you to "restate in your own words, and provide an example"?

 

[hajer]

Did your textbook and instructor provide no examples? If not, then you might want to spend some time studying online lessons, which will include examples.

Or is it your homework exercise that wants you to "restate in your own words, and provide an example"?

actually I found it in a publication related to network coding and the author used it to derive a probability equation. and it was not clear how did they used it and why. I tried to search the internet and read about this principle, I found other formulas which I understood. but this one with real valued functions I couldn't find examples of it and I didn't find sufficient information to understand it.

 

[hajer]

Include Everything
Whoops! Too much. Subtract some.
Whoops! Too much. Add some back.
Whoops! Too much. Subtract some.
Whoops! Too much. Add some back.
Whoops! Too much. Subtract some.
Whoops! Too much. Add some back.
ad infinitum...

The formula is fine, but perhaps irrationally difficult to dissect.

I actually couldn't understand how to apply the summation since J is a set not a specific point or value value.