[Combinatorial] 2 排列与组合习题

H1 (2/2 分数)

1. 小于10000的含1的正整数有____个
   3439 - 正确

2. 小于10000的含0的正整数有____个
   2619 - 正确

1）

解法一：小于10000的不包含1的正整数可以视为4位数，但是不包括0000，所以有9∗9∗9∗9−1=6560个;小于10000的正整数有9999个，所以不包含1的正整数有9999－6560=3439个。

解法二：全部4位数有104个，,不含1的四位数有94个,含1的4位数为两个的差: 104−94=3439个

2）

“含0”和“含1”是不可以直接套用的，比如0019含1但不含0。需要注意的是，在组合的习题中有许多类似的隐含的规定，要特别留神。

不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个，不含0小于10000的正整数有：9+92+93+94=7380个。所以含0小于10000的正整数有9999−7380=2619个

H2 (3 满分)
如图所示，从O点出发，到达P点，每次只能移动一个单位，

求满足下列条件的从O到P的最短路径数

1. 路径必须经过A点
   560
   C(5,2)C(8,3)=1056=560

2. 路径必须过道路AB
   350
   C(5,2)C(7,3)=1035=350

3. 路径必须过A和C
   240
   C(5,2)C(4,1)C(4,2)=1046=240

我这题就想复杂了本来是分步要用乘法，我用了加法，啊！！！

H3 (1 满分)
给三个孩子发水果,一共12个一样的苹果,每个孩子至少有一个苹果,问有____种分法。

我这题就想复杂了，我想的是，先给孩子一人一个苹果，再分剩下的九个苹果，采用隔板法。但是这样就会产生一个问题就是隔板法里的隔板都是防在不同位置上的。而这里的隔板存在放在一起的可能。我算的是C(10,2)=45，答案是C(11,2)=55，就差了这10个放在一起的隔板。

正解：
设分给第i个孩子的水果数为xi,xi≥1,x1+x2+x3=12,
令y1=x1−1,y2=x2−1,y3=x3−1,y1+y2+y3=9,yi≥0
非负整数解的个数为C(9+3−1,9)=55。
思考：x1+x2+x3=12,x1≤5,x2≤8,x3≤5的非负整数解的个数。（容斥)