For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags?

Question

For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags ?

Let me rephrase the question by example, we have a set T{O,C} (*assume O: open tag, C: close tag). The grammar is same as for any Well formed XML Doc, for every 'O' (open tag) there must be a C (close tag) and it must not appear before its corresponding open tag.

Given maximum number of tags is 6. The possible arrangements could be

1. O,O,O,C,C,C
2. O,O,C,C,O,C
3. O,C,O,C,O,C
4. O,C,O,O,C,C etc.

So

1. How I can find the number of such possible arrangements for a given length of String/tags n.
2. How I can find the number of such possible arrangements, when a sub-string is given for string of length n.

example n = 6, sub-string : OO

1. O,O,O,C,C,C
2. O,O,O,C,C,C ( 1 & 2 can be counted as one arrangement)
3. O,O,C,C,O,C
4. O,C,O,O,C,C etc.

(* OCOCOC cannot be counted here as it doesn't have substring OO)

Thanks in advance.

Edit: The question might be better understood by taking open and close brackets. OOCC => (()) OCOCOC => ()()()

Answer 1

This answer is a slight expansion of my comment.

Enumerating correctly nested parentheses is equivalent to enumerating Dyck paths, which are paths consisting of steps $u=(1,1)$ and $d=(1,-1)$ that start and end on the horizontal axis and never go below it. So for example, the string "(()(()))" is equivalent to $uuduuddd$.

There is a relatively recent (2007) paper, "Counting strings in Dyck paths" by A. Sapounakis, I. Tasoulas, and P. Tsikouras, that addresses the question you are interested in. I have not read the paper, but they appear to have worked out the details substrings of length 4, which appears to be the state of the art. Their work is based on earlier (1999) work by Emeric Deutsch in "Dyck path enumeration". Deutsch's paper computes, among many other things, the generating function for the number of paths according to length and number of $duu$s. The constant term of this generating gives the number of paths with no $duu$'s, from which, of course, one may obtain the number of paths with at least one $duu$.

Both papers contain many references to prior work. Google Scholar may turn up more recent work on these topics.

Answer 2

What you are looking for is described by the Dyck language.The number of possible strings (or "words") of length $2n$ that can be constructed in this language, of which XML with only one tag type is an example, is given by the Catalan number $C_n$: $$C_n = \left(\begin{array}{c}2n\\n\\\end{array}\right) - \left(\begin{array}{c}2n\\n+1\\\end{array}\right)$$ For your case $2n=6 \rightarrow n = 3$, So the number of possible configurations is: $$C_3 = 5$$