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

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)

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

• Is each open / close individual? or are all O's and C's equal? If they are all individual, then you also need to specify the number of possible sets. – nbubis Jan 1 '13 at 10:38
• For the former, the answer is the Catalan numbers: en.wikipedia.org/wiki/Catalan_number – ShreevatsaR Jan 1 '13 at 10:45
• @nbubis I doubt I know correctly what's your question. You may just consider as open and close brackets, every bracket is counted as individual regardless its open or closed one. But the arrangement counted for must follow the grammer. e.g n=4 -> ( ( ) ) two open and two close – Saurabh Tripathi Jan 1 '13 at 11:20
• The paper "Counting strings in Dyck paths" by A. Sapounakis, I. Tasoulas, and P. Tsikouras seems to address the question you are interested in. I have not read the paper, but they appear to have worked out the details for all 16 possible substrings of length 4. – Will Orrick Jan 1 '13 at 17:24
• @WillOrrick - nice find. You could post this an an answer. – nbubis Jan 2 '13 at 7:26

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.

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$$

• I agree, thanks to @ShreevatsaR and you. but that doesn't answer the second question if sub-string is given how many arrangements could be there to satisfy... like for n=4 and sub-string (( only one string is there (()) – Saurabh Tripathi Jan 1 '13 at 12:02
• @SaurabhTripathi - is the sub-string necessarily a proper string? – nbubis Jan 1 '13 at 12:51
• no, as if you see the previous example n=4 and sub-string (( and (( is not a proper sub-string. Also in some cases answer could be zero. e.g. sub-string ((( for n = 4 ; no possible arrangement could be there. – Saurabh Tripathi Jan 2 '13 at 6:14