Thanks for the answer. Is an alternate approach possible, that is based on finding without having a count of first few cases. I mean that the above approach seems like induction, as generates a formula based on few initial cases. I hence request a formula that is based on something like my approach.

Please elaborate your last comment, as am unable to understand how over-counting is possible. I mean that the case for $5$ consecutive ones is different from any case for $4$ consecutive ones, as on either side of $4$ consecutive ones there should be either nothing (as the block occurs in a corner) or a $0$; while $5$ consecutive ones is a different case.

Example if I understand definition of $A_i$ correctly. $11111000 \in A_1 \cap A_2$

@SiongThyeGoh Am confused as to how the bit string $11111000$ can be in both categories. For me, the case $11111000$ cannot occur in for the case of $4$ consecutive bits' block. Please elaborate it, as I feel you mean by $A_1$ the case for $4$ consecutive $1$s; & by $A_2$ the case for $5$ consecutive $1$s.

$A_i$ has $1$ starting from position $i$, it is also possible to have $1$ at position $i-1$. $11111000$ has $5$ consecutive $1$. It is in $A_1$ since starting from position $1$, there are $5$ consecutive $1$'s. It is in $A_2$ since starting from position $2$, there are $4$ consecutive $1$'s.

@SiongThyeGoh I am confused even more. May be, am unable to grasp the crux of the author's comment at all, which talks of $A_i$. So, sorry cannot follow your comment. May be need big help to understand, so request chat.

Please accede to my request for chat.

hmm... I didn't receive any prompt for chat.

first, need to get the definition consistent I think

Sorry for that. In future, would send prompt too.

from my understanding, which could be wrong, $A_i$ is the collection of bit strings with the property that from position $i$ to position $i+1$, they are all $1$.

there are no restrictions in other positions

The author has seemingly taken the approach of taking $5$ positions, i.e. $4$ consecutive $1$ s as one position & $4$ other positions.

So, a total of $5=4+1$ positions.

I think he meant to define $A_1, A_2, A_3, A_4, A_5$

where the $i$ in $A_i$ denotes the starting position

Yes, with each having a different start position for the block of four consective $1$s.

He states that over-count occurs when more than $4$ consecutive $1$s occur.

$A_i$ are sets where position $i, i+1, i+2, i+3$ has $1$.

hence you should be able to check that $11111000$ is in $A_1$ and in $A_2$.

yes, a block of four $1$s

$11111000$ is in $A_1$ because $\color{blue}{1111}1000$

$11111000$ is in $A_2$ because $1\color{blue}{1111}000$.

then it is clearer if the approach is taken further to how to get complete solution of $48$

while it's possible to do something ... it is cumbersome

for this particular question there are properties like $|A_i \cap A_j | = 2^{4-\max(i,j)+\min(i,j)}$ to simplify the working but still seems too troublesome for me.

his current answer can be generalized to other similar questions

Cannot get how to reach the formula $|A_i \cap A_j | = 2^{4-\max(i,j)+\min(i,j)}$, as can only consider one case for $i=1, j=2$. For the above case $\max(i,j) = 2, \min(i,j)=1$. But, this translates to $|A_i \cap A_j | = 2^{4-\max(i,j)+\min(i,j)} = 2^3 = 8$ ways. I request those eight cases, if you have followed the approach of taking an actual set of examples' intersection.

$11111xyz$

also i could be wrong, that is just my intuiton of a possible simplification

but yup, think it's still too troublesome

I hope you mean that there are eight intersections for the fifth position between $1111axyz$ & $11111xyz$, with $a=1$, i.e. $a000, a001, a010, a011, a100, a101, a110, a111$. But, how it gets with $A_i, i = \{1,2,3,4,5\}$ is not clear.

Sorry, you have meant intersectiion between positions $A_1, A_2$ for the same (four) $1$ bits.

but, how the formula is derived is not clear

i just observe that take any two $A_i$, the intersection is non-empty

for this very special example

then observe where must the mandatory $1$ appears

still the computation seems high

