Help a philosophy student with some math about possibilities

[Donnyj1981]

Hello, I am a philosophy student. I have no extensive training at math so please don't deluge me with formalism or terms of art off the bat. I also know that I run the risk of asking a really basic question here, but forgive me if so.

In my studies, I am often confronted with the need to enumerate the possibilities given the following circumstances.

Take, say, the ordered symbols XYZ.

Now take the square bracket, [..] which can go around any of the symbols or any ordered string of the symbols.

The rules are the square bracket must go around at least one of the symbols.

I get the following possibilities:

[X]YZ
X[Y]Z
XY[Z]
[XY]Z
X[YZ]
[XYZ]
[X][Y]Z
X[Y][Z]
[X]Y[Z]
[XY][Z]
[X][YZ}
[X][Y][Z]

Can someone please explain the general pattern or formula that allows one to calculate the number of these possibilities from an n-ly long string of symbols? So a triply long string of symbols nets you 12 possibilities.

Then there are these sets of possibilities if we open up what the square bracket can go around. In the first it can go around any symbol within a bracket and in the second it can also go around any brackets.

[X]YZ
X[Y]Z
XY[Z]
[XY]Z
[[X]Y]Z
[X[Y]]Z
X[YZ]
X[[Y]Z]
X[Y[Z]]
[XYZ]
[[X]YZ]
[X[Y]Z]
[XY[Z]]
[[XY]Z]
[[[X]Y]Z]
[[X[Y]]Z]
[X[YZ]]
[X[[Y]Z]]
[X[Y[Z]]]
[X][Y]Z
X[Y][Z]
[X]Y[Z]
[XY][Z]
[[X]Y][Z]
[X[Y]][Z]
[X][YZ]
[X][[Y]Z]
[X][Y[Z]]
[X][Y][Z]

and:

[X]YZ
X[Y]Z
XY[Z]
[XY]Z
[[X]Y]Z
[X[Y]]Z
X[YZ]
X[[Y]Z]
X[Y[Z]]
[XYZ]
[[X]YZ]
[X[Y]Z]
[XY[Z]]
[[XY]Z]
[[XY][Z]]
[[[X]Y]Z]
[[[X]Y][Z]]
[[X[Y]]Z]
[[X[Y]][Z]]
[X[YZ]]
[[X][YZ]]
[X[[Y]Z]]
[[X][[Y]Z]]
[X[Y[Z]]]
[[X][Y[Z]]]
[[X][Y]Z]
[[X]Y[Z]]
[X[Y][Z]]
[[X][Y][Z]]
[X][Y]Z
X[Y][Z]
[X]Y[Z]
[XY][Z]
[[X]Y][Z]
[X[Y]][Z]
[X][YZ]
[X][[Y]Z]
[X][Y[Z]]
[X][Y][Z]

I might have missed some of these but hopefully the pattern is reasonably clear.

[curtis95112]

Well let me tackle your first question.
I'll try a recursive solution.

First, let's say that there are k_n possibilities for a string of n symbols.

Now let's find out how many possibilities there are for a string of n+1 symbols.

Obviously there are k_n possibilities from the first n symbols. This covers all the cases in which the closing bracket is not after the n+1th symbol.
There are another n+1 possibilities in which the closing bracket is after the n+1th symbol (Because the opening bracket can start in front of any symbol, and there are n+1 symbols.)

So we get the equation: k_n+1 = n + 1 + k_n.
This in turn, n+1+k_n = n+1 + (n + k_n-1).
Going all the way down to k₁, we get k_n+1 = (n+1) + (n) + (n-1) + ... + 3 + 2 + k₁
Which is equal to k₁ + (n+1)(n+2)/2
And since k₁ = 1
k_n+1 = 1 + (n+1)(n+2)/2
And substituting in n instead of n+1
k_n = 1 + (n)(n+1)/2
Which also happens to be the sum of all integers from 1 to n, plus one.

Hopefully I haven't made any mistakes

It should be reasonably easy to solve your second problem in much the same way. Find out how the number of possibilities when you have n symbols is related to the number of possibilities when you have less symbols. Then follow the math down the chain, until you reach the trivial case of n=1.

edit to not use [math] tags

[Desiato]

The above is not correct, there are a lot more possibilities added in each step.

