To solve this problem, we need to determine the number of valid parentheses sequences that can be formed using n pairs of parentheses. This is a classic problem that can be efficiently solved using Catalan numbers.

Approach

The number of valid parentheses sequences of length 2n (i.e., n pairs) is given by the n-th Catalan number. The formula for the n-th Catalan number is:
[ C(n) = \frac{1}{n+1} \binom{2n}{n} ]
where (\binom{2n}{n}) is the binomial coefficient representing the number of ways to choose n elements from 2n elements.

Solution Code

import math

n = int(input())
catalan = math.comb(2 * n, n) // (n + 1)
print(catalan)

Explanation

1. Binomial Coefficient: The term (\binom{2n}{n}) calculates the total number of ways to arrange 2n characters (n opening and n closing parentheses) without any constraints.
2. Adjustment: Dividing by n+1 accounts for the invalid sequences (those where closing parentheses exceed opening ones at any point), leaving only the valid sequences.

For example:

• For n=3, the Catalan number is (5) (valid sequences: ((())), (()()), (())(), ()(()), ()()()).
• For n=2, it's (2) (()(), (())).

This approach efficiently computes the result using Python's built-in math.comb function, which handles binomial coefficients directly. The solution runs in (O(n)) time (due to the binomial coefficient calculation) and is optimal for typical input sizes.

Answer: The code outputs the number of valid parentheses sequences for the given n. For example, if input is 3, the output is 5.

\boxed{5} (for input 3; replace with the actual output based on input)

作者声明:本文包含人工智能生成内容。