우선 이 문제는 카탈란 수와 연관이 있는데요, 자세한 이유는 구글이나 네이버를 참고해보세요(???)

2n의 괄호 쌍이 가지는 배열들의 개수는 카탈란수 입니다.

또한, 괄호가 보기 눈 아파서 저는 괄호를 다른 모양으로 치환했는데요, 

다음과 같이 산 모양으로 치환할 수 있습니다.

여기서 위 대각선은 "(" , 아래 대각선은 ")" 입니다.

이 때, 문제에서 말한 "괄호쌍의 레벨"은 대각선이 위치한 높이입니다. 즉, n=3에서 두번째 그림을 보면

각각의 괄호의 높이가 1,1,1,2,2,1이므로 레벨은 1,1,1,2,2,1입니다. 참고로 여기서는 괄호쌍 대신 괄호 하나, 즉 작대기 하나로 보고 했습니다.

이 때, 괄호쌍들의 레벨의 곱은 모든 괄호의 곱의 제곱근임을 알 수 있습니다. 즉, 아까 n=3에서 두번째 그림의 레벨의 곱은  입니다.

대충 이까지네요

우선, Scubed님이 말하신 것처럼 괄호의 개수가 2n개인 배열 중 알맞은 괄호쌍이 만들어지는 경우의 수는 카탈란 수로,  입니다. 괄호쌍들중 이 괄호쌍을 포함하는 괄호쌍이 없는, 즉, (()())에서는 1번째와 마지막 괄호로 이루어진 괄호쌍을 '최고 괄호쌍'이라고 해봅시다. 최고 괄호쌍은 여러개일수도 있습니다. (())()같은 경우에는 1번째와 4번째 괄호, 5번째와 6번째 괄호가 최고 괄호쌍입니다. 최고 괄호쌍들의 레벨의 합은, n입니다. 여기서 최고 괄호쌍 안에 속해 있는 괄호쌍들의 레벨은 해당 최고 괄호쌍의 레벨보다 항상 낮습니다. 그리고 1레벨의 괄호쌍이 최소, '최고 괄호쌍'의 개수만큼은 있습니다. 최고 괄호쌍의 개수를 k개라고 하면, 입니다. 이걸 이용해서 뭔가 한번 해봐야겠네요

댓글이 없네요...

제가 노가다한 바로는(???)

이 나올 것 같습니다.

그래서 점화식 세워서 풀면 될 것 같은데...ㅠ 

이런 꼴까지는 정리했는데, 이 다음부터는 좀 막막하네요. 좋은 조합론적인 풀이가 없을까요?

길이 2n의 배열은 윗 댓글에서 나와있는 것처럼 그 모양을 산과 대응시킬 수 있습니다.

열린 괄호 ( 을 up step ↗ 으로, 닫힌 괄호 ) 을 down step ↘으로 바꾸어주면 됩니다. "이때 우리는 한 배열을 여러 개의 경우의 수를 모아둔 집합으로 바라보고자 합니다."

만들어진 산 모양의 up step 각각에 숫자를 할당시키는 것인데, 대응되는 숫자는 항상 그 up step이 위치한 높이와 같거나 작게 할당합니다.(여기서 높이는 직관적으로 이해하면 됩니다.) 이렇게 대응시키는 이유는 배열의 값이 사실은 집합의 크기와 같도록 만들기 위해서 입니다

(말로하면 어려우니 아래 예를 봅시다. 값이 2인 괄호는 모양은 같지만 각 up step에 할당된 숫자가 다른 2개의 경우가 모인 집합입니다. 집합의 크기는 배열의 값과 정확히 같습니다. 그림에서 level이 아니라 배열의 값이 2임을 표현하고 싶었습니다.)

배열의 값과 집합의 크기가 같은 것은 당연합니다. 배열의 값은 각 괄호의 level을 곱한 것인데 우리의 정의에 따르면 up step에 대응시킬 수 있는 숫자의 개수가 그 up step이 위치한 높이이므로 그것이 바로 level입니다. 그러면 우리는 배열들의 총 값의 합을 구하는 문제에서 "Dyck path의 경우의 수를 구하는 문제로 바꾸었습니다." (위에서 이야기한 산 모양에 up step에 숫자를 할당시키는 과정을 Dyck path라 합니다) 그리고 너무나 유명하게도 길이 2n개의 Dyck path의 경우의 수는 (2n-1)!! 입니다. 

