TAILIEUCHUNG - Báo cáo toán học: "Catalan Traffic at the Beach"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Catalan Traffic at the Beach. | Catalan Traffic at the Beach Heinrich Niederhausen Department of Mathematical Sciences Florida Atlantic University Boca Raton USA Niederhausen@ Submitted March 17 2002 Accepted August 12 2002. MR Subject Classifications 05A15 05A19 Abstract The ubiquitous Catalan numbers Cn 2n n 1 occur as t n n in the following table showing the number of ways to reach the point n m on a rectangular grid under certain traffic restrictions indicated by arrows. 12 12 12j glgafe 2. 3. 3 12 3. 61 15 41 91 2 . 61 13 30 9. 19 4 4 28 62 42 90j 1 1U 3 6 9 2 3 3 1 gate 1. 1. 1. 1. 2. 2 3. 5 t n m m 2 1 start here 1 2 3 4 5 0 1 2 3 4 5 n We prove this with the help of hypergeometric identities and also by solving an equivalent lattice path problem. On the way we pick up several identities and discuss other known sequences of numbers occurring in the Catalan traffic scheme like the Motzkin numbers in row m 1 and the Tri-Catalan numbers 1 1 3 12 55 . at the gates. 1 Catalan Traffic There are 66 problems in Stanley s book Enumerative Combinatorics Vol. II 10 Chpt. 6 about different combinatorial structures counted by the Catalan numbers Ci ĩ ĩ Ợi . One example Ballot problem or Dyck paths is the total count of lattice paths with step vectors East and South ị starting at the origin ending on the diagonal y x 0 never going below that line. If we think of the lattice as the streets on a city map the diagonal as the beach we are talking about the number of shortest trips between two spots at the beach. THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 R33 1 start here 1 ĩ 1 2 1 3 1 4 1 5 2 5 9 14 5 14 28 14 42 42 Table 1 The number of routes from the starting point to any other point on the beach are the Catalan numbers We will prove that the following obstacle course a carefully designed system of detours and right turns again allows us to visit the diagonal in the same Catalan- number of ways as before with the added benefit that we cannot get off the diagonal anymore. m 2 1 start here

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.