Đếm các cặp tập con rời rạc

Question

Tôi muốn đếm # các cặp rời rạc $A, B \subseteq \{1, 2, 3, ..., n\}$, st

• $|A| = |B| = s$
• $a_1 < b_1$
• $a_k > b_k$ cho một số $k$

Ở đây các phần tử của tập hợp $A$ Chúng tôi $a_1 < a_2 < \cdots < a_s$, tương tự cho $B$.

Ví dụ: tất cả các cặp cho $n = 6, s = 3$ Chúng tôi:

$$ (\{1, 2, 6\}, \{3, 4, 5\})\\ (\{1, 3, 6\}, \{2, 4, 5\})\\ (\{1, 4, 5\}, \{2, 3, 6\})\\ (\{1, 4, 6\}, \{2, 3, 5\})\\ (\{1, 5, 6\}, \{2, 3, 4\}) $$

Thông qua một số mã hóa và tìm kiếm các chuỗi OEIS để tìm manh mối, tôi đã tìm thấy công thức sau có vẻ hoạt động:

$$\left( \frac{n!}{(n - 2 s) !s!s!} \right) \cdot \left( \frac{1}{2} - \frac{1}{s + 1} \right) $$

Bất cứ ai có thể giải thích tại sao / nếu điều này hoạt động (hoặc nếu có một số cách đơn giản hơn để tính điều này)?

Answer 1

Tính như sau. Lấy$$\frac{1}{2}\binom{n}{s}\binom{n-s}{s},$$ đây là cách để chọn hai tập hợp rời rạc và bạn sắp xếp chúng dựa trên thứ tự của phần tử đầu tiên, đó là lý do tại sao bạn chia cho $2.$ Bạn biết rằng phần tử thấp nhất đi đến $A.$

Bây giờ, bạn phải quan tâm đến tình trạng khác. Phủ định của điều đó là$a_k<b_k$ cho tất cả $k.$ Chọn $2s$ các yếu tố ngoài $n$ và xem xét cấu trúc sau đây mỗi khi bạn chọn một phần tử cho $B$ bạn phải chọn một phần tử cho $A$điều này cũng giống như cách giải thích tổ hợp cho các số Catalan dưới dạng đường đi Dyck. Công thức của bạn trở thành$$\binom{n}{2s}C_s=\frac{1}{s+1}\binom{n}{2s}\binom{2s}{s}.$$ Nhận sự khác biệt bởi vì bạn đang lấy chúng ra và bạn đã hoàn thành.