k_n+1:
k_n as above for the cases where there's no bracket behind the last symbol.
Now we add square brackets around the last symbol. This gives us k_n+1 (because the "no brackets at all"-case before the last symbol was not previously included) additional cases.
If we add square brackets around the last two symbols, then before those, we have another k_n-1+1 possibilities.
...
If we add square brackets around the last n symbols, then before those, we have k₁+1 possibilities.
And we can of course add square brackets around the entire string.

So we have k_n+1 = k_n + n + 1 + sum(i=1 to n) k_i

For small n, you can just compute them from k₁=1

Edit: Forgot the case [string]
Edit the second: It appears that this is http://oeis.org/A027941

[Lothar]

Obviously there are k_n possibilities from the first n symbols. This covers all the cases in which the closing bracket is not after the n+1th symbol.
There are another n+1 possibilities in which the closing bracket is after the n+1th symbol (Because the opening bracket can start in front of any symbol, and there are n+1 symbols.)

Unfortunately, here is a mistake. The opening bracket can indeed start in front of any of n + 1 symbols, but there might be more than one bracket, and hence more than n + 1 ways of having the closing bracket after the last symbol. My recursive analysis (for the first question):

Consider k_n. Indeed, the last symbol might not be enclosed in a bracket, in which case we get k_{n - 1} possibilities.

Otherwise, it is in a bracket, which could start before any of the n symbols. Suppose it starts before symbol i. Then there are i - 1 symbols before it which may be bracketed in k_{i - 1} ways or might have no brackets (1 way). In order to make this work for i = 1, we need k₀ = 0, which seems reasonable, as there must be a bracket, but a bracket must go around a symbol and there are no symbols in an empty string, hence there are no admissible bracketings of length 0. Reindexing for convenience we get

\begin{eqnarray}k_0 &=& 0\\
k_n &=& k_{n - 1} + \sum_{i = 0}^{n - 1} (k_i + 1)\end{eqnarray}

We can simplify this by pulling out the last term of the sum, noting that the remaining sum appears in the recursive expression for k_{n - 1}:

k_n = k_{n - 1} + \sum_{i = 0}^{n - 1} (k_i + 1) = 2k_{n - 1} + 1 + \sum_{i = 0}^{n - 2} (k_i + 1) = 2k_{n - 1} + 1 + k_{n - 1} - k_{n - 2}

So we get the recursive formula

\begin{eqnarray}k_0 &=& 0\\
k_1 &=& 1\\
k_n &=& 3k_{n - 1} - k_{n - 2} + 1\end{eqnarray}

This can be solved, for instance via generating functions. Define

F(x) = \sum_{n = 0}^\infty k_n x^n

Using the recurrence relation, we get

\begin{eqnarray}F(x) &=& 0 + 1x + \sum_{n = 2}^\infty (3k_{n - 1} - k_{n - 2} + 1) x^n\\
&=& x + 3x \sum_{n = 2}^\infty k_{n - 1} x^{n - 1} - x^2 \sum_{n = 2}^\infty k_{n - 2} x^{n - 2} + x^2 \sum_{n = 2}^\infty x^{n - 2}\\
&=& x + 3x F(x) - x^2 F(x) + \frac{x^2}{1 - x}\end{eqnarray}

And thus we have the closed form for F:

F(x) = \frac{x}{(1 - 3x + x^2)(1 - x)} = \frac{x}{(1 - \frac{3 + \sqrt{5}}{2}x)(1 - \frac{3 - \sqrt{5}}{2}x)(1 - x)}

Using partial fractions we get

F(x) = \frac{\frac{5 + \sqrt{5}}{10}}{1 - \frac{3 + \sqrt{5}}{2}x} + \frac{\frac{5 - \sqrt{5}}{10}}{1 - \frac{3 - \sqrt{5}}{2}x} - \frac{1}{1 - x}

Using the geometric series, we then get

F(x) = \sum_{n = 0}^\infty \left(\frac{5 + \sqrt{5}}{10} \left(\frac{3 + \sqrt{5}}{2}\right)^n + \frac{5 - \sqrt{5}}{10} \left(\frac{3 - \sqrt{5}}{2}\right)^n - 1\right)x^n

Thus

k_n = \frac{5 + \sqrt{5}}{10} \left(\frac{3 + \sqrt{5}}{2}\right)^n + \frac{5 - \sqrt{5}}{10} \left(\frac{3 - \sqrt{5}}{2}\right)^n - 1

[Talith]

