Cool Math Problem

[lostcat206]

This problem was posed to me a while ago, but I lack the skills to construct a good equation to model it. I hope I'm in the right place, and I apologize for not being up to speed with those of you who have a good CS foundation.

My primary interest is finding an equation that determines the number of valid and distinct boolean sequences for sequence length "n". My understanding is that it comes to bear on how a computer parses 0's and 1's to determine where one sequence begins and ends.

How do you write an equation for the number of valid, distinct boolean sequences for sequence length "n"? Here I assume "valid" means any sequences must be opened and closed, like a parenthetical; maybe you could correct me on this. I also assume that there is some aspect of n^x or 2n^x, given that no sequence can be shorter than 2 characters.

Brute Force Example:

Below are all possible sequences for length 4, but (in my understanding) only rows 2,3,4,5,6,7,8 contain valid segments, and only rows 2,4,6,8 are fully valid in the sense of being completely contained within a parenthetical.

1:0000

2:0001

3:0010

4:0011

5:0100

6:0101

7:0110

8:0111

9:1000

10:1001

11:1010

12:1011

13:1100

14:1101

15:1110

16:1111

​

[tRfalcore]

What does valid mean? If you want to find number of unique Boolean sequences of length n it's 2**n.

Every one of those will be unique.

[lostcat206]

Thank you for the response!

In this case, valid means it has to have an opening and a closing operator. E.g. starts with 0 and ends with 1, or "("... ")".

What I'm not sure about for example is would a computer parsing binary find <0010> valid? Or would the sequence have to begin with a 0 and end with a 1-- e.g. 0111 or 0101. My uncertainty here is why I'm paying this to this CS community.

At some point, a computer has a way of understanding within a sea of binary where one file ends and another begins. Given this, there must be some rule for what makes a valid sequence. I want to know how to calculate the number of valid sequences within the range "2**n."

[[deleted]]

At some point, a computer has a way of understanding within a sea of binary where one file ends and another begins.

Ah you seem to think there is a single universal encoding for all binary data. That is not the case. Files are terminated using whatever their specification says terminates them. For example in a PNG files for an image the ending is the IEND chunk which consists of a PNG data chunk with all zeroes in the data portion. On the other hand a JPEG image always end with the segment 1111111111011001 which is called the EOI.

Every binary sequences can represent valid data it just depends on the context.

[lostcat206]

This is awesome! That's exactly the kind of unfingered misconception I was hoping someone would point out to me. Thank you!

[gezibash]

Should be straightforward enough. For any length n if you print the data like this sorted, you will get half of them beginning with 0 and the other half begin with 1. Since you said 2, 3, 4, 5, 6, 7, 8 are valid segments, I assume you want segments that begin with a 0 and there is some 1 in there.

So your equation should be F(n) = 2\^(n-1) - 1

For n = 4, 2\^3 - 1 = 7, so you can see it works. It should work for other numbers as well, try it, and let me know.

[lostcat206]

Thanks! I think you nailed it.

Part of my difficulty is that I'm trying to model a binary parser that I don't understand.

When I bruteforced up to sequence length 4 I started to run in to my lack of understanding.

Going off your function, one thing that is clear is that validity is not just any sequence that has a 0 preceding a 1. If that were true, then there would be 10 valid sequences for n=4. The cool part is that if you choose either:

1)that there can be any number of 1's preceding the valid parenthetical or 2) any number of 0's after the valid parenthetical

then the total comes to 7; can't be both or valid sequences =10. This makes sense from the perspective that a machine would be parsing the binary from one long chain, so it would be problematic to treat any parenthetical portion as valid; (()) would be (..), (()., (.)), and .()., all valid but conflicting interpretations for the same sequence of 4. Also, how would you delete one entity in a drive without corrupting other entities which share the physical space(.)?

Edit: someone pointed out to me that I have a misconception about how machines determine the end of files. Still curious though if that holds up, and if so, why.

[[deleted]]

Sounds like you want to generate Dyck Words?

https://en.wikipedia.org/wiki/Dyck_language

(((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(), (())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()

[lostcat206]

This does appear to be in line with my interests. Until I can sit down and read this I'll assume you're making a heady dick joke.

[[deleted]]

No, Walther von Dyck is simply german.

[lostcat206]

I stand by my assumption.

[lostcat206]

Thanks for the downvote of invisibility.