Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the number of possible row and column sums of 0,1-matrices. | On the number of possible row and column sums of 0 1-matrices Daniel Goldstein and Richard Stong Center for Communications Research 4320 Westerra Court San Diego CA 92121 dgoldste@ccrwest.org Department of Mathematics Rice University Houston TX 77005 stong@math.rice.edu Submitted Aug 9 2005 Accepted Apr 4 2006 Published Apr 18 2006 Mathematics Subject Classification 05A15 Abstract For n a positive integer we show that the number of of 2n-tuples of integers that are the row and column sums of some n X n matrix with entries in 0 1 is evenly divisible by n 1. This confirms a conjecture of Benton Snow and Wallach. We also consider a ợ-analogue for m X n matrices. We give an efficient recursion formula for this analogue. We prove a divisibility result in this context that implies the n 1 divisibility result. 1 Introduction We study the number p m n of m n -tuples of integers that are the row and column sums of some m X n matrix with entries in 0 1 . For each n 1 the sequence p m n 1 1 is a linear recursion of degree n. Moreover this recursion is annihilated by the polynomial T n 1 n. It follows that if 1 n m then p m n is evenly divisible by n 1 m-n 1. This confirms a conjecture of Benton Snow and Wallach. For positive integers m and n let M Mmn be the set of m X n matrices with entries in 0 1 . For M in M we write M Mij . We have two vector-valued functions on M the vector x M x1 . xm of row sums where xi 52 i_ j n Mij for 1 i m and the vector y M y1 . yn of column sums where yj mi m Mij for 1 j n. Define RC RCm n to be the set of pairs of row and column sums x M y M as M ranges over M. Our main result concerns the cardinality p m n of RCmn. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 N8 1 Theorem 1 We have 1. p 1 1 2. 2. p m n p n m for m n 1. 3. If 1 n m then p m n VKi n 1 i 1 n n 1 ip m i n . Of these statements part 1 is clear and part 2 follows by taking transpose for x Mt y M and y Mt x M . Part 3 says that for each n 1 the sequence p m n 1 1 is a linear .
