본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[슬기로운 수학생활] 슬16. 괄호쌍의 레벨은?
수학동아 2021.07.28 11:28 조회 425

 

n개의 여는 괄호와 n개의 닫는 괄호로 구성된 총 2n개 괄호의 나열을 생각하자. 그 중 여는 괄호와 닫는 괄호의 쌍이 완전히 맞는 배열만을 고려하자. 이를테면 "(()())()"는 쌍이 맞지만 "())(()"는 쌍이 맞지 않는다.

괄호 쌍이 맞는 배열에 대해, 이 배열의 각 괄호쌍은 '레벨'이 있다. 괄호쌍의 '레벨'은 해당 괄호쌍을 포함하는 괄호쌍들의 개수에 1을 더한 값으로 정의한다.

예를 들어 "(()())()"에서 첫번째 글자 "("와 여섯번째 글자 ")"는 하나의 괄호쌍을 이루고, 이 괄호쌍은 포함하는 다른 괄호쌍이 없으므로 레벨 1이다.

"(()(()))"에서 다섯, 여섯번째 글자가 이루는 괄호쌍은 넷, 일곱번째 글자 / 첫, 마지막 글자가 이루는 괄호쌍에 포함되어 있으므로 레벨 3이다.

괄호 쌍이 맞는 하나의 배열에 대해, 이 배열의 값을 나타나는 모든 괄호쌍들의 레벨들의 곱으로 정의하자.

가능한 모든 길이 2n의 괄호 쌍이 맞는 배열들의 총 값의 합을 구하라.

  •  
    Scubed Lv.6 2021.08.13 18:01

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

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    Scubed Lv.6 2021.08.13 18:07

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

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

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

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

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

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

     

    대충 이까지네요

    댓글 작성하기 좋아요0 댓글수0
  •  
    은총알 Lv.11 2021.08.19 14:51

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    Scubed Lv.6 2021.09.27 22:38

    댓글이 없네요...

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

    (2n-1)!!

    이 나올 것 같습니다.

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

    댓글 작성하기 좋아요0 댓글수0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911