## Help a philosophy student with some math about possibilities

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

### Help a philosophy student with some math about possibilities

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.
Donnyj1981

Posts: 3
Joined: Fri Jan 13, 2012 2:34 am UTC

### Re: Help a philosophy student with some math about possibili

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

First, let's say that there are kn 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: kn+1 = n + 1 + kn.
This in turn, n+1+kn = n+1 + (n + kn-1).
Going all the way down to k1, we get kn+1 = (n+1) + (n) + (n-1) + ... + 3 + 2 + k1
Which is equal to k1 + (n+1)(n+2)/2
And since k1 = 1
kn+1 = 1 + (n+1)(n+2)/2
And substituting in n instead of n+1
kn = 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
addams wrote: There is no such thing as an Unbiased Jury.
curtis95112

Posts: 519
Joined: Thu Jan 27, 2011 5:23 pm UTC

### Re: Help a philosophy student with some math about possibili

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

kn+1:
kn 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 kn+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 kn-1+1 possibilities.
...
If we add square brackets around the last n symbols, then before those, we have k1+1 possibilities.
And we can of course add square brackets around the entire string.

So we have kn+1 = kn + n + 1 + sum(i=1 to n) ki

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

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

Posts: 42
Joined: Fri Nov 25, 2011 11:15 pm UTC

### Re: Help a philosophy student with some math about possibili

curtis95112 wrote: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 kn. Indeed, the last symbol might not be enclosed in a bracket, in which case we get kn - 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 ki - 1 ways or might have no brackets (1 way). In order to make this work for i = 1, we need k0 = 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 kn - 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
Always program as if the person who will be maintaining your program is a violent psychopath that knows where you live.

If you're not part of the solution, you're part of the precipitate.

1+1=3 for large values of 1.

Lothar

Posts: 60
Joined: Sat Dec 23, 2006 11:37 am UTC
Location: Berlin, Germany

### Re: Help a philosophy student with some math about possibili

Lothar wrote:
curtis95112 wrote:
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.
Last edited by Talith on Sat Jan 14, 2012 4:31 am UTC, edited 5 times in total.

Talith
Proved the Goldbach Conjecture

Posts: 844
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

### Re: Help a philosophy student with some math about possibili

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:

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?
Donnyj1981

Posts: 3
Joined: Fri Jan 13, 2012 2:34 am UTC

### Re: Help a philosophy student with some math about possibili

Talith wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5187
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Help a philosophy student with some math about possibili

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 .

Talith
Proved the Goldbach Conjecture

Posts: 844
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

### Re: Help a philosophy student with some math about possibili

Donnyj1981 wrote: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, 2n(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.
Small Government Liberal

Qaanol

Posts: 2241
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Help a philosophy student with some math about possibili

Oh sorry, I didn't realize you could have more than one set of brackets. Reading fail.
addams wrote: There is no such thing as an Unbiased Jury.
curtis95112

Posts: 519
Joined: Thu Jan 27, 2011 5:23 pm UTC

### Re: Help a philosophy student with some math about possibili

Talith wrote:
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

PM 2Ring

Posts: 2589
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

### Re: Help a philosophy student with some math about possibili

Brain fart I guess...

Talith
Proved the Goldbach Conjecture

Posts: 844
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

### Re: Help a philosophy student with some math about possibili

Qaanol wrote: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?
Donnyj1981

Posts: 3
Joined: Fri Jan 13, 2012 2:34 am UTC

### Re: Help a philosophy student with some math about possibili

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.
Last edited by mike-l on Sun Jan 15, 2012 12:17 am UTC, edited 1 time in total.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2513
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Help a philosophy student with some math about possibili

Donnyj1981 wrote: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 2n-1 non-empty subsets. In the case allowing overlap and/or nesting, there are then 22ⁿ-1-1 options with at least one band containing at least one element.

mike-l wrote: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.
Small Government Liberal

Qaanol

Posts: 2241
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Help a philosophy student with some math about possibili

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)
fishfry

Posts: 91
Joined: Wed Dec 21, 2011 6:25 am UTC

### Re: Help a philosophy student with some math about possibili

Qaanol wrote:
Donnyj1981 wrote: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 2n-1 non-empty subsets. In the case allowing overlap and/or nesting, there are then 22ⁿ-1-1 options with at least one band containing at least one element.

mike-l wrote: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
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2513
Joined: Tue Sep 04, 2007 2:16 am UTC