证明二项式定理：这里是n个元素中取r个的组合数。

证明定理17.18.

定理17.18:设G*是具有h(k≥2)个连通分支的平面图G的对偶图,n*m*,r*和n,m,r分别为G*和G的顶点数,边数,面数,则

(1)n*=r,(2)m*= m;(3)r*=n-k+1;

(4)设G*的顶点v_t*，位于G的面R_t中,则d_G*(v_t*)=dcg(R_t).

问题描述:设是要进行排列的n个元素.其中元素可能相同.试设计一个算法,列出R的所有不同排列.

算法设计:给定n及待排列的n个元素.计算出这n个元素的所有不同排列.

数据输入:由文件input.txt提供输入数据.文件的第1行是元素个数n,1≤n≤500.接下来的1行是待排列的n个元素.

结果输出:将计算出的n1个元素的所有不同排列输出到文件output.txt.文件最后1行中

的数是排列总数.

设X是含有n个元素的集合,从X中均匀地选取元素.设第k次选取时首次出现重复.

(1)试证明当n充分大时,k的期望值为.其中,.

(2)由此设计一个计算给定集合X中元素个数的概率算法.

设齐次方程组

的系数矩阵的秩为r，证明：方程组的任意n-r个线性无关的解都是它的一基础解系。

假定要把长为的n个程序放在磁带T₁和T₂上,并且希望按照使最大检索时间取最小值的方式存放,即如果存放在T₁和T₂上的程序集合分别是A和B,则希中所选择的A和B使得取最小值.

贪心算法:开始将A和B都初始化为空,然后一次考虑一个程序.如果则将当前正在考虑的那个程序分配给A,否则分配给B.证明无论是按还是按的次序来考虑程序的,这种方法都不能产生最优解.应当采用什么策略？写出一个完整的算法并证明其正确性.

设α₁，α₂，···，α_n是n个互不相同的整数，证明：在Q[x]中不可约。

设α是欧氏空间V中的一个非零向量，α₁，α₂，···，α_p是V中p个向量，满足

证明：

1)α₁，α₂，···，α_p线性无关;

2)n维欧氏空间中最多有n+1个向量，使其两两夹角都大于π/2。

利用范式证明下列公式为永真式(证明合取范式的每一个合取项中含有互补文字,或其主析取范式中含有2ⁿ个析取项,n是公式中变元的个数).