总结装错信封问题g.docxVIP

装错信封问题

容斥原理

|A?A ???A

|?|A|??n|A|? ?|A ?A |

1 2 n

i i i

i?1 1?i?i?n 1 2

1 2

???(?1)k

? |A ?A

???A

|???(?1)n|A?A

???A |.

1?i?i

12

i i2 ik

?1???ikn

?

1

1 2 n

|A?A

1 2

? ?A

n

|??n

|A|?

i

? |A?A |

i i

1 2

i?1 1?i?i?n

12

???(?1)k?1

? |A ?A

???A

|???(?1)n?1|A?A

???A |.

1?i?i

12

i i2 ik

?1???ikn

?

1

1 2 n

装错信封问题

“装错信封问题”是由当时最有名的数学家约翰·伯努利（JohannBernoulli，1667—1748）的儿子丹尼尔·伯努利（DanidBernoulli，1700—1782）提出来的，大意如下：一个人写了n封信都装错了信封，问都装错信封的装法有多少种？

其他叙述方式

“拿错帽子问题”

“分发贺卡问题”

“更列问题”

设n封为a,?,a，n个信封为A,?,A，装对的情形为a装入A

(i?1,2,?,n).我

1 n 1 n i i

们把都装错的情形数记为n.

若不考虑是否装对信封，则有An

n

?n!种.

若至少有1封信装对信封，即a

装入A，而其他n?1封信的装法有An-1?(n-1)!.

i i n-1

由于a装入A有C1种，所以，至少有1封信装对信封的装法有C1An-1种.

i i n

n n-1

若至少有2封信装对信封，即a

i

装入A，a

i j

装入A

j

，而其他n?2封信的装法

有An-2

?(n-2)!，所以，至少有2封信装对信封的装法有C2An-2种.

n-2

至少有3封信装对信封的装法有C3An-3种.

n n-2

n n-3

1

一般地，其中至少有k封装对的装法有CkAn?k种.

n n?k

于是，由容斥原理，封信都装错的情形种数为.

n?n!?C1?(n?1)!?C2?(n?2)!? ?(?1)kCk?(n?k)!? ?(?1)n?1

n n n

另证.

设n封为a,?,a，n个信封为A,?,A，装对的情形为a装入A

(i?1,2,?,n).我

1 n 1 n i i

们把都装错的情形数记为n.

首先研究a

1

装入A

2

时，信封装错的种数.分两种情况.

a

1

装入A,a

2 2

装入A

1

.此时，其余n?2封信都装错的种数为n?2.

a

1

装入A,a

2 2

没有装入A

1

.此时，其余n?1封信都装错的种数为n?1.

这样，当a

1

装入A

2

时，信封装错的种数为n?1+n?2.

同样，当a

1

装入A

3

，当a

1

装入A

4

，??，当a

1

装入A

n

时，信封装错的种数也为

n?1+n?2.

从而，信封装错的所有种数为

n?(n?1)(n?1?n?2).

n?n?n?1?n?1?(n?1)?n?2.

于是，有递推公式

n?n?n?1?(?1)[n?1?(n?1)?n?2].

取n?2,3,4,?,n,可得

3?3?2?(?1)(2?2?1)

n?n?n?1?(?1)[n?1?(n?1)?n?2]

相乘得

n?n?n?1?(?1)n?2(2?2?1).

容易求出2?1,1?0.

于是 n?n?n?1?(?1)n.

n

从而 ?

n?1

?(?1)n.

取n?2,3,4,?,n,可得

n! (n?1)! n!

2?1?(?1)2

2! 1! 2!

2

??

n? n?1 ?(?1)n.

n! (n?1)! n!

相加得

n?1?

1?1?

1?1

???

(?1)n.

n! 1! 2! 3! 4! 5! n!

化为

n?n!?[1

?1?

1?1

? ?(?1)n].

2! 3! 4!