k_n = \frac{5 + \sqrt{5}}{10} \left(\frac{3 + \sqrt{5}}{2}\right)^n + \frac{5 - \sqrt{5}}{10} \left(\frac{3 - \sqrt{5}}{2}\right)^n - 1

I can't help but think the golden ratio is floating around in there somewhere.

k_n = \frac{1}{5}\left(2+\Phi\right)\left(1+\Phi\right)^n+\frac{1}{5}\left(2-\frac{1}{\Phi}\right)\left(1-\frac{1}{\Phi}\right)^n-1

k_n = \frac{1}{5}(2+\Phi)\Phi^{2n}+\frac{1}{5}(2-\Phi^{-1})\Phi^{-2n}-1

looks rather forced to me.

[Donnyj1981]

I'm glad I provided an interesting point of departure for you guys, but as I said, I know little math.

Almost immediately after I typed up my problem I realized that the presentation was infelicitous as I wasn't able to articulate clearly the differing conditions between lists 1, 2, and 3.

Here's the general form of the problem:

Suppose you have a board with n ordered pegs.

You have an infinite supply of rubber bands that can go around any number of pegs but they can't exactly overlap.

what counts as a possibility is a state of the board with at least one rubber band going around some number of pegs.

How many possibilities are there:

1) given no additional restrictions?
2) given no partial overlap? (case 1 above)
3) given partial overlap so long as the partially overlapping bands each go around some peg the band they overlap with doesn't?
4) given partial overlap so long as one of the partially overlapping bands goes around all the pegs the other partially overlapping band does? (case 3 above)


Of course the equation is going to be a function from number of pegs to possibilities.

I hope that clears things up. I am gathering, however, that there is no simple equation to describe this task?

[jestingrabbit]

I can't help but think the golden ratio is floating around in there somewhere.

k_n = \frac{1}{5}\left(2+\Phi\right)\left(1+\Phi\right)^n+\frac{1}{5}\left(2-\frac{1}{\Phi}\right)\left(1-\frac{1}{\Phi}\right)^n-1

k_n = \frac{1}{5}\left(2+\Phi\right)\Phi^{2n}+\frac{1}{5}\left(2-\frac{1}{\Phi}\right)\Phi^{-2n}-1

looks rather forced to me.

1+\phi = \phi^2 and 1-\frac{1}{\phi} = \frac{1}{\phi^2} cleans it up a little.

edit: and I see you've already noticed that, simultaneously, but you'd have to agree that its starting to look a lot less forced.

[Talith]

Yeh sorry, I kept submitting as I was editting... it's starting to look a lot nicer now, although that pesky -1 breaks a nice symmetry .

[Qaanol]

Suppose you have a board with n ordered pegs. You have an infinite supply of rubber bands that can go around any number of pegs but they can't exactly overlap. what counts as a possibility is a state of the board with at least one rubber band going around some number of pegs.

Are you saying that [A (B) C] is different from [A (B] C), where the different brackets represent different rubber bands? If we allow things like [A (B] C), where the rubber bands can overlap without being nested, I think the count of possibilities will be simpler to calculate, because then it’s just a matter of counting all possible places a rubber band could go, and raising 2 to that power (and then subtracting 1 because you have ruled out the zero-rubber band case). In particular, 2^n(n-1)/2-1.

For the version that has neither nested nor overlapped bands, I expect a rather complicated formula. For the version that allows nested but not overlapped bands, I expect an even more complicated formula, which has a recursive-though-still-complicated representation in terms of the the non-nested-and-non-overlapping case.

[curtis95112]

Oh sorry, I didn't realize you could have more than one set of brackets. Reading fail.

[PM 2Ring]

k_n = \frac{1}{5}\left(2+\Phi\right)\left(1+\Phi\right)^n+\frac{1}{5}\left(2-\frac{1}{\Phi}\right)\left(1-\frac{1}{\Phi}\right)^n-1

k_n = \frac{1}{5}\Phi^3\Phi^{2n}+\frac{1}{5}\Phi^{-3}\Phi^{-2n}-1

Um, where did the Phi³ come from? Phi³ = Phi² + Phi > Phi² + 1

[Talith]

Brain fart I guess...

[Donnyj1981]

Are you saying that [A (B) C] is different from [A (B] C), where the different brackets represent different rubber bands? If we allow things like [A (B] C), where the rubber bands can overlap without being nested, I think the count of possibilities will be simpler to calculate, because then it’s just a matter of counting all possible places a rubber band could go, and raising 2 to that power (and then subtracting 1 because you have ruled out the zero-rubber band case). In particular, 2n(n-1)/2-1.

