下面几个集合的券商大小集合之和是多少
点击联系发帖人
时间：2017-08-18 05:19
小木虫 --- 600万学术达人喜爱的学术科研平台
热门搜索：
&&查看话题
求助，如何将一个图划分为几个大小相等的集群并集群间的互联度最小
如题，请教各位高手，
& & 采用什么算法，能够运用图论原理，针对一个给定的通信互联图，选择最优的集群大小值，将其划分为多个大小相等的集群，并使得集群间的互联度最小。
如附件中的通信互联图
想要把他划分为多个相等大小的集群，
&&1） 如何确定最优的集群大小值，如：是划分为3个集群大小为4的集群，还是4个集群大小为3的集群？？？
&&2）如何实现集群划分，当规模较大时，什么算法划分较快且效果较好
& &&&烦请告之相关算法，参考书及参考文献。
& &&&欢迎关注，先行谢过
学术必备与600万学术达人在线互动！
扫描下载送金币java 中计算数组 集合长度的方法
全部答案（共1个回答）
数组有length属性，直接数组名.length 就可以了。 不是length()方法。字符串是length().数组才是字符串的length属性.这个东西有个...
#include main (){int y,m,d,i,n=0;int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30...
错误挺多的ray是封装类不是数组。2.内部类运用错误。直接写代码块要用{},要不就写在构造函数或方法内。ray[0] {ArrayList array = ne...
(1) |A|=n.A的所有子集的个数为2^n.这是因为A中有1个空子集，C(n,1)个一个元素的子集，C(n,2)个2个元素的子集，...,C(n,k)个k个...
新建一个较长的数组，在把原数组的内容一个一个拷过去。或者可以使用vector。
答: 想学达内的java，请问学java之前需要有什么基础吗？？？
答: 这个要设计到JNI的开发,就是用Java来调用C语言的函数库,还要编写缓冲器来解决传输问题,还有就是网络协议一定要了解,做的时候要用多线程来控制你所有的缓冲器,...
答: 所谓的网络编程，不论c还是java，本质上都是通过socket进行数据传输；一般情况下可以使用的传输协议有tcp、udp、ftp等等，这些协议为网络变成提供基本...
大家还关注
确定举报此问题
举报原因(必选)：
广告或垃圾信息
激进时政或意识形态话题
不雅词句或人身攻击
侵犯他人隐私
其它违法和不良信息
报告，这不是个问题
报告原因(必选)：
这不是个问题
这个问题分类似乎错了
这个不是我熟悉的地区
相关问答：123456789101112131415请登录查看
JPA查询集合大小示例我们可以使用SIZE函数来获取实体计数。以下代码选择具有两个员工的部门。&SELECT d FROM Department d WHERE SIZE(d.employees) = 2&)
例子下面的代码来自PersonDaoImpl.java。
import java.util.L
import javax.persistence.EntityM
import javax.persistence.PersistenceC
import org.springframework.transaction.annotation.T
@Transactional
public class PersonDaoImpl {
public void test() {
prepareData();
List l = em.createQuery(
&SELECT d FROM Department d WHERE SIZE(d.employees) = 2&)
.getResultList();
for (Object p : l) {
printResult(p);
private void prepareData() {
Professor p = new Professor();
p.setId(0);
p.setName(&TOM&);
p.setSalary(1111L);
Department d = new Department();
d.setId(1);
d.setName(&Design&);
p.setDepartment(d);
d.getProfessors().add(p);
Phone phone = new Phone();
phone.setId(1);
phone.setNumber(&111-111-1111&);
phone.setProfessor(p);
em.persist(p);
em.persist(phone);
em.persist(d);
private static void printResult(Object result) {
if (result == null) {
System.out.print(&NULL&);
} else if (result instanceof Object[]) {
Object[] row = (Object[])
System.out.print(&[&);
for (int i = 0; i & row. i++) {
printResult(row[i]);
System.out.print(&]&);
} else if (result instanceof Long || result instanceof Double
|| result instanceof String) {
System.out.print(result.getClass().getName() + &: & + result);
System.out.print(result);
System.out.println();
@PersistenceContext
private EntityM
以下代码来自Address.java。
import javax.persistence.E
import javax.persistence.Id;
public class Address {
public int getId() {
public void setId(int id) {
public String getStreet() {
public void setStreet(String address) {
this.street =
public String getCity() {
public void setCity(String city) {
this.city =
public String getState() {
public void setState(String state) {
this.state =
public String getZip() {
public void setZip(String zip) {
this.zip =
public String toString() {
return &Address id: & + getId() +
&, street: & + getStreet() +
&, city: & + getCity() +
&, state: & + getState() +
&, zip: & + getZip();
以下代码来自Phone.java。
import javax.persistence.E
import javax.persistence.Id;
import javax.persistence.ManyToO
public class Phone {
@ManyToOne
public long getId() {
public void setId(long id) {
public String getNumber() {
public void setNumber(String phoneNo) {
this.number = phoneNo;
public String getType() {
public void setType(String phoneType) {
this.type = phoneT
public Professor getProfessor() {
public void setProfessor(Professor employee) {
this.employee =
public String toString() {
return &Phone id: & + getId() +
&, no: & + getNumber() +
&, type: & + getType();
下面的代码来自Department.java。
import java.util.HashS
import java.util.S
import javax.persistence.E
import javax.persistence.Id;
import javax.persistence.OneToM
public class Department {
@OneToMany(mappedBy=&department&)
private Set&Professor& employees = new HashSet&Professor&();
public int getId() {
public void setId(int deptNo) {
this.id = deptNo;
public String getName() {
public void setName(String deptName) {
this.name = deptN
public Set&Professor& getProfessors() {
public String toString() {
return &Department no: & + getId() +
&, name: & + getName();
以下代码来自Professor.java。
import java.util.ArrayL
import java.util.C
import java.util.D
import javax.persistence.E
import javax.persistence.Id;
import javax.persistence.ManyToM
import javax.persistence.ManyToO
import javax.persistence.OneToM
import javax.persistence.OneToO
import javax.persistence.T
import javax.persistence.TemporalT
public class Professor {
@Temporal(TemporalType.DATE)
private Date startD
@OneToMany(mappedBy=&employee&)
private Collection&Phone& phones = new ArrayList&Phone&();
@ManyToOne
@ManyToOne
@OneToMany(mappedBy=&manager&)
private Collection&Professor& directs = new ArrayList&Professor&();
@ManyToMany(mappedBy=&employees&)
private Collection&Project& projects = new ArrayList&Project&();
public int getId() {
public void setId(int empNo) {
this.id = empNo;
public String getName() {
public void setName(String name) {
this.name =
public long getSalary() {
public void setSalary(long salary) {
this.salary =
public Date getStartDate() {
return startD
public void setStartDate(Date startDate) {
this.startDate = startD
public Collection&Phone& getPhones() {
public void addPhone(Phone phone) {
if (!getPhones().contains(phone)) {
getPhones().add(phone);
if (phone.getProfessor() != null) {
phone.getProfessor().getPhones().remove(phone);
phone.setProfessor(this);
public Department getDepartment() {
public void setDepartment(Department department) {
if (this.department != null) {
this.department.getProfessors().remove(this);
this.department =
this.department.getProfessors().add(this);
public Collection&Professor& getDirects() {
public void addDirect(Professor employee) {
if (!getDirects().contains(employee)) {
getDirects().add(employee);
if (employee.getManager() != null) {
employee.getManager().getDirects().remove(employee);
employee.setManager(this);
public Professor getManager() {
public void setManager(Professor manager) {
this.manager =
public Collection&Project& getProjects() {
public void addProject(Project project) {
if (!getProjects().contains(project)) {
getProjects().add(project);
if (!project.getProfessors().contains(this)) {
project.getProfessors().add(this);
public Address getAddress() {
public void setAddress(Address address) {
this.address =
public String toString() {
return &Professor & + getId() +
&: name: & + getName() +
&, salary: & + getSalary() +
&, phones: & + getPhones() +
&, managerNo: & + ((getManager() == null) ? null : getManager().getId()) +
&, deptNo: & + ((getDepartment() == null) ? null : getDepartment().getId());
以下代码来自Project.java。
import java.util.ArrayL
import java.util.C
import javax.persistence.E
import javax.persistence.Id;
import javax.persistence.I
import javax.persistence.ManyToM
@Inheritance
public class Project {
protected S
@ManyToMany
protected Collection&Professor& employees = new ArrayList&Professor&();
public int getId() {
public void setId(int projectNo) {
this.id = projectNo;
public String getName() {
public void setName(String projectName) {
this.name = projectN
public Collection&Professor& getProfessors() {
public void addProfessor(Professor employee) {
if (!getProfessors().contains(employee)) {
getProfessors().add(employee);
if (!employee.getProjects().contains(this)) {
employee.getProjects().add(this);
public String toString() {
return getClass().getName().substring(getClass().getName().lastIndexOf(&.&)+1) +
& no: & + getId() +
&, name: & + getName();
以下是数据库转储。Table Name: ADDRESS
Table Name: DEPARTMENT
Column Name: ID,
Column Type: INTEGER:
Column Value: 1
Column Name: NAME,
Column Type: VARCHAR:
Column Value: Design
Table Name: PHONE
Column Name: ID,
Column Type: BIGINT:
Column Value: 1
Column Name: NUMBER,
Column Type: VARCHAR:
Column Value: 111-111-1111
Column Name: TYPE,
Column Type: VARCHAR:
Column Value: null
Column Name: EMPLOYEE_ID,
Column Type: INTEGER:
Column Value: 0
Table Name: PROFESSOR
Column Name: ID,
Column Type: INTEGER:
Column Value: 0
Column Name: NAME,
Column Type: VARCHAR:
Column Value: TOM
Column Name: SALARY,
Column Type: BIGINT:
Column Value: 1111
Column Name: STARTDATE,
Column Type: DATE:
Column Value: null
Column Name: ADDRESS_ID,
Column Type: INTEGER:
Column Value: null
Column Name: DEPARTMENT_ID,
Column Type: INTEGER:
Column Value: 1
Column Name: MANAGER_ID,
Column Type: INTEGER:
Column Value: null
Table Name: PROJECT
Table Name: PROJECT_PROFESSOR
意见反馈：
联系方式：
广告等垃圾信息
不友善内容
违反法律法规的内容
不宜公开讨论的政治内容集合及其划分
集合及其划分 集合及其划分一、集合基础知识复习 1．1 基本概念：一组对象构成集合的条件―确定性；集合的表示―列举法、描述法和文氏 图法；集合的分类―数集和点集，有限集和无限集，等等；有限集合的元素个数。理解一个 集合关键是理解集合的元素。 1．2 集合的运算： 子集、真子集和相等；交集、并集和余集。在包含关系 A ? B 中，要注重空集 Φ 的作 用。 1．3 性质：A ? B ? CU A ? CU B ； A ∩ B = Φ ? A ? CU B ? B ? CU A ； A ∪ B = U ? CU A ? B ? CU B ? A ； A ? B ? A∩ B = A ? A∪ B = B； A∩ B ? A∪ B ? A = B； A = CU B ? A ∩ B = Φ ，且 A ∪ B = U ；CU ( A ∩ B ) = (CU A) ∪ (CU B ) ； CU ( A ∪ B ) = (CU A) ∩ (CU B ) ；A ∪ (B ∩ C ) = ( A ∩ B ) ∪ ( A ∩ C ) ； A ∩ (B ∪ C ) = ( A ∪ B ) ∩ ( A ∪ C ) ；注： 这些运算等式中的括号是必要的， 譬如： 可以验证 ( A ∪ B ) ∩ C = A ∪ (B ∩ C ) ” “ ， 因此形如“ A ∪ B ∩ C ”的写法是没有意义的。 1．4 要十分重视文氏图的作用：譬如，应当写出下面文氏图（1）中任一块的集合表示，能 否看出来集合等式“ card ( A ∪ B ∪ C ) + card ( A) + card (B ) + card (C ) = card ( A ∪ B )+ card (B ∪ C ) + card (C ∪ A) + card ( A ∩ B ∩ C ) ”是否成立？回答是肯定的。1 A B U AB (1) C (2)又如，根据文氏图（2） ，有A = ( A ∩ B ) ∪ ( A ∩ CU B ) ， B = (B ∩ A) ∪ (B ∩ CU A) ，等等。例 1 已知 M = 抛物线 ， N = 直线 ，求 card (M ∩ N ) 。 例 2 M 1 = 20 p + 16q + 12r p、q、r ∈ Z ， M 2 = 12m + 8n + 4l m、n、l ∈ Z ， 证明： M 1 = M 2 。 例 3 已知集合 A = x x ? x ? 4 & 2, x ∈ R ， B = x x + 2 2 ? x + 1 ≥ 0, x ∈ R ，2{}{}{}{}{}{}? 1 ? x C = ?x ? & & 1, x ∈ R ? 2 2? x ? ?，D = x y = 1 + x + 3 ? x + 1, x ∈ R{}，M = y y = 1 + x + 3 ? x + 1, x ∈ D 。求 C B ∪ D ( A ∩ (C ∪ M )) 。解： [ A] ，先简化各个集合，得{}A = x x 2 ? x ? 2 x 2 ? x ? 6 & 0 = {x ( x + 2 )( x + 1)( x ? 2 )( x ? 3) & 0}{()() }= (? 2,?1) ∪ (2,3) ，B = ?x ? ?(2?x)2? 2 2 ? x ? 3 ≤ 0? = x ? ?{(2? x ?3)(2 ? x +1 ≤ 0) }= x 2 ? x ? 3 ≤ 0 = {x 0 ≤ 2 ? x ≤ 9} = [? 7,2] ，{}? ? ? x ? ? ( x ? 1)( x + 2 ) 1? ? ? ?? x C = ?x ? ? 1?? + ? & 0? = ? x & 0? = (? 2,1) ， 2 (2 ? x ) ? ? ? 2 ? x ?? 2 ? x 2 ? ? ? ? ?D = [? 1,3] ，2 ? ? M = ? y y = 4 + 2 3 + 2 x ? x 2 + 1, x ∈ D ? ? ?? ? 2 = ? y y = 4 + 2 4 ? ( x ? 1) + 1, x ∈ D ? = 3,2 2 + 1 ， ? ?再把各集合表示在数轴上，如下：B C D M A -7 -2 -1 1 2 A 4 3[]∴A ∩ (C ∪ M ) = (? 2,?1) ， B ∪ D = [? 7,3] C B ∪ D ( A ∩ (C ∪ M )) = [? 7,?2] ∪ [? 1,3] 。故例 4 把不超过 20 的质数（正整数）所成的集合记作全集 U ，其子集 A、B 满足(CU A) ∩ B = {5}， A ∩ (CU B ) = {2,11,17} ， (CU A) ∩ (CU B ) = {13,19} 。求集合 A ∩ B 。解：根据题意，作下面文氏图，U A 2 5 11 17 13 19 B∵U = {2,3,5,7,11,13,17,19}， A ∩ B = {3,7} 。∴例 5 设集合 A = x 2 x ? x 2 ≤ x ， B = ? x{}?x x ? 2 ≤ ? ， C = x ax + x + b & 0 ， ? 1? x 1? x ?{(}如果 ( A ∪ B ) ∩ C = Φ ，且 ( A ∪ B ) ∪ C = R ，求实数 a、b 的值。 例 6 已 知 A = x x 2 ? mx + m 2 ? 19 = 0{}，B = x log 2 x 2 ? 5 x + 8 = 1 ，{) }C = x x 2 + 2 x ? 8 = 0 ，且 A ∩ B ≠ Φ ， A ∩ C = Φ ，求 m 的值。3{} 注：解题时，大多使用的是条件的必要性，所以解出后，要自觉地检验题设中的各个条 件是否成立。譬如，本题解得 m = ?2,5 ，经检验， m ≠ 5 。 例 7 设A ={(x, y ) x = n, y = an + b, n ∈ Z }，B = {(x, y ) x = m, y = 3m2+ 15, m ∈ Z ，}C = ( x, y ) x 2 + y 2 ≤ 144 。问：是否存在 a、b ∈ R ，使得 A ∩ B ≠ Φ ，且 (a, b ) ∈ C 。例 8 数集 M 由 2006 个不同的实数组成，对于 M 中任何两个不同的元素 a、b ，都有{}a 2 + b 2 ∈ Q 。证明： M ? a 2 a ∈ Q 。证明：再任取 b、c ∈ M ，使得 a、b、c 两两互异，则{}a 2 + b 2、b 2 + a 2、c 2 + a 2、c 2 + b 2 ∈ Q ?a 2 ? b 2 = c 2 + a 2 ? c 2 + b 2 ∈ Q ? ?1 2 2 ? a 2 ?b 2 a 2 + b 2 ? 2 = a + b 2 ? b + a 2 ∈Q ?2∴(( )() () ()) ()故a 2 ? b 2、a 2 + b 2 ? 2 ∈ Q ，a 2= 1 1 a 2 + b 2 + a 2 ? b 2 ∈Q 。 2 2∴ 故() ()结论成立。例 9 已知 S = m 2 + n 2 m、n ∈ Z ，证明： x、y ∈ S ? xy ∈ S 。{}例 10 在一次数学竞赛中共出了 3 道试题 A、B、C，共 25 人参加，其中每人至少解出 一道题。在未解除 A 的人中，解出 B 的人数为解出 C 的人数的 2 倍；只解出 A 的人数比解 出 A 的其余人数多 1；在解出一道题的人中有一半没解出 A。求只解出 B 的人数。A z z+t z+t-1 z-2t (1) tBC(2)解：根据题意，造出文氏图（1） ，并有数据关系：4 ? x + y + z + u + v + s + t = 25 ? z + s = 2(s + t ) ? ，由此得简化文氏图（2） ，以及数据关系 ? ?x = y + u + v + 1 ?x = z + t ? ?t + 4 z ? 1 = 25 ?t + 4 z = 26 ?t + 4 z = 26 ? z ? 2t ≥ 0 ? z ? 2(26 ? 4 z ) ≥ 0 ? 52 25 ? ? ? ?? ≤z≤ ?? ? 3 ?z + t ? 1 ≥ 0 ?25 ? 3 z ≥ 0 ?9 ?t , z ∈ N ?t , z ∈ N ?t , z ∈ N ? ? ? ?t + 4 z = 26 ?z & 7 ?z = 6 ? ?? ?? 。 ?t = 2 ? z = 6,7,8 ?t , z ∈ N ?∴ 只解出 B 题的人有 6 人，这 25 的具体分布是A 6 8 7 2 2 (2)BC。 例 11 已知 A = 求实数 a 使得 （1） card (( A ∪ B ) ∩ C ) = 2 ； （答：0，1） （2） card (( A ∪ B ) ∩ C ) = 3 。 （答： ? 1 ±{(x, y ) ax + y = 1}， B = {(x, y ) x + ay = 1}， C = {(x, y ) x2+ y2 = 1 。}2）例 12 已 知 函 数 f ( x ) = x 2 + ax + b ， 定 义 集 合 ： A ={(x, y ) f (x ) = x, x ∈ R} ，C = {( x, y ) f ( f ( x )) = x, x ∈ R}。（1）证明： A ∪ B = B ； （2）若 A = {? 1,3} ，求 B ； （3）若 card ( A) = 1 ，证明： A = B 。 例 13 设 集 合 A = {a1 , a 2 , a3 , a 4 , a5 } ， B = a1 , a 2 , a3 , a 4 , a52 2 2 2{2}， 其 中 a ∈ Ni*5 （ i = 1,2,3,4,5 ） 并且 a1 & a 2 & a 3 & a 4 & a5 ， a1 + a 4 = 10 ，A ∩ B = {a1 , a 4 } ， A ∪ B ， 中所有元素之和为 224，求集合 A。 解：由 A ∩ B = {a1 , a 4 } ，可知， a1、a 4 都是完全平方数，再根据 a1 + a 4 = 10 ，可知a1 = 1, a 4 = 9 ，从而，有?1 & a 2 & a 3 & 9 & a5 ? ? ?1 & a 2 2 & a 3 2 & 81 & a 5 2 ?若 a 3 = 9 ，则 a 3 = 3, a 2 = 2 ，必有2A ∪ B = 1,2,3,4,9,81, a5 , a5∵ ∴{2}A ∪ B 中所有元素之和为 224，a5 + a5 ? 124 = 0 ，但这方程无非负整数解。2故a 2 = 9 ，则 a 2 = 3 ，必有2A ∪ B = 1,3,9,81, a3 , a3 , a5 , a5 ， a 3 ≥ 4 ， a 5 ≥ 10 。2 2{}∵ ∴A ∪ B 中所有元素之和为 224，a5 + a5 + a3 + a3 = 130 。2 2又a5 ≥ 10 ? a5 + a5 ≥ 110 ，2∴a3 + a3 ≤ 20 ? a3 ≤ 4 ? a3 = 4 ，2故a5 + a5 = 110 ? a5 = 10 。2∴A = { ,3,4,9,10}。 1M 1 = x 2 + Ax + B x ∈ Z ， M 2 = 2 x 2 + 2 x + C x ∈ Z 。例 14 对固定的整数 A、B、C，定义集合：{}{}证明：无论对怎样的 A、B ∈ Z ，都可以选择 C ∈ Z ，使得 M 1 ∩ M 2 = Φ 。 证明：∵2 x 2 + 2 x + C ≡ C (mod 2 ) ，∴M 2 中的数都与整数 C 的奇偶性相同。当 A 是奇数时，有 x 2 + Ax + B ≡ B (mod 2 ) ，即 M 1 中的数都与整数 B 奇偶性相同， 所以，只要取 C = B + 1 即可。6 当 A 是偶数时， x + Ax + B = ? x +2? ?A? A2 +B? ≡ B, B + 1, B + 3(mod 4 ) ，而 ? 2? 422 x 2 + 2 x + C ≡ C (mod 4 ) ，所以，只要取 C = B + 2 即可。二、容斥原理与筛法公式? n ? n ? U Ai ? = ∑ card ( Ai ) ? ∑ card (Ai ∩ A j ) 容斥计数： card ? ? 1≤i & j ≤ n ? i =1 ? i =1+ L + (? 1)r ?1 1≤i1 & i2 &L& ir ≤ n∑ card (Ai1∩ Ai2 ∩ L ∩ Air)+ L + (? 1) card ( A1 ∩ A2 ∩ L ∩ An ) ，n筛法公式： card ? ??? i =1? I A ? = card (I ) ? ∑ card ( A ) + ∑ card (A ∩ A ) ?n n i?i =1 ri1≤ i & j ≤ nij+ L + (? 1)1≤ i1 & i2 &L& ir ≤ n n +1∑ card (Ai1∩ Ai2 ∩ L ∩ Air)+ L + (? 1)card ( A1 ∩ A2 ∩ L ∩ An ) 。n证明方法：数学归纳法、组合方法（ ?x ∈U A ，证明这个 x 在左右两边计入的次数i i =1相同） 例1 （1） 1 到 10000 的正整数中， 在 既不是整数的平方也不是整数的立方的数有多少？ （2）把 1 到 10 分成两个不相交的集合 A、B ， A 由可以表示成一个完全平方数和一个完 全立方数之和的所有数组成； B 由其余所有数组成。试判断 card ( A) 与 card (B ) 的大小关 系。 解 ：（ 1 ） 任 取 x ≤ 10000 ? x ≤ 21 ； 任 取 y 2 ≤ 10000 ? y ≤ 100 ； 任 取3 6z 6 ≤ 10000 ? z 3 ≤ 100 ? z ≤ 4 。由容斥原理，得，所求数的个数是 10000 ? 100 ? 21 + 4 = 9883 。（2） ?n ∈ A ， ?k、m ∈ N ，使得 n = k + m ；由 n ≤ 10 ，可得 k ≤ 10 ， m ≤ 10 ，2 3 6 3 2所以，二元集 {k, m} 的个数不多于 10 。5故card ( A) ≤ 10 5 & 10 6 ? 10 5 & 10 6 ? card ( A) = card (B )例 2 在 1 到 300 的整数中，计算 （1）能被 3 或被 5 或被 7 整除的数用多少？ （2）不能被 3，5，7 中的任何一个整除的数有多少？7 （3）能被 3 整除，但不能被 5、7 中任何一个整除的数有多少呢？ 例 3 由 5 对夫妻排成一行，求没有任何一对夫妻相邻的排法种数。 解：由容斥原理，不同排法的总数是1 3 5 10!?C 5 ? 2!?9!+C 52 ? 2!?2!?8!?C 5 ? 2!?2!?2!?7!+C 54 2!?2!?2!?2!?6!?C 5 2!?2!?2!?2!?2!?5!= 5!(40 × 8 × 7 × 6 ? 80 × 7 × 6 + 80 × 6 ? 32) = 120 × 16(40 × 7 × 3 ? 10 × 7 × 3 + 10 × 3 ? 2)= 120 × 16 × 658 = 1263360 。例 4 设 M = ?( x, y, z , u )? ?? x? y y ? z z ?u u ? x + + + & 0, x、y、z、u ∈ D ? ，其中 x+ y y+ z z +u u + x ?D＝{x x ∈ Z ,1 ≤ x ≤ 10}。求 card (M ) 。解：设 f (a, b, c, d ) =a?b b?c c?d d ?a ，记 + + + a+b b+c c+d d +a? ? f ( x, y , z , u ) & 0 ? A = ?( x, y, z, u ) ? ?， ? x, y , z , u ∈ A ? ? ? ? f ( x, y , z , u ) & 0 ? B = ?( x, y, z, u ) ? ?， ? x, y, z , u ∈ A ? ? ? ? f ( x, y , z , u ) = 0 ? C = ?( x, y, z, u ) ? ?。 ? x, y , z , u ∈ A ? ?则card ( A) + card (B ) + card (C ) = 10 4先证： card ( A) = card (B ) 。 ∵(a, b, c, d ) ∈ A ? f (a, b, c, d ) & 0 ? a ? b + b ? c + c ? da+b b+c ?a?d c?b b?c a?b + + + & 0 ? f (a, d , c, b ) & 0 ? (a, d , c, b ) ∈ B ， a+d c+b b+c a+bc+d+d ?a &0 d +a∴card ( A) = card (B ) 。再计算 card (C ) 。? ? f ( x, y , z , u ) = 0 ? C = ?( x, y, z, u ) ? ? ? x, y , z , u ∈ A ? ?8 ? ? ?x ? y y ? z z ?u u ? x + + + = 0? ? ? = ?( x, y, z, u ) ? x + y y + z z + u u + x ? ? ? x、y、z、u ∈ D ? ? ? ?? ?( z ? x )(u ? y )( xz ? yu ) = 0? = ?( x, y, z, u ) ? ? ? x、y、z、u ∈ D ? ?= C1 ∪ C 2 ∪ C 3 ，其中? ? ?x = z C1 = ?( x, y, z, u ) ? ?， ? x、y、z、u ∈ D ? ?? ? ?u = y ? ? ? C 2 = ?(x, y, z , u ) ? x ≠ z ?， ? ? x、y、z、u ∈ D ? ? ? ? ? ? ? xz = yu ? ? ? C 3 = ?( x, y, z , u ) ? x ≠ z , u ≠ y ?。 ? ? x、y、z、u ∈ D ? ? ? ?∴card (C ) = card (C1 ) + card (C 2 ) + card (C 3 ) 。又C1 = {( x, y, x, u ) x、y、u ∈ D} ? card (C1 ) = 1000 ，? ? ?x ≠ z C 2 = ?( x, y, z, y ) ? ? ? card (C 2 ) = 900 ， ? x、y、z ∈ D ? ? ? ? ? ? ?x ≠ z ?x ≠ y C3 = ?( x, x, z, z ) ? ? ∪ ?( x, y, y, x ) ? ? ? x、z ∈ D ? ? ? x、y ∈ D ? ?? ? ? xz = yu ? ? ? ∪ ?( x, y, y, x ) ? x、y、z、u ∈ D ? ? card (C 3 ) = 90 + 90 + 9 × 4 × 2 ? ? x、y、z、u互异? ? ? ?其中最后一步是根据数表 1＊2 1＊3 2＊3 1＊4 2*4 3*4 1＊5 2*5 3*5 4*5 1＊6 2*6 3*6 4*6 5*6 1＊7 2*7 3*7 4*7 5*7 6*7 1*8 2*8 3*8 4*8 5*8 6*8 7*8 1*9 2*9 3*9 4*9 5*9 6*9 7*9 8*9 1*10 2*10 3*10 4*10 5*10 6*10 7*10 8*109 9*10 得到就个四元互异数乘积等式：1 × 6 = 2 × 3 1 × 8 = 2 × 4 1 × 10 = 2 × 5 1 3 × 4 = 2 × 6 3 × 6 = 2 × 9 3 × 8 = 4 × 6 算得 9 × C 2 × 2!×21 = 9 × 4 × 2 。 4 × 5 = 2 × 10 5 × 6 = 3 × 10 5 × 8 = 4 × 10∴card (C ) = 1000 + 900 + 252 = 2152 。card ( A) = 10000 ? card (C ) = 3924 。 2故例 5 已知集合 S = { ,2,3, L ,280} ，求最小的正整数 n ，使得 S 的每个 n 元子集都含有 1 5 个两两互素的数。 解：先利用四个素数 2，3，5，7 的倍数构造一个集合A = A2 ∪ A3 ∪ A5 ∪ A7 ，其中 Ak = {n ∈ S n ≡ 0(mod k )}(k = 2,3,5,7 ) 。∵? 280 ? ? 280 ? ? 280 ? card ( A2 ) = ? ? = 140 ， card ( A3 ) = ? 3 ? = 93 ， card ( A5 ) = ? 5 ? = 56 ， ? 2 ? ? ? ? ? ? 280 ? ? 280 ? card ( A7 ) = ? ? = 40 ， card ( A2 ∩ A3 ) = ? 6 ? = 46 ， ? 7 ? ? ? ? 280 ? ? 280 ? card ( A2 ∩ A5 ) = ? ? = 28 ， card ( A2 ∩ A7 ) = ? 14 ? = 20 ， ? 10 ? ? ? ? 280 ? ? 280 ? card ( A3 ∩ A5 ) = ? ? = 18 ， card ( A3 ∩ A7 ) = ? 21 ? = 13 ， ? 15 ? ? ? ? 280 ? ? 280 ? card ( A5 ∩ A7 ) = ? ? = 8 ， card ( A2 ∩ A3 ∩ A5 ) = ? 30 ? = 9 ， ? 35 ? ? ? ? 280 ? ? 280 ? card ( A2 ∩ A3 ∩ A7 ) = ? ? = 6 ， card ( A2 ∩ A5 ∩ A7 ) = ? 70 ? = 4 ， ? 42 ? ? ? ? 280 ? ? 280 ? card ( A3 ∩ A5 ∩ A7 ) = ? ? = 2 ， card ( A2 ∩ A3 ∩ A5 ∩ A7 ) = ? 210 ? = 1 ? 105 ? ? ?∴card ( A) = 140 + 93 + 56 + 40 ? 46 ? 28 ? 20 ? 18 ? 13 ? 8 + 9 + 6 + 4 + 2 ? 1= 216∵ 在 A 中任取 5 个数，总有两个数不是互素的， ∴ n ≥ 217 。 下面构造 S 的元素个数不少于 5 的子集，其元素个数尽可能多，把这些子集都找出来； 为此，我们列表把 S 中的数作一分类：10 合数 素数与 1 2×素数 2＊2， 2＊139， 2＊137， 2＊131， 2＊127， 2＊113， 2＊109， 2＊107， 1，2，3，5， 7，11，13，17， 19，23，29，31， 37，41，43，47， 53，59，61，67， 71，73，79，83， 89，97，101，103， 107，109，113， 127，131，137， 139，149，151， 157，163，167， 173， 179，181， 191，193，197， 199，211，223， 227，229，233， 239，241，251， 257，263，269， 271，277， 2＊103， 2＊101 2＊97 2＊89 2＊83 2＊79 2＊73 2＊71 2＊67 2＊61 2＊59 2＊53 2＊47 2＊43 2＊41 2＊37 2＊31 2＊29 2＊23 2＊19 2＊17 2＊13 2＊11 2＊7 2＊5 2＊3 令 3×素数 3＊3 3＊89 3＊83 3＊79 3＊73 3＊71 3＊67 3＊61 3*59 3*53 3*47 3*43 3*41 3*37 3*31 3*29 3*23 3*19 3*17 3*13 3＊11 3＊7 3＊5 5×素数 5＊5 5＊53 5＊47 5＊43 5＊41 5＊37 5＊31 5＊29 5＊23 5＊19 5＊17 5＊13 5＊11 5*7 7×素数 7＊7 7＊37 7＊31 7＊29 7＊23 7＊19 7＊17 7＊13 7＊11 11×素数 11＊11 11＊23 11＊19 11＊17 11＊13 13×素数 13＊13 13＊19 13＊17B1 = { } ∪ {S中的素数} ? card (B1 ) = 60 ， 1B2 = 2 2 ,3 2 ,5 2 ,7 2 ,112 ,13 2 ? card (B2 ) = 6 ， B3 = {2 × 139,3 × 89,5 × 53,7 × 37,11 × 23,13 × 19} ? card (B3 ) = 6 ，{}11 B4 = {2 × 137,3 × 83,5 × 47,7 × 31,11 × 19,13 × 17} ? card (B4 ) = 6 ，B5 = {2 × 131,3 × 79,5 × 43,7 × 29,11 × 17} ? card (B5 ) = 5 ， B5 = {2 × 127,3 × 73,5 × 41,7 × 23,11 × 13} ? card (B6 ) = 5以及 B = B1 ∪ B2 ∪ B3 ∪ B4 ∪ B5 ∪ B6 ，则card (B ) = 88 ， card (C S B ) = 280 ? 88 = 192现在 S 中任取 217 个数，则至少有 217 ? 192 = 25 个数在 B 中；因为25 & 4 ，所以由 6抽屉原理，知至少有 5 个数在上述某一个集合 Bi (i = 1,2,3,4,5,6 ) 中；再由 Bi 的定义知，这 5 个数两两互质。 故 所求 n 的最小值是 217。 证法二：在 S 任取中任取 217 个数，令其组成子集 A 。如果其中至少有 5 个素数，则 结论成立；否则，其中至多 4 个素数，至少有 213 个合数。故 S 中的 220 个合数中多有 7 个不在其中。构造 S 的 8 个互素合数子集，使其中恰好有 5 个元素，作为抽屉：B1 = 2 2 ,3 2 ,5 2 ,7 2 ,112 ，{}B2 = {2 × 139,3 × 89,5 × 53,7 × 37,11 × 23} ，B3 = {2 × 137,3 × 83,5 × 47,7 × 31,13 × 17} ，B4 = {2 × 131,3 × 79,5 × 43,7 × 29,11 × 17}，B5 = {2 × 127,3 × 73,5 × 41,7 × 23,11 × 13} ，B6 = 2 × 113,3 × 71,5 × 37,7 × 19,13 2 ，{}B7 = {2 × 109,3 × 67,5 × 31,7 × 17,13 × 19}， B8 = {2 × 107,3 × 61,5 × 29,7 × 13,11 × 19}。由于这 8 个子集中至多有 7 个元素不在 A 中， 所以必存在某个 Bi ? A ， A 中必存在 故 5 个数两两互素。 证法三：设 T ? S ，且 card (T ) = 217 ，记 S 中的所有素数和 1 构成的集合为 M ，则card (M ) = 60 ， S 中的合数共 220 个。若 card (T ∩ M ) ≥ 5 ，则 T 中存在 5 个数两两互质。12 若 card (T ∩ M ) = 4 ， 则设其余素数按从小到大的顺序排成 p1 , p 2 , p3 , L ， p1 ≤ 11 ， 则p 2 ≤ 13 ， p3 ≤ 17 ， p 4 ≤ 19 ， p5 ≤ 23 ，于是，由数表p1 p1 p2 p3 p4 p5 L可找到 8 个合数2 p12 , p1 p 2 , p1 p 3 , p1 p 4 , p1 p5 , p 2 , p 2 p3 , p 2 p 4 ∈ Sp2 p1 p 2 2 p2p3 p1 p3 p 2 p32 p3p4 p1 p 4 p2 p4 p3 p 4 p2 4p5Lp2 1p1 p5 L p 2 p5 L p3 p5 L p 4 p5 L 2 p5 L L LLLLL∵ T 中只有 213 个合数， ∴ S 中恰有 7 个合数不在 T 中， 故上述 8 个合数中必有一个在 T 中， 这一个合数 T 中 的 4 个素数一起构成两两互素的 5 个数。 若 card (T ∩ M ) ≤ 3 ，则 T 中至少有 214 个合数，那么 S 中的 220 个合数中，至多有 6 个不在 T 中。考虑 6 个特殊的合数 2 2 ,3 2 ,5 2 ,7 2 ,112 ,13 2 ，若其中有 5 个在 T 中，则这 5 个数两两互素；若其中只有 4 个在 T 中，则这 4 个合数只含有 2、3、4、7、11、13 中的 4 个素数，可以完全重复 card (T ∩ M ) = 4 的情形，完成证明；若其中至多有 3 个在 T 中， 在其他合数至多有 3 个不在 T 中，因此，下面两个集合中的 12 个合数中至多有 3 个不在 T 中：{}{2 × 139,3 × 89,5 × 53,7 × 37,11 × 23,13 × 19}， {2 × 137,3 × 83,5 × 47,7 × 31,11 × 19,13 × 17}∴ 由抽屉原理知，其中必有一个子集中存在 5 个数在 T 中，它们两两互素。 评注：本题充分体现了容斥原理、抽屉原理、极端性原理、表格处理方法以及瞄准目标 穷追不舍逐步接近结论的数学思想方法的综合应用。 例 6 对有限集合 S，其元素个数记为 S ，子集个数记为 n(S ) 。如果三个有限集合 A、 B、C 满足 A = B = 100 ，并且 n( A) + n(B ) + n(C ) = n( A ∪ B ∪ C ) ，求 A ∩ B ∩ C 的最 小值。 解：有题意，得2100 + 2100 + 2C=2A ∪ B ∪C? 1+ 2C ?101=2A∪ B ∪C ?101若 C ? 101 ≥ 1 ，则 2A ∪ B ∪C是不小于 3 的奇数，矛盾！13 ∴C = 101 ， A ∪ B ∪ C = 102 。由容斥原理，得A∩ B ∩C = A∪ B ∪C + A + B + C ? A∪ B ? B ∪C ? C ∪ A = 403 ? A ∪ B ? B ∪ C ? C ∪ A∵ ∴ 同理，得A∪ B ? A∪ B ∪CA ∪ B ≤ A ∪ B ∪ C = 102 ，B ∪ C ≤ 102 ， C ∪ A ≤ 102 。故A ∩ B ∩ C ≥ 403 ? 306 = 97 。为构造“＝”成立的例子，我们先构造“＝”成立状况下的文试图：A 1 97 2 2 C B根据这个文氏图，我们可以构造出A = { ,2,L,100} ， B = {3,4,5,L,102} ， C = { ,2,4,5,6, L,100,101,102} ， 满 足 1 1 A ∩ B ∩ C = 97 。∴A ∩ B ∩ C 的最小值为 97。三、子集与对应：利用子集对应解题。 （1） n 元集合共有 2 n 个子集，能够按照相邻元素只相差一个元素的办法排成一列。 （2）利用单射对子集计数 例 1 求满足条件 { ,2,3} ? A ? { ,2,3,4, L , n}(n & 3) 的集合 A 的个数。 1 1 例 2 如果子集 A ? S = { ,2,3, L ,49} 中至少有两个数相邻，且 card ( A) = 6 ，证明：多 1 有这种子集 A 的个数为 C 49 ? C 44 。6 614 证明：集合 S 的所有 6 元子集的个数为 C 49 ，但其中有 6 个数互不相邻的子集6A' = {a1 , a 2 , L , a 6 } ， 1 ≤ a1 & a 2 & a 3 & a 4 & a 5 & a 6 ≤ 49 ， a i + 1 & ai +1 ，i = 1,2,3,4,5 。不满足要求，这部分子集个数记作 W1 ；故只需证明这种 A' 的个数为 C 44 。 换元： bi = ai ? i + 1 ， i = 1,2,3,4,5,6 ，则 1 ≤ b1 & b2 & b3 & b4 & b5 & b6 ≤ 44 ，子集6 {b1 , b2 , b3 , b4 , b5 , b6 } ? {1,2,3,L,44}共 C 44 个，它们构成集合 W2 ，作映射 6f : W1 → W2 , {a1 , a 2 , a3 , a 4 , a5 , a 6 } a {b1 , b2 , b3 , b4 , b5 , b6 }6 则这映射是单射，所以 card (W1 ) = card (W2 ) = C 44 。故 符合条件的子集 A 的个数是 C 49 ? C 44 。6 6例 3 有锁若干把，现有六个人格掌握一部分钥匙。已知任意两个人同时去开锁，都有一 把锁打不开，而且任何三个人都可以把全部锁打开。问：最少有多少把锁？ 解：先界定最值： 六个人 1，2，3，4，5，6 共有 C 6 = 15 各“二人组” ，记其集合为 S；由题意，对任意2的“二人组” {i, j} ，总有一些锁打不开，这些锁的集合记作 A{i , j } ，全部锁的集合记作 A。 作映射f : {i, j}(∈ S ) → A{i , j } ? A则这个映射是单射，否则，存在两个不同的二人组 {i, j} 与 {k, l }，合在一起至少 3 个人，但 他们打不开所有的锁，这与题意矛盾！ 故{i , j }card ( A) ≥ ∑ card (A{i , j} ) ≥ ∑ 1 = 15 。{i , j }方案构造：现安装 15 把锁，这 15 把锁的集合共有 15 个 14 元子集，把这些子集与 15 个“二人组”相对应，先完成 15 把锁的钥匙在 15 个二人组中的分配管理：表（1） 1 ｛1，2｝ ｛1，3｝ ｛1，4｝ ｛1，5｝ ｛1，6｝ ｛2，3｝ ｛2，4｝ ｛2，5｝ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ 2 √ √ 3 √ √ √ 4 √ √ √ √ 5 √ √ √ √ √ 6 √ √ √ √ √ √ 7 √ √ √ √ √ √ √ 8 √ √ √ √ √ √ √ √ 9 √ √ √ √ √ √ √ √ 10 √ √ √ √ √ √ √ √ 11 √ √ √ √ √ √ √ √ 12 √ √ √ √ √ √ √ √ 13 √ √ √ √ √ √ √ √ 14 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √1515 ｛2，6｝ ｛3，4｝ ｛3，5｝ ｛3，6｝ ｛4，5｝ ｛4，6｝ ｛5，6｝ 1 1 2 3 4 5 6 √ √ √ √√ √ √ √ √ √ √ 2√ √ √ √ √ √ √ 3√ √ √ √ √ √ √ 4√ √ √ √ √ √ √ 5 √√ √ √ √ √ √ √ 6 √√ √ √ √ √ √ √ 7 √√ √ √ √ √ √ √ 8 √ √ √ √ √ √ √ 9 √ √√√ √√ √ √√ √ √ √√ √ √ √ √√ √ √ √ √ √√ √ √ √ √ √ √√ √ √ √ √ 10 √ √ √ √ √ √ 11 √ √√ √ √ 12 √ √ √ √ √ 13 √ √ √√ 14 √ √ √ √ √ √ √ √ 15进一步实现 15 把锁的钥匙在 6 个人中的管理：表（2）√ √√ √ √√ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √√ √ √ √√ √ √ √√ √ √方案解释：由表（1）可知，任何两人到场都不能打开全部锁，由表（2）可知每一把锁 的钥匙恰好有两个人不管理，所以任何三人到场都能打开全部锁。 ∴(card ( A))min= 15 。例 4 某银行的管理保险柜由 11 人保管，保险柜上安装锁若干把，这些锁的钥匙分发给 11 人保管使用。问：最少要为保险柜安装多少把锁，才能使任何 6 人同时到场时就能打开 保险柜，而任何 5 人到场都不能打开？5 解：由 11 人组成的“五人组”个数为 C11 = 462 ，记其集合为 S；按题意，在装锁最少的情况下，对任一“五人组” {a, b, c, d , e}，总有唯一的一把锁 A{a ,b ,c ,d ,e} 不能打开；全部锁 的集合记作 A。作映射f : {a, b, c, d , e}(∈ S ) → A{a ,b,c ,d ,e} ? A则这个映射是单射，否则，存在两个不同的“五人组” {a, b, c, d , e}与 {a ' , b' , c' , d ' , e'}，他 们都不能打开同一把锁，但是两组合在一起至少 6 个人，而他们打不开所有的锁，这与题意 矛盾！ 故(card ( A))min={a ,b ,c , d ,e∑1 } = C5 11= 462 。思考：本题能否应用 spenner 定理求解？ 四、子集最值问题：求满足某种条件的子集个数最大值。 例 1 集 合 A = {0,1,2, L ,9} 的 非 空 子 集 族 D = {B1 , B2 , L , Bn } 满 足card (Bi ∩ B j ) ≤ 2(1 ≤ i & j ≤ n ) ， 求 n 的最大值。解：明显 n max ≥ C10 + C10 + C10 = 175 ，下面证明 n max ≤ 175 。1 2 316 对任一满足条件的 D = {B1 , B2 , L , Bn } ，若存在 B ∈ D ，使得 card (B ) ≥ 4 ，则存在b ∈ B ； 由 C B {b}? D ， 用 C B {b} 替 换 D 中 的 B ， 得 到 子 集 族 D ' ， 并 且card (D') = n = card (D ) ；由这种子集族元素个数的不变性，我们继续这种操作，经过有限次操作，必然能得到 A 的一个子集族 D ' ' ? T ，并且 card (D ' ') = n ，其中 T 为 A 元素个 数不超过 3 的所有子集组成的集合，故n ≤ card (T ) = 175∴n max ≤ 175 ， n max = 175 。故例 2 在一个车厢中，任何 m(m ≥ 3) 个游客都有唯一公共朋友（当甲是乙的朋友时，乙 也是甲的朋友，但任何人不作为自己的朋友） 。问：在这个车厢中，朋友最多的人有几个朋 友？ 解：设朋友最多的人 A 的朋友的集合为 S = {B1 , B2 , L , Bk } ，即他有 k 个朋友，则k≥m若 k & m ，任取 Bi1 , Bi2 , L , Bim ?1 ? S ，则 A, Bi1 , Bi2 , L , Bim ?1 有唯一公共的朋友 C i ， 并且 C i ∈ S ；定义映射{}f : Bi1 , Bi2 , L , Bim ?1 → C i则 f 是 单 射 ， 否 则 ， 设 Bi1 , Bi2 , L , Bim ?1 和 B j1 , B j2 , L , B jm ?1 的 像 都 是 C ， 则{}{} {}{Bi1, Bi2 , L , Bim ?1 ∪ B j1 , B j2 , L , B jm ?1 中至少有 m 个人，他们有两个公共朋友 A、C 。C km ?1 ≤ k 。 k & m ≥ 3，1 k ≥ C km ?1 ≥ C k2 & C k = k ，也矛盾！} {}矛盾！ ∴ 又 ∴故k min = m 。五、 Spenner 定理? 定理：设 A 为 n 元集合，它的 k 个子集 A1 , A2 , L , Ak 互不包含，则 k max = C n 2 ? 。 ?n? ? ?17 证明：由已知， Φ ≠ Ai ? A ，且 t i = card ( Ai ) & card ( A) ，把 Ai 中的元素作全排列， 并在其后接上 C A Ai 的元素的全排列， a i ,1 , a i , 2 , L , a i ,ti ， a i ,ti +1 , ai ,ti + 2 , L , ai ,n ，这样的 n 元 排列共有 t i !?(n ? t i )! 个，称为由 Ai “引导的 n 元排列” 。对 1 ≤ i & j ≤ k ，如果 t i & t j ，则 由 Ai ? A j 知，由 Ai 引导的任一 n 元排列的前 t i 项和由 A j 引导的任一 n 元排列的前 t i 项都 不一样， 所以由 Ai 引导的任一 n 元排列和由 A j 引导的任一 n 元排列互不相同； 如果 t i & t j ， 也有同样的结论；如果 t i = t j ，则由已知 Ai ≠ A j ，同样有 Ai 和 A j 各自引导的 n 元排列也 互不相同。 ∵ 由 A1 , A2 , L , Ak 各自引导的 n 元排列都是 A 的 n 个元素的全排列，∴∑ ti !?(n ? t i )! ≤ n! ? ∑i =1kki =11 ≤ 1。 t C ni又 ∴C ≤Cti n?n? ?2? ? ? nk(i = 1,2,L, k ) ，1 ≤ 1， t C ni?n? ?2? ? ? nk C故?n? ?2? ? ? n≤∑i =1 ?n? ?2? ? ? nk ≤C， k max = C?n? ? ? n ?? ? ? ? i = 1,2,L, k = C ? 2 ? ? 。 ，此时 card ( Ai ) = t i = ? ? n ? ? 2 ?? ? ?1993 年全国高中数学联赛加试题第三题，实质上就是这个定理： “设 A 为 n 元集合，它 的 k 个子集 A1 , A2 , L , Ak 互不包含。证明： （1）∑Ci =1k1Ai n（2） ∑ C n i ≥ k 2 ” 。其中 ≤ 1；A i =1k第二问可利用（1）的结论由均值不等式推证。 例 1 有 n 支球队要举行主客场双循环赛（每两支球队比赛两场，各有一场主场比赛） ， 每支球队在一周（从周日到周六的七天）内可进行多场客场比赛。但如果某周内该球队有主 场比赛，则在这一周内不能安排该球队的客场比赛。如果 4 周内能够完成全部比赛，求 n 的 最大值。 （注：甲乙两队在甲方场地举行的比赛，称为甲队的主场比赛，乙队的客场比赛） 解： 个周组成集合 A， 4 记第 i 支球队的 “主场周” 的集合为 Ai ， Ai ? A (i = 1,2, L , n ) ， 则 并且其中任意两个不互相包含，否则，不妨设 A1 ? A2 ，则第 1、2 两队进行的比赛都是双 方的主场，它们之间不打客场，与题意向违。由 Spenner 定理，得2 n ≤ C4 = 6 。各队的“主场周”安排如下： 球队 第一周 第二周 第三周 第四周18 1 2 3 4 5 6＊ ＊ ＊＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊方案说明：每个球队带“＊”的周次，表示该球队打主场，不出访。具体主客场比赛表 安排如下： 周次 周一 第一周 1―4 2―5 3―6 1―5 2―6 3―4 1―6 2―4 3―5 第二周 1―2 4―3 5―6 1―3 4―6 5―2 4―2 5―3 第三周 2―1 6―5 2―3 4―5 6―1 4―1 6―3 第四周 3―1 6―4 3―2 5―4 5―1 6―2周二周三周四 周五 周六 周日 （周四、五、六、日完全可以休息） 应用 spenner 定理，一定要注意把握问题的条件。譬如，我们在用 spenner 定理求解下 面的问题。 例 2 有锁若干把，现有六个人格掌握一部分钥匙。已知任意两个人同时去开锁，有且恰 有一把锁打不开，而且任何三个人都可以把全部锁打开。问：最少有多少把锁？ 解：设有 n 把锁，组成集合 A，由 6 个人组成的 C 6 = 15 个“二人组”分管的钥匙能打2开的锁的集合分别为 A1 , A2 , L , A15 ，则 Ak ≠ A(?k ) 。 ∵ ∴ 任何两个“二人组”至少有 3 个人，Ai ∪ A j = A(1 ≤ i & j ≤ 15) ， A1 , A2 , L , A15 中任意两个都不互相包含。?n? ?2? ? ? n故由 Spenner 定理，得15 ≤ C，故 n ≥ 6。 但是，当 n = 6 时，每个“二人组”能打开 3 把锁，也不能打开 3 把锁，这当然不是锁 最少的状况，故实际应有 n & 6 。这是应用 spenner 定理失败的典型例子，究其原因，本题 要求的条件比 Spenner 要求的条件更多、更强。19 例 3 由 11 个剧团参加汇演，每天都排定其中某些剧团的演出，其余剧团则跻身于普通 观众之列。在汇演结束时，每个剧团出了自己的演出日外，至少观看观看过其它每个剧团的 一次表演。问：这样的汇演最少要安排几天？1 解：设总汇演日集合 S = { ,2, L , n} n ∈ N(*) ，第 k 个剧团的演出日的集合为 Ak，则Ak ? S (k = 1,2, L , n ) ， Ai ? A j (?i ≠ j ) ，由 Spenner 定理，得2 11 ≤ C n ? n ≥ 6对于 n = 6 ，可以排除下面的汇演日期表 1 2 3 4 5 1 2 3 4 5 6 √ √ √ √ √ √ √ √ √ √67891011√ √√√√ √ √√ √ √√ √∴ 安排汇演日期天数最少是 6 天。 例 4 已知共有 12 个剧团参加一次为期 7 天的戏剧节，要求每个剧团都能看到其它所有 剧团的演出（当天没有演出任务的演员在台下观看演出） 。问：最少共要演出多少场？ 解：由 Spenner 定理，可知用 6 天的时间可以安排完成，但现在要求的是演出的场数 最少，而不要求安排演出天数最少。 按题意，每个剧团至少演出 1 场。如果 A 剧团在 7 天中只演 1 场，则在 A 团演出的当 天，其它剧团都没有演出，否则将看不到 A 团的演出。这样，该添置演出这 1 场。 如果有 3 个剧团在戏剧节期间都仅仅各演 1 场， 则这 3 个剧团占据 7 天中的 3 天。 从而 其余 9 个剧团只能在其余 4 天中演出。 由于这 9 个剧团也要相互观摩， 故它们各自演出的日2 期号的集合互不包含，由 Spenner 定理，应有 9 ≤ C 4 ，矛盾！所以，至多有 2 个剧团各演1 场，其余剧团每团至少都演 2 场，即至少共演 22 场。 1 1 2 3 4 5 6 7 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ 2 3 4 5 6 7 8 9 10 11 12六、应用抽屉原理证明存在性问题 例 1 由 10 个两位正整数组成集合 S ， 证明： 存在两个无公共元素的非空子集 S1、S 2 ， S 使得其中元素之和相等。20 例 2 一群童子军，年龄从 7 岁到 13 岁，来自 11 个国家。证明：至少有 5 个孩子，每一 个的同龄人多于同国籍的人。 解：作下表帮助分析，把第 i 国且 j + 6 岁的孩子的总人数填入第 i 行第 j 列，记作 a i , j 。 “一个孩子的同龄人多于同国籍的人”就是说“第 i 行的人数少于第 j 列的人数” 。 1（＋6） 1 2 3 4 5 6 7 8 9 10 11 作行列和： 2（＋6） 3（＋6） 4（＋6） 5（＋6） 6（＋6） 7（＋6）a1,1 a 2,1a1, 2 a 2, 2ai, jri计算：= ∑ ai , j (i = 1,2,L,11) ， s j = ∑ a i , j ( j = 1,2, L ,7 )j =1i =1711? 1 1 ? 7 11 ?1 1 ? ai , j ? ? ? = ∑∑ a i , j ? ? ? ∑ ? r s ? j =1 i =1 ? r s ? i, j j ? j ? ? i ? i= ∑∑j =1 i =1 11 7 11ai , j ri7? ∑∑j =1 i =1711ai , j sj=∑i =1117 1 7 1 ∑ ai, j ? ∑ s ri j =1 j =1 j∑ai =111i, j= ∑1 ? ∑ 1 = 4 ，i =1 j =1∵?1 1 ? a i , j ? ? ? & 1 ，对所有 i、j ， ?r s ? j ? ? i至少存在 5 项 a i , j ?∴?1 1 ? ? ?a i , j ≥ 1 至少有 5 个。 ? ?&0?? ?r s ? ?s j & ri i j ? ? ?故 结论成立。 评注：本题充分体现了赋值方法、表格、抽屉原理和换序求和 七、瞄准目标，跟踪配对21 例 1 子集 A ? S = { ,2,3, L ,50} 满足：任意两个不同的元素之和不能被 7 整除。求 1card ( A) 的最大值。解：按照 mod 7 对 S 进行划分：S 0 = {7,14,21,28,35,42,49} ? card (S 0 ) = 7 ，S1 = { ,8,15,22,29,36,43,50} ? card (S1 ) = 8 ， 1 S 2 = {2,9,16,23,30,37,44} ? card (S 2 ) = 7 ，S 3 = {3,10,17,24,31,38,45} ? card (S 3 ) = 7 ，S 4 = {4,11,18,25,32,39,46} ? card (S 4 ) = 7 ，S 5 = {5,12,19,26,33,40,47} ? card (S 5 ) = 7 ， S 6 = {6,13,20,27,34,41,48} ? card (S 6 ) = 7 ，取 A = S1 ∪ S 2 ∪ S 3 ∪ {7} 记的元素个数最多的子集，元素个数为 23。 例 2 设 A ? M = { ,2,3, L ,1995} ，并且当 x ∈ A 时，总有 15 x ? A ，求 card ( A) 的最 1 大值。 解：把 S 中的数按照 15 的倍数分类： 1 2 134 138 … 15 15 × 15 ∴ 15×2 15 × 15 ×2 15×3 15 × 15 ×3 15×4 15 × 15 ×4 15×5 15 × 15 ×5139 15×6 15 × 15 ×6140 15×7 15 × 15 ×7141 15×8 15 × 15 ×8… …133 15 × 133A = { ,2,3,L,8} ∪ { ,135,L,1995} 是元素个数最多的子集，其元素个数为 1 1341870。 注：从后向前拆分：{1,2,3,L,1995} = {,L ,134}∪ {133,132,L ,9} ∪ {8,7,L ,2,1} 。例 3 设 A ? S = { ,2,3, L ,2002} ，并且任意两个数之差既不等于 4，也不等于 7，求 1card ( A) 的最大值；如果 A ? S = { ,2,3,L,2006} ， card ( A) 的最大值是多少？ 1解：从 1，2，3，4，5，6，7，8，9，10，11 这 11 个数中最多选出 1，4，6，7，9 五 个数符合要求。这 5 个数都加上 11 得到的 5 个数也符合要求，由 2002 = 11 × 182 ，所以，card ( A) 的最大值 ≥ 182 × 5 = 910 。22 如果 card ( A) ≥ 911 = 182 × 5 + 1 ，则 182 个数组： （1，2，3，4，5，6，7，8，9，10， 11）（12，13，14，15，16，17，18，19，20，21，22） 、 ，…， （，， ，，，2002）中，至少有一个数组包含子集 A 的至少 6 个数，不妨设这组数是（1，2，3，4，5，6，7，8，9，10，11） ，再将这组数分成 5 个小组 （4，7，11）（3，10）（2，6）（5，9）（1，8） ， ， ， ， ，则其中必有一组中存在 2 个数是前述 6 个数中的，故 A 中必有 2 个数，它们的差是 4 或 7。故 card ( A) 的最大值 & 910 。 ∴card ( A) 的最大值是 910。如果 S = { ,2,3, L ,2006} ，由 2006 = 11 × 182 + 4 ，由上述推证，可得 card ( A) 的最大 1 值是 914。 例 4 已知 M ? S = { ,2,3, L ,100}中没有一个数是另一个数的 2 倍，求 card (M ) 的最 1 大值。 1 2 3 4 5 6 … 12 … 25 … 50 … 100 2 4 6 8 10 12 … 24 … 50 … 100 4 8 12 16 20 24 … 48 … 100 8 16 24 32 40 48 … 96 16 32 48 64 80 96 32 64 96 64 4 3 3card (M ) 的最大值是： 100 ? 50 + 25 ? 12 + 6 ? 3 + 1 = 50 + 13 + 4 = 67 。 M = { ,3,5,L,99} ∪ { } 1例 5 对 Φ ≠ X ? M = { ,2,3, L ,1000} ， α X 为 X 中的最大数和最小数之和，求所有 1 令 这些数 α X 的平均数。 解法一：将集合 M 的所有非空子集进行配对，对 Φ ≠ X ? M ，令X '= { 1001 ? x x ∈ X }23 则 X 1 ≠ X 2 ? X 1 ≠ X 2 ，于是所有的非空子集可以分成两类：' 'T1 = {X X ? M , X ' ≠ X }， T1 = {X X ? M , X ' = X }对 X ∈ T1 ? α X + α X ' = 1001 ，X ∈ T2 ? α X = 1001 ， 所以， 所求的平均数为 1001。 解法二：考虑每个元素对平均数的贡献，采用换序求和方法。 例 6 设集合 A = { ,2,3, L ,336}，若 A 的二元子集 B = {a, b}满足 17 a + b ，则称 B 具 1 有性质 P。 （1）求 A 的具有性质 P 的二元子集的个数； （2） A 的一组二元子集 S1 , S 2 , L , S k ，两两不相交，并且具有性质 P ， k 的最大值。 例 7 设 S = { ,2,3,4}，数列 a1 , a 2 , L , a n 满足：任取非空 B ? S ，在该数列中有相邻的 1card (B ) 项恰好组成集合 B ，求 n 的最小值。例 8 对 n 元 集 合 S 的 两 个 子 集 A、B ， 求 的 card ( A ∩ B ) ， 试 计 算f =A? S , B ? S∑ card ( A ∩ B ) 。A? S B ? S解： f =1 ∑ ∑ card ( A ∩ B ) = ∑ 2 ∑ [card ( A ∩ B ) + card ( A ∩ C B )]A? S B? S S1 1 2 n ?1 n n ?1 = ∑ ∑ card ( A) = ∑ 2 card ( A) = 2 ∑ card ( A) = 2 A? S B ? S 2 A? S 2 A? S 2 n?1 = ? n ? 2 n = n ? 4 n?1 。 2例 9 当 (a1 , a 2 , L , a n ) 取遍 (1,2, L , n ) 的排列时，求A? S∑ [card ( A) + card (C A)]Sf = (a1 ? a 2 ) + (a 2 ? a3 ) + L + (a n ?1 ? a n )2 22的平均值。 对相异两数 x、y ∈ { ,2, L , n} ，( x ? y ) 共出现在 2 ? (n ? 1)! 个 f 中， 1 解： 共有 n! 个 f ，2所以，所有 f 的平均数为24 2 ? (n ? 1)!1≤ x & y ≤ n∑ (x ? y )2n!==2 ? (n ? 1)! ∑≤nx 2 + y 2 ? 2 xy n! 1≤ x & y()2 ? (n ? 1)! n y ?1 2 ∑∑ x + y 2 ? 2 xy n! y = 2 x =1()=2 ? (n ? 1)! n ? 1 ? ∑ ? 6 ( y ? 1)y(2 y ? 1) + ( y ? 1)y 2 ? y 2 ( y ? 1)? n! ? y =2 ? 2 ? (n ? 1)! n 1 ∑ 6 ( y ? 1)y(2 y ? 1) n! y =2==(n ? 1)!3n!∑ (2 yn y=23? 3y 2 + yn)n(n ? 1)! ? n == 3n! ? 2 ?? ?∑ 2 y ? ∑ 3 y + ∑ y ? 3n! ? y = 2 y =2 y =2 ?3 2(n ? 1)! ? 1 n 2 (n + 1)2 ? 2 ? 1 n(n + 1)(2n + 1) + 3 + 1 n(n + 1) ? 1?2 2 ? ?=(n ? 1)! ? n 4 ? n 23n! 2=1 3 n n 2 ? 1 = C n +1 。 6()评注：如果利用表格帮助直观，则可由上三角直接得到f =2 n ?1 i 2 1 n ?1 1 n ?1 j = i (i + 1)(2i + 1) = ∑∑ ∑ ∑ [2i(i + 1)(i + 2) ? 3i(i + 1)] n i =1 j =1 3n i =1 3n i =1==1 n ?1 1 n ?1 1 2 Ai3+ 2 ? 3 Ai2+1 = ∑ ∑ 12Ci3+2 ? 6Ci2+1 = n 4C n4+ 2 ? 2C n3+1 3n i =1 3n i =11 (n + 2)(n + 1)(n ? 1) ? 1 (n + 1)(n ? 1) = 1 (n + 1)n(n ? 1) = C n3+1 。 6 3 6()()()八、递推计数方法 例 1 如果 T ? S = { ,2,3, L ,10} 中至少有 2 个元素， 1 且其中任意两个元素之差的绝对值 大于 1，则称子集 T 具有性质 P ，求 S 的所有具有性质 P 的子集的个数。 解：一般化，设 { ,2, L , n} 的具有性质 P 的所有子集的个数为 a n ，则 1a n+ 2 = a n +1 + a n + n n ∈ N * ， a1 = 0 ， a 2 = 0 ， a 3 = 1 ， a 4 = 3递推，可得 a10 = 133 。()25 例 2 整数 1,2,3, L , n 的排列满足：每个数或者大于它前面的所有数，或者小于它前面的 所有数，求这样排列的个数。 解：记所求的排列个数为 a n ，则 a1 = 1 ；对 n ≥ 2 ，如果 n 排在第 k (≥ 2 ) 位，则它后面n ? k 个数完全确定，即 n ? k , n ? k ? 1, L ,3,2,1 ；它前面的 k ? 1 个数有 a k ?1 种排法（每个数只和它前面的数相比较） ；当 n 排在第一位时，只有一种排法 n, n ? 1, L ,3,2,1 。所以，由 加法原理，得a n = 1 + a1 + a 2 + L + a n ?1 (n ≥ 2) 。可以证明： a n = 2n ?1(n ∈ N )。*评注： 也可以根据末位数是 1 或 n ， 直接创建一个根简单的递推关系 a n = 2a n ?1 (n ≥ 2 ) 。 例 3 用正整数组成数列，使数列的每一项都比它前一项的平方还大，而最后一项均为 1969（这类数列可以有不同的长度） 。证明：这种数列的个数少于 1969。 解：把以 n 结尾并具有题目中所述性质的数列的个数记为 f (n ) ，则f (1) = 1, f (2) = 2, f (3) = 2, f (4) = 2 。对 n ≥ 5 ，目标是证明： f (n ) & n ；假设对所有 k & n ，总有 f (k ) ≤ k ；则当 k = n 时， 把所有满足要求的数列的最后一项 n 去掉，那么除了只有一项“ n ”的数列之外，其余数列 都变成最后一项小于 n 的数列，并且仍具有题目要求的性质，故由归纳假设，得f (n ) ≤ 1 + ∑ f (k ) ≤ 1 + ∑ k = 1 +k =1 k =1[ n][ n]1 2[ n ][ n ]+ 1) ≤ 1 + 1 n ( ( 2n +1 & n 。)故f (1969) & 1969 。例 4 正整数 1，2，3，4，5，6 的排列 (n1 , n 2 , n3 , n 4 , n5 , n6 ) 具有具有如下性质：对于i ∈ { ,2,3,4,5}， (n1 , n 2 , L , ni ) 都不是 (1,2, L, i ) 的排列。求这种排列的总数。 1解法：设 (m1 , m2 , m3 , m 4 , m5 , m6 ) 是不满足条件的排列，则存在 2 ≤ i ≤ 6 ，使得{mi , ni +1 ,L , m6 } = {i, i + 1,L,6}，{m , njj +1, L , m6 } ≠ { j , j + 1, L ,6}， j = i + 1, i + 2, L 6 。26 其中当 i = 6 时，后一个式子不存在。记满足上述条件的排列 (mi , ni +1 , L , m6 ) 的个数为f (i ) ，则不符合条件的排列的总数 S = ∑ f (i )(i ? 1)! 。i=26∵f (6) = 1 ， f (5) = 2!? f (6) = 1 ， f (4 ) = 3!? f (5) ? 2! f (6) = 3 ， f (3) = 4!? f (4) ? 2! f (5) ? 3! f (6) = 13 ， f (2 ) = 5!? f (3) ? 2! f (4) ? 3! f (5) ? 4! f (6) = 71 ，∴ S = 71 + 13 × 2!+3 × 3!+1 × 4!+1 × 5! = 259 。 故 符合条件的排列的总数为： 6!?259 = 461 。 例 5 给 200 人依次编号为 1，2，3，…，2000，如果某几个人（可以 1 人，但不可无人） 的编号之和是 5 的倍数，则称之为“优团” 。求这 2000 人可组成所有“优团”的个数。 解 ： 令 S n = { ,2,3, L , n} ， 对 其 子 集 ， 按 其 中 数 之 和 mod 5 的 值 分 成 5 类 ： 1M j ( j = 0,1,2,3,4 ) ，记这 5 类子集的个数依次为 a n , bn , c n , d n , en ，则本题目标是求 a 2000 ，一般些，先求出 a 5 n 。 按定义，有a n + bn + c n + d n + en = 2 n ， n = 1,2,3, La 5n = 2a5 n ?1 ， a 5n ?1 = a 5 n? 2 + b5n ? 2 ， a 5n ? 2 = a 5 n?3 + c5n ?3 ， b5 n? 2 = b5 n ?3 + d 5n ?3 ，∴a 5n = 2(a 5n ? 2 + b5 n? 2 ) = 2(a5 n ?3 + c5 n?3 + b5n ?3 + d 5 n?3 ) a 5 n = 2 5 n ? 2 ? 2e 5 n ? 3∵e 5n ? 3 = e 5 n ? 4 + c 5n ? 4 , e 5n ? 4 = e 5n ? 5 + d 5 n ? 5 ， c5n ? 4 = c5 n?5 + b5n ?5 a 5n = 2 5 n ? 2 ? 2(e5n ? 4 + c5 n ? 4 ) = 2 5n ? 2 ? 2(e5n ?5 + d 5n ?5 + c5n ?5 + b5 n ?5 ) = 2 5 n ? 2 ? 2 2 5 n ? 5 ? a 5 n ? 5 = 3 × 2 5 n ? 4 + 2a 5 n ? 5 a5n = 3 × 2 n × 2 4n ? 1 + 2n 。 4 2 ?1∴()故27 ∴a 2000 =2 400 21600 + 4 。 5 2 400 21600 + 4 ? 1。 5()除掉空集，可知，优团的个数为 a 2000 ? 1 =()九、元素与子集的结合关系对应表L 1 取 A1、A2、 、Ak ? { ,2,L , n}(n ∈ N , n ≥ 2 ) ， 记 元 素 i 含 在 取 定 的 d i 个 子 集 中(i = 1,2,L , n ) ； 当且仅当 i ∈ A j 时， 在下表第 i 行第 j 列填入 1 (i = 1,2,L , j = 1,2,L , k ) 。A11 2 3 … 1 1 1 1 1 1 1 1A2A31…Aj…Ak1 1i…n（1）统计表中 1 的个数，就是计算表中 1 的总和：分别按行、列先后统计，算两次，得∑ d i = a = ∑ card ( Ai ) 。i =1 i =1nk（2）当且仅当 t ∈ Ai ∩ A j 时，称 Ai , A j 为关联于元素 t 的一个子集对，统计与所有元素 关联的子集对总数，得{}∑Ci =1n2 di=b=1≤ i & j ≤ k∑ card (A ∩ A ) 。i j这是两个及其常用的关系等式，通常表现为（1）是条件，对（2）应用 Caughy 不等式 或逐步调整法，求最值，推证存在性。 十、等价关系 10．1 关系：在集合的元素之间引入一种关系 R ，当两个元素 a、b 之间具有这种关系时， 记作 aRb ，否则记作 a Rb 。 定 理 ： 集 合 A 上 的 一 种 关 系 R ， 确 定 A 到 W = {r , f } 的 一 个 映 射 R : A → W ，aRb ? f (a ) = f (b )，?a、b ∈ R ；反之，一个映射 R : A → W 给出集合 A 中元素之间的28 一种关系 aRb ? f (a ) = f (b )，?a、b ∈ R 。 10．2 等价关系：在集合 A 的元素之间如果存在一种关系 R（如果 A 的两个元素 x、y 之间 有这种关系，就记作 xRy ；如果 A 的两个元素 x、y 之间没有这种关系，就记作 x R y ）满 足三个条件： ； ；③ ， ① aRa, ?a ∈ A（反身性） ② aRb ? bRa（对称性） (aRb ) ∧ (bRc ) ? aRc（传递性） 则称关系 R 为集合 A 的元素间的一个等价关系。譬如：数的相等、图形的全等、数的同余、 同班同学、同母生、同国籍、同省份，等等，这些都是等价关系；但是，数之间的大于、人 之间的朋友、同学，等，这些都不是等价关系。 等价关系要求的三个条件时相互独立的，思考下面的推理有什么错误？ 假设集合 A 上的一个关系 R 满足对称性和传递性，则 aRb ? bRa ? aRa ，即由对称性与传递性可以推出反身性，为什么？ 10．3 等价分类：如果非空集合 A 的元素之间定义了一种等价关系 R ，则可以把其中相互等 价的元素归入一类，譬如 A 中与 a∈ A 的所有元素组成 A 的一个子集，记作[a] = {x ∈ A xRa}，这个子集称为元素 a 的等价类，也称 [a] 中其它元素的等价类；可以证明： 定理 1： [a ] ≠ Φ 。 定理 2：如果 a、b ∈ A ，当 a Rb ，则 [a ] ∩ [b ] = Φ ；当 aRb 时， [a ] = [b ] 。 定 理 3 ： 如 果 A 的 元 素 可 以 组 成 k 个 互 不 相 同 的 等 价 类 [a1 ], [a 2 ], L , [a k ] ， 则A = [a1 ] ∪ [a 2 ] ∪ L ∪ [a k ] ， 且 [ai ] ∩ a j ≠ Φ (1 ≤ i & j ≤ k ) 。 这 时 ， 就 称 全 体等 价 类[ ][a1 ], [a2 ],L, [ak ] 构成集合 A 的一个 k ? 等价划分（ k 类） 。例 1 整数集 Z 可以按照 mod n 划分成 n 个同余类： Z = [0] ∪ [1] ∪ [2] ∪ L ∪ [n ? 1]。 十一、集合的划分 11． 1 定义：如果存在集合 A 的 k 个非空子集 A1 , A2 , L , Ak ， 使得 A =kUAi =1i，并 且Ai ∩ A j = Φ(1 ≤ i & j ≤ n ) ，则称子集族 {A1 , A2 , L , Ak } 构成集合 A 的一个 k ? 划分；其中每个子集 Ai 成为一个快。 定理 4：集合 A 上的等价关系与集合 A 的划分是一一对应的。 11．2 定义：一个 n 元集合的全部 k ? 划分的个数，称为第二类 Stirling 数，记作 S (n, k ) 。 这种数有如下性质：29 ① S (n,1) = 1 ； ② S (n, n ) = 1 ； ③ S (n, k ) = 0(k & n ) ； ④ S (n + 1, k ) = S (n, k ? 1) + kS (n, k )(1 ≤ k ≤ n ) ； ⑤ S (n,2 ) = 2n ?1?1；2⑥ S (n, n ? 1) = C n ； ⑦ S (n, k ) =m = k ?1∑Cnm n? S (m, k ? 1) 。其中①、②、③都是平凡的，下面我们证明④～⑦。 证明：④把 n + 1 元集合 A = {a1 , a 2 , L , a n +1 }的所有 k ? 划分分成两类： 其一， {a n +1 } 是 A 的 k ? 划分中的一块，这时只需在对 n 元集合 C A {a n +1 } 作 k ?1 ? 划 分，有 S (n, k ? 1) 种，故 A 的这类 k ? 划分共有 S (n, k ? 1) 种。 其二， {a n +1 } 不是 A 的 k ? 划分中的一块，先对 n 元集合 C A {a n +1 } 作 k ? 划分，共有1 S (n, k ) 种方法，再将 a n+1 添加到 k 块中的某一块，有 C k 种方法，每一种添加法解得到 A 的一个 k 划分，共有 kS (n, k ) 个划分。 ∴S (n + 1, k ) = S (n, k ? 1) + kS (n, k ) 。⑤利用④把 S (n,2 ) 作如下展开：S (n,2) = S (n ? 1,1) + 2S (n ? 1,2) = 1 + 2[S (n ? 2,1) + 2S (n ? 2,1)]= 1 + 2 + 2 2 S (n ? 2,2 )= LL= 1 + 2 + 2 2 + L + 2 n? 2 S (2,2 ) = 1 + 2 + 2 2 + L + 2 n ? 2 = 2 n ?1 ? 1 。⑥利用④把 S (n, n ? 1) 作如下展开：S (n, n ? 1) = S (n ? 1, n ? 2) + (n ? 1)S (n ? 1, n ? 1) = S (n ? 1, n ? 2) + (n ? 1)30 = S (n ? 2, n ? 3) + (n ? 2) + (n ? 1)= LL = S (2,1) + 2 + 3 + L + (n ? 1) = 1 + 2 + 3 + L + (n ? 1)= n(n ? 1) 2 = Cn 2⑦ S (n + 1, k ) 是集合 A = {a1 , a 2 , L , a n , a n +1 } 的 k 划分数。对于 A 的一个 k 划分，设包含a n+1 的那一块为 B ，则其余的 k ? 1 块构成集合 C A B 的一个 k ? 1 划分；反过来，给定 A 的一个含 a n +1 的子集 B ，若 card (C A B ) ≥ k ? 1 ，则 C A B 的一个 k ? 1 划分连同 B 就构成 A 的 一个 k 划分。 如下构造 A 的 k 划分：先取 A 的一个不含 a n +1 的子集 C ，使得 card (C ) ≥ k ? 1 ；作 C 的一 个 k ? 1 划分，再拼上 C A C 就构成 A 的一个 k 划分；而 m = card ( C ) ∈ {k ? 1, k ,L , n ? 1} ， 并且取定了 m ，有 C n 种方法选择 C ，每个 C 的 k ? 1 划分数有 S (m, k ? 1) ，所以，有mS ( n + 1, k ) =m = k ?1） ∑ C S ( m, k ? 1) （没有重复！m nn ?1以上算法是构造性的，同时也给出了划分的构造方法。譬如：1 例 1 S (4,2 ) = 2 3 ? 1 = 7 ，说明集合 A = { ,2,3,4} 有 7 个 2 ? 划分，可以按上述算法写出来：{1,2,3,4} = {1,2} ∪ {3,4} = {1,3}∪ {2,4} = {1,4} ∪ {2,3}= {2,3,4} ∪ { } = { ,3,4} ∪ {2} = { ,2,4} ∪ {3} = { ,2,3} ∪ {4} 1 1 1 1由此及 S (5,2 ) = 2 4 ? 1 = 15 ，可以作出 5 元集合 A = { ,2,3,4,5}的 15 个 2 ? 划分，它们是： 1{1,2,3,4,5} = {5} ∪ {1,2,3,4} = {4,5} ∪ {1,2,3} = {4}∪ {1,2,3,5} = {3,4,5}∪ {1,2}= {3,4} ∪ { ,2,5} = {3,5} ∪ { ,2,4} = {3} ∪ { ,2,4,5} = { ,3,5} ∪ {2,4} 1 1 1 1 = { ,3} ∪ {2,4,5} = { ,3,4,5} ∪ {2} = { ,3,4} ∪ {2,5} = {2,3,5} ∪ { ,4} 1 1 1 1 = {2,3} ∪ { ,4,5} = {2,3,4,5} ∪ { } = {2,3,4} ∪ { ,5} 1 1 111．3 有限集合的 m 类平均划分31 定义：如果数集 X = { ,2,3, L , n}的一个 m 划分 1X = U Ai (m ≥ 2 )i =1m满足条件? ? n? ?card ( Ai ) = card (A j )? = m ? ? ? ? (1 ≤ i & j ≤ n ) ? ? n(n + 1) ? ? ∑ x = ∑ x? = ? ? x∈Ai 2m ? x∈A j ? ? 则称这个划分为集合 X 的 m 类平均划分。定理：如果数集 X = { ,2, L , n} 有 m 类平均划分，则 1 是， m 也是奇数；反之，也成立。 证明： (? ) 若 X 有 m 类平均划分，则存在 p ∈ N * ， p & 1 ，使得 n = mp ，所以每一类的元素之 和为n = p ∈ N * ，并且当 p 是奇数 mx∈Ai∑x = m∑x =x∈ A1n(n + 1) mp(mp + 1) p(mp + 1) = = ∈ N* 2m 2m 2∴当 p 是奇数时， (2, p ) = 1 ? 2 mp + 1 ? mp 是奇数 ? m 是奇数。(?) 已知数集 X = {1,2,L, n}，n = mp ，m、p ∈ N * , m ≥ 2 但除去“ p 是奇数，且 m是偶数”的情况。 ①若 p = 2k ，则 n = 2km ，把 X 中的数如下排成 2k × m 数阵：1 2m 2m + 1 4m L 2km2 2m ? 1 2m + 2 4m ? 1 L 2km ? 1L L L L L Lm ?1 m+2 3m ? 1 3m + 2 Lm m +1 3m 3m + 1 L2(k ? 1)m + 1 2(k ? 1)m + 2 L(2k ? 1)m ? 1 (2k ? 1)m (2k ? 1)m + 2 (2k ? 1)m + 1将第一列、第二列、…、第 m 列的数分别作成集合 A1 , A2 , L , Am ，则所得子集族{A1 , A2 ,L , Am }构成集合 X 的一个 m 类平均划分。* 则 ②若 p = 2k + 1 k ∈ N ， n = (2k + 1)m ，()∑ x = 2 m(2k + 1)[m(2k + 1) + 1]，所以，1x∈A32 m ∑ x ? “ m 是奇数 ? n 是奇数” 。x∈A先将 1,2, L , n 的后 n ? 3m （偶数）个连续正整数仿①排成 (2k + 1) ? 3 = 2k ? 1 行， m 列数阵；再把 1,2,3, L ,3m 排成 3 行 m 列，且各列之和 =3(3m + 1) 即可： 21 3m + 1 2 3m2 2mL Lm?2 m+25m ? 1 5m + 3 L 2 2m ?1 3m + 3 2 2m + 1m m +1 5m + 1 2(左 ← 右，先奇数位后偶数位) (左 ← 右，先偶数位后奇数位)这样排得的各列之和都是 11．4 置换的结构与计数(3m + 1) ? 3m = 3(3m + 1) 。2m 2设 A = { ,2,L , n} ， 则 称 映 射 f : A → A 为 集 合 A 的 一 个 置 换 。 任 取 一 个 置 换 1f : A → A ，构图 G ( A, E ) ：把 A = { ,2,L , n} 中的元素作为点，从 i 向 f (i ) 连一（有向） 1条边，得一有向图。任取 i ∈ A ，则存在最小正整数 k i ，使得 f( ki )(i ) = i ，那么图 G 有一条(k ?1) (k ) 中存在一条从 i 出发又回到 i 的圈： i → f (i ) → f (2 ) (i ) → L → f i (i ) → f i (i ) = i ，叫轮换；从 G 中取出这个圈，对剩下的元素如此操作，得到图 G 若干个不相交的圈（轮换） 组成。所以，如果在集合 A = { ,2,L , n} 的元素之间定义一个关系 R ： aRb ? ?l ∈ N ， 1*使得 f (l ) (a ) = b ，则这是一个等价关系，从而可得到集合 A 的一个 k ? 划分，其中每一块 就是一个轮换中的元素，k 就是组成置换 f : A → A 的不同轮换的个数。 设置换 f : A → A 有 λi 个长为 i 的轮换（圈）组成，则称 f : A → A 为 1 1 2 2 L nλ λ λn型的，这类置换的个数为n!∏ii =1n，所以要计算满足某种条件的置换的个数，首先要弄清楚满足这种条件的置换的λiλi !型。 11．5 第一类 stirling 数 定义：给定正整数 n ，则称关于 x 的 n 次多项式x ( x ? 1)( x ? 2 )L ( x ? n + 1) = s ( n, 0 ) + s ( n,1) x + s ( n, 2 ) x 2 + L + s ( n, n ) x n L 的系数 s ( n, 0 )，s ( n,1)，s ( n, 2 ) x ， ，s ( n, n ) 为第一类 stirling 数。233 递推公式： s ( n + 1, k ) = s ( n, k ? 1) ? ns ( n, k ) ， k ∈ {1, 2,L , n} 。 证明：由x ( x ? 1)( x ? 2 )L ( x ? n + 1) = ( s ( n, 0 ) + s ( n,1) x + s ( n, 2 ) x 2 + L + s ( n, n ) x n ) ( x ? n )= ? ns ( n, 0 ) + ( s ( n, 0 ) ? ns ( n,1) ) x + ( s ( n,1) ? ns ( n, 2 ) ) x 2 +L + ( s ( n, n ? 1) ? ns ( n, n ) ) x n + s ( n, n ) x n +1∴s ( n + 1, k ) = s ( n, k ? 1) ? ns ( n, k ) ， k ∈ {1, 2,L , n} 。11．6 集合划分的例 例 1 能否把所有正整数分组，使得第 k 组恰好有 k 个数 (k = 1,2,3, L , ) ，并且使得每组 中的所有数之和都恰好为某个正整数的平方？ 解：正整数集 N 得这种划分是存在的，譬如：*A1 = { }， A2 = {2,2 7 ? 2}， A3 = { ,4,3 7 ? 3 ? 4}，……， 1 3Ak = a1 , a 2 , L , a k ?1 , k 7 ? a1 ? a 2 ? L ? a k ?1 ， k = 4,5,6, L 。其中 Ak 的前 k ? 1 个数是前 k ? 1 个集合 A1 , A2 , L , Ak ?1 未曾出现过的最小的 k ? 1 个正整 数。 例 2 给定正有理数 c ≠ 1 ， 证明： 正整数集合 N 可以表示成两个不不相交的子集 A、B*{}的并，使得同一子集的任何两个数之比都不等于 c 。 证明：我们递归地构造集合 A、B 。令 1 ∈ A ；当 1,2, L , n 已按要求分配到集合 A、B 中之后，我们来如下安排 n + 1 ：如果存在 k1 ∈ { ,2, L , n}，使得 1 到不含 k1 的那个子集中；如果存在 k 2 ∈ { ,2, L , n} ，使得 1k1 = c ，则把 n + 1 分配 n +1n +1 = c ，则把 n + 1 分配到不含 k2k 2 的那个子集中；如果上述 k1、k 2 都不存在，则把把 n + 1 随意分配到子集 A、B 中，并使k1 n +1 * &1& ，故 k1、k 2 不可能同时存在。故正整数集 N 存在 n +1 k2两者都不是空集；由于 符合题意的 2 划分。例 3 将集合 S = { ,2,3, L ,100} 分成 7 个子集，求证：其中至少有一个子集，要么含有 1 4 个数 a、b、c、d ，使得 a + b = c + d ，要么含有 3 个数 e、f、g ，使得 e + f = 2 g 。34 证明：考虑从元素较多的那个子集入手。 ∵ 100 = 14 × 7 + 2 ∴ 必有一个子集含有至少 15 个数，设 A = {a1 , a 2 , L , a15 , L , a k }(k ≥ 15) ，不妨设1 ≤ a1 & a 2 & L & a15 & L & a k ， 则 由 其 中 较 小 的 15 个 数 a1 , a 2 , L , a15 可 组 成2 C15 = 105 & 99 个差 a j ? ai (1 ≤ i & j ≤ 15) ∈ { ,2, L ,99}，由抽屉原理，这些差中必存在相 1等 数 ， 不 妨 设 a j ? a k = ai ? a h ( j & i ) 。 若 h = j ， 则 a i + a k = 2a j ； 若 j ≠ h ， 则a k , a h , a j , a k 互不相同，并且 a j + a h = a i + a k 。例 4 给定 n 个正整数： a1 = 1, a 2 , a 3 , L , a n ，其中 a i ≤ a i +1 ≤ 2ai (i = 1,2, L , n ? 1) ， 并且所有 n 个数之和为偶数。问：能否把这些整数分成两组，使得两组中整数之和相等？ 解：首先，将 a n、a n ?1 分别放入 A、B 两组，然后再依次放入 a n ? 2 , a n ?3 , L , a 2 , a1 ，具 体方法是：每次放入和数较小的一组之中；当两组和数相等时，可任选一组放入；直到放完a1 为止，就把所给的正整数分成了 A、B 两组。∵a i ≤ a i +1 ≤ 2ai ? ai ≤ 2 i ?1 a1 = 2 i ?1 ， a n ≤ 2 n?1 ， a n?1 ≤ 2 n ? 2 ， a n? 2 ≤ 2 n ?3 ，…， a 2 ≤ 2 ， a n ≤ 1 。∴∵ ∴0 ≤ a n ? a n ?1 ≤ a n ?1 ，将 a n、a n ?1 分别放入 A、B 两组之后， 0 ≤∑x?∑x ≤ ax∈A x∈Bn ?1，接着，应该把a n? 2 ≤ 2 n ?3 放入 B 组，这时有∑ x ? ∑ x = a ? (ax∈A x∈B nn ?1+ a n ? 2 ) = (a n ? a n ?1 ) ? a n ? 2 ≤ a n ?1 ? a n ? 2 ≤ a n ? 2 ， + a n ? 2 ) ≥ a n ? (a n + a n ? 2 ) = ? a n ? 2∑ x ? ∑ x = a ? (ax∈A x∈B nn ?1故∑x?∑x ≤ ax∈ A x∈Bn?2 。假设放完 a n , a n ?1 , L , a i 之后，有∑x?∑x ≤ ax∈ A x∈Bi，接下来的怎么放 a i ?1 ，应根据∑ x ? ∑ x 的正负确定。x∈ A x∈B若0 ≤∑ x ? ∑ x ≤ a ，则令 ax∈A x∈B ii ?1∈ B ，这时，有35 ? a i ?1 ≤ ∑ x ? ∑ x ≤ ai ? ai ?1 ≤ ai ?1 ，从而 ∑ x ? ∑ x ≤ a i ?1 ；x∈ A x∈B x∈ A x∈B若 ? ai ≤∑ x ? ∑ x ≤ 0 ，则令 ax∈A x∈B x∈ Ai ?1∈ A ，这时，有? a i ?1 ≤ a i ?1 ? a i ≤ ∑ x ? ∑ x ≤ ai ?1 ，从而也有 ∑ x ? ∑ x ≤ a i ?1 。x∈B x∈ A x∈B故放完 a n , a n ?1 , L , a i , a i ?1 之后，应有∑x?∑x ≤ ax∈ A x∈Bi ?1 。由数学归纳法，可知，按上述方法，放完 a n , a n ?1 , L , a i 时，总成立∑x?∑x ≤ a 。x∈ A x∈B i 1∴按上述方法，依次放完 a n , a n ?1 ,L , a 2 , a1 时，应该成立nn n∑x?∑x ≤ ax∈ A x∈B= 1，又2 ∑ a i ， ∑ x ? ∑ x = ∑ ai ? 2∑ x ≡ ∑ a i (mod 2 ) ，i =1x∈A x∈B i =1 x∈B i =1∴2∑ x ? ∑ x ? ∑ x ? ∑ x = 0，x∈A x∈B x∈A x∈B故按上述方法依次放完 a n , a n ?1 ,L , a 2 , a1 ，有∑x = ∑x。x∈A x∈B评注：自然应从最自然的方法入手。 例 5 试证：对每个大于 1 的整数 r ，都能找到一个最小的正整数 h(r ) ，使得在集合{1,2,L, h(r )}的 任 何 r ? 划 分 中 ， 都 存 在 整 数 a ≥ 0 及 1≤ x ≤ y ， 满 足a + x, a + y, a + x + y 含于划分的同一组中。证明：先证 h(r ) ≥ 2r ，考察集合 { ,2, L ,2r ? 1}的如下划分： 1{1,1 + r}, {2,2 + r},L, {r ? 1,2r ? 1}, {r}。如果存在整数 a ≥ 0 及 1 ≤ x ≤ y ，使得 a + x, a + y , a + x + y 含于同一组中，由这三个 数中至少有两个不等，所以，它们不能同在 {r }组中。设它们都在 {k , k + r }(1 ≤ k ≤ r ? 1) ， 则必有?x = y = k ? a ?a + x = a + y = k ?? ，矛盾！ ? ?a + x + y = k + r ?a = k ? r & 0故 不存在满足要求的整数 a ≥ 0 及 1 ≤ x ≤ y ，所以 h(r ) ≥ 2r 。36 再证： h(r ) = 2r 满足要求。1 则 对 { ,2, L ,2r ? 1,2r} 的任一 r ? 划分， r , r + 1, r + 2, L ,2r 这 r + 1 个正整数中必有两个数 u、v 含于同一组，不妨设 u & v ，令a = 2u ? v(≥ 0), x = y = v ? u (≥ 1) 。则a + x = a + y = u ， a + x + y = v 在同一组。故h(r ) 的最小值是 2r 。*例 6 设k ∈ N ， 集合 M k = 2k + k ,2k + k + 1,2k + k + 2, L ,2k + 3k 是否存在 22 2 2 2{}－划分，使得两个子集中个数的平方和相等？ 解：答案是肯定的，譬如，取Ak = 2k 2 + k ,2k 2 + k + 1,2k 2 + k + 2, L ,2k 2 + 2k ， Bk = 2k 2 + 2k + 1,2k 2 + 2k + 2,2k 2 + k + 2, L ,2k 2 + 3k ，则{ {}}M k = Ak ∪ Bk ，且 Ak ∩ Bk = Φ 。计算：x∈Ak∑x2?x∈Bk∑x22= ∑ 2k 2 + k + i ? ∑ 2 k 2 + 2 k + i2 i =0 i =1kk()k()2= (2k2+ k ) + ∑ [(2ki =1 k 22+ k + i ? 2 k 2 + 2k + i) (2)]2= 2k 2 + k = 2k 2 + k∴x∈Ak() ? ∑ k (4ki =12+ 3k + 2i)()2? k 4k 3 + 4k 2 + k = 02()∑x2=x∈Bk∑x。例 5 设 A = (0,1) ∩ Q ， ?p ∈ A ，且 ( p, q ) = 1 ，定义区间 q? p? ? p 1 p 1 ? I? ? = ? ? 2 , + 2 ? ? q ? ? q 4q q 4 q ? ? ? ? ?37 证明：数解p ∈A qU I? q ? 。 ? ?? ?? p?十二、正整数的分拆 12 ． 1 定 义 ： 正 整 数 n 的 一 个 k 分 拆 就 是 把 n 写 成 k 个 正 整 数 之 和 ：n = n1 + n 2 + L + n k k ∈ N * 的一种表示方法；其中 ni ∈ N * (1 ≤ i ≤ k ) 叫做该分拆的的部分量；分拆分为有序分拆和无序分拆，在有序分拆中， ni ∈ N * (1 ≤ i ≤ k ) 叫做该有序分拆 的第 i 个部分量。 12．2 有序分拆的计数公式 ①正整数 n 的有序 k 分拆 n = n1 + n 2 + L + n k k ∈ N * 的个数等于不定方程()()x1 + x 2 + L + x k = nk ?1 的正整数解数 C n ?1 。②正整数 n 的要求第 i 个部分量 ni ≥ pi 的有序 k 分拆 n = n1 + n 2 + L + n k k ∈ N * 的个数 是 C k ?1k()。n+k ?∑ pi ?1i =1k ?1 ③正偶数 2n 的 k 分拆，要求个分量都是正偶数的有序分拆数为 C n ?1 。2n = n1 + n2 + L + nk ? n =n n1 n2 + +L+ k 2 2 2k ?1 2 ?1④正整数 n ≡ k (mod 2 ) 的满足个分量都是奇数的有序 k 分拆的个数为 C n + k 。 转化为n = n1 + n2 + L + nk ?的正整数解数 C n + k ，或2 ?1 k ?1n +1 n + k n1 + 1 n2 + 1 = + +L+ k 2 2 2 2n = n1 + n2 + L + nk ?的非负整数解数 C n ? k2 k ?1 + k ?1 ?1n +1 n + k n1 + 1 n2 + 1 = + +L+ k 2 2 2 2k? = C n +1 。 k 212．3 无序分拆的计数结论 正整数 n 的无序 k 分拆 n = n1 + n 2 + L + n k 的个数记作 B (n, k ) ，n 的所有无序分拆的38 个数记作 B (n ) ，则 ① B (n, k ) = 0(k & n ) ， B (n,1) = 1 ， B (n, n ) = 1 ； ② B (n ) =∑ B(n, k ) ；k =1n③ B (n + k , k ) = B (n,1) + B (n,2 ) + L + B (n, k ) 。 证明： n = n1 + n 2 + L + n k ，不妨设 n1 ≥ n 2 ≥ L ≥ nk ≥ 1 （无序可定序） 正整数 n 的至多 k 个分布量的无序分拆总数＝ B (n,1) + B (n,2 ) + L + B(n, k ) ，每个这 样的分拆可以表示为n = n1 + n 2 + L + n m + 0 + L + 0 ，共 k 个分布量，其中 n1 ≥ n 2 ≥ L ≥ n m ≥ 1(1 ≤ m ≤ k ) 。作映射 f : 把正整数 n 的这个 m 分拆映射到正整数n + k 的 k 分拆： n + k = (n1 + 1) + (n 2 + 1) + L + (n m + 1) + 1 + L + 1 ，共 k 个分布量，其中 n1 + 1 ≥ n 2 + 1 ≥ L ≥ n m + 1 ≥ 2(1 ≤ m ≤ k ) 。 可以证明： f 是双射，所以B(n + k , k ) = B(n,1) + B(n,2) + L + B(n, k )④正整数 n 的 2 分拆数 B (n,2 ) = ? ? 。 ?2? 证明：由二分拆 n = n1 + n 2 , n1 ≥ n 2 ≥ 1 ? n 2 ∈ ?1,2,3, L , ? ? ? ，所以有 2?n?? ?? n ?? ? ???n? B (n,2 ) = ? ? 。 ?2?⑤如果正整数 n 的无序 k 分拆中有 k i 个分量为 i (1 ≤ i ≤ n ) ，则该分拆可写为n = k1 ? 1 + k 2 ? 2 + L + k n ? n其中 k1 + k 2 + L + k n = k , k i ≥ 0(i = 1,2, L , n ) 。 例 1 若干个正整数之和等于 1976，求这些正整数之积的最大值。 解：因为和为 1976 的正整数有且只有有限组，所以，所求最大值是存在的。39 设 x1 + x 2 + L + x n = 1976 xi ∈ N , i = 1,2, L , n ， 下 面 应 用 逐 步 调 整 法 求*()f = x1 x 2 L x n 的最大值。①若存在某个 xi & 4 ，由 2 + ( xi ? 2 ) = xi ，且 2 × ( xi ? 2 ) = 2 xi ? 4 & xi ，所以，用两 个数 2 和 xi ? 2 代替一个数 xi 时，可使乘积 f 变大，故所有 xi ≤ 4 。 ②若存在某个 xi = 1 ，由 xi x j = x j & x i + x j ，所以用一个数 xi + x j 代替两个数 xi , x j 后，可使乘积 f 变大，故所有 xi ∈ {2,3,4} 。 ③由 4 = 2 + 2 = 2 × 2 = 4 ，若存在 xi = 4 ，则可用两个 2 代替一个 4，乘积 f 的值不 变，故可令所有 xi ∈ {2,3} 。r t 由 且 故若 r ≥ 3 ， ④综上所述， 乘积 f = 2 ? 3 (r、t ∈ N ) ； 2 + 2 + 2 = 3 + 3 ， 2 & 3 ，3 2则可用两个 3 代替三个 2，使得乘积 f 继续变大，故 r ∈ {0,1,2}。 ⑤由 1976 = 658 × 3 + 2 ，知 r = 1, s = 658 ，所以 f max = 2 × 3658。例 1 证明：除了有限个正整数之外，其他正整数 n 均可表示成 2005 个正整数之和：n = a1 + a 2 + L + a 2005并且满足 1 ≤ a1 & a 2 & L & a 2004 , a i ai +1 (i = 1,2,3, L ,2004 ) 。十三、分配问题汇总 把 n 个小球分配到 r 个盒子里，不同方法总数记为 f (n, r ) ；求解分配问题种数要考虑 以下三方面的因素： n 个球是完全相同的，还是完全不同的？ n 个盒子是完全相同的，还是 完全不同的；是否允许有空盒？各种分配问题的计数结果如下表：n 个小球不同 不同r 个盒子 是否允许有空盒 分配方案数不同 不同 允许 不允许数学模型 重元排列rnr!?S (n, r )不同相同允许∑ S (n, i )i =1n集合划分40 不同相同不允许S (n, r )不定方程r? C n +1?1 r相同不同允许x1 + x2 + L + xr = n的非负整数解数 不定方程相同不同不允许r ?1 C n ?1x1 + x2 + L + xr = n的正整数解数相同相同允许∑ B(n, i )i =1r正整数的无序分拆 相同 相同 不允许B(n, r )十四、卡特兰数 14．1 定义：一个凸 n 边形，通过不相交于形内的对角线，把这个凸 n 边形划分成若干个三 角形，不同划分的数目称为卡特兰数 ( Catalan ) ，记作 hn 。 14．2 引理：一个凸 n 边形，通过不相交于形内的对角线，把这个凸 n 边形划分成若干个三 角形，对角线的条数为 an = n ? 3 。 证明： a3 = 0 = 3 ? 3 。 假设 ak = k ? 3 ，则对凸 k + 1 边形，先任意作出一条对角线， 把这个凸 k + 1 边形分成一个凸 s 边形和一个凸 r 边形，则A1 An+1 An A2 Ak+1 Ak-1 Akak +1 = as + ar + 1 = ( s ? 3) + ( r ? 3) + 1 = s + r ? 5 。∵ ∴r + s = k + 3，ak +1 = s + r ? 5 = ( k + 3) ? 5 = ( k + 1) ? 3 ，an = n ? 3 。故14．3 初值： h2 = 1 ， h3 = 1 ， h4 = 2 ， h5 = 5 。 14．4 递推公式： （1） hn +1 = h2 hn + h3 hn ?1 + L + hn h2 ； （2） ( n ? 3) hn =n ( h3hn?1 + h4 hn? 2 + L + hn ?1h3 ) 。 241 Ak-1Ak证明： （1）如图， ?A1 Ak An +1 把凸 n + 1 边形分成一个凸 k 边 形和一个凸 ( n + 1) ? ( k ? 1) = n + 2 ? k 边形，这时不同分法共有A2 Ak+1A1hk hn + 2 ? k ，对 k = 2, L , n 求和，得 3,An An+1hn +1 = h2 hn + h3 hn ?1 + L + hn h2 。（2）对角线 A1 Ak 把把凸 n 边形分成一个凸 k 边形和一个凸A3 Ak- 1 Akn ? ( k ? 2 ) = n + 2 ? k 边形，这时不同分法共有 hk hn + 2 ? k ，对k = 3, L , n ? 1 求和，得 h3 hn ?1 + h4 hn ? 2 + L + hn ?1h3 。把 A1 依 4,次换成 A2、A3、 、An ，再求和，得 LA2A1 AnAn-1( n ? 3) hn = ( h3hn?1 + h4 hn? 2 + L + hn ?1h3 ) 。14．5 通项公式： hn =n 21 n?2 C2 n ? 4 ( n ≥ 3 ) 。 n ?1证明：由以上两个递推关系，得( n ? 3) hn = ( hn +1 ? 2h2 hn ) =∴n hn +1 ? nhn ， 2 h 2n ? 3 hn nhn +1 = 2 ( 2n ? 3) hn ，即 n +1 = 2? ? ，递推，得 n +1 n +1 nn 2hn +1 ? 2n ? 3 ? ? 2n ? 5 ? ? 1 h2 ? n ?1 ( 2n ? 3 ) !! ， = ? 2? ??? 2? ??L?? 2? ? ? = 2 ? n +1 ? n +1 ? ? n ? ( n + 1)! ? 3 2?故hn +1 = 2n ?1 ?( 2n ? 3)!! = ( 2n ? 2 )! = 1 C n ?1 ， h = 1 C n ?2 。 2 n? 2 n 2 n?4 n! n !? ( n ? 1) ! n n ?114．6 应用：广泛的应用问题的结果是卡特兰数。 定理：给定整点 A ( a, b ) 和 B ( m, n ) ，则 （1）从 A 到整点 B 存在一条由些率为 1 或 ?1 的斜线段构成的折线充要条件是? n ?b ≤ m? a ? ； ? ?2 m + n ? a ? b ?（2） 当整数 a、b、m、n 满足 （1） 的条件时， 由些率为 1 或 ?1 的斜线段构成联结 A、B1 2 的折线的条数是 Cm ? a( m + n ? a ?b )；（3）当整数 a、b、m、n 满足（1）的条件，并且 ??b & 0 时，由些率为 1 或 ?1 的斜线 ?n & 042 段构成联结 A、B 的折线条数等于从 A ' ( a, ?b ) 到 B ( m, n ) 的由些率为 1 或 ?1 的斜线段所 有折线条数； （4）当整数 a、b、m、n 满足（1）的条件，并且 ? 段构成的联结 A、B 的所有折线分成两类： ①与 x 轴有公共点的折线的条数是 C1 2 Cm ? a 1 ( m + n ? a +b ) 2 m?a?b & 0 时，由些率为 1 或 ?1 的斜线 ?n & 0；②与 x 轴没有公共点的折线的条数是( m + n ? a ?b )2 ? Cm ? a1( m + n ? a +b ).y A(m,n)(a,b)Ax O例 1 甲乙两人参加竞选，甲的选票 m 张，乙的选票 n 张，并且 m & n ；问：在 m + n 张 选票逐一唱票的过程中，求甲的得票数一直领先的点票纪录总数. 例 2 戏院票房有 2n 个人排队买票，每张票的价格 5 元，其中有 n 个人各持一张 5 元纸 币，另 n 个人各持一张 10 元纸币，售票处没有零钱找补. 问：使大家都能顺利买票而不至 于发生找补零钱困难的排队方法有多少种？ 例 3 甲乙两人打乒乓球，打成 14 :14 ，问：在比赛过程中，途中恰有一次比分相等外， 甲总领先的比分序列共有多少种？例 4 甲有 m 粒豆子，乙有 m + 2n 粒豆子 m、n ∈ N * ，甲乙两人以丢掷硬币为游戏， 出正面时，乙给甲 1 粒豆子，出反面时，甲给乙 1 粒豆子；如果某人的豆子输光，则游戏结 束；以 A 记恰好在第 m + 2n 次丢掷硬币后，甲把 m 粒豆子输光的掷序列的集合，求()card ( A) .43 练习题? f (1) = 1 ? n 。 （1）给代数式 a1a2 L an 添括号的不同方法数 f ( n ) 满足 ? f (n) = ∑ f (k ) f (n ? k ) ? ? k =1（2）由 n 个 1 和 n 个 0 组成一位 2n 为二进制数，要求从左到右扫描，1 的累计数不小于 0 的累计数，则满足这种条件的数共有 p2 n =1 n C2 n 。 n +1 2 n ?1 C2 n ? 2 。 n（3）从点 ( 0, 0 ) 到 ( n, n ) 除端点外不接触直线 y = x 的路径条数为 qn =（4）有 n 个叶子的完}
热门搜索：
&&查看话题
求助，如何将一个图划分为几个大小相等的集群并集群间的互联度最小
如题，请教各位高手，
& & 采用什么算法，能够运用图论原理，针对一个给定的通信互联图，选择最优的集群大小值，将其划分为多个大小相等的集群，并使得集群间的互联度最小。
如附件中的通信互联图
想要把他划分为多个相等大小的集群，
&&1） 如何确定最优的集群大小值，如：是划分为3个集群大小为4的集群，还是4个集群大小为3的集群？？？
&&2）如何实现集群划分，当规模较大时，什么算法划分较快且效果较好
& &&&烦请告之相关算法，参考书及参考文献。
& &&&欢迎关注，先行谢过
学术必备与600万学术达人在线互动！
扫描下载送金币java 中计算数组 集合长度的方法
全部答案（共1个回答）
数组有length属性，直接数组名.length 就可以了。 不是length()方法。字符串是length().数组才是字符串的length属性.这个东西有个...
#include main (){int y,m,d,i,n=0;int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30...
错误挺多的ray是封装类不是数组。2.内部类运用错误。直接写代码块要用{},要不就写在构造函数或方法内。ray[0] {ArrayList array = ne...
(1) |A|=n.A的所有子集的个数为2^n.这是因为A中有1个空子集，C(n,1)个一个元素的子集，C(n,2)个2个元素的子集，...,C(n,k)个k个...
新建一个较长的数组，在把原数组的内容一个一个拷过去。或者可以使用vector。
答: 想学达内的java，请问学java之前需要有什么基础吗？？？
答: 这个要设计到JNI的开发,就是用Java来调用C语言的函数库,还要编写缓冲器来解决传输问题,还有就是网络协议一定要了解,做的时候要用多线程来控制你所有的缓冲器,...
答: 所谓的网络编程，不论c还是java，本质上都是通过socket进行数据传输；一般情况下可以使用的传输协议有tcp、udp、ftp等等，这些协议为网络变成提供基本...
大家还关注
确定举报此问题
举报原因(必选)：
广告或垃圾信息
激进时政或意识形态话题
不雅词句或人身攻击
侵犯他人隐私
其它违法和不良信息
报告，这不是个问题
报告原因(必选)：
这不是个问题
这个问题分类似乎错了
这个不是我熟悉的地区
相关问答：123456789101112131415请登录查看
JPA查询集合大小示例我们可以使用SIZE函数来获取实体计数。以下代码选择具有两个员工的部门。&SELECT d FROM Department d WHERE SIZE(d.employees) = 2&)
例子下面的代码来自PersonDaoImpl.java。
import java.util.L
import javax.persistence.EntityM
import javax.persistence.PersistenceC
import org.springframework.transaction.annotation.T
@Transactional
public class PersonDaoImpl {
public void test() {
prepareData();
List l = em.createQuery(
&SELECT d FROM Department d WHERE SIZE(d.employees) = 2&)
.getResultList();
for (Object p : l) {
printResult(p);
private void prepareData() {
Professor p = new Professor();
p.setId(0);
p.setName(&TOM&);
p.setSalary(1111L);
Department d = new Department();
d.setId(1);
d.setName(&Design&);
p.setDepartment(d);
d.getProfessors().add(p);
Phone phone = new Phone();
phone.setId(1);
phone.setNumber(&111-111-1111&);
phone.setProfessor(p);
em.persist(p);
em.persist(phone);
em.persist(d);
private static void printResult(Object result) {
if (result == null) {
System.out.print(&NULL&);
} else if (result instanceof Object[]) {
Object[] row = (Object[])
System.out.print(&[&);
for (int i = 0; i & row. i++) {
printResult(row[i]);
System.out.print(&]&);
} else if (result instanceof Long || result instanceof Double
|| result instanceof String) {
System.out.print(result.getClass().getName() + &: & + result);
System.out.print(result);
System.out.println();
@PersistenceContext
private EntityM
以下代码来自Address.java。
import javax.persistence.E
import javax.persistence.Id;
public class Address {
public int getId() {
public void setId(int id) {
public String getStreet() {
public void setStreet(String address) {
this.street =
public String getCity() {
public void setCity(String city) {
this.city =
public String getState() {
public void setState(String state) {
this.state =
public String getZip() {
public void setZip(String zip) {
this.zip =
public String toString() {
return &Address id: & + getId() +
&, street: & + getStreet() +
&, city: & + getCity() +
&, state: & + getState() +
&, zip: & + getZip();
以下代码来自Phone.java。
import javax.persistence.E
import javax.persistence.Id;
import javax.persistence.ManyToO
public class Phone {
@ManyToOne
public long getId() {
public void setId(long id) {
public String getNumber() {
public void setNumber(String phoneNo) {
this.number = phoneNo;
public String getType() {
public void setType(String phoneType) {
this.type = phoneT
public Professor getProfessor() {
public void setProfessor(Professor employee) {
this.employee =
public String toString() {
return &Phone id: & + getId() +
&, no: & + getNumber() +
&, type: & + getType();
下面的代码来自Department.java。
import java.util.HashS
import java.util.S
import javax.persistence.E
import javax.persistence.Id;
import javax.persistence.OneToM
public class Department {
@OneToMany(mappedBy=&department&)
private Set&Professor& employees = new HashSet&Professor&();
public int getId() {
public void setId(int deptNo) {
this.id = deptNo;
public String getName() {
public void setName(String deptName) {
this.name = deptN
public Set&Professor& getProfessors() {
public String toString() {
return &Department no: & + getId() +
&, name: & + getName();
以下代码来自Professor.java。
import java.util.ArrayL
import java.util.C
import java.util.D
import javax.persistence.E
import javax.persistence.Id;
import javax.persistence.ManyToM
import javax.persistence.ManyToO
import javax.persistence.OneToM
import javax.persistence.OneToO
import javax.persistence.T
import javax.persistence.TemporalT
public class Professor {
@Temporal(TemporalType.DATE)
private Date startD
@OneToMany(mappedBy=&employee&)
private Collection&Phone& phones = new ArrayList&Phone&();
@ManyToOne
@ManyToOne
@OneToMany(mappedBy=&manager&)
private Collection&Professor& directs = new ArrayList&Professor&();
@ManyToMany(mappedBy=&employees&)
private Collection&Project& projects = new ArrayList&Project&();
public int getId() {
public void setId(int empNo) {
this.id = empNo;
public String getName() {
public void setName(String name) {
this.name =
public long getSalary() {
public void setSalary(long salary) {
this.salary =
public Date getStartDate() {
return startD
public void setStartDate(Date startDate) {
this.startDate = startD
public Collection&Phone& getPhones() {
public void addPhone(Phone phone) {
if (!getPhones().contains(phone)) {
getPhones().add(phone);
if (phone.getProfessor() != null) {
phone.getProfessor().getPhones().remove(phone);
phone.setProfessor(this);
public Department getDepartment() {
public void setDepartment(Department department) {
if (this.department != null) {
this.department.getProfessors().remove(this);
this.department =
this.department.getProfessors().add(this);
public Collection&Professor& getDirects() {
public void addDirect(Professor employee) {
if (!getDirects().contains(employee)) {
getDirects().add(employee);
if (employee.getManager() != null) {
employee.getManager().getDirects().remove(employee);
employee.setManager(this);
public Professor getManager() {
public void setManager(Professor manager) {
this.manager =
public Collection&Project& getProjects() {
public void addProject(Project project) {
if (!getProjects().contains(project)) {
getProjects().add(project);
if (!project.getProfessors().contains(this)) {
project.getProfessors().add(this);
public Address getAddress() {
public void setAddress(Address address) {
this.address =
public String toString() {
return &Professor & + getId() +
&: name: & + getName() +
&, salary: & + getSalary() +
&, phones: & + getPhones() +
&, managerNo: & + ((getManager() == null) ? null : getManager().getId()) +
&, deptNo: & + ((getDepartment() == null) ? null : getDepartment().getId());
以下代码来自Project.java。
import java.util.ArrayL
import java.util.C
import javax.persistence.E
import javax.persistence.Id;
import javax.persistence.I
import javax.persistence.ManyToM
@Inheritance
public class Project {
protected S
@ManyToMany
protected Collection&Professor& employees = new ArrayList&Professor&();
public int getId() {
public void setId(int projectNo) {
this.id = projectNo;
public String getName() {
public void setName(String projectName) {
this.name = projectN
public Collection&Professor& getProfessors() {
public void addProfessor(Professor employee) {
if (!getProfessors().contains(employee)) {
getProfessors().add(employee);
if (!employee.getProjects().contains(this)) {
employee.getProjects().add(this);
public String toString() {
return getClass().getName().substring(getClass().getName().lastIndexOf(&.&)+1) +
& no: & + getId() +
&, name: & + getName();
以下是数据库转储。Table Name: ADDRESS
Table Name: DEPARTMENT
Column Name: ID,
Column Type: INTEGER:
Column Value: 1
Column Name: NAME,
Column Type: VARCHAR:
Column Value: Design
Table Name: PHONE
Column Name: ID,
Column Type: BIGINT:
Column Value: 1
Column Name: NUMBER,
Column Type: VARCHAR:
Column Value: 111-111-1111
Column Name: TYPE,
Column Type: VARCHAR:
Column Value: null
Column Name: EMPLOYEE_ID,
Column Type: INTEGER:
Column Value: 0
Table Name: PROFESSOR
Column Name: ID,
Column Type: INTEGER:
Column Value: 0
Column Name: NAME,
Column Type: VARCHAR:
Column Value: TOM
Column Name: SALARY,
Column Type: BIGINT:
Column Value: 1111
Column Name: STARTDATE,
Column Type: DATE:
Column Value: null
Column Name: ADDRESS_ID,
Column Type: INTEGER:
Column Value: null
Column Name: DEPARTMENT_ID,
Column Type: INTEGER:
Column Value: 1
Column Name: MANAGER_ID,
Column Type: INTEGER:
Column Value: null
Table Name: PROJECT
Table Name: PROJECT_PROFESSOR
意见反馈：
联系方式：
广告等垃圾信息
不友善内容
违反法律法规的内容
不宜公开讨论的政治内容集合及其划分
集合及其划分 集合及其划分一、集合基础知识复习 1．1 基本概念：一组对象构成集合的条件―确定性；集合的表示―列举法、描述法和文氏 图法；集合的分类―数集和点集，有限集和无限集，等等；有限集合的元素个数。理解一个 集合关键是理解集合的元素。 1．2 集合的运算： 子集、真子集和相等；交集、并集和余集。在包含关系 A ? B 中，要注重空集 Φ 的作 用。 1．3 性质：A ? B ? CU A ? CU B ； A ∩ B = Φ ? A ? CU B ? B ? CU A ； A ∪ B = U ? CU A ? B ? CU B ? A ； A ? B ? A∩ B = A ? A∪ B = B； A∩ B ? A∪ B ? A = B； A = CU B ? A ∩ B = Φ ，且 A ∪ B = U ；CU ( A ∩ B ) = (CU A) ∪ (CU B ) ； CU ( A ∪ B ) = (CU A) ∩ (CU B ) ；A ∪ (B ∩ C ) = ( A ∩ B ) ∪ ( A ∩ C ) ； A ∩ (B ∪ C ) = ( A ∪ B ) ∩ ( A ∪ C ) ；注： 这些运算等式中的括号是必要的， 譬如： 可以验证 ( A ∪ B ) ∩ C = A ∪ (B ∩ C ) ” “ ， 因此形如“ A ∪ B ∩ C ”的写法是没有意义的。 1．4 要十分重视文氏图的作用：譬如，应当写出下面文氏图（1）中任一块的集合表示，能 否看出来集合等式“ card ( A ∪ B ∪ C ) + card ( A) + card (B ) + card (C ) = card ( A ∪ B )+ card (B ∪ C ) + card (C ∪ A) + card ( A ∩ B ∩ C ) ”是否成立？回答是肯定的。1 A B U AB (1) C (2)又如，根据文氏图（2） ，有A = ( A ∩ B ) ∪ ( A ∩ CU B ) ， B = (B ∩ A) ∪ (B ∩ CU A) ，等等。例 1 已知 M = 抛物线 ， N = 直线 ，求 card (M ∩ N ) 。 例 2 M 1 = 20 p + 16q + 12r p、q、r ∈ Z ， M 2 = 12m + 8n + 4l m、n、l ∈ Z ， 证明： M 1 = M 2 。 例 3 已知集合 A = x x ? x ? 4 & 2, x ∈ R ， B = x x + 2 2 ? x + 1 ≥ 0, x ∈ R ，2{}{}{}{}{}{}? 1 ? x C = ?x ? & & 1, x ∈ R ? 2 2? x ? ?，D = x y = 1 + x + 3 ? x + 1, x ∈ R{}，M = y y = 1 + x + 3 ? x + 1, x ∈ D 。求 C B ∪ D ( A ∩ (C ∪ M )) 。解： [ A] ，先简化各个集合，得{}A = x x 2 ? x ? 2 x 2 ? x ? 6 & 0 = {x ( x + 2 )( x + 1)( x ? 2 )( x ? 3) & 0}{()() }= (? 2,?1) ∪ (2,3) ，B = ?x ? ?(2?x)2? 2 2 ? x ? 3 ≤ 0? = x ? ?{(2? x ?3)(2 ? x +1 ≤ 0) }= x 2 ? x ? 3 ≤ 0 = {x 0 ≤ 2 ? x ≤ 9} = [? 7,2] ，{}? ? ? x ? ? ( x ? 1)( x + 2 ) 1? ? ? ?? x C = ?x ? ? 1?? + ? & 0? = ? x & 0? = (? 2,1) ， 2 (2 ? x ) ? ? ? 2 ? x ?? 2 ? x 2 ? ? ? ? ?D = [? 1,3] ，2 ? ? M = ? y y = 4 + 2 3 + 2 x ? x 2 + 1, x ∈ D ? ? ?? ? 2 = ? y y = 4 + 2 4 ? ( x ? 1) + 1, x ∈ D ? = 3,2 2 + 1 ， ? ?再把各集合表示在数轴上，如下：B C D M A -7 -2 -1 1 2 A 4 3[]∴A ∩ (C ∪ M ) = (? 2,?1) ， B ∪ D = [? 7,3] C B ∪ D ( A ∩ (C ∪ M )) = [? 7,?2] ∪ [? 1,3] 。故例 4 把不超过 20 的质数（正整数）所成的集合记作全集 U ，其子集 A、B 满足(CU A) ∩ B = {5}， A ∩ (CU B ) = {2,11,17} ， (CU A) ∩ (CU B ) = {13,19} 。求集合 A ∩ B 。解：根据题意，作下面文氏图，U A 2 5 11 17 13 19 B∵U = {2,3,5,7,11,13,17,19}， A ∩ B = {3,7} 。∴例 5 设集合 A = x 2 x ? x 2 ≤ x ， B = ? x{}?x x ? 2 ≤ ? ， C = x ax + x + b & 0 ， ? 1? x 1? x ?{(}如果 ( A ∪ B ) ∩ C = Φ ，且 ( A ∪ B ) ∪ C = R ，求实数 a、b 的值。 例 6 已 知 A = x x 2 ? mx + m 2 ? 19 = 0{}，B = x log 2 x 2 ? 5 x + 8 = 1 ，{) }C = x x 2 + 2 x ? 8 = 0 ，且 A ∩ B ≠ Φ ， A ∩ C = Φ ，求 m 的值。3{} 注：解题时，大多使用的是条件的必要性，所以解出后，要自觉地检验题设中的各个条 件是否成立。譬如，本题解得 m = ?2,5 ，经检验， m ≠ 5 。 例 7 设A ={(x, y ) x = n, y = an + b, n ∈ Z }，B = {(x, y ) x = m, y = 3m2+ 15, m ∈ Z ，}C = ( x, y ) x 2 + y 2 ≤ 144 。问：是否存在 a、b ∈ R ，使得 A ∩ B ≠ Φ ，且 (a, b ) ∈ C 。例 8 数集 M 由 2006 个不同的实数组成，对于 M 中任何两个不同的元素 a、b ，都有{}a 2 + b 2 ∈ Q 。证明： M ? a 2 a ∈ Q 。证明：再任取 b、c ∈ M ，使得 a、b、c 两两互异，则{}a 2 + b 2、b 2 + a 2、c 2 + a 2、c 2 + b 2 ∈ Q ?a 2 ? b 2 = c 2 + a 2 ? c 2 + b 2 ∈ Q ? ?1 2 2 ? a 2 ?b 2 a 2 + b 2 ? 2 = a + b 2 ? b + a 2 ∈Q ?2∴(( )() () ()) ()故a 2 ? b 2、a 2 + b 2 ? 2 ∈ Q ，a 2= 1 1 a 2 + b 2 + a 2 ? b 2 ∈Q 。 2 2∴ 故() ()结论成立。例 9 已知 S = m 2 + n 2 m、n ∈ Z ，证明： x、y ∈ S ? xy ∈ S 。{}例 10 在一次数学竞赛中共出了 3 道试题 A、B、C，共 25 人参加，其中每人至少解出 一道题。在未解除 A 的人中，解出 B 的人数为解出 C 的人数的 2 倍；只解出 A 的人数比解 出 A 的其余人数多 1；在解出一道题的人中有一半没解出 A。求只解出 B 的人数。A z z+t z+t-1 z-2t (1) tBC(2)解：根据题意，造出文氏图（1） ，并有数据关系：4 ? x + y + z + u + v + s + t = 25 ? z + s = 2(s + t ) ? ，由此得简化文氏图（2） ，以及数据关系 ? ?x = y + u + v + 1 ?x = z + t ? ?t + 4 z ? 1 = 25 ?t + 4 z = 26 ?t + 4 z = 26 ? z ? 2t ≥ 0 ? z ? 2(26 ? 4 z ) ≥ 0 ? 52 25 ? ? ? ?? ≤z≤ ?? ? 3 ?z + t ? 1 ≥ 0 ?25 ? 3 z ≥ 0 ?9 ?t , z ∈ N ?t , z ∈ N ?t , z ∈ N ? ? ? ?t + 4 z = 26 ?z & 7 ?z = 6 ? ?? ?? 。 ?t = 2 ? z = 6,7,8 ?t , z ∈ N ?∴ 只解出 B 题的人有 6 人，这 25 的具体分布是A 6 8 7 2 2 (2)BC。 例 11 已知 A = 求实数 a 使得 （1） card (( A ∪ B ) ∩ C ) = 2 ； （答：0，1） （2） card (( A ∪ B ) ∩ C ) = 3 。 （答： ? 1 ±{(x, y ) ax + y = 1}， B = {(x, y ) x + ay = 1}， C = {(x, y ) x2+ y2 = 1 。}2）例 12 已 知 函 数 f ( x ) = x 2 + ax + b ， 定 义 集 合 ： A ={(x, y ) f (x ) = x, x ∈ R} ，C = {( x, y ) f ( f ( x )) = x, x ∈ R}。（1）证明： A ∪ B = B ； （2）若 A = {? 1,3} ，求 B ； （3）若 card ( A) = 1 ，证明： A = B 。 例 13 设 集 合 A = {a1 , a 2 , a3 , a 4 , a5 } ， B = a1 , a 2 , a3 , a 4 , a52 2 2 2{2}， 其 中 a ∈ Ni*5 （ i = 1,2,3,4,5 ） 并且 a1 & a 2 & a 3 & a 4 & a5 ， a1 + a 4 = 10 ，A ∩ B = {a1 , a 4 } ， A ∪ B ， 中所有元素之和为 224，求集合 A。 解：由 A ∩ B = {a1 , a 4 } ，可知， a1、a 4 都是完全平方数，再根据 a1 + a 4 = 10 ，可知a1 = 1, a 4 = 9 ，从而，有?1 & a 2 & a 3 & 9 & a5 ? ? ?1 & a 2 2 & a 3 2 & 81 & a 5 2 ?若 a 3 = 9 ，则 a 3 = 3, a 2 = 2 ，必有2A ∪ B = 1,2,3,4,9,81, a5 , a5∵ ∴{2}A ∪ B 中所有元素之和为 224，a5 + a5 ? 124 = 0 ，但这方程无非负整数解。2故a 2 = 9 ，则 a 2 = 3 ，必有2A ∪ B = 1,3,9,81, a3 , a3 , a5 , a5 ， a 3 ≥ 4 ， a 5 ≥ 10 。2 2{}∵ ∴A ∪ B 中所有元素之和为 224，a5 + a5 + a3 + a3 = 130 。2 2又a5 ≥ 10 ? a5 + a5 ≥ 110 ，2∴a3 + a3 ≤ 20 ? a3 ≤ 4 ? a3 = 4 ，2故a5 + a5 = 110 ? a5 = 10 。2∴A = { ,3,4,9,10}。 1M 1 = x 2 + Ax + B x ∈ Z ， M 2 = 2 x 2 + 2 x + C x ∈ Z 。例 14 对固定的整数 A、B、C，定义集合：{}{}证明：无论对怎样的 A、B ∈ Z ，都可以选择 C ∈ Z ，使得 M 1 ∩ M 2 = Φ 。 证明：∵2 x 2 + 2 x + C ≡ C (mod 2 ) ，∴M 2 中的数都与整数 C 的奇偶性相同。当 A 是奇数时，有 x 2 + Ax + B ≡ B (mod 2 ) ，即 M 1 中的数都与整数 B 奇偶性相同， 所以，只要取 C = B + 1 即可。6 当 A 是偶数时， x + Ax + B = ? x +2? ?A? A2 +B? ≡ B, B + 1, B + 3(mod 4 ) ，而 ? 2? 422 x 2 + 2 x + C ≡ C (mod 4 ) ，所以，只要取 C = B + 2 即可。二、容斥原理与筛法公式? n ? n ? U Ai ? = ∑ card ( Ai ) ? ∑ card (Ai ∩ A j ) 容斥计数： card ? ? 1≤i & j ≤ n ? i =1 ? i =1+ L + (? 1)r ?1 1≤i1 & i2 &L& ir ≤ n∑ card (Ai1∩ Ai2 ∩ L ∩ Air)+ L + (? 1) card ( A1 ∩ A2 ∩ L ∩ An ) ，n筛法公式： card ? ??? i =1? I A ? = card (I ) ? ∑ card ( A ) + ∑ card (A ∩ A ) ?n n i?i =1 ri1≤ i & j ≤ nij+ L + (? 1)1≤ i1 & i2 &L& ir ≤ n n +1∑ card (Ai1∩ Ai2 ∩ L ∩ Air)+ L + (? 1)card ( A1 ∩ A2 ∩ L ∩ An ) 。n证明方法：数学归纳法、组合方法（ ?x ∈U A ，证明这个 x 在左右两边计入的次数i i =1相同） 例1 （1） 1 到 10000 的正整数中， 在 既不是整数的平方也不是整数的立方的数有多少？ （2）把 1 到 10 分成两个不相交的集合 A、B ， A 由可以表示成一个完全平方数和一个完 全立方数之和的所有数组成； B 由其余所有数组成。试判断 card ( A) 与 card (B ) 的大小关 系。 解 ：（ 1 ） 任 取 x ≤ 10000 ? x ≤ 21 ； 任 取 y 2 ≤ 10000 ? y ≤ 100 ； 任 取3 6z 6 ≤ 10000 ? z 3 ≤ 100 ? z ≤ 4 。由容斥原理，得，所求数的个数是 10000 ? 100 ? 21 + 4 = 9883 。（2） ?n ∈ A ， ?k、m ∈ N ，使得 n = k + m ；由 n ≤ 10 ，可得 k ≤ 10 ， m ≤ 10 ，2 3 6 3 2所以，二元集 {k, m} 的个数不多于 10 。5故card ( A) ≤ 10 5 & 10 6 ? 10 5 & 10 6 ? card ( A) = card (B )例 2 在 1 到 300 的整数中，计算 （1）能被 3 或被 5 或被 7 整除的数用多少？ （2）不能被 3，5，7 中的任何一个整除的数有多少？7 （3）能被 3 整除，但不能被 5、7 中任何一个整除的数有多少呢？ 例 3 由 5 对夫妻排成一行，求没有任何一对夫妻相邻的排法种数。 解：由容斥原理，不同排法的总数是1 3 5 10!?C 5 ? 2!?9!+C 52 ? 2!?2!?8!?C 5 ? 2!?2!?2!?7!+C 54 2!?2!?2!?2!?6!?C 5 2!?2!?2!?2!?2!?5!= 5!(40 × 8 × 7 × 6 ? 80 × 7 × 6 + 80 × 6 ? 32) = 120 × 16(40 × 7 × 3 ? 10 × 7 × 3 + 10 × 3 ? 2)= 120 × 16 × 658 = 1263360 。例 4 设 M = ?( x, y, z , u )? ?? x? y y ? z z ?u u ? x + + + & 0, x、y、z、u ∈ D ? ，其中 x+ y y+ z z +u u + x ?D＝{x x ∈ Z ,1 ≤ x ≤ 10}。求 card (M ) 。解：设 f (a, b, c, d ) =a?b b?c c?d d ?a ，记 + + + a+b b+c c+d d +a? ? f ( x, y , z , u ) & 0 ? A = ?( x, y, z, u ) ? ?， ? x, y , z , u ∈ A ? ? ? ? f ( x, y , z , u ) & 0 ? B = ?( x, y, z, u ) ? ?， ? x, y, z , u ∈ A ? ? ? ? f ( x, y , z , u ) = 0 ? C = ?( x, y, z, u ) ? ?。 ? x, y , z , u ∈ A ? ?则card ( A) + card (B ) + card (C ) = 10 4先证： card ( A) = card (B ) 。 ∵(a, b, c, d ) ∈ A ? f (a, b, c, d ) & 0 ? a ? b + b ? c + c ? da+b b+c ?a?d c?b b?c a?b + + + & 0 ? f (a, d , c, b ) & 0 ? (a, d , c, b ) ∈ B ， a+d c+b b+c a+bc+d+d ?a &0 d +a∴card ( A) = card (B ) 。再计算 card (C ) 。? ? f ( x, y , z , u ) = 0 ? C = ?( x, y, z, u ) ? ? ? x, y , z , u ∈ A ? ?8 ? ? ?x ? y y ? z z ?u u ? x + + + = 0? ? ? = ?( x, y, z, u ) ? x + y y + z z + u u + x ? ? ? x、y、z、u ∈ D ? ? ? ?? ?( z ? x )(u ? y )( xz ? yu ) = 0? = ?( x, y, z, u ) ? ? ? x、y、z、u ∈ D ? ?= C1 ∪ C 2 ∪ C 3 ，其中? ? ?x = z C1 = ?( x, y, z, u ) ? ?， ? x、y、z、u ∈ D ? ?? ? ?u = y ? ? ? C 2 = ?(x, y, z , u ) ? x ≠ z ?， ? ? x、y、z、u ∈ D ? ? ? ? ? ? ? xz = yu ? ? ? C 3 = ?( x, y, z , u ) ? x ≠ z , u ≠ y ?。 ? ? x、y、z、u ∈ D ? ? ? ?∴card (C ) = card (C1 ) + card (C 2 ) + card (C 3 ) 。又C1 = {( x, y, x, u ) x、y、u ∈ D} ? card (C1 ) = 1000 ，? ? ?x ≠ z C 2 = ?( x, y, z, y ) ? ? ? card (C 2 ) = 900 ， ? x、y、z ∈ D ? ? ? ? ? ? ?x ≠ z ?x ≠ y C3 = ?( x, x, z, z ) ? ? ∪ ?( x, y, y, x ) ? ? ? x、z ∈ D ? ? ? x、y ∈ D ? ?? ? ? xz = yu ? ? ? ∪ ?( x, y, y, x ) ? x、y、z、u ∈ D ? ? card (C 3 ) = 90 + 90 + 9 × 4 × 2 ? ? x、y、z、u互异? ? ? ?其中最后一步是根据数表 1＊2 1＊3 2＊3 1＊4 2*4 3*4 1＊5 2*5 3*5 4*5 1＊6 2*6 3*6 4*6 5*6 1＊7 2*7 3*7 4*7 5*7 6*7 1*8 2*8 3*8 4*8 5*8 6*8 7*8 1*9 2*9 3*9 4*9 5*9 6*9 7*9 8*9 1*10 2*10 3*10 4*10 5*10 6*10 7*10 8*109 9*10 得到就个四元互异数乘积等式：1 × 6 = 2 × 3 1 × 8 = 2 × 4 1 × 10 = 2 × 5 1 3 × 4 = 2 × 6 3 × 6 = 2 × 9 3 × 8 = 4 × 6 算得 9 × C 2 × 2!×21 = 9 × 4 × 2 。 4 × 5 = 2 × 10 5 × 6 = 3 × 10 5 × 8 = 4 × 10∴card (C ) = 1000 + 900 + 252 = 2152 。card ( A) = 10000 ? card (C ) = 3924 。 2故例 5 已知集合 S = { ,2,3, L ,280} ，求最小的正整数 n ，使得 S 的每个 n 元子集都含有 1 5 个两两互素的数。 解：先利用四个素数 2，3，5，7 的倍数构造一个集合A = A2 ∪ A3 ∪ A5 ∪ A7 ，其中 Ak = {n ∈ S n ≡ 0(mod k )}(k = 2,3,5,7 ) 。∵? 280 ? ? 280 ? ? 280 ? card ( A2 ) = ? ? = 140 ， card ( A3 ) = ? 3 ? = 93 ， card ( A5 ) = ? 5 ? = 56 ， ? 2 ? ? ? ? ? ? 280 ? ? 280 ? card ( A7 ) = ? ? = 40 ， card ( A2 ∩ A3 ) = ? 6 ? = 46 ， ? 7 ? ? ? ? 280 ? ? 280 ? card ( A2 ∩ A5 ) = ? ? = 28 ， card ( A2 ∩ A7 ) = ? 14 ? = 20 ， ? 10 ? ? ? ? 280 ? ? 280 ? card ( A3 ∩ A5 ) = ? ? = 18 ， card ( A3 ∩ A7 ) = ? 21 ? = 13 ， ? 15 ? ? ? ? 280 ? ? 280 ? card ( A5 ∩ A7 ) = ? ? = 8 ， card ( A2 ∩ A3 ∩ A5 ) = ? 30 ? = 9 ， ? 35 ? ? ? ? 280 ? ? 280 ? card ( A2 ∩ A3 ∩ A7 ) = ? ? = 6 ， card ( A2 ∩ A5 ∩ A7 ) = ? 70 ? = 4 ， ? 42 ? ? ? ? 280 ? ? 280 ? card ( A3 ∩ A5 ∩ A7 ) = ? ? = 2 ， card ( A2 ∩ A3 ∩ A5 ∩ A7 ) = ? 210 ? = 1 ? 105 ? ? ?∴card ( A) = 140 + 93 + 56 + 40 ? 46 ? 28 ? 20 ? 18 ? 13 ? 8 + 9 + 6 + 4 + 2 ? 1= 216∵ 在 A 中任取 5 个数，总有两个数不是互素的， ∴ n ≥ 217 。 下面构造 S 的元素个数不少于 5 的子集，其元素个数尽可能多，把这些子集都找出来； 为此，我们列表把 S 中的数作一分类：10 合数 素数与 1 2×素数 2＊2， 2＊139， 2＊137， 2＊131， 2＊127， 2＊113， 2＊109， 2＊107， 1，2，3，5， 7，11，13，17， 19，23，29，31， 37，41，43，47， 53，59，61，67， 71，73，79，83， 89，97，101，103， 107，109，113， 127，131，137， 139，149，151， 157，163，167， 173， 179，181， 191，193，197， 199，211，223， 227，229，233， 239，241，251， 257，263，269， 271，277， 2＊103， 2＊101 2＊97 2＊89 2＊83 2＊79 2＊73 2＊71 2＊67 2＊61 2＊59 2＊53 2＊47 2＊43 2＊41 2＊37 2＊31 2＊29 2＊23 2＊19 2＊17 2＊13 2＊11 2＊7 2＊5 2＊3 令 3×素数 3＊3 3＊89 3＊83 3＊79 3＊73 3＊71 3＊67 3＊61 3*59 3*53 3*47 3*43 3*41 3*37 3*31 3*29 3*23 3*19 3*17 3*13 3＊11 3＊7 3＊5 5×素数 5＊5 5＊53 5＊47 5＊43 5＊41 5＊37 5＊31 5＊29 5＊23 5＊19 5＊17 5＊13 5＊11 5*7 7×素数 7＊7 7＊37 7＊31 7＊29 7＊23 7＊19 7＊17 7＊13 7＊11 11×素数 11＊11 11＊23 11＊19 11＊17 11＊13 13×素数 13＊13 13＊19 13＊17B1 = { } ∪ {S中的素数} ? card (B1 ) = 60 ， 1B2 = 2 2 ,3 2 ,5 2 ,7 2 ,112 ,13 2 ? card (B2 ) = 6 ， B3 = {2 × 139,3 × 89,5 × 53,7 × 37,11 × 23,13 × 19} ? card (B3 ) = 6 ，{}11 B4 = {2 × 137,3 × 83,5 × 47,7 × 31,11 × 19,13 × 17} ? card (B4 ) = 6 ，B5 = {2 × 131,3 × 79,5 × 43,7 × 29,11 × 17} ? card (B5 ) = 5 ， B5 = {2 × 127,3 × 73,5 × 41,7 × 23,11 × 13} ? card (B6 ) = 5以及 B = B1 ∪ B2 ∪ B3 ∪ B4 ∪ B5 ∪ B6 ，则card (B ) = 88 ， card (C S B ) = 280 ? 88 = 192现在 S 中任取 217 个数，则至少有 217 ? 192 = 25 个数在 B 中；因为25 & 4 ，所以由 6抽屉原理，知至少有 5 个数在上述某一个集合 Bi (i = 1,2,3,4,5,6 ) 中；再由 Bi 的定义知，这 5 个数两两互质。 故 所求 n 的最小值是 217。 证法二：在 S 任取中任取 217 个数，令其组成子集 A 。如果其中至少有 5 个素数，则 结论成立；否则，其中至多 4 个素数，至少有 213 个合数。故 S 中的 220 个合数中多有 7 个不在其中。构造 S 的 8 个互素合数子集，使其中恰好有 5 个元素，作为抽屉：B1 = 2 2 ,3 2 ,5 2 ,7 2 ,112 ，{}B2 = {2 × 139,3 × 89,5 × 53,7 × 37,11 × 23} ，B3 = {2 × 137,3 × 83,5 × 47,7 × 31,13 × 17} ，B4 = {2 × 131,3 × 79,5 × 43,7 × 29,11 × 17}，B5 = {2 × 127,3 × 73,5 × 41,7 × 23,11 × 13} ，B6 = 2 × 113,3 × 71,5 × 37,7 × 19,13 2 ，{}B7 = {2 × 109,3 × 67,5 × 31,7 × 17,13 × 19}， B8 = {2 × 107,3 × 61,5 × 29,7 × 13,11 × 19}。由于这 8 个子集中至多有 7 个元素不在 A 中， 所以必存在某个 Bi ? A ， A 中必存在 故 5 个数两两互素。 证法三：设 T ? S ，且 card (T ) = 217 ，记 S 中的所有素数和 1 构成的集合为 M ，则card (M ) = 60 ， S 中的合数共 220 个。若 card (T ∩ M ) ≥ 5 ，则 T 中存在 5 个数两两互质。12 若 card (T ∩ M ) = 4 ， 则设其余素数按从小到大的顺序排成 p1 , p 2 , p3 , L ， p1 ≤ 11 ， 则p 2 ≤ 13 ， p3 ≤ 17 ， p 4 ≤ 19 ， p5 ≤ 23 ，于是，由数表p1 p1 p2 p3 p4 p5 L可找到 8 个合数2 p12 , p1 p 2 , p1 p 3 , p1 p 4 , p1 p5 , p 2 , p 2 p3 , p 2 p 4 ∈ Sp2 p1 p 2 2 p2p3 p1 p3 p 2 p32 p3p4 p1 p 4 p2 p4 p3 p 4 p2 4p5Lp2 1p1 p5 L p 2 p5 L p3 p5 L p 4 p5 L 2 p5 L L LLLLL∵ T 中只有 213 个合数， ∴ S 中恰有 7 个合数不在 T 中， 故上述 8 个合数中必有一个在 T 中， 这一个合数 T 中 的 4 个素数一起构成两两互素的 5 个数。 若 card (T ∩ M ) ≤ 3 ，则 T 中至少有 214 个合数，那么 S 中的 220 个合数中，至多有 6 个不在 T 中。考虑 6 个特殊的合数 2 2 ,3 2 ,5 2 ,7 2 ,112 ,13 2 ，若其中有 5 个在 T 中，则这 5 个数两两互素；若其中只有 4 个在 T 中，则这 4 个合数只含有 2、3、4、7、11、13 中的 4 个素数，可以完全重复 card (T ∩ M ) = 4 的情形，完成证明；若其中至多有 3 个在 T 中， 在其他合数至多有 3 个不在 T 中，因此，下面两个集合中的 12 个合数中至多有 3 个不在 T 中：{}{2 × 139,3 × 89,5 × 53,7 × 37,11 × 23,13 × 19}， {2 × 137,3 × 83,5 × 47,7 × 31,11 × 19,13 × 17}∴ 由抽屉原理知，其中必有一个子集中存在 5 个数在 T 中，它们两两互素。 评注：本题充分体现了容斥原理、抽屉原理、极端性原理、表格处理方法以及瞄准目标 穷追不舍逐步接近结论的数学思想方法的综合应用。 例 6 对有限集合 S，其元素个数记为 S ，子集个数记为 n(S ) 。如果三个有限集合 A、 B、C 满足 A = B = 100 ，并且 n( A) + n(B ) + n(C ) = n( A ∪ B ∪ C ) ，求 A ∩ B ∩ C 的最 小值。 解：有题意，得2100 + 2100 + 2C=2A ∪ B ∪C? 1+ 2C ?101=2A∪ B ∪C ?101若 C ? 101 ≥ 1 ，则 2A ∪ B ∪C是不小于 3 的奇数，矛盾！13 ∴C = 101 ， A ∪ B ∪ C = 102 。由容斥原理，得A∩ B ∩C = A∪ B ∪C + A + B + C ? A∪ B ? B ∪C ? C ∪ A = 403 ? A ∪ B ? B ∪ C ? C ∪ A∵ ∴ 同理，得A∪ B ? A∪ B ∪CA ∪ B ≤ A ∪ B ∪ C = 102 ，B ∪ C ≤ 102 ， C ∪ A ≤ 102 。故A ∩ B ∩ C ≥ 403 ? 306 = 97 。为构造“＝”成立的例子，我们先构造“＝”成立状况下的文试图：A 1 97 2 2 C B根据这个文氏图，我们可以构造出A = { ,2,L,100} ， B = {3,4,5,L,102} ， C = { ,2,4,5,6, L,100,101,102} ， 满 足 1 1 A ∩ B ∩ C = 97 。∴A ∩ B ∩ C 的最小值为 97。三、子集与对应：利用子集对应解题。 （1） n 元集合共有 2 n 个子集，能够按照相邻元素只相差一个元素的办法排成一列。 （2）利用单射对子集计数 例 1 求满足条件 { ,2,3} ? A ? { ,2,3,4, L , n}(n & 3) 的集合 A 的个数。 1 1 例 2 如果子集 A ? S = { ,2,3, L ,49} 中至少有两个数相邻，且 card ( A) = 6 ，证明：多 1 有这种子集 A 的个数为 C 49 ? C 44 。6 614 证明：集合 S 的所有 6 元子集的个数为 C 49 ，但其中有 6 个数互不相邻的子集6A' = {a1 , a 2 , L , a 6 } ， 1 ≤ a1 & a 2 & a 3 & a 4 & a 5 & a 6 ≤ 49 ， a i + 1 & ai +1 ，i = 1,2,3,4,5 。不满足要求，这部分子集个数记作 W1 ；故只需证明这种 A' 的个数为 C 44 。 换元： bi = ai ? i + 1 ， i = 1,2,3,4,5,6 ，则 1 ≤ b1 & b2 & b3 & b4 & b5 & b6 ≤ 44 ，子集6 {b1 , b2 , b3 , b4 , b5 , b6 } ? {1,2,3,L,44}共 C 44 个，它们构成集合 W2 ，作映射 6f : W1 → W2 , {a1 , a 2 , a3 , a 4 , a5 , a 6 } a {b1 , b2 , b3 , b4 , b5 , b6 }6 则这映射是单射，所以 card (W1 ) = card (W2 ) = C 44 。故 符合条件的子集 A 的个数是 C 49 ? C 44 。6 6例 3 有锁若干把，现有六个人格掌握一部分钥匙。已知任意两个人同时去开锁，都有一 把锁打不开，而且任何三个人都可以把全部锁打开。问：最少有多少把锁？ 解：先界定最值： 六个人 1，2，3，4，5，6 共有 C 6 = 15 各“二人组” ，记其集合为 S；由题意，对任意2的“二人组” {i, j} ，总有一些锁打不开，这些锁的集合记作 A{i , j } ，全部锁的集合记作 A。 作映射f : {i, j}(∈ S ) → A{i , j } ? A则这个映射是单射，否则，存在两个不同的二人组 {i, j} 与 {k, l }，合在一起至少 3 个人，但 他们打不开所有的锁，这与题意矛盾！ 故{i , j }card ( A) ≥ ∑ card (A{i , j} ) ≥ ∑ 1 = 15 。{i , j }方案构造：现安装 15 把锁，这 15 把锁的集合共有 15 个 14 元子集，把这些子集与 15 个“二人组”相对应，先完成 15 把锁的钥匙在 15 个二人组中的分配管理：表（1） 1 ｛1，2｝ ｛1，3｝ ｛1，4｝ ｛1，5｝ ｛1，6｝ ｛2，3｝ ｛2，4｝ ｛2，5｝ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ 2 √ √ 3 √ √ √ 4 √ √ √ √ 5 √ √ √ √ √ 6 √ √ √ √ √ √ 7 √ √ √ √ √ √ √ 8 √ √ √ √ √ √ √ √ 9 √ √ √ √ √ √ √ √ 10 √ √ √ √ √ √ √ √ 11 √ √ √ √ √ √ √ √ 12 √ √ √ √ √ √ √ √ 13 √ √ √ √ √ √ √ √ 14 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √1515 ｛2，6｝ ｛3，4｝ ｛3，5｝ ｛3，6｝ ｛4，5｝ ｛4，6｝ ｛5，6｝ 1 1 2 3 4 5 6 √ √ √ √√ √ √ √ √ √ √ 2√ √ √ √ √ √ √ 3√ √ √ √ √ √ √ 4√ √ √ √ √ √ √ 5 √√ √ √ √ √ √ √ 6 √√ √ √ √ √ √ √ 7 √√ √ √ √ √ √ √ 8 √ √ √ √ √ √ √ 9 √ √√√ √√ √ √√ √ √ √√ √ √ √ √√ √ √ √ √ √√ √ √ √ √ √ √√ √ √ √ √ 10 √ √ √ √ √ √ 11 √ √√ √ √ 12 √ √ √ √ √ 13 √ √ √√ 14 √ √ √ √ √ √ √ √ 15进一步实现 15 把锁的钥匙在 6 个人中的管理：表（2）√ √√ √ √√ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √√ √ √ √√ √ √ √√ √ √方案解释：由表（1）可知，任何两人到场都不能打开全部锁，由表（2）可知每一把锁 的钥匙恰好有两个人不管理，所以任何三人到场都能打开全部锁。 ∴(card ( A))min= 15 。例 4 某银行的管理保险柜由 11 人保管，保险柜上安装锁若干把，这些锁的钥匙分发给 11 人保管使用。问：最少要为保险柜安装多少把锁，才能使任何 6 人同时到场时就能打开 保险柜，而任何 5 人到场都不能打开？5 解：由 11 人组成的“五人组”个数为 C11 = 462 ，记其集合为 S；按题意，在装锁最少的情况下，对任一“五人组” {a, b, c, d , e}，总有唯一的一把锁 A{a ,b ,c ,d ,e} 不能打开；全部锁 的集合记作 A。作映射f : {a, b, c, d , e}(∈ S ) → A{a ,b,c ,d ,e} ? A则这个映射是单射，否则，存在两个不同的“五人组” {a, b, c, d , e}与 {a ' , b' , c' , d ' , e'}，他 们都不能打开同一把锁，但是两组合在一起至少 6 个人，而他们打不开所有的锁，这与题意 矛盾！ 故(card ( A))min={a ,b ,c , d ,e∑1 } = C5 11= 462 。思考：本题能否应用 spenner 定理求解？ 四、子集最值问题：求满足某种条件的子集个数最大值。 例 1 集 合 A = {0,1,2, L ,9} 的 非 空 子 集 族 D = {B1 , B2 , L , Bn } 满 足card (Bi ∩ B j ) ≤ 2(1 ≤ i & j ≤ n ) ， 求 n 的最大值。解：明显 n max ≥ C10 + C10 + C10 = 175 ，下面证明 n max ≤ 175 。1 2 316 对任一满足条件的 D = {B1 , B2 , L , Bn } ，若存在 B ∈ D ，使得 card (B ) ≥ 4 ，则存在b ∈ B ； 由 C B {b}? D ， 用 C B {b} 替 换 D 中 的 B ， 得 到 子 集 族 D ' ， 并 且card (D') = n = card (D ) ；由这种子集族元素个数的不变性，我们继续这种操作，经过有限次操作，必然能得到 A 的一个子集族 D ' ' ? T ，并且 card (D ' ') = n ，其中 T 为 A 元素个 数不超过 3 的所有子集组成的集合，故n ≤ card (T ) = 175∴n max ≤ 175 ， n max = 175 。故例 2 在一个车厢中，任何 m(m ≥ 3) 个游客都有唯一公共朋友（当甲是乙的朋友时，乙 也是甲的朋友，但任何人不作为自己的朋友） 。问：在这个车厢中，朋友最多的人有几个朋 友？ 解：设朋友最多的人 A 的朋友的集合为 S = {B1 , B2 , L , Bk } ，即他有 k 个朋友，则k≥m若 k & m ，任取 Bi1 , Bi2 , L , Bim ?1 ? S ，则 A, Bi1 , Bi2 , L , Bim ?1 有唯一公共的朋友 C i ， 并且 C i ∈ S ；定义映射{}f : Bi1 , Bi2 , L , Bim ?1 → C i则 f 是 单 射 ， 否 则 ， 设 Bi1 , Bi2 , L , Bim ?1 和 B j1 , B j2 , L , B jm ?1 的 像 都 是 C ， 则{}{} {}{Bi1, Bi2 , L , Bim ?1 ∪ B j1 , B j2 , L , B jm ?1 中至少有 m 个人，他们有两个公共朋友 A、C 。C km ?1 ≤ k 。 k & m ≥ 3，1 k ≥ C km ?1 ≥ C k2 & C k = k ，也矛盾！} {}矛盾！ ∴ 又 ∴故k min = m 。五、 Spenner 定理? 定理：设 A 为 n 元集合，它的 k 个子集 A1 , A2 , L , Ak 互不包含，则 k max = C n 2 ? 。 ?n? ? ?17 证明：由已知， Φ ≠ Ai ? A ，且 t i = card ( Ai ) & card ( A) ，把 Ai 中的元素作全排列， 并在其后接上 C A Ai 的元素的全排列， a i ,1 , a i , 2 , L , a i ,ti ， a i ,ti +1 , ai ,ti + 2 , L , ai ,n ，这样的 n 元 排列共有 t i !?(n ? t i )! 个，称为由 Ai “引导的 n 元排列” 。对 1 ≤ i & j ≤ k ，如果 t i & t j ，则 由 Ai ? A j 知，由 Ai 引导的任一 n 元排列的前 t i 项和由 A j 引导的任一 n 元排列的前 t i 项都 不一样， 所以由 Ai 引导的任一 n 元排列和由 A j 引导的任一 n 元排列互不相同； 如果 t i & t j ， 也有同样的结论；如果 t i = t j ，则由已知 Ai ≠ A j ，同样有 Ai 和 A j 各自引导的 n 元排列也 互不相同。 ∵ 由 A1 , A2 , L , Ak 各自引导的 n 元排列都是 A 的 n 个元素的全排列，∴∑ ti !?(n ? t i )! ≤ n! ? ∑i =1kki =11 ≤ 1。 t C ni又 ∴C ≤Cti n?n? ?2? ? ? nk(i = 1,2,L, k ) ，1 ≤ 1， t C ni?n? ?2? ? ? nk C故?n? ?2? ? ? n≤∑i =1 ?n? ?2? ? ? nk ≤C， k max = C?n? ? ? n ?? ? ? ? i = 1,2,L, k = C ? 2 ? ? 。 ，此时 card ( Ai ) = t i = ? ? n ? ? 2 ?? ? ?1993 年全国高中数学联赛加试题第三题，实质上就是这个定理： “设 A 为 n 元集合，它 的 k 个子集 A1 , A2 , L , Ak 互不包含。证明： （1）∑Ci =1k1Ai n（2） ∑ C n i ≥ k 2 ” 。其中 ≤ 1；A i =1k第二问可利用（1）的结论由均值不等式推证。 例 1 有 n 支球队要举行主客场双循环赛（每两支球队比赛两场，各有一场主场比赛） ， 每支球队在一周（从周日到周六的七天）内可进行多场客场比赛。但如果某周内该球队有主 场比赛，则在这一周内不能安排该球队的客场比赛。如果 4 周内能够完成全部比赛，求 n 的 最大值。 （注：甲乙两队在甲方场地举行的比赛，称为甲队的主场比赛，乙队的客场比赛） 解： 个周组成集合 A， 4 记第 i 支球队的 “主场周” 的集合为 Ai ， Ai ? A (i = 1,2, L , n ) ， 则 并且其中任意两个不互相包含，否则，不妨设 A1 ? A2 ，则第 1、2 两队进行的比赛都是双 方的主场，它们之间不打客场，与题意向违。由 Spenner 定理，得2 n ≤ C4 = 6 。各队的“主场周”安排如下： 球队 第一周 第二周 第三周 第四周18 1 2 3 4 5 6＊ ＊ ＊＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊方案说明：每个球队带“＊”的周次，表示该球队打主场，不出访。具体主客场比赛表 安排如下： 周次 周一 第一周 1―4 2―5 3―6 1―5 2―6 3―4 1―6 2―4 3―5 第二周 1―2 4―3 5―6 1―3 4―6 5―2 4―2 5―3 第三周 2―1 6―5 2―3 4―5 6―1 4―1 6―3 第四周 3―1 6―4 3―2 5―4 5―1 6―2周二周三周四 周五 周六 周日 （周四、五、六、日完全可以休息） 应用 spenner 定理，一定要注意把握问题的条件。譬如，我们在用 spenner 定理求解下 面的问题。 例 2 有锁若干把，现有六个人格掌握一部分钥匙。已知任意两个人同时去开锁，有且恰 有一把锁打不开，而且任何三个人都可以把全部锁打开。问：最少有多少把锁？ 解：设有 n 把锁，组成集合 A，由 6 个人组成的 C 6 = 15 个“二人组”分管的钥匙能打2开的锁的集合分别为 A1 , A2 , L , A15 ，则 Ak ≠ A(?k ) 。 ∵ ∴ 任何两个“二人组”至少有 3 个人，Ai ∪ A j = A(1 ≤ i & j ≤ 15) ， A1 , A2 , L , A15 中任意两个都不互相包含。?n? ?2? ? ? n故由 Spenner 定理，得15 ≤ C，故 n ≥ 6。 但是，当 n = 6 时，每个“二人组”能打开 3 把锁，也不能打开 3 把锁，这当然不是锁 最少的状况，故实际应有 n & 6 。这是应用 spenner 定理失败的典型例子，究其原因，本题 要求的条件比 Spenner 要求的条件更多、更强。19 例 3 由 11 个剧团参加汇演，每天都排定其中某些剧团的演出，其余剧团则跻身于普通 观众之列。在汇演结束时，每个剧团出了自己的演出日外，至少观看观看过其它每个剧团的 一次表演。问：这样的汇演最少要安排几天？1 解：设总汇演日集合 S = { ,2, L , n} n ∈ N(*) ，第 k 个剧团的演出日的集合为 Ak，则Ak ? S (k = 1,2, L , n ) ， Ai ? A j (?i ≠ j ) ，由 Spenner 定理，得2 11 ≤ C n ? n ≥ 6对于 n = 6 ，可以排除下面的汇演日期表 1 2 3 4 5 1 2 3 4 5 6 √ √ √ √ √ √ √ √ √ √67891011√ √√√√ √ √√ √ √√ √∴ 安排汇演日期天数最少是 6 天。 例 4 已知共有 12 个剧团参加一次为期 7 天的戏剧节，要求每个剧团都能看到其它所有 剧团的演出（当天没有演出任务的演员在台下观看演出） 。问：最少共要演出多少场？ 解：由 Spenner 定理，可知用 6 天的时间可以安排完成，但现在要求的是演出的场数 最少，而不要求安排演出天数最少。 按题意，每个剧团至少演出 1 场。如果 A 剧团在 7 天中只演 1 场，则在 A 团演出的当 天，其它剧团都没有演出，否则将看不到 A 团的演出。这样，该添置演出这 1 场。 如果有 3 个剧团在戏剧节期间都仅仅各演 1 场， 则这 3 个剧团占据 7 天中的 3 天。 从而 其余 9 个剧团只能在其余 4 天中演出。 由于这 9 个剧团也要相互观摩， 故它们各自演出的日2 期号的集合互不包含，由 Spenner 定理，应有 9 ≤ C 4 ，矛盾！所以，至多有 2 个剧团各演1 场，其余剧团每团至少都演 2 场，即至少共演 22 场。 1 1 2 3 4 5 6 7 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ 2 3 4 5 6 7 8 9 10 11 12六、应用抽屉原理证明存在性问题 例 1 由 10 个两位正整数组成集合 S ， 证明： 存在两个无公共元素的非空子集 S1、S 2 ， S 使得其中元素之和相等。20 例 2 一群童子军，年龄从 7 岁到 13 岁，来自 11 个国家。证明：至少有 5 个孩子，每一 个的同龄人多于同国籍的人。 解：作下表帮助分析，把第 i 国且 j + 6 岁的孩子的总人数填入第 i 行第 j 列，记作 a i , j 。 “一个孩子的同龄人多于同国籍的人”就是说“第 i 行的人数少于第 j 列的人数” 。 1（＋6） 1 2 3 4 5 6 7 8 9 10 11 作行列和： 2（＋6） 3（＋6） 4（＋6） 5（＋6） 6（＋6） 7（＋6）a1,1 a 2,1a1, 2 a 2, 2ai, jri计算：= ∑ ai , j (i = 1,2,L,11) ， s j = ∑ a i , j ( j = 1,2, L ,7 )j =1i =1711? 1 1 ? 7 11 ?1 1 ? ai , j ? ? ? = ∑∑ a i , j ? ? ? ∑ ? r s ? j =1 i =1 ? r s ? i, j j ? j ? ? i ? i= ∑∑j =1 i =1 11 7 11ai , j ri7? ∑∑j =1 i =1711ai , j sj=∑i =1117 1 7 1 ∑ ai, j ? ∑ s ri j =1 j =1 j∑ai =111i, j= ∑1 ? ∑ 1 = 4 ，i =1 j =1∵?1 1 ? a i , j ? ? ? & 1 ，对所有 i、j ， ?r s ? j ? ? i至少存在 5 项 a i , j ?∴?1 1 ? ? ?a i , j ≥ 1 至少有 5 个。 ? ?&0?? ?r s ? ?s j & ri i j ? ? ?故 结论成立。 评注：本题充分体现了赋值方法、表格、抽屉原理和换序求和 七、瞄准目标，跟踪配对21 例 1 子集 A ? S = { ,2,3, L ,50} 满足：任意两个不同的元素之和不能被 7 整除。求 1card ( A) 的最大值。解：按照 mod 7 对 S 进行划分：S 0 = {7,14,21,28,35,42,49} ? card (S 0 ) = 7 ，S1 = { ,8,15,22,29,36,43,50} ? card (S1 ) = 8 ， 1 S 2 = {2,9,16,23,30,37,44} ? card (S 2 ) = 7 ，S 3 = {3,10,17,24,31,38,45} ? card (S 3 ) = 7 ，S 4 = {4,11,18,25,32,39,46} ? card (S 4 ) = 7 ，S 5 = {5,12,19,26,33,40,47} ? card (S 5 ) = 7 ， S 6 = {6,13,20,27,34,41,48} ? card (S 6 ) = 7 ，取 A = S1 ∪ S 2 ∪ S 3 ∪ {7} 记的元素个数最多的子集，元素个数为 23。 例 2 设 A ? M = { ,2,3, L ,1995} ，并且当 x ∈ A 时，总有 15 x ? A ，求 card ( A) 的最 1 大值。 解：把 S 中的数按照 15 的倍数分类： 1 2 134 138 … 15 15 × 15 ∴ 15×2 15 × 15 ×2 15×3 15 × 15 ×3 15×4 15 × 15 ×4 15×5 15 × 15 ×5139 15×6 15 × 15 ×6140 15×7 15 × 15 ×7141 15×8 15 × 15 ×8… …133 15 × 133A = { ,2,3,L,8} ∪ { ,135,L,1995} 是元素个数最多的子集，其元素个数为 1 1341870。 注：从后向前拆分：{1,2,3,L,1995} = {,L ,134}∪ {133,132,L ,9} ∪ {8,7,L ,2,1} 。例 3 设 A ? S = { ,2,3, L ,2002} ，并且任意两个数之差既不等于 4，也不等于 7，求 1card ( A) 的最大值；如果 A ? S = { ,2,3,L,2006} ， card ( A) 的最大值是多少？ 1解：从 1，2，3，4，5，6，7，8，9，10，11 这 11 个数中最多选出 1，4，6，7，9 五 个数符合要求。这 5 个数都加上 11 得到的 5 个数也符合要求，由 2002 = 11 × 182 ，所以，card ( A) 的最大值 ≥ 182 × 5 = 910 。22 如果 card ( A) ≥ 911 = 182 × 5 + 1 ，则 182 个数组： （1，2，3，4，5，6，7，8，9，10， 11）（12，13，14，15，16，17，18，19，20，21，22） 、 ，…， （，， ，，，2002）中，至少有一个数组包含子集 A 的至少 6 个数，不妨设这组数是（1，2，3，4，5，6，7，8，9，10，11） ，再将这组数分成 5 个小组 （4，7，11）（3，10）（2，6）（5，9）（1，8） ， ， ， ， ，则其中必有一组中存在 2 个数是前述 6 个数中的，故 A 中必有 2 个数，它们的差是 4 或 7。故 card ( A) 的最大值 & 910 。 ∴card ( A) 的最大值是 910。如果 S = { ,2,3, L ,2006} ，由 2006 = 11 × 182 + 4 ，由上述推证，可得 card ( A) 的最大 1 值是 914。 例 4 已知 M ? S = { ,2,3, L ,100}中没有一个数是另一个数的 2 倍，求 card (M ) 的最 1 大值。 1 2 3 4 5 6 … 12 … 25 … 50 … 100 2 4 6 8 10 12 … 24 … 50 … 100 4 8 12 16 20 24 … 48 … 100 8 16 24 32 40 48 … 96 16 32 48 64 80 96 32 64 96 64 4 3 3card (M ) 的最大值是： 100 ? 50 + 25 ? 12 + 6 ? 3 + 1 = 50 + 13 + 4 = 67 。 M = { ,3,5,L,99} ∪ { } 1例 5 对 Φ ≠ X ? M = { ,2,3, L ,1000} ， α X 为 X 中的最大数和最小数之和，求所有 1 令 这些数 α X 的平均数。 解法一：将集合 M 的所有非空子集进行配对，对 Φ ≠ X ? M ，令X '= { 1001 ? x x ∈ X }23 则 X 1 ≠ X 2 ? X 1 ≠ X 2 ，于是所有的非空子集可以分成两类：' 'T1 = {X X ? M , X ' ≠ X }， T1 = {X X ? M , X ' = X }对 X ∈ T1 ? α X + α X ' = 1001 ，X ∈ T2 ? α X = 1001 ， 所以， 所求的平均数为 1001。 解法二：考虑每个元素对平均数的贡献，采用换序求和方法。 例 6 设集合 A = { ,2,3, L ,336}，若 A 的二元子集 B = {a, b}满足 17 a + b ，则称 B 具 1 有性质 P。 （1）求 A 的具有性质 P 的二元子集的个数； （2） A 的一组二元子集 S1 , S 2 , L , S k ，两两不相交，并且具有性质 P ， k 的最大值。 例 7 设 S = { ,2,3,4}，数列 a1 , a 2 , L , a n 满足：任取非空 B ? S ，在该数列中有相邻的 1card (B ) 项恰好组成集合 B ，求 n 的最小值。例 8 对 n 元 集 合 S 的 两 个 子 集 A、B ， 求 的 card ( A ∩ B ) ， 试 计 算f =A? S , B ? S∑ card ( A ∩ B ) 。A? S B ? S解： f =1 ∑ ∑ card ( A ∩ B ) = ∑ 2 ∑ [card ( A ∩ B ) + card ( A ∩ C B )]A? S B? S S1 1 2 n ?1 n n ?1 = ∑ ∑ card ( A) = ∑ 2 card ( A) = 2 ∑ card ( A) = 2 A? S B ? S 2 A? S 2 A? S 2 n?1 = ? n ? 2 n = n ? 4 n?1 。 2例 9 当 (a1 , a 2 , L , a n ) 取遍 (1,2, L , n ) 的排列时，求A? S∑ [card ( A) + card (C A)]Sf = (a1 ? a 2 ) + (a 2 ? a3 ) + L + (a n ?1 ? a n )2 22的平均值。 对相异两数 x、y ∈ { ,2, L , n} ，( x ? y ) 共出现在 2 ? (n ? 1)! 个 f 中， 1 解： 共有 n! 个 f ，2所以，所有 f 的平均数为24 2 ? (n ? 1)!1≤ x & y ≤ n∑ (x ? y )2n!==2 ? (n ? 1)! ∑≤nx 2 + y 2 ? 2 xy n! 1≤ x & y()2 ? (n ? 1)! n y ?1 2 ∑∑ x + y 2 ? 2 xy n! y = 2 x =1()=2 ? (n ? 1)! n ? 1 ? ∑ ? 6 ( y ? 1)y(2 y ? 1) + ( y ? 1)y 2 ? y 2 ( y ? 1)? n! ? y =2 ? 2 ? (n ? 1)! n 1 ∑ 6 ( y ? 1)y(2 y ? 1) n! y =2==(n ? 1)!3n!∑ (2 yn y=23? 3y 2 + yn)n(n ? 1)! ? n == 3n! ? 2 ?? ?∑ 2 y ? ∑ 3 y + ∑ y ? 3n! ? y = 2 y =2 y =2 ?3 2(n ? 1)! ? 1 n 2 (n + 1)2 ? 2 ? 1 n(n + 1)(2n + 1) + 3 + 1 n(n + 1) ? 1?2 2 ? ?=(n ? 1)! ? n 4 ? n 23n! 2=1 3 n n 2 ? 1 = C n +1 。 6()评注：如果利用表格帮助直观，则可由上三角直接得到f =2 n ?1 i 2 1 n ?1 1 n ?1 j = i (i + 1)(2i + 1) = ∑∑ ∑ ∑ [2i(i + 1)(i + 2) ? 3i(i + 1)] n i =1 j =1 3n i =1 3n i =1==1 n ?1 1 n ?1 1 2 Ai3+ 2 ? 3 Ai2+1 = ∑ ∑ 12Ci3+2 ? 6Ci2+1 = n 4C n4+ 2 ? 2C n3+1 3n i =1 3n i =11 (n + 2)(n + 1)(n ? 1) ? 1 (n + 1)(n ? 1) = 1 (n + 1)n(n ? 1) = C n3+1 。 6 3 6()()()八、递推计数方法 例 1 如果 T ? S = { ,2,3, L ,10} 中至少有 2 个元素， 1 且其中任意两个元素之差的绝对值 大于 1，则称子集 T 具有性质 P ，求 S 的所有具有性质 P 的子集的个数。 解：一般化，设 { ,2, L , n} 的具有性质 P 的所有子集的个数为 a n ，则 1a n+ 2 = a n +1 + a n + n n ∈ N * ， a1 = 0 ， a 2 = 0 ， a 3 = 1 ， a 4 = 3递推，可得 a10 = 133 。()25 例 2 整数 1,2,3, L , n 的排列满足：每个数或者大于它前面的所有数，或者小于它前面的 所有数，求这样排列的个数。 解：记所求的排列个数为 a n ，则 a1 = 1 ；对 n ≥ 2 ，如果 n 排在第 k (≥ 2 ) 位，则它后面n ? k 个数完全确定，即 n ? k , n ? k ? 1, L ,3,2,1 ；它前面的 k ? 1 个数有 a k ?1 种排法（每个数只和它前面的数相比较） ；当 n 排在第一位时，只有一种排法 n, n ? 1, L ,3,2,1 。所以，由 加法原理，得a n = 1 + a1 + a 2 + L + a n ?1 (n ≥ 2) 。可以证明： a n = 2n ?1(n ∈ N )。*评注： 也可以根据末位数是 1 或 n ， 直接创建一个根简单的递推关系 a n = 2a n ?1 (n ≥ 2 ) 。 例 3 用正整数组成数列，使数列的每一项都比它前一项的平方还大，而最后一项均为 1969（这类数列可以有不同的长度） 。证明：这种数列的个数少于 1969。 解：把以 n 结尾并具有题目中所述性质的数列的个数记为 f (n ) ，则f (1) = 1, f (2) = 2, f (3) = 2, f (4) = 2 。对 n ≥ 5 ，目标是证明： f (n ) & n ；假设对所有 k & n ，总有 f (k ) ≤ k ；则当 k = n 时， 把所有满足要求的数列的最后一项 n 去掉，那么除了只有一项“ n ”的数列之外，其余数列 都变成最后一项小于 n 的数列，并且仍具有题目要求的性质，故由归纳假设，得f (n ) ≤ 1 + ∑ f (k ) ≤ 1 + ∑ k = 1 +k =1 k =1[ n][ n]1 2[ n ][ n ]+ 1) ≤ 1 + 1 n ( ( 2n +1 & n 。)故f (1969) & 1969 。例 4 正整数 1，2，3，4，5，6 的排列 (n1 , n 2 , n3 , n 4 , n5 , n6 ) 具有具有如下性质：对于i ∈ { ,2,3,4,5}， (n1 , n 2 , L , ni ) 都不是 (1,2, L, i ) 的排列。求这种排列的总数。 1解法：设 (m1 , m2 , m3 , m 4 , m5 , m6 ) 是不满足条件的排列，则存在 2 ≤ i ≤ 6 ，使得{mi , ni +1 ,L , m6 } = {i, i + 1,L,6}，{m , njj +1, L , m6 } ≠ { j , j + 1, L ,6}， j = i + 1, i + 2, L 6 。26 其中当 i = 6 时，后一个式子不存在。记满足上述条件的排列 (mi , ni +1 , L , m6 ) 的个数为f (i ) ，则不符合条件的排列的总数 S = ∑ f (i )(i ? 1)! 。i=26∵f (6) = 1 ， f (5) = 2!? f (6) = 1 ， f (4 ) = 3!? f (5) ? 2! f (6) = 3 ， f (3) = 4!? f (4) ? 2! f (5) ? 3! f (6) = 13 ， f (2 ) = 5!? f (3) ? 2! f (4) ? 3! f (5) ? 4! f (6) = 71 ，∴ S = 71 + 13 × 2!+3 × 3!+1 × 4!+1 × 5! = 259 。 故 符合条件的排列的总数为： 6!?259 = 461 。 例 5 给 200 人依次编号为 1，2，3，…，2000，如果某几个人（可以 1 人，但不可无人） 的编号之和是 5 的倍数，则称之为“优团” 。求这 2000 人可组成所有“优团”的个数。 解 ： 令 S n = { ,2,3, L , n} ， 对 其 子 集 ， 按 其 中 数 之 和 mod 5 的 值 分 成 5 类 ： 1M j ( j = 0,1,2,3,4 ) ，记这 5 类子集的个数依次为 a n , bn , c n , d n , en ，则本题目标是求 a 2000 ，一般些，先求出 a 5 n 。 按定义，有a n + bn + c n + d n + en = 2 n ， n = 1,2,3, La 5n = 2a5 n ?1 ， a 5n ?1 = a 5 n? 2 + b5n ? 2 ， a 5n ? 2 = a 5 n?3 + c5n ?3 ， b5 n? 2 = b5 n ?3 + d 5n ?3 ，∴a 5n = 2(a 5n ? 2 + b5 n? 2 ) = 2(a5 n ?3 + c5 n?3 + b5n ?3 + d 5 n?3 ) a 5 n = 2 5 n ? 2 ? 2e 5 n ? 3∵e 5n ? 3 = e 5 n ? 4 + c 5n ? 4 , e 5n ? 4 = e 5n ? 5 + d 5 n ? 5 ， c5n ? 4 = c5 n?5 + b5n ?5 a 5n = 2 5 n ? 2 ? 2(e5n ? 4 + c5 n ? 4 ) = 2 5n ? 2 ? 2(e5n ?5 + d 5n ?5 + c5n ?5 + b5 n ?5 ) = 2 5 n ? 2 ? 2 2 5 n ? 5 ? a 5 n ? 5 = 3 × 2 5 n ? 4 + 2a 5 n ? 5 a5n = 3 × 2 n × 2 4n ? 1 + 2n 。 4 2 ?1∴()故27 ∴a 2000 =2 400 21600 + 4 。 5 2 400 21600 + 4 ? 1。 5()除掉空集，可知，优团的个数为 a 2000 ? 1 =()九、元素与子集的结合关系对应表L 1 取 A1、A2、 、Ak ? { ,2,L , n}(n ∈ N , n ≥ 2 ) ， 记 元 素 i 含 在 取 定 的 d i 个 子 集 中(i = 1,2,L , n ) ； 当且仅当 i ∈ A j 时， 在下表第 i 行第 j 列填入 1 (i = 1,2,L , j = 1,2,L , k ) 。A11 2 3 … 1 1 1 1 1 1 1 1A2A31…Aj…Ak1 1i…n（1）统计表中 1 的个数，就是计算表中 1 的总和：分别按行、列先后统计，算两次，得∑ d i = a = ∑ card ( Ai ) 。i =1 i =1nk（2）当且仅当 t ∈ Ai ∩ A j 时，称 Ai , A j 为关联于元素 t 的一个子集对，统计与所有元素 关联的子集对总数，得{}∑Ci =1n2 di=b=1≤ i & j ≤ k∑ card (A ∩ A ) 。i j这是两个及其常用的关系等式，通常表现为（1）是条件，对（2）应用 Caughy 不等式 或逐步调整法，求最值，推证存在性。 十、等价关系 10．1 关系：在集合的元素之间引入一种关系 R ，当两个元素 a、b 之间具有这种关系时， 记作 aRb ，否则记作 a Rb 。 定 理 ： 集 合 A 上 的 一 种 关 系 R ， 确 定 A 到 W = {r , f } 的 一 个 映 射 R : A → W ，aRb ? f (a ) = f (b )，?a、b ∈ R ；反之，一个映射 R : A → W 给出集合 A 中元素之间的28 一种关系 aRb ? f (a ) = f (b )，?a、b ∈ R 。 10．2 等价关系：在集合 A 的元素之间如果存在一种关系 R（如果 A 的两个元素 x、y 之间 有这种关系，就记作 xRy ；如果 A 的两个元素 x、y 之间没有这种关系，就记作 x R y ）满 足三个条件： ； ；③ ， ① aRa, ?a ∈ A（反身性） ② aRb ? bRa（对称性） (aRb ) ∧ (bRc ) ? aRc（传递性） 则称关系 R 为集合 A 的元素间的一个等价关系。譬如：数的相等、图形的全等、数的同余、 同班同学、同母生、同国籍、同省份，等等，这些都是等价关系；但是，数之间的大于、人 之间的朋友、同学，等，这些都不是等价关系。 等价关系要求的三个条件时相互独立的，思考下面的推理有什么错误？ 假设集合 A 上的一个关系 R 满足对称性和传递性，则 aRb ? bRa ? aRa ，即由对称性与传递性可以推出反身性，为什么？ 10．3 等价分类：如果非空集合 A 的元素之间定义了一种等价关系 R ，则可以把其中相互等 价的元素归入一类，譬如 A 中与 a∈ A 的所有元素组成 A 的一个子集，记作[a] = {x ∈ A xRa}，这个子集称为元素 a 的等价类，也称 [a] 中其它元素的等价类；可以证明： 定理 1： [a ] ≠ Φ 。 定理 2：如果 a、b ∈ A ，当 a Rb ，则 [a ] ∩ [b ] = Φ ；当 aRb 时， [a ] = [b ] 。 定 理 3 ： 如 果 A 的 元 素 可 以 组 成 k 个 互 不 相 同 的 等 价 类 [a1 ], [a 2 ], L , [a k ] ， 则A = [a1 ] ∪ [a 2 ] ∪ L ∪ [a k ] ， 且 [ai ] ∩ a j ≠ Φ (1 ≤ i & j ≤ k ) 。 这 时 ， 就 称 全 体等 价 类[ ][a1 ], [a2 ],L, [ak ] 构成集合 A 的一个 k ? 等价划分（ k 类） 。例 1 整数集 Z 可以按照 mod n 划分成 n 个同余类： Z = [0] ∪ [1] ∪ [2] ∪ L ∪ [n ? 1]。 十一、集合的划分 11． 1 定义：如果存在集合 A 的 k 个非空子集 A1 , A2 , L , Ak ， 使得 A =kUAi =1i，并 且Ai ∩ A j = Φ(1 ≤ i & j ≤ n ) ，则称子集族 {A1 , A2 , L , Ak } 构成集合 A 的一个 k ? 划分；其中每个子集 Ai 成为一个快。 定理 4：集合 A 上的等价关系与集合 A 的划分是一一对应的。 11．2 定义：一个 n 元集合的全部 k ? 划分的个数，称为第二类 Stirling 数，记作 S (n, k ) 。 这种数有如下性质：29 ① S (n,1) = 1 ； ② S (n, n ) = 1 ； ③ S (n, k ) = 0(k & n ) ； ④ S (n + 1, k ) = S (n, k ? 1) + kS (n, k )(1 ≤ k ≤ n ) ； ⑤ S (n,2 ) = 2n ?1?1；2⑥ S (n, n ? 1) = C n ； ⑦ S (n, k ) =m = k ?1∑Cnm n? S (m, k ? 1) 。其中①、②、③都是平凡的，下面我们证明④～⑦。 证明：④把 n + 1 元集合 A = {a1 , a 2 , L , a n +1 }的所有 k ? 划分分成两类： 其一， {a n +1 } 是 A 的 k ? 划分中的一块，这时只需在对 n 元集合 C A {a n +1 } 作 k ?1 ? 划 分，有 S (n, k ? 1) 种，故 A 的这类 k ? 划分共有 S (n, k ? 1) 种。 其二， {a n +1 } 不是 A 的 k ? 划分中的一块，先对 n 元集合 C A {a n +1 } 作 k ? 划分，共有1 S (n, k ) 种方法，再将 a n+1 添加到 k 块中的某一块，有 C k 种方法，每一种添加法解得到 A 的一个 k 划分，共有 kS (n, k ) 个划分。 ∴S (n + 1, k ) = S (n, k ? 1) + kS (n, k ) 。⑤利用④把 S (n,2 ) 作如下展开：S (n,2) = S (n ? 1,1) + 2S (n ? 1,2) = 1 + 2[S (n ? 2,1) + 2S (n ? 2,1)]= 1 + 2 + 2 2 S (n ? 2,2 )= LL= 1 + 2 + 2 2 + L + 2 n? 2 S (2,2 ) = 1 + 2 + 2 2 + L + 2 n ? 2 = 2 n ?1 ? 1 。⑥利用④把 S (n, n ? 1) 作如下展开：S (n, n ? 1) = S (n ? 1, n ? 2) + (n ? 1)S (n ? 1, n ? 1) = S (n ? 1, n ? 2) + (n ? 1)30 = S (n ? 2, n ? 3) + (n ? 2) + (n ? 1)= LL = S (2,1) + 2 + 3 + L + (n ? 1) = 1 + 2 + 3 + L + (n ? 1)= n(n ? 1) 2 = Cn 2⑦ S (n + 1, k ) 是集合 A = {a1 , a 2 , L , a n , a n +1 } 的 k 划分数。对于 A 的一个 k 划分，设包含a n+1 的那一块为 B ，则其余的 k ? 1 块构成集合 C A B 的一个 k ? 1 划分；反过来，给定 A 的一个含 a n +1 的子集 B ，若 card (C A B ) ≥ k ? 1 ，则 C A B 的一个 k ? 1 划分连同 B 就构成 A 的 一个 k 划分。 如下构造 A 的 k 划分：先取 A 的一个不含 a n +1 的子集 C ，使得 card (C ) ≥ k ? 1 ；作 C 的一 个 k ? 1 划分，再拼上 C A C 就构成 A 的一个 k 划分；而 m = card ( C ) ∈ {k ? 1, k ,L , n ? 1} ， 并且取定了 m ，有 C n 种方法选择 C ，每个 C 的 k ? 1 划分数有 S (m, k ? 1) ，所以，有mS ( n + 1, k ) =m = k ?1） ∑ C S ( m, k ? 1) （没有重复！m nn ?1以上算法是构造性的，同时也给出了划分的构造方法。譬如：1 例 1 S (4,2 ) = 2 3 ? 1 = 7 ，说明集合 A = { ,2,3,4} 有 7 个 2 ? 划分，可以按上述算法写出来：{1,2,3,4} = {1,2} ∪ {3,4} = {1,3}∪ {2,4} = {1,4} ∪ {2,3}= {2,3,4} ∪ { } = { ,3,4} ∪ {2} = { ,2,4} ∪ {3} = { ,2,3} ∪ {4} 1 1 1 1由此及 S (5,2 ) = 2 4 ? 1 = 15 ，可以作出 5 元集合 A = { ,2,3,4,5}的 15 个 2 ? 划分，它们是： 1{1,2,3,4,5} = {5} ∪ {1,2,3,4} = {4,5} ∪ {1,2,3} = {4}∪ {1,2,3,5} = {3,4,5}∪ {1,2}= {3,4} ∪ { ,2,5} = {3,5} ∪ { ,2,4} = {3} ∪ { ,2,4,5} = { ,3,5} ∪ {2,4} 1 1 1 1 = { ,3} ∪ {2,4,5} = { ,3,4,5} ∪ {2} = { ,3,4} ∪ {2,5} = {2,3,5} ∪ { ,4} 1 1 1 1 = {2,3} ∪ { ,4,5} = {2,3,4,5} ∪ { } = {2,3,4} ∪ { ,5} 1 1 111．3 有限集合的 m 类平均划分31 定义：如果数集 X = { ,2,3, L , n}的一个 m 划分 1X = U Ai (m ≥ 2 )i =1m满足条件? ? n? ?card ( Ai ) = card (A j )? = m ? ? ? ? (1 ≤ i & j ≤ n ) ? ? n(n + 1) ? ? ∑ x = ∑ x? = ? ? x∈Ai 2m ? x∈A j ? ? 则称这个划分为集合 X 的 m 类平均划分。定理：如果数集 X = { ,2, L , n} 有 m 类平均划分，则 1 是， m 也是奇数；反之，也成立。 证明： (? ) 若 X 有 m 类平均划分，则存在 p ∈ N * ， p & 1 ，使得 n = mp ，所以每一类的元素之 和为n = p ∈ N * ，并且当 p 是奇数 mx∈Ai∑x = m∑x =x∈ A1n(n + 1) mp(mp + 1) p(mp + 1) = = ∈ N* 2m 2m 2∴当 p 是奇数时， (2, p ) = 1 ? 2 mp + 1 ? mp 是奇数 ? m 是奇数。(?) 已知数集 X = {1,2,L, n}，n = mp ，m、p ∈ N * , m ≥ 2 但除去“ p 是奇数，且 m是偶数”的情况。 ①若 p = 2k ，则 n = 2km ，把 X 中的数如下排成 2k × m 数阵：1 2m 2m + 1 4m L 2km2 2m ? 1 2m + 2 4m ? 1 L 2km ? 1L L L L L Lm ?1 m+2 3m ? 1 3m + 2 Lm m +1 3m 3m + 1 L2(k ? 1)m + 1 2(k ? 1)m + 2 L(2k ? 1)m ? 1 (2k ? 1)m (2k ? 1)m + 2 (2k ? 1)m + 1将第一列、第二列、…、第 m 列的数分别作成集合 A1 , A2 , L , Am ，则所得子集族{A1 , A2 ,L , Am }构成集合 X 的一个 m 类平均划分。* 则 ②若 p = 2k + 1 k ∈ N ， n = (2k + 1)m ，()∑ x = 2 m(2k + 1)[m(2k + 1) + 1]，所以，1x∈A32 m ∑ x ? “ m 是奇数 ? n 是奇数” 。x∈A先将 1,2, L , n 的后 n ? 3m （偶数）个连续正整数仿①排成 (2k + 1) ? 3 = 2k ? 1 行， m 列数阵；再把 1,2,3, L ,3m 排成 3 行 m 列，且各列之和 =3(3m + 1) 即可： 21 3m + 1 2 3m2 2mL Lm?2 m+25m ? 1 5m + 3 L 2 2m ?1 3m + 3 2 2m + 1m m +1 5m + 1 2(左 ← 右，先奇数位后偶数位) (左 ← 右，先偶数位后奇数位)这样排得的各列之和都是 11．4 置换的结构与计数(3m + 1) ? 3m = 3(3m + 1) 。2m 2设 A = { ,2,L , n} ， 则 称 映 射 f : A → A 为 集 合 A 的 一 个 置 换 。 任 取 一 个 置 换 1f : A → A ，构图 G ( A, E ) ：把 A = { ,2,L , n} 中的元素作为点，从 i 向 f (i ) 连一（有向） 1条边，得一有向图。任取 i ∈ A ，则存在最小正整数 k i ，使得 f( ki )(i ) = i ，那么图 G 有一条(k ?1) (k ) 中存在一条从 i 出发又回到 i 的圈： i → f (i ) → f (2 ) (i ) → L → f i (i ) → f i (i ) = i ，叫轮换；从 G 中取出这个圈，对剩下的元素如此操作，得到图 G 若干个不相交的圈（轮换） 组成。所以，如果在集合 A = { ,2,L , n} 的元素之间定义一个关系 R ： aRb ? ?l ∈ N ， 1*使得 f (l ) (a ) = b ，则这是一个等价关系，从而可得到集合 A 的一个 k ? 划分，其中每一块 就是一个轮换中的元素，k 就是组成置换 f : A → A 的不同轮换的个数。 设置换 f : A → A 有 λi 个长为 i 的轮换（圈）组成，则称 f : A → A 为 1 1 2 2 L nλ λ λn型的，这类置换的个数为n!∏ii =1n，所以要计算满足某种条件的置换的个数，首先要弄清楚满足这种条件的置换的λiλi !型。 11．5 第一类 stirling 数 定义：给定正整数 n ，则称关于 x 的 n 次多项式x ( x ? 1)( x ? 2 )L ( x ? n + 1) = s ( n, 0 ) + s ( n,1) x + s ( n, 2 ) x 2 + L + s ( n, n ) x n L 的系数 s ( n, 0 )，s ( n,1)，s ( n, 2 ) x ， ，s ( n, n ) 为第一类 stirling 数。233 递推公式： s ( n + 1, k ) = s ( n, k ? 1) ? ns ( n, k ) ， k ∈ {1, 2,L , n} 。 证明：由x ( x ? 1)( x ? 2 )L ( x ? n + 1) = ( s ( n, 0 ) + s ( n,1) x + s ( n, 2 ) x 2 + L + s ( n, n ) x n ) ( x ? n )= ? ns ( n, 0 ) + ( s ( n, 0 ) ? ns ( n,1) ) x + ( s ( n,1) ? ns ( n, 2 ) ) x 2 +L + ( s ( n, n ? 1) ? ns ( n, n ) ) x n + s ( n, n ) x n +1∴s ( n + 1, k ) = s ( n, k ? 1) ? ns ( n, k ) ， k ∈ {1, 2,L , n} 。11．6 集合划分的例 例 1 能否把所有正整数分组，使得第 k 组恰好有 k 个数 (k = 1,2,3, L , ) ，并且使得每组 中的所有数之和都恰好为某个正整数的平方？ 解：正整数集 N 得这种划分是存在的，譬如：*A1 = { }， A2 = {2,2 7 ? 2}， A3 = { ,4,3 7 ? 3 ? 4}，……， 1 3Ak = a1 , a 2 , L , a k ?1 , k 7 ? a1 ? a 2 ? L ? a k ?1 ， k = 4,5,6, L 。其中 Ak 的前 k ? 1 个数是前 k ? 1 个集合 A1 , A2 , L , Ak ?1 未曾出现过的最小的 k ? 1 个正整 数。 例 2 给定正有理数 c ≠ 1 ， 证明： 正整数集合 N 可以表示成两个不不相交的子集 A、B*{}的并，使得同一子集的任何两个数之比都不等于 c 。 证明：我们递归地构造集合 A、B 。令 1 ∈ A ；当 1,2, L , n 已按要求分配到集合 A、B 中之后，我们来如下安排 n + 1 ：如果存在 k1 ∈ { ,2, L , n}，使得 1 到不含 k1 的那个子集中；如果存在 k 2 ∈ { ,2, L , n} ，使得 1k1 = c ，则把 n + 1 分配 n +1n +1 = c ，则把 n + 1 分配到不含 k2k 2 的那个子集中；如果上述 k1、k 2 都不存在，则把把 n + 1 随意分配到子集 A、B 中，并使k1 n +1 * &1& ，故 k1、k 2 不可能同时存在。故正整数集 N 存在 n +1 k2两者都不是空集；由于 符合题意的 2 划分。例 3 将集合 S = { ,2,3, L ,100} 分成 7 个子集，求证：其中至少有一个子集，要么含有 1 4 个数 a、b、c、d ，使得 a + b = c + d ，要么含有 3 个数 e、f、g ，使得 e + f = 2 g 。34 证明：考虑从元素较多的那个子集入手。 ∵ 100 = 14 × 7 + 2 ∴ 必有一个子集含有至少 15 个数，设 A = {a1 , a 2 , L , a15 , L , a k }(k ≥ 15) ，不妨设1 ≤ a1 & a 2 & L & a15 & L & a k ， 则 由 其 中 较 小 的 15 个 数 a1 , a 2 , L , a15 可 组 成2 C15 = 105 & 99 个差 a j ? ai (1 ≤ i & j ≤ 15) ∈ { ,2, L ,99}，由抽屉原理，这些差中必存在相 1等 数 ， 不 妨 设 a j ? a k = ai ? a h ( j & i ) 。 若 h = j ， 则 a i + a k = 2a j ； 若 j ≠ h ， 则a k , a h , a j , a k 互不相同，并且 a j + a h = a i + a k 。例 4 给定 n 个正整数： a1 = 1, a 2 , a 3 , L , a n ，其中 a i ≤ a i +1 ≤ 2ai (i = 1,2, L , n ? 1) ， 并且所有 n 个数之和为偶数。问：能否把这些整数分成两组，使得两组中整数之和相等？ 解：首先，将 a n、a n ?1 分别放入 A、B 两组，然后再依次放入 a n ? 2 , a n ?3 , L , a 2 , a1 ，具 体方法是：每次放入和数较小的一组之中；当两组和数相等时，可任选一组放入；直到放完a1 为止，就把所给的正整数分成了 A、B 两组。∵a i ≤ a i +1 ≤ 2ai ? ai ≤ 2 i ?1 a1 = 2 i ?1 ， a n ≤ 2 n?1 ， a n?1 ≤ 2 n ? 2 ， a n? 2 ≤ 2 n ?3 ，…， a 2 ≤ 2 ， a n ≤ 1 。∴∵ ∴0 ≤ a n ? a n ?1 ≤ a n ?1 ，将 a n、a n ?1 分别放入 A、B 两组之后， 0 ≤∑x?∑x ≤ ax∈A x∈Bn ?1，接着，应该把a n? 2 ≤ 2 n ?3 放入 B 组，这时有∑ x ? ∑ x = a ? (ax∈A x∈B nn ?1+ a n ? 2 ) = (a n ? a n ?1 ) ? a n ? 2 ≤ a n ?1 ? a n ? 2 ≤ a n ? 2 ， + a n ? 2 ) ≥ a n ? (a n + a n ? 2 ) = ? a n ? 2∑ x ? ∑ x = a ? (ax∈A x∈B nn ?1故∑x?∑x ≤ ax∈ A x∈Bn?2 。假设放完 a n , a n ?1 , L , a i 之后，有∑x?∑x ≤ ax∈ A x∈Bi，接下来的怎么放 a i ?1 ，应根据∑ x ? ∑ x 的正负确定。x∈ A x∈B若0 ≤∑ x ? ∑ x ≤ a ，则令 ax∈A x∈B ii ?1∈ B ，这时，有35 ? a i ?1 ≤ ∑ x ? ∑ x ≤ ai ? ai ?1 ≤ ai ?1 ，从而 ∑ x ? ∑ x ≤ a i ?1 ；x∈ A x∈B x∈ A x∈B若 ? ai ≤∑ x ? ∑ x ≤ 0 ，则令 ax∈A x∈B x∈ Ai ?1∈ A ，这时，有? a i ?1 ≤ a i ?1 ? a i ≤ ∑ x ? ∑ x ≤ ai ?1 ，从而也有 ∑ x ? ∑ x ≤ a i ?1 。x∈B x∈ A x∈B故放完 a n , a n ?1 , L , a i , a i ?1 之后，应有∑x?∑x ≤ ax∈ A x∈Bi ?1 。由数学归纳法，可知，按上述方法，放完 a n , a n ?1 , L , a i 时，总成立∑x?∑x ≤ a 。x∈ A x∈B i 1∴按上述方法，依次放完 a n , a n ?1 ,L , a 2 , a1 时，应该成立nn n∑x?∑x ≤ ax∈ A x∈B= 1，又2 ∑ a i ， ∑ x ? ∑ x = ∑ ai ? 2∑ x ≡ ∑ a i (mod 2 ) ，i =1x∈A x∈B i =1 x∈B i =1∴2∑ x ? ∑ x ? ∑ x ? ∑ x = 0，x∈A x∈B x∈A x∈B故按上述方法依次放完 a n , a n ?1 ,L , a 2 , a1 ，有∑x = ∑x。x∈A x∈B评注：自然应从最自然的方法入手。 例 5 试证：对每个大于 1 的整数 r ，都能找到一个最小的正整数 h(r ) ，使得在集合{1,2,L, h(r )}的 任 何 r ? 划 分 中 ， 都 存 在 整 数 a ≥ 0 及 1≤ x ≤ y ， 满 足a + x, a + y, a + x + y 含于划分的同一组中。证明：先证 h(r ) ≥ 2r ，考察集合 { ,2, L ,2r ? 1}的如下划分： 1{1,1 + r}, {2,2 + r},L, {r ? 1,2r ? 1}, {r}。如果存在整数 a ≥ 0 及 1 ≤ x ≤ y ，使得 a + x, a + y , a + x + y 含于同一组中，由这三个 数中至少有两个不等，所以，它们不能同在 {r }组中。设它们都在 {k , k + r }(1 ≤ k ≤ r ? 1) ， 则必有?x = y = k ? a ?a + x = a + y = k ?? ，矛盾！ ? ?a + x + y = k + r ?a = k ? r & 0故 不存在满足要求的整数 a ≥ 0 及 1 ≤ x ≤ y ，所以 h(r ) ≥ 2r 。36 再证： h(r ) = 2r 满足要求。1 则 对 { ,2, L ,2r ? 1,2r} 的任一 r ? 划分， r , r + 1, r + 2, L ,2r 这 r + 1 个正整数中必有两个数 u、v 含于同一组，不妨设 u & v ，令a = 2u ? v(≥ 0), x = y = v ? u (≥ 1) 。则a + x = a + y = u ， a + x + y = v 在同一组。故h(r ) 的最小值是 2r 。*例 6 设k ∈ N ， 集合 M k = 2k + k ,2k + k + 1,2k + k + 2, L ,2k + 3k 是否存在 22 2 2 2{}－划分，使得两个子集中个数的平方和相等？ 解：答案是肯定的，譬如，取Ak = 2k 2 + k ,2k 2 + k + 1,2k 2 + k + 2, L ,2k 2 + 2k ， Bk = 2k 2 + 2k + 1,2k 2 + 2k + 2,2k 2 + k + 2, L ,2k 2 + 3k ，则{ {}}M k = Ak ∪ Bk ，且 Ak ∩ Bk = Φ 。计算：x∈Ak∑x2?x∈Bk∑x22= ∑ 2k 2 + k + i ? ∑ 2 k 2 + 2 k + i2 i =0 i =1kk()k()2= (2k2+ k ) + ∑ [(2ki =1 k 22+ k + i ? 2 k 2 + 2k + i) (2)]2= 2k 2 + k = 2k 2 + k∴x∈Ak() ? ∑ k (4ki =12+ 3k + 2i)()2? k 4k 3 + 4k 2 + k = 02()∑x2=x∈Bk∑x。例 5 设 A = (0,1) ∩ Q ， ?p ∈ A ，且 ( p, q ) = 1 ，定义区间 q? p? ? p 1 p 1 ? I? ? = ? ? 2 , + 2 ? ? q ? ? q 4q q 4 q ? ? ? ? ?37 证明：数解p ∈A qU I? q ? 。 ? ?? ?? p?十二、正整数的分拆 12 ． 1 定 义 ： 正 整 数 n 的 一 个 k 分 拆 就 是 把 n 写 成 k 个 正 整 数 之 和 ：n = n1 + n 2 + L + n k k ∈ N * 的一种表示方法；其中 ni ∈ N * (1 ≤ i ≤ k ) 叫做该分拆的的部分量；分拆分为有序分拆和无序分拆，在有序分拆中， ni ∈ N * (1 ≤ i ≤ k ) 叫做该有序分拆 的第 i 个部分量。 12．2 有序分拆的计数公式 ①正整数 n 的有序 k 分拆 n = n1 + n 2 + L + n k k ∈ N * 的个数等于不定方程()()x1 + x 2 + L + x k = nk ?1 的正整数解数 C n ?1 。②正整数 n 的要求第 i 个部分量 ni ≥ pi 的有序 k 分拆 n = n1 + n 2 + L + n k k ∈ N * 的个数 是 C k ?1k()。n+k ?∑ pi ?1i =1k ?1 ③正偶数 2n 的 k 分拆，要求个分量都是正偶数的有序分拆数为 C n ?1 。2n = n1 + n2 + L + nk ? n =n n1 n2 + +L+ k 2 2 2k ?1 2 ?1④正整数 n ≡ k (mod 2 ) 的满足个分量都是奇数的有序 k 分拆的个数为 C n + k 。 转化为n = n1 + n2 + L + nk ?的正整数解数 C n + k ，或2 ?1 k ?1n +1 n + k n1 + 1 n2 + 1 = + +L+ k 2 2 2 2n = n1 + n2 + L + nk ?的非负整数解数 C n ? k2 k ?1 + k ?1 ?1n +1 n + k n1 + 1 n2 + 1 = + +L+ k 2 2 2 2k? = C n +1 。 k 212．3 无序分拆的计数结论 正整数 n 的无序 k 分拆 n = n1 + n 2 + L + n k 的个数记作 B (n, k ) ，n 的所有无序分拆的38 个数记作 B (n ) ，则 ① B (n, k ) = 0(k & n ) ， B (n,1) = 1 ， B (n, n ) = 1 ； ② B (n ) =∑ B(n, k ) ；k =1n③ B (n + k , k ) = B (n,1) + B (n,2 ) + L + B (n, k ) 。 证明： n = n1 + n 2 + L + n k ，不妨设 n1 ≥ n 2 ≥ L ≥ nk ≥ 1 （无序可定序） 正整数 n 的至多 k 个分布量的无序分拆总数＝ B (n,1) + B (n,2 ) + L + B(n, k ) ，每个这 样的分拆可以表示为n = n1 + n 2 + L + n m + 0 + L + 0 ，共 k 个分布量，其中 n1 ≥ n 2 ≥ L ≥ n m ≥ 1(1 ≤ m ≤ k ) 。作映射 f : 把正整数 n 的这个 m 分拆映射到正整数n + k 的 k 分拆： n + k = (n1 + 1) + (n 2 + 1) + L + (n m + 1) + 1 + L + 1 ，共 k 个分布量，其中 n1 + 1 ≥ n 2 + 1 ≥ L ≥ n m + 1 ≥ 2(1 ≤ m ≤ k ) 。 可以证明： f 是双射，所以B(n + k , k ) = B(n,1) + B(n,2) + L + B(n, k )④正整数 n 的 2 分拆数 B (n,2 ) = ? ? 。 ?2? 证明：由二分拆 n = n1 + n 2 , n1 ≥ n 2 ≥ 1 ? n 2 ∈ ?1,2,3, L , ? ? ? ，所以有 2?n?? ?? n ?? ? ???n? B (n,2 ) = ? ? 。 ?2?⑤如果正整数 n 的无序 k 分拆中有 k i 个分量为 i (1 ≤ i ≤ n ) ，则该分拆可写为n = k1 ? 1 + k 2 ? 2 + L + k n ? n其中 k1 + k 2 + L + k n = k , k i ≥ 0(i = 1,2, L , n ) 。 例 1 若干个正整数之和等于 1976，求这些正整数之积的最大值。 解：因为和为 1976 的正整数有且只有有限组，所以，所求最大值是存在的。39 设 x1 + x 2 + L + x n = 1976 xi ∈ N , i = 1,2, L , n ， 下 面 应 用 逐 步 调 整 法 求*()f = x1 x 2 L x n 的最大值。①若存在某个 xi & 4 ，由 2 + ( xi ? 2 ) = xi ，且 2 × ( xi ? 2 ) = 2 xi ? 4 & xi ，所以，用两 个数 2 和 xi ? 2 代替一个数 xi 时，可使乘积 f 变大，故所有 xi ≤ 4 。 ②若存在某个 xi = 1 ，由 xi x j = x j & x i + x j ，所以用一个数 xi + x j 代替两个数 xi , x j 后，可使乘积 f 变大，故所有 xi ∈ {2,3,4} 。 ③由 4 = 2 + 2 = 2 × 2 = 4 ，若存在 xi = 4 ，则可用两个 2 代替一个 4，乘积 f 的值不 变，故可令所有 xi ∈ {2,3} 。r t 由 且 故若 r ≥ 3 ， ④综上所述， 乘积 f = 2 ? 3 (r、t ∈ N ) ； 2 + 2 + 2 = 3 + 3 ， 2 & 3 ，3 2则可用两个 3 代替三个 2，使得乘积 f 继续变大，故 r ∈ {0,1,2}。 ⑤由 1976 = 658 × 3 + 2 ，知 r = 1, s = 658 ，所以 f max = 2 × 3658。例 1 证明：除了有限个正整数之外，其他正整数 n 均可表示成 2005 个正整数之和：n = a1 + a 2 + L + a 2005并且满足 1 ≤ a1 & a 2 & L & a 2004 , a i ai +1 (i = 1,2,3, L ,2004 ) 。十三、分配问题汇总 把 n 个小球分配到 r 个盒子里，不同方法总数记为 f (n, r ) ；求解分配问题种数要考虑 以下三方面的因素： n 个球是完全相同的，还是完全不同的？ n 个盒子是完全相同的，还是 完全不同的；是否允许有空盒？各种分配问题的计数结果如下表：n 个小球不同 不同r 个盒子 是否允许有空盒 分配方案数不同 不同 允许 不允许数学模型 重元排列rnr!?S (n, r )不同相同允许∑ S (n, i )i =1n集合划分40 不同相同不允许S (n, r )不定方程r? C n +1?1 r相同不同允许x1 + x2 + L + xr = n的非负整数解数 不定方程相同不同不允许r ?1 C n ?1x1 + x2 + L + xr = n的正整数解数相同相同允许∑ B(n, i )i =1r正整数的无序分拆 相同 相同 不允许B(n, r )十四、卡特兰数 14．1 定义：一个凸 n 边形，通过不相交于形内的对角线，把这个凸 n 边形划分成若干个三 角形，不同划分的数目称为卡特兰数 ( Catalan ) ，记作 hn 。 14．2 引理：一个凸 n 边形，通过不相交于形内的对角线，把这个凸 n 边形划分成若干个三 角形，对角线的条数为 an = n ? 3 。 证明： a3 = 0 = 3 ? 3 。 假设 ak = k ? 3 ，则对凸 k + 1 边形，先任意作出一条对角线， 把这个凸 k + 1 边形分成一个凸 s 边形和一个凸 r 边形，则A1 An+1 An A2 Ak+1 Ak-1 Akak +1 = as + ar + 1 = ( s ? 3) + ( r ? 3) + 1 = s + r ? 5 。∵ ∴r + s = k + 3，ak +1 = s + r ? 5 = ( k + 3) ? 5 = ( k + 1) ? 3 ，an = n ? 3 。故14．3 初值： h2 = 1 ， h3 = 1 ， h4 = 2 ， h5 = 5 。 14．4 递推公式： （1） hn +1 = h2 hn + h3 hn ?1 + L + hn h2 ； （2） ( n ? 3) hn =n ( h3hn?1 + h4 hn? 2 + L + hn ?1h3 ) 。 241 Ak-1Ak证明： （1）如图， ?A1 Ak An +1 把凸 n + 1 边形分成一个凸 k 边 形和一个凸 ( n + 1) ? ( k ? 1) = n + 2 ? k 边形，这时不同分法共有A2 Ak+1A1hk hn + 2 ? k ，对 k = 2, L , n 求和，得 3,An An+1hn +1 = h2 hn + h3 hn ?1 + L + hn h2 。（2）对角线 A1 Ak 把把凸 n 边形分成一个凸 k 边形和一个凸A3 Ak- 1 Akn ? ( k ? 2 ) = n + 2 ? k 边形，这时不同分法共有 hk hn + 2 ? k ，对k = 3, L , n ? 1 求和，得 h3 hn ?1 + h4 hn ? 2 + L + hn ?1h3 。把 A1 依 4,次换成 A2、A3、 、An ，再求和，得 LA2A1 AnAn-1( n ? 3) hn = ( h3hn?1 + h4 hn? 2 + L + hn ?1h3 ) 。14．5 通项公式： hn =n 21 n?2 C2 n ? 4 ( n ≥ 3 ) 。 n ?1证明：由以上两个递推关系，得( n ? 3) hn = ( hn +1 ? 2h2 hn ) =∴n hn +1 ? nhn ， 2 h 2n ? 3 hn nhn +1 = 2 ( 2n ? 3) hn ，即 n +1 = 2? ? ，递推，得 n +1 n +1 nn 2hn +1 ? 2n ? 3 ? ? 2n ? 5 ? ? 1 h2 ? n ?1 ( 2n ? 3 ) !! ， = ? 2? ??? 2? ??L?? 2? ? ? = 2 ? n +1 ? n +1 ? ? n ? ( n + 1)! ? 3 2?故hn +1 = 2n ?1 ?( 2n ? 3)!! = ( 2n ? 2 )! = 1 C n ?1 ， h = 1 C n ?2 。 2 n? 2 n 2 n?4 n! n !? ( n ? 1) ! n n ?114．6 应用：广泛的应用问题的结果是卡特兰数。 定理：给定整点 A ( a, b ) 和 B ( m, n ) ，则 （1）从 A 到整点 B 存在一条由些率为 1 或 ?1 的斜线段构成的折线充要条件是? n ?b ≤ m? a ? ； ? ?2 m + n ? a ? b ?（2） 当整数 a、b、m、n 满足 （1） 的条件时， 由些率为 1 或 ?1 的斜线段构成联结 A、B1 2 的折线的条数是 Cm ? a( m + n ? a ?b )；（3）当整数 a、b、m、n 满足（1）的条件，并且 ??b & 0 时，由些率为 1 或 ?1 的斜线 ?n & 042 段构成联结 A、B 的折线条数等于从 A ' ( a, ?b ) 到 B ( m, n ) 的由些率为 1 或 ?1 的斜线段所 有折线条数； （4）当整数 a、b、m、n 满足（1）的条件，并且 ? 段构成的联结 A、B 的所有折线分成两类： ①与 x 轴有公共点的折线的条数是 C1 2 Cm ? a 1 ( m + n ? a +b ) 2 m?a?b & 0 时，由些率为 1 或 ?1 的斜线 ?n & 0；②与 x 轴没有公共点的折线的条数是( m + n ? a ?b )2 ? Cm ? a1( m + n ? a +b ).y A(m,n)(a,b)Ax O例 1 甲乙两人参加竞选，甲的选票 m 张，乙的选票 n 张，并且 m & n ；问：在 m + n 张 选票逐一唱票的过程中，求甲的得票数一直领先的点票纪录总数. 例 2 戏院票房有 2n 个人排队买票，每张票的价格 5 元，其中有 n 个人各持一张 5 元纸 币，另 n 个人各持一张 10 元纸币，售票处没有零钱找补. 问：使大家都能顺利买票而不至 于发生找补零钱困难的排队方法有多少种？ 例 3 甲乙两人打乒乓球，打成 14 :14 ，问：在比赛过程中，途中恰有一次比分相等外， 甲总领先的比分序列共有多少种？例 4 甲有 m 粒豆子，乙有 m + 2n 粒豆子 m、n ∈ N * ，甲乙两人以丢掷硬币为游戏， 出正面时，乙给甲 1 粒豆子，出反面时，甲给乙 1 粒豆子；如果某人的豆子输光，则游戏结 束；以 A 记恰好在第 m + 2n 次丢掷硬币后，甲把 m 粒豆子输光的掷序列的集合，求()card ( A) .43 练习题? f (1) = 1 ? n 。 （1）给代数式 a1a2 L an 添括号的不同方法数 f ( n ) 满足 ? f (n) = ∑ f (k ) f (n ? k ) ? ? k =1（2）由 n 个 1 和 n 个 0 组成一位 2n 为二进制数，要求从左到右扫描，1 的累计数不小于 0 的累计数，则满足这种条件的数共有 p2 n =1 n C2 n 。 n +1 2 n ?1 C2 n ? 2 。 n（3）从点 ( 0, 0 ) 到 ( n, n ) 除端点外不接触直线 y = x 的路径条数为 qn =（4）有 n 个叶子的完}
我要回帖
更多关于 mongodb 集合大小限制 的文章
更多推荐
- ·荒野大镖客2强制存档作弊后怎么保存进度-作弊后存档方法
- ·无限金币钻石的内购游戏盒子_无限内购破解内购游戏盒子子
- ·lol杀完人后lol四边有红线柱是什么
- ·炉石传说暴风城下的集结任务在哪暗影崛起炸弹战怎么玩_炉石传说暴风城下的集结任务在哪暗影崛起炸弹战玩法攻略一览
- ·请教STM32G070 ADC无法完成ADC有哪些校准方法是怎么回事？
- ·刚毕业出来工作有压力，我去新单位怀孕一个星期能测出来，感觉是那种被动，受到同岗位几年经验的人的压力。
- ·如何定义不定宏定义 带参数函数数
- ·韩国原辰整形外科医院2017年什么时候休假最长？
- ·2017镰刀龙勇士读后感感三百字以上
- ·孩子6岁了嗓子哑发病友有嗓子痒咳嗽一个月了了请问吃啥
- ·有没遇到关门大声的穿女装被舍友肛了，怎么破
- ·粤语 古汉语真是汉语族群中的独立语言么
- ·消防喷淋可以采用内外消防涂塑钢管管么
- ·imds申报的imds标准材料号是指原imds标准材料号还是指整车的可回用imds标准材料号
- ·如果这个世界人人按用圣人的标准要求别人行事，会怎样？
- ·政府部门决算收支总计比上年度收支决算表减少，原因怎么写
- ·种驴市场什么价格肉驴苗养殖养殖的技术要点
- ·听说Java不适合写外挂，那么go语言安装适合吗？？？为什么？
- ·周琦在火箭最新消息与火箭达成一份多年协议什么意思
- ·胆结石13X7mm，无痛，要做胆囊息肉7mm需手术吗吗
- ·下面几个集合的券商大小集合之和是多少
- ·如何成为有效的管理者读书笔记 7
- ·学美国的科蒂思维学科英语好吗英语和一般学校里学的英语有什么差别吗？
- ·济南心理咨询师3级可以自己报名吗？2017济南小学报名时间间是什么时候？
- ·普通话成绩查不出来出来了，有能查到的吗
- ·3.83.9+dpsc3.9090yxs.com.13.9
- ·西川中学哪些泾县中学最好数学老师师教得好
- ·国家定额永久2010轨道工程定额维修时，一个工多少米
- ·得重正重度肌无力力已两年了能吃消炎药吗
- ·KimberliteDiamond饕餮怎么读读
- ·廊庙多贤才，而野人亦不失为君子贤其贤是什么意思
- ·ICP光室使用气体氮气吹扫的气体流量怎么保证氮气吹扫的气体流量干净
- ·我儿子同学的妈妈叫我给孩子报名科蒂集团思维英语，有谁听过这个学校吗？感觉怎么样？
- ·户外用灯用led投光灯什么牌子好好还是泛光灯好
- ·现在父母离婚孩子抚养权养孩子更容易了吗
- ·爱普生针式打印机纸张大小怎么设置纸张大小