길이가 2n일 때 Dyck path의 경우의 수가 (2n-1)!!인 것을 한 번 보여봅시다. 너무 유명하기에 따로 인터넷에서 찾아봐도 됩니다.

"조합론에서 귀납법이 너무나 강력한 도구인 이유는 조합론은 셀 수 있는 것들을 다루기 때문입니다." 따라서 우리는 귀납법을 사용할 것입니다. 

A : 길이 2n-2인 하나의 path를 2n의 path로 만들 수 있는데, 다음 그림과 같이 하나의 path를 두 부분으로 자릅니다. 그런 다음 1이 할당된 up step을 하나 끼워놓고 마지막에 down step을 끼어넣은 후, 새로 끼어넣은 up step과 down step사이에 할당된 값들은 전부 1을 더해주는 것입니다.

B : 반대의 과정 역시 생각해볼 수 있습니다. 길이 2n의 Dyck path가 주어졌을 때, 값이 1로 할당된 up step중에서 맨 마지막에 나온 up step을 제거하고, down step 역시 맨 끝의 것을 제거합니다. 그 후 그 사이에 있는 up step에 1을 빼주면 우리는 2n-2 길이의 Dyck path를 만든 것입니다. (이 과정 속에서 항상 1이 할당된 up step은 최소한 1개 존재하므로 모든 길이 2n의 Dyck path에 적용할 수 있음을 어렵지 않게 알 수 있습니다.)

(말로하면 너무 어려우니 아래 그림을 봅시다). 

위와 같은 대응 방식은 길이 2n짜리의 Dyck path의 갯수는 길이 2n-2짜리의 갯수에 2n-1을 곱한 사실을 알려줍니다. 

첫째, 위 A와 같은 방식으로 주어진 길이 2n-2의 Dyck path에서 2n짜리로 만들 수 있는 경우의 수가 2n-1을 곱한 것입니다. 왜냐하면 값이 1로 할당된 up step을 우리는 각 step 사이에 끼어넣을 수 있기 때문에 양쪽 끝에 2개를 합한 2n-1 공간이 있기 때문입니다.

둘째, 우리는 임의로 주어진 길이 2n짜리의 Dyck path를 위 A 과정을 통해 만들 수 있는 재료 2n-2 path를 항상 찾을 수 있습니다. 왜냐하면 길이 2n짜리에 B과정을 적용시킨 후 B과정으로 없앤 up step에 바로 다시 새로 up step을 끼어주는 A과정을 적용하면 되기 때문입니다. (우리는 지금 일대일대응 관계임을 보인 것입니다.)

따라서 결국 길이 2n의 Dyck path의 경우의 수는 귀납적으로 (2n-1)!!임을 증명하게 됩니다.

+여담) 솔직히 위 풀이는 조합론 문제답게 가장 아름답게 푼 풀이라고 생각합니다. 3주 동안에 10개 남짓한 방법으로 시도를 하다 오늘 1시간만에 풀게 되었는데, 그럴 수 있었던 까닭은 double factorial에 관한 논문을 찾아보다가 이와 유사한 문제를 보고 아이디어를 얻었기 때문입니다. "경우의 수를 찾는 문제보다 위 문제가 어려운 까닭은 각 경우에 1이 아닌 특정한 수들을 할당했기 때문입니다." 때문에 저는 이를 경우의 수를 구하는 문제로 바꾸고 싶었고 이를 위해 (2n-1)!!의 경우의 수를 갖는 문제들을 찾아본 것 뿐입니다. 이 문제의 풀이에서 제가 기여한 것은 하나도 없으며 오직 Dyck path의 문제와 위 문제를 연결시킨 것 뿐입니다. 아래는 제가 읽어보았던 논문입니다. 저는 오늘도 자괴스럽습니다. 

https://arxiv.org/abs/0906.1317