Home > Combinatorics > Đếm ma trận {0,1}

Đếm ma trận {0,1}


Xét hai vector sao cho

Một kết quả quen thuộc là:

Số các ma trận với các số hạng 0,1 sao cho tổng dòng thứ i băng , tổng cột thứ j bằng , kí hiệu là B(s,t), bằng số các đồ thị lưỡng phân (có gán nhãn) với phần thứ nhất gồm m đỉnh với bậc tương ứng là bộ , phần thứ hai có n đỉnh với các bậc tương ứng là

Giả sử là ma trận vơi các số hạng 0,1. Kí hiệu là số các ma trận cấp với các số hạng 0,1 và tổng các hàng, các cột tương ứng là sao cho nếu bằng 1 thì .

Trường hợp đặc biệt thì ko có điều kiện rằng buộc gì nên .

Chú ý rằng tỉ số bằng xác suất chọn ngẫu nhiên một ma trận với các số hạng 0,1 với tổng các hàng, các cột tương ứng là s,t, và ma trận này có các số hạng bằng 0 tại các vị trí mà bằng 1.

Ta kí hiệu có nghĩa là các lấy trên các số hạng có giá trị bằng 1, có nghĩa là các lấy trên các số hạng có giá trị bằng 0.

Để ý rằng chính là hệ số của số hạng chứa trong tích

Thế thì theo công thức Cauchy về hệ số ta có:

ở đây mỗi tích phân lấy theo một đường biên đơn, đóng theo ngược chiều kim đồng hồ.

Categories: Combinatorics
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: