What equation or pattern applies to this kind of combinatorial possiblity?

[mcintyw2]

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 string of 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.Update***

I would also like to know about the pattern that would get one the following set of possibilities:

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

 

[Stephen Tashi]

I don't recognize your problem as one that has a simple formula. I think it would be possible to write a short computer program to count the possibilities.

We need to define precisely what it would mean to extend the problem to a string of n symbols. My guess at what you mean by the first type of problem is:

In how many ways can pairs of non-nested pairs brackets be placed around the subsequences of a string of n distinct symbols such that at most n pairs of brackets are used?

How to generalize your second type of problem to a string of n symbols is less clear. Do we say that the maximum level of nesting that is allowed is n? Are there still at most n pairs of brackets allowed?

 

[Kindayr]

If order didn't matter, I'd look up Bell numbers, they arise as a way to count the amount of partitions there are to any given set.

Since order does matter, you know that your number you will want to count should be less than this.

I hope that helps.

 

[mcintyw2]

Thank you for the helpful replies. My initial presentation was vague, as the first commenter pointed out. I also posted this over at http://forums.xkcd.com/viewtopic.php?f=17&t=79427 and have presented my clarifications of the parameters of the problem over there, if any are interested.

 

[awkward]

Although not an exact match to your problem, you might find the Catalan numbers interesting. The nth Catalan number counts the number of ways of completely parenthesizing a string of n symbols (and a huge list of equivalent problems).

http://en.wikipedia.org/wiki/Catalan_number