yes, as even if $i=1, j=5$ then still have intersections. But would (for complete confidence's sake) request you to provide for the case of $i=1, j=5$ that includes all intersections.

11111111

but, how you arrived at this beautiful formula?

suppose i< j, then the position of i are from i to j+3

then count other places that are not fixed yet

but the workload still seems very high and it's like an exercise that just get u busy

not clear how the position of $i$ is from $i$ to $j+3$

if an element is in $A_i$ which positions we know for sure it must take value $1$?

$i$th to $i+3$

but $i+3$ is different from $j+3$

the element is also in $A_j$

not clear, about your last line that restates that $i+3 = j+3$

I am not claiming that $i+3=j+3$

the element is in $A_i \cap A_j$ we let $j> i$.

whcih positions must take value $1$?

$i$th to $i+3$

and $j$th to $j+3$

yup, also for this particular question, the consecutive block of $1$ with lenght at least $4$ must be connected.

I hope by 'connected' you mean 'common values'

such two blocks are not separated by a $0$.

also i have included a python code

but yup, the computationa would just involved lots of geometric series ...

so you state from $i$ to $j+3$, which in extreme means $i=1, j+3=8$. Please give link for the code.

it's in the original post

The formula is derivable seemingly by : max. possible intersections of $A_i, A_j = 2^4$, and

positions that must take value $1$ are from $i$ to $j+3$, there are $j-i+4$ of them

the other positions are free

not clear about the value $j-i+4$ except that it is the max. value.

i.e. when $i=1, j=5$

Assume $i<j$, position $i, i+1, i+2, i+3, j, j+1, j+2, j+3$ are having value $1$ right

yes, for the case $i=1, j=5$

u can also verify for the other values

Please pursue my approach, that there are $2^4$ max. intersections. This max. will decrease to $2^\{4- ....\}$ for $j>i$.

need to fill in the blanks by (j-i)

but am unable to

the further $i$ and $j$ are apart, the less freedom we have

if we reduce $j$ by $1$, our free bit grows by $1$.

if we increase $i$ by $1$, our free bit grows by $1$ too

then this formula is independent of $n=8$

any value of $n$ suffices

only $i,j,4$ matter

nope

if $n=9$, it is possible to have $111101111$

I am taking advantage of $n=8$ here and the required block size is at least $4$.

My method assumes there are no gap between two blocks

so, this approach does not work when $i+j+(block size)\lt n$

should be, brain a bit tired to judge now

to have no gap, i think i need i + blocksize >=j

yes

I changed code to codeskulptor.org/#user45_yECz4uMAGS_1.py, but am still unable to understand the reason why the program is designed such.

I am trying to compute the cardinality of the intersection

Please elaborate the function of each of 3 blocks of code

Added explaination in the original post

it's just inclusion exclusion

Request even more elaboration (in answer) as to (i) why $A_i\cap A_j\cap A_k = ....$, (ii) how the inclusion exclusion formula is working, by expln. of each term in it

u mean why $A_1 \cap A_2 \cap A_3 = A_1 \cap A_3$?

I was referring to $A_i \cap A_j \cap A_k = A_{\max(i,j,k)} \cap A_{\min(i,j,k)}$, but your last response (I hope is not stated in answer) also needs elaboration.

try to understand $A_1 \cap A_2 \cap A_3 = A_1 \cap A_3$ first

write down the index where they must take value $1$.

$i=1,2,5,6$ as a must

(1,2,3,4)(2,3,4,5)(3,4,5,6) that is 1,2,3,4,5,6

and we don't really need the middle part

it is due to for this particular example, there is no gap between two large blocks

Please help with the second part (ii) of my earlier request regarding 'how the inclusion-exclusion principle is applying'

we want to compute the union right

of different cases : but which cases?

$A_i$

why need nested loops (i.e. summations)

those summations are from inclusion exclusion right

not clear about the theory here (i.e., of how the terms correspond to logical terms by inclusion-exclusion)

write down inclusion exclusion?

(all possible cases in the universe (including duplicities)) - (intersection of two at a time, for all possible pairs) + (intersection of three at a time, for all possble triplets) -(slrly., if pair of four is possible) + (slrly., if pair of five is possible)

yup, that's why the summation

there could be some simplification due to the symmetric of the problem... but i don't see it yet

yes, first the sign alternates from +, - , +,....

second the pairing increase by a factor of 1 each time

that gives the form of the generalized formula, as also given everywhere

But, in your formula the upper limit is decreasing successively, which is not clear to me

I am just describing i<j<k

if there are more variables, the less values $i$ can take

also, the exponent terms ignore the middle terms

we have argued that we can drop the middle term

but something to think about, how many for loops did i use, why don't I just enumerate things, is inclusion exclusion the right tool

if you could give some example & more details in the answer . I have modified code to : codeskulptor.org/#user45_yECz4uMAGS_2.py; but still confuses as cannot form a link

which part?

the formula part: (i) why index limits' decrease, (ii) significance of decrease by taking an example - of the nested loops (summation), & (iii) their increasing levels corresponding to higher pairings in the I-E formula.

can u describe $1 \le i < j<k \le 5$?

what are all the possible tuple

what are the values that $i$ can take

what about $1 \le i < j \le 5$, what are the values that $i$ can take?

$i = \{ 1, 2,3,4 \}$

$j=i+1$

should I add more?

which part did u describe

the first or the second?

second

try the first and see the difference

the first part's answer is : $i = \{1,2,3\}$

$j=i+1, k=j+1$

yup, so u can see the value for $i$ is less right

the difference should enable me to see that the more nested nested the pairings are, it is logical that the limits decrease for the 'upper side' for indexes from left-to-right. Also, that the more nestings correspond to higher level of pairings - in a logical (with example) manner. I can put an example, but still fail to see that higher nesting == more level of pairings

i don't get your doubt

an example is already given my last modification to the code. But, I fail to see why the smaller upper limit for indexes (from left to right) corresponds to higher level of pairings(in the Venn-diagram) for applying the I-E principle.

hmmm

maybe i will think of another way rather than using python

But, I do not think that new way could be by desmos, might be by some other way to visualize; or even by some details only.

desmos is a software ....

what is ur doubt again??

I fail to see why the smaller upper limit for indexes (from left to right) corresponds to higher level of pairings(in the Venn-diagram) for applying the I-E principle.

ok, so it has nothing to do with the question

but rather a problem with I-E

when u have more variables upper bounding u

u can only take less values

u need to leave space for those variables that are bigger than u

But, how the I-E principle is implemented that way - is not clear still. Better have a number line with positive x-axis part showing the elements from $1$ to $8$. Then, how the intervals for $i$ need be decreased for higher level of pairings. You stated that the difference between the 'first example' & 'second example' shows the reason. But, why have $i \lt j \lt k \lt l$ is not clear, why not $i \le j \le k \le l$?

....

u want to intersect indices that are different

not the same

to get exactly $4$ terms, we make sure the $4$ indices are different

Please elaborate with a small example (n=8, block size =4) as already there.

forget about this example

the problem is u don't get I-E

can u write down I-E for $3$ sets?

let the sets be having cardinalities $A, B, C$, then : $A + B + C - A\cap B - A\cap C - C\cap B + A\cap B \cap C$

$A+B+C$ is the universe with duplicates

notation wise a bit strange but i will skip it for now

notice that for the last term

u wrote $A\cap B\cap C$ and not $A \cap A \cap C$ or $A \cap B \cap B$.

yes, but still need a better way. might be, number line helps. might be not, just a guess.

hmmm ... so u just consider a few values that u can take

consider all possiblities

then, it is a smaller/better way to take the value of $n = 4$, block size $=3$. I would enumerate all $2^4 =16$ cases, & try to see how non-overlapping indices are needed.

u should really forget about this question for now

and focus on undertanding I-E

then please help by goading

???

I meant that cannot learn by book, or other literature seemingly. Need guidance by you.

huh

i dunno how to teach

but i just found out ur I-E is not that correct

hmmm

I know this principle for many many years, but still am not clear on it

rather than $A, B, C$ try $A_1, A_2, A_3$

try to write down and see that they are non-repeating in a term

let the sets be $A_1, A_2, A_3$ with cardinalities $|A_1|, |A_2|, |A_3| $, then : $|A_1| + |A_2| + |A_3| - |A_1|\cap |A_2| - |A_1|\cap |A_3| - |A_3|\cap |A_2| + |A_1|\cap |A_2| \cap |A_3|$

$\cap $ is a binary operator between sets

not cardinaility

sorry, messed it all. There should be elements involved not the cardnality of the sets

let the sets be $A_1, A_2, A_3$ with cardinalities $|A_1|, |A_2|, |A_3| $, then : $A_1 + A_2 + A_3 - A_1\cap A_2 - A_1\cap A_3 - A_3\cap A_2 + A_1\cap A_2 \cap A_3$

what does addition of sets mean

btw, i need to go out to run some errants

the common elements are not repeated, others are added up to the combined set

for the case of $n=4$, block size $=2$, the $A_1 = \{1100, 1110, 1111\}, A_2 = \{0110, 0111, 1110, 1111\}$

$A_3 = \{0011\}.

Sorry, $A_1 = \{1100, 1101, 1110, 1111\}, A_3 = \{0011, 0111, 1011, 1111\}. Now $A_1\cap A_2 = \{1110, 1111\}, A_1\cap A_3 = \{1111\}, A_2 \cap A_3 = \{1111\},

having no sound is a big issue for me

sorry, $A_2 \cap A_3 = \{0111, 1111\}$

yup

yes

please see my last example

with $n=4, block size $=2$. There are $3$ groupings of $2$ bits possible.

seems fine

$A_1 = \{1100, 1101, 1110, 1111\}, A_3 = \{0110, 0111, 1110, 1111\}, A_3 = \{0011, 0111, 1011, 1111\}, A_1\cap A_2 = \{1110, 1111\}, A_1\cap A_3 = \{1111\}, A_2 \cap A_3 = \{1111, O111\}$

seems fine

\begin{align}\left| \bigcup_{i=1}^3 A_i\right|&=\sum_{i=1}^32^3- \sum_{i=1}^2 \sum_{j=i+1}^32^{3-j+i} + \sum_{i=1}^1 \sum_{j=i+1}^2\sum_{k=j+1}^32^{3-k+i}-1\\& \end{align}

please vet the last response of mine

if could do the last response's equivalent by using the set of $16$ elements, may be could understand the application of I-E principle better.

$|A_i|=4$

also i updated my answer to use less for loops

but that's not a big issue.... u should not spend too much time on such stuff

if could see a link between my last response & how I-E principle is applied with the help of the small set of $16$ elements

$|A_i|=4$, the first term makes no sense

sorry for that, each part contributes the same number of $4$ elements

\begin{align}\left| \bigcup_{i=1}^3 A_i\right|&=\sum_{i=1}^32^2- \sum_{i=1}^2 \sum_{j=i+1}^32^{2-j+i} + \sum_{i=1}^1 \sum_{j=i+1}^2\sum_{k=j+1}^32^{2-k+i}-1\\& \end{align}

so can u check if it si correct

?

I am unable, as need to draw a link between the terms and the set elements

You can modify the code to verify if the result is correct right?

or use the other solution to check if the number match?

\begin{align}\left| \bigcup_{i=1}^3 A_i\right|&=\sum_{i=1}^32^2- \sum_{i=1}^2 \sum_{j=i+1}^32^{2-j+i} + \sum_{i=1}^1 \sum_{j=i+1}^2\sum_{k=j+1}^32^{2-k+i}-1\\&=\sum_{i=1}^32^2- (2^{1} + 2^0 + 2^{1}) + (2^0) -1\\&=2^2\cdot 3- (2^{1} + 2^0 + 2^{1}) + (2^0)-1\\&=12 - (5) + 1 -1 = 7 \end{align}

Now need to list individually the elements that are in each term

your program (modified) does the same too

but I request a further modification over my last one - that clearly shows the elements in each term

??

the last modified version is codeskulptor.org/#user45_yECz4uMAGS_7.py

i have too many screens open now with codes... maybe i can edit later

just change the limit isn't it?

range(5) to range(3)?

just change 4-j+i to 2-j+i

codeskulptor.org/#user45_yECz4uMAGS_9.py

but still face issues in linking elements ; say for the first loop have : $\{(0,1), (0,2), (1,2)\}$.

request interpretation of this set of 3 elements

my interpretation is that the three pairwise intersections between the 3 sets have these common elements

i need to stare at the other screen for a while

the last set $\{(0,1,2)\}$ gives the elements common to all three sets

unable to get sync between the set with numbers, as there should be only element in common between $A_1$ & $A_3$. $A_1 = \{1100, 1101, 1110, 1111\}, A_3 = \{0110, 0111, 1110, 1111\}, A_3 = \{0011, 0111, 1011, 1111\}, A_1\cap A_2 = \{1110, 1111\}, A_1\cap A_3 = \{1111\}, A_2 \cap A_3 = \{1111, O111\}$

i don't understand your question

is it a maths prob or a programming prob?

there are sets of pairwise values, each having 2 terms

it is a maths problem

but intersection between $A_1, A_3$ should yield one element not two

sorry, it is a programming issue

the math is clear

try to figure out for a while

i m debugging another thing too =/

so, is it just listing the intersecting sets with no mention of the intersecting elements

the program is not capable of listing elements, just lists the cardinalities with the intersecting set

please help by modifying ( or better a new one) to get a program that lists the intersecting elements also.

why would listing those things make u learn anything?

please.... I hope that at least would make me better at programming. it is beyound my thought how to do it

so u want a program that list $A_i$? and their intersection?

yes, please.

py3.codeskulptor.org/#user302_kT0JJxnA85dzpc1.py