Yes they would be different possibilities. The only question, as you saw, is whether [A (B] C) is a permissible possibility - that would depend on whether overlapping bands are permitted.

So some conditions are:

1) no conditions beyond no exact overlap which is always a condition - the 'general' case, i.e. [[X]]YZ wouldn't be a possibility
2) No nesting, i.e. [[X]Y]Z wouldn't be a possibility
3) no overlap, i.e. no [X(Y]Z)
3) no nesting or overlap, i.e. neither of the above two
5) only singly nested bands, i.e. no [[[X]Y]Z]
6) only one band per nest, i.e. no [[X][Y]Z]
7) only two bands per nest, i.e. no [[X][Y][Z]]
etc.

Now let's say I allowed the bands to skip order - as in a band going around XZ. Would this be the problem of Bell's number?

[mike-l]

2 of those conditions are relatively easy:

1) No conditions, there are n(n+1)/2 choices of end points (with repetition), and you can pick any nonempty subset of those pairs, so 2^(n(n+1)/2) - 1.
4) A non nesting/non overlapping set is the same as picking an even (nonzero) number of points from n, which is the same as picking any number of points from n-1 and including n if necessary to make things even, so 2^(n-1)-1 (again eliminating the selection of no points) (This only works if bands must be around more than one peg, alternatively, you can do it as the sum of (n choose i)*B_i where B_i is the number of ways of writing i as the sum of 1s and 2s, with order mattering.)

Non-overlapping (but nesting allowed) you'll want to do recursively I think (like the posters above), and you can put restrictions on the recursion for your other restrictions.

Non-nested but overlapping allowed seems hard to me.

[Qaanol]

Now let's say I allowed the bands to skip order - as in a band going around XZ. Would this be the problem of Bell's number?

Each non-empty subset is now a valid place for a band, and there are 2ⁿ-1 non-empty subsets. In the case allowing overlap and/or nesting, there are then 2^2ⁿ-1-1 options with at least one band containing at least one element.

4) A non nesting/non overlapping set is the same as picking an even (nonzero) number of points from n, which is the same as picking any number of points from n-1 and including n if necessary to make things even, so 2^(n-1)-1 (again eliminating the selection of no points)

I do not follow the line of reasoning here. What makes you say “A non nesting/non overlapping set is the same as picking an even (nonzero) number of points from n”? Suppose n=2, so the possibilities for non-nesting/non-overlapping band placements are [A]B, A[B], [AB], [A][B], making a total of 4 options, of which 3 have exactly one band.

Suppose n=3, so the possibilities are [A]BC, A[B]C, AB[C], [AB]C, A[BC], A]B[C, [AB][C], [A][BC], A][B][C, [A][B]C, [A]B[C], A[B][C], [A][B][C], [ABC], making a total of 14 options, of which 7 have exactly one band.

[fishfry]

There seems to be some vagueness here about the rules for brackets. But if you are just talking about the different ways to group a set of objects as say "x x x", "xx x", "x xx", etc., then this is just the theory of combinatorial compositions.

http://en.wikipedia.org/wiki/Composition_(number_theory)

[mike-l]

Now let's say I allowed the bands to skip order - as in a band going around XZ. Would this be the problem of Bell's number?

Each non-empty subset is now a valid place for a band, and there are 2ⁿ-1 non-empty subsets. In the case allowing overlap and/or nesting, there are then 2^2ⁿ-1-1 options with at least one band containing at least one element.

4) A non nesting/non overlapping set is the same as picking an even (nonzero) number of points from n, which is the same as picking any number of points from n-1 and including n if necessary to make things even, so 2^(n-1)-1 (again eliminating the selection of no points)

I do not follow the line of reasoning here. What makes you say “A non nesting/non overlapping set is the same as picking an even (nonzero) number of points from n”? Suppose n=2, so the possibilities for non-nesting/non-overlapping band placements are [A]B, A[B], [AB], [A][B], making a total of 4 options, of which 3 have exactly one band.

You're right, I neglected the possibility of a band around a single element. I suppose you could first choose elements to be on their own and then sum over the sizes of subsets using my formula for bands around multiple elements, but that seems gross.

Anyway, editing the original to be correct for the other case