Число неупорядоченных покрытий конечного множества подмножествами фиксированного размера.

?????????? ?????????? ??????????
2010
????????????? ?????? ?????????? ?????????? ??????????
?4(10)
????????????? ??????
?????????? ?????????? ??????????
??? 519.1
????? ??????????????? ????????
????????? ????????? ??????????????
?????????????? ???????
?. ?. ????????????
????????? ??????????????? ???????????, ?. ??????, ??????
E-mail: rodion@utmn.ru
??????????????? ????? ??? ????????????? ?????, ??????????? ?????????? ???????? ????????? ????????? ?????????????? ? ????????? ??????????. ???????????? ??? ??????????? ? ????????. ??????????? ????????? ????? ???? ?????. ?????????? ??????? ?????? ????? ????????????? ????? ??? ????????????
????????? ????????????? ? ????????????? ???? ?????.
???????? ?????: ????????, ???????? ?????????, ????????????? ?????.
1. ???????? ???????
????? ???? ???????? ????????? X ???????? n ? ????????? S ??? ???????? ????????????? ???????????, ?????????? ????????? ???????????? ?????????:
|X| = n,
S ? P0 (X) ,
S
U? = X,
(1)
U? ?S
??? P0 (X) ? ????????? ???? ???????? ??????????? ????????? X [1]. ????????? ????
???????? S, ??????????????? ??????? (1), ????????? C (X):
S
0
C (X) = S ? P (X) :
U? = X ,
(2)
U? ?S
? ????????? ????????, ?????????? ?????? ??????????? ???????????? X, ????????? C 0 (X):
C 0 (X) = {S ? C (X) : X ?
/ S} .
(3)
??? ????????? ????????, ?????????? ????? k ???????????, ??? 1 6 k 6 2n ? 1,
?????????? ??????????? Ck (X):
Ck (X) = {S ? C (X) : |S| = k} .
(4)
? ???????? ??????? ????????? ????????? X ????? ????? ????????? ????? ?????
?? 1 ?? n:
Xn = {1, 2, . . . , n} .
(5)
6
?. ?. ????????????
???????? ??????? [1, 2], ???????? ????????? C (X), ?????? ?????????? ???? ???????? ????????? ?????????, ????? ????????? ?? ??????? (??? ??????? ?????????
?? ??????????? ???????? ????????? ???????? ????? 1):
|C (X)| =
n
1P
n?i
(?1)i Cni 22 ,
2 i=0
(6)
???????? ????????? C 0 (X) ? ?? ???????
n
n
22
1P
n?i
(?1)i Cni 22 ?
,
|C (X)| =
2 i=0
4
0
(7)
? ???????? ????????? Ck (X) ? ?? ???????
|Ck (X)| =
n
P
(?1)i Cni C2kn?i ?1 ,
(8)
i=0
??? Cni ? ???????????? ???????????:
Cni =
n!
= Cnn?i .
i!(n ? i)!
(9)
??????????? ???????? ???????????, ???????????? ????????? S (1), ? ?????? ???????????
S (k1 , k2 , . . . , kn )
(10)
??? ????????, ??????????? ki ??????????? ???????? i (??? ???? i). ???????? ??????
???????? ?????
n
P
|S (k1 , k2 , . . . , kn )| =
ki .
i=1
?????????? ???????????? (2)?(4) ?????? ??????????? ??? ????????? ???????? (10):
C (k1 , k2 , . . . , kn ) (X) = {S (k1 , k2 , . . . , kn )} .
(11)
???????? ?????????? ????????? ????????? ????????? ???????:
|C (k1 , k2 , . . . , kn ) (X)| = n N (k1 , k2 , . . . , kn ) .
(12)
? ??????, ????? ?? ????? ???? ?????? ????????? ki , ????? ???????????? ?????? ????????????:
k1 k2 иииkm
(13)
n N l1 l2 иии lm ,
??? ki ? ??? ?????????? ??????????? ???????? li ? ????????. ????????:
? 4 N23 = 4 N (0, 3, 0, 0) ? ?????????? ???????? ????????? ???????? 4, ????????? ??
???? ??????????? ???????? 2;
? 5 N2331 = 5 N (0, 3, 1, 0, 0) ? ?????????? ???????? ????????? ???????? 5, ?????????
?? ???? ??????????? ???????? 2 ? ?????? ???????????? ???????? 3.
???????? ??????????? ?????? ? ??? ????????? ???????? (11):
k1 k2 иииkm
n C l1 l2 иии lm
(X) .
(14)
????? ??????????????? ???????? ????????? ?????????
7
??? ??????????? ????????????? ? (12) ?????????? ????????? ???????????:
0 6 ki 6 Cni ,
? ??? ????????????? ? (13), (14) ? ?????????:
1 6 m 6 n,
1 6 l1 < l2 < и и и < lm 6 n,
1 6 ki 6 Cnli .
?????????? ????????? X ???????? 3 ? ???? ?????? ????? X3 = {1, 2, 3}, ? ?????
??? ????????? ???????? X3 , ????????? ?????? ?? ??????????? ???????? 2:
{1, 2} ? {2, 3} = X3 ,
{1, 3} ? {2, 3} = X3 ,
{1, 2} ? {1, 3} = X3 ,
{1, 2} ? {2, 3} ? {1, 3} = X3 .
????? ???????, ????????????? ????? ???? 3 N2k = 3 N (0, k, 0) ?????
3 N (0, 1, 0)
= 0;
3 N (0, 2, 0)
= 3;
3 N (0, 3, 0)
= 1.
?????????? ?????? ??? ???????? X3 , ????????? ?? ??????????? ???????? 2 ? 3:
{1, 2} ? {1, 2, 3} = X3 ,
{1, 3} ? {1, 2, 3} = X3 ,
{2, 3} ? {1, 2, 3} = X3 ,
{1, 2} ? {2, 3} ? {1, 2, 3} = X3 ,
{1, 3} ? {2, 3} ? {1, 2, 3} = X3 ,
{1, 2} ? {1, 3} ? {1, 2, 3} = X3 ,
{1, 2} ? {2, 3} ? {1, 3} ? {1, 2, 3} = X3 .
?????????????, ????????????? ????? ???? 3 N2k3l = 3 N (0, k, l), ??? k 6= 0 ? l 6= 0, ?????
3 N (0, 1, 1)
= 3;
3 N (0, 2, 1)
= 3;
3 N (0, 3, 1)
= 1.
? ??????? ???????? ???? ????????? ???????? ????? ???????? ? ????????? ???????????? ???? 3 N (m, k, l):
3 N (1, 0, 0)
= 0,
3 N (2, 1, 0) = 6,
3 N (3, 2, 0) = 3,
3 N (1, 0, 1) = 3,
3 N (2, 1, 1) = 9,
3 N (3, 2, 1) = 3,
3 N (2, 0, 0)
= 0,
3 N (3, 1, 0) = 3,
3 N (1, 3, 0) = 3,
3 N (2, 0, 1) = 3,
3 N (3, 1, 1) = 3,
3 N (1, 3, 1) = 3,
3 N (3, 0, 0)
= 1,
3 N (1, 2, 0) = 9,
3 N (2, 3, 0) = 3,
3 N (3, 0, 1) = 1,
3 N (1, 2, 1) = 9,
3 N (2, 3, 1) = 3,
3 N (1, 1, 0)
= 3,
3 N (2, 2, 0) = 9,
3 N (3, 3, 0) = 1,
3 N (1, 1, 1) = 9,
3 N (2, 2, 1) = 9,
3 N (3, 3, 1) = 1.
8
?. ?. ????????????
2. ??????????? ? ?????????
??? ??????????? ? ????????? ??? ????????????? ????? (12), (13) ??????? ?????
???????? ??? ???????? ???? ?????, ????? ??? ???????????? ???????? ????? ?????????? ???????? (?? ???? ??? ????????????? ????? n Nkl ). ? ???? ?????? ?????????
?????????? ? ???????? ????????.
?????? ??????????? ????????????? ????? n Nlk ?? ???????????? ????????????? Cji ? ????????????? ????? ?????????? ???????? ???? n?i Nlk . ????????? X ???????? n ????? Cnl ??????????? ???????? l. ?? ???? ??????????? ????? ??????? CCk l
n
????????? k ???????????. ?? ??? ??? ?????? ??????????? ????? ???????? ?????????
????????? X. ????????? ?? ??? ???????? ?????????? ??????????? ??????????? ????????? ????????? X. ?????????????, ????? ???????? ????????? X k ?????????????? ???????? l ????? ????? CCk l ????? ????? ???? ???????? ??????????? ???????????
n
??? ?? ??????????? ??????????? ? ?????? ?? ??????????:
k
P |U? | Ckl (U? ) .
n Cl (X) = C k l ?
(15)
Cn
U? ?X
? ????????? ???????? n ?????????? Cni ??????????? ???????? (n?i). ??????????
???????? ????????? ???????? n ? i ? ??? ????????????? ????? n?i Nlk . ????????????
???????? ???????????? ??????????? ??? ????? ???????? ?????????:
k
n Nl
= CCk nl ? n?1 Nlk Cn1 ? n?2 Nlk Cn2 ? n?3 Nlk Cn3 ? и и и
(16)
l
?????????? ? (16) ??????? ???? n?i Nlk > 0, ?? ???? ???? Cn?i
> k. ????? ???????,
??????? (16) ????? ???????? ? ?????????? ????
k
n Nl
=
CCk nl
l
Cn?i
>k
?
k i
n?i Nl Cn .
P
(17)
i>1
??????? ? ??????????? (17) ??? ????????? ? ?????????????? ??????? Nlk ? ?????
???????, ? ???????????? ??????????? CCk l ? ? ??????:
n
CCk nl
=
k
n Nl
l
>k
Cn?i
l
Cn?i
>k
+
P
k i
n?i Nl Cn
i>1
=
P
k i
n?i Nl Cn .
(18)
i>0
????????? (18) ???????????? ????? ???????????? ?????????????? [3]. ????????? ???????? ???????????? ??????????????, ???????
P
P
k
(?1)i Cni CCk l = CCk l + (?1)i Cni CCk l .
(19)
n Nl =
i>0
n
n?i
i>1
n?i
??????? ??????????? (19) ????????? ??? ?????? ??????. ?? ????????? X ???????? n ????? ??????? Cnli ????????? ???????????? ???????? li . ?? ????? ?????
??????????? ??????? ki ??????????? ????? C kili ?????????. ??? ??? ??? ??????????
Cn
???????? li ?? ????? ????? ?????, ?? ??????? ?????????, ?????????? k1 ???????????
???????? l1 , k2 ??????????? ???????? l2 ? ?. ?., ????? ????????? ?????? ????????:
m
Q
i=1
C kili .
Cn
????? ??????????????? ???????? ????????? ?????????
9
????? ???????, ? ????? ?????? ????????? (15) ????? ????? ????????? ???:
k k иииkm
k=m
Q ki
P n C 1 2
=
|U? | Ck1 k2 иииkm (U? ) .
(X)
C
?
l
l1 l2 иииlm
l1 l2 иииlm
i
i=1
Cn
U? ?X
? ????????? ???????? n ?????????? Cni ??????????? ???????? n ? i. ??????????
???????? ????????? ???????? n ? i ?????????????? ? ?????????????? ????????иииkm
. ???????? ???????????? ??????????? ???
?? ???? ????????????? ????? n?i Nlk11lk22иииl
m
????? ???????? ?????????:
k1 k2 иииkm
n Nl1 l2 иииlm
=
m
Q
i=1
C kili ?
Cn
P
i>1
иииkm
,
Cni n?i Nlk11lk22иииl
m
(20)
??? ???????? ????? i ????????? ?????? ?????????????
lj
?j ? {1, 2, . . . , m} Cn?i > kj .
??????????? ? ?????? ????? (20) ?? ????????????? ????? N ? ??????? ?????????иииkm
, ??????????
???? ??????????????, ??????? ?????????????? ????????? ??? n Nlk11lk22иииl
m
?????? ???????????? ????????????:
k1 k2 иииkm
n Nl1 l2 иииlm
=
m
Q
i=1
C kili +
Cn
P
(?1)i Cni
i>1
m
Q
j=1
C
kj
l
j
Cn?i
.
(21)
?????? ??????????? ????????????? ????? n Nlk ?? ????????????? ????? ?????????? ???????? ???? n?i Nlk?1 , ??? 0 6 i 6 l. ?????????? ???????????? ???????? ????????? ???????? n ? i, ????????? ?? k ? 1 ??????????? ???????? l. ?????? ???????
? ???? ??? ???? ????????? ???????? l ????? ???????, ????? ???????????? ????????? ????? ????????? ??? ????????? ???????? n. ??? ????? ??????????? ?????????
?????? ????????? i ?????????, ?? ???????? ? ??????????? ????????? ???????? n ? i,
?, ?????????????, l ? i ?????????, ???????? ? ????.
?????????? ??????, ????? i = 0. ? ????????? ???????? n ?????????? Cnl ??????????? ???????? l. ?? ??? k ? 1 ??? ?????? ? ????????. ??????, ? ??? ???????? ?????
???????? ???? ?? Cnl ? k + 1 ?????????? ???????????. ??? ??? ? ????????? ???????? n ?????????? n Nlk?1 ????????, ????????? ?? k ? 1 ??????????? ???????? l, ??
?????????? ??? ?????? ???????????? ????
Cnl ? k + 1 n Nlk?1
(22)
???????? ????? ????????? k ?????????????? ???????? l.
? ??????, ????? i > 0, ?????????? n?i Nlk?1 ???????? ????????? ???????? n ? i
?????????????? ???????? l ? ?????????? k ? 1. ? ????????? ???????? n ??????????
Cnn?i ??????????? ???????? n?i. ???????? ??????? l?i ????????? ?? ????????? ???l?i
????? n ? i ????? Cn?i
. ????? ???????, ?????????? ????????? ????????? ?????????
?? ???????? ????????? ???????? n ? i ???????? ????????? ???????? n ?????
l?i i
l?i n?i
Cn n?i Nlk?1 .
Cn?i
Cn n?i Nlk?1 = Cn?i
(23)
??? ??? ???????? ? ???????? ????? ????? ?? k ??????????? ???????? l, ??,
????????????? (22) ? (23) ??? ???? i, ???????????? ????????
l
P
1
k?1
l?i i
k?1
k
l
.
(24)
Cn ? k + 1 n Nl +
Cn?i Cn n?i Nl
n Nl =
k
i=1
10
?. ?. ????????????
?????? ???? ?????????, ???????? ?????? ??? ????????? (24):
k
n Nl
=
l
1P
k ? 1 k?1
l?i i
Cn?i
Cn n?i Nlk?1 ?
.
n Nl
k i=0
k
(25)
? ??????? ??????????? ??????????? ????? ??????? ??????????? ??? ??????
??????
#
"
lj
P
1
k иии(kj ?1)иииkm
lj ?i i
k иии(kj ?1)иииkm
k1 иииkj иииkm
, (26)
+
Cn?i
Cn n?i Nl11иииlj иииl
Cnlj ? kj + 1 n Nl11иииlj иииl
n Nl1 иииlj иииlm =
m
m
kj
i=1
??? 1 6 j 6 m.
??????? ????????? (24) ? ??????? ???? ?????????????? ????????? (19). ????????? ?????????
C l ? k + 1 k?1
CCk nl = n
CC l
n
k
? (19), ???????
k?1
1 P
k
l
i i
.
(?1) Cn Cn?i ? k + 1 CC l
n Nl =
n?i
k i>0
?????? ????????? ?????? CCk?1
?????? ????? ??????????? (18):
l
n?i
#
P
P
1
k?1 j
k
l
Cn?i .
(?1)i Cni Cn?i
?k+1
n Nl =
n?j?i Nl
k i>0
j>0
"
?????????? ?????? i + j ? i ? i ? j ? ???????? ??????? ????????????:
#
"
i
P
P
1
i?j j
k?1
k
l
(?1)j Cn?j
Cn Cn?j
?k+1 .
n Nl =
n?i Nl
k i>0
j=0
???????? ????????? ??? ?????? ????? ?? ??? ?????????:
i
P
i?j j l
(?1)j Cn?j
Cn Cn?j ? (k ? 1)
j=0
i
P
i?j j
(?1)j Cn?j
Cn .
(27)
j=0
??? i = 0 ?????? ????? ????? 1. ??? ?????????? ???? ????????????? ???????????
??? ???????????? ????????????? [3]:
Csr =
t
Csr Cs?r
=
Cr =
P r t?rs
Cs Cp
=
Css?r ,
r
Cr+t
Csr+t ,
r
(?1)r Cr?s?1
,
t
Cs+p .
(28)
r
??????????? ?????? ????? ? (27):
i
P
i?j j l
(?1)j Cn?j
Cn Cn?j = Cni
j=0
i
P
n?l?j
(?1)j Cij Cn?j
= Cni
j=0
=
n?l
Cni (?1)n?l Ci?l?1
i
P
n?l?j
(?1)j Cij (?1)n?l?j C?l?1
=
j=0
=
n?l
Cni Cn?i
l?i
= Cni Cn?i
.
(29)
11
????? ??????????????? ???????? ????????? ?????????
?????? ????? ???????? ??? i > 0:
i
P
i?j j
(?1)j Cn?j
Cn =
j=0
i
P
i
P
n?i j
(?1)j Cn?j
Cn = (?1)i
j=0
i?j
i
Ci?n?1
Cnj = (?1)i Ci?1
= 0.
(30)
j=0
???????????????? (29) ? (30), ? ????? ???????? ???????? ?????? ????? ??? i = 0,
???????? ????????? (24).
???????????? ??????????? (24) ??? k = 1 ? n = l ????
1
l Nl
= 0 Nl0 .
????? ???????, ????????
0
0 Nl
= 1,
??? ????? ???????????????? ????????? ???????: ????? ???????? ??????? ?????????
?????????? ???????????, ?? ?????????? ?? ?????? ????????????, ????? 1.
3. ?????
???????? ????? ???? ????????????? ????? n N (k1 k2 и и и kn ) ??? ????????????? n.
??? ??? ????????????? ?????????? (21)
P
n
n
PP
Q
k
(?1)i Cni
CC jj ,
n N (k1 , k2 , . . . , kn ) =
k>0 i
k>0
j=1
n?i
??? k > 0 ? ????? ??????? ??? ???? ????? ?? ?????? (k1 , k2 , . . . , kn ). ???????? ???????
????????????,
??????? ???? ????????? ?? ???????????? ? ????????????? ??????????
P i
n
Cn = 2 :
i
P
n N (k1 , k2 , . . . , kn ) =
n
P
(?1)i Cni
i
k>0
P
ks >0
s
CCkn?i
s
k
PQ
k>0 j6=s
CC jj
=
n?i
n
P Q kj
P
s
CC j .
(?1)i Cni 2Cn?i
i
k>0 j6=s
n?i
??????????, ?????? ?? ?????? ?????????, ???????
P
n N (k1 , k2 , . . . , kn )
=
n
P
P
(?1)
i
Cni 2
j
j
Cn?i
=
i
k>0
n
P
(?1)i Cni 22
n?i ?1
,
i
??? ????? ????? ???? ???????? ????????? ???????? n (6).
??????? ???????? ????????? ????:
P i
иииkm
Cn n?i Nlk11lk22иииl
;
m
(31)
i>0
P
иииkm
(?1)n n Nlk11lk22иииl
;
m
(32)
n>1
X (?1)n
n>1
n
k1 k2 иииkm
n Nl1 l2 иииlm ;
(33)
X (?1)n
k1 k2 иииkm
n Nl1 l2 иииlm .
n(n
?
1)
n>1
(34)
иииkm
? ????????? (20) ????????? ???? ????????????? ????? n Nlk11lk22иииl
?? ?????? ?????
m
???????? ????? (31):
m
P i
Q
иииkm
Cn n?i Nlk11lk22иииl
=
C kili .
m
i>0
i=1
Cn
12
?. ?. ????????????
??? ?????????? ?????? ???? ????????????? ????????????? (25) ? (26). ?????????
? (32) ?????? n Nlk ?????? ????? ?? (25) ? ??????????? ?????????:
l
P
P
1 P l?i i
k ? 1 k?1
k?1
n
k
n
C C n?i Nl ?
=
(?1) n Nl =
(?1)
n Nl
k i=0 n?i n
k
n>1
n>1
l
P
k?1 P
1P
l?i i
=
Cn n?i Nlk?1 ?
(35)
(?1)n Cn?i
(?1)n n Nlk?1 .
k n>1
k
n>1
i=0
? ?????? ????? ? (3) ?????????? ?????? n ? i ? n:
P
(?1)n
n>1
l
P
i=0
l?i i
Cn?i
Cn n?i Nlk?1 =
l
P
P
i
(?1)n n Nlk?1 (?1)i Cn+i
Cnl?i .
n
i=0
????????????? ??????????? (28):
l
P
i
Cnl?i =
(?1)i Cn+i
l
P
l
i
= (?1)l Cll = (?1)l .
Cnl?i = C?1
C?n?1
i=0
i=0
????????? ???????? ?????? ????? ? (3), ??????? ???????????? ???????????
P
(?1)n n Nlk =
n>1
(?1)l ? k + 1 P
(?1)n n Nlk?1 .
k
n>1
(36)
??? k = 1 ???????? ????? (32) ?????
P
(?1)n n Nl1 = (?1)l l Nl1 = (?1)l .
n>1
??????????? ? ????????? (36) ??? ?????? ? ???????? ????????? l ??????????????
?????
(
?1, ???? l ????????,
(?1)l ? k + 1
=
2?k
k
, ???? l ??????.
k
??? k = 2 ??????????? ??? ?????? l ????? 0. ???????????? ????????
?
? (?1)k , ???? l ????????,
P
n
k
1, ???? l ?????? ? k = 1,
(?1) n Nl =
?
n>1
0, ???? l ?????? ? k > 1.
? ????? ?????? ????? (32) ?????
P
?
ki
(?1)
,
?
P
?
?
ki
P
(?1)
,
иииkm
(?1)n n Nlk11lk22иииl
=
m
?
n>1
?
?
0,
???? ??? li ????????,
???? ki = 1 ??? ???? ?????? li ; ????? ????
?????? ?? i, ??? ??????? li ???????,
???? ki > 1 ???? ?? ??? ?????? ??????? li .
????????? n Nlk ?? (25) ? (33) ? ??????????? ???????????? ?????????:
!
l
X (?1)n
X (?1)n 1 X
k
?
1
l?i i
k?1
k
Cn?i
Cn n?i Nlk?1 ?
=
n Nl =
n Nl
n
n
k
k
n>1
n>1
i=0
l
1 X (?1)n X l?i i
k ? 1 X (?1)n
k?1
=
Cn?i Cn n?i Nlk?1 ?
.
n Nl
k n>1 n i=0
k n>1 n
13
????? ??????????????? ???????? ????????? ?????????
????????????? ??????????
1 i
1
Cn =
Ci
n
n ? i n?1
? ?????????? ?????? n ? i ? n ? ?????? ?????:
l
l
X
1 X (?1)n X l?i i
1 X (?1)n
k?1
i
.
N
Cn?i Cn n?i Nlk?1 =
(?1)i Cnl?i Cn+i?1
n l
k n>1 n i=0
k n
n
i=0
??? ?????????? ????? ???????????? ???????????? ????????????? ?????????????
??????????? (28):
l
P
i
(?1)i Cnl?i Cn+i?1
=
i=0
l
P
i
Cnl?i C?n
= C0l = 0.
i=0
????? ???????, ????????
X (?1)n
n>1
n
k
n Nl
=?
k ? 1 X (?1)n
(?1)k?1 X (?1)n
k?1
1
=
n Nl
n Nl .
k n>1 n
k
n
n>1
(37)
??? k = 1 ???????? ????? (33) ?????
X (?1)n
n>1
n
1
n Nl =
(?1)l 1 (?1)l
.
l Nl =
l
l
???????????? ???????? ???????? ????? ????????????? ?????????????:
X (?1)n
n>1
n
k
n Nl
=
(?1)k+l?1
.
kl
? ????? ?????? ??? m > 1 ????? (33) ?????
X (?1)n
n>1
n
k1 иииki иииkm
n Nl1 иииli иииlm
=
(?1)ki +li ?1 X (?1)n
k1 иии1иииkm
n Nl1 иииli иииlm = 0,
ki li
n
n>1
??? ???, ???????? (37),
X (?1)n
n>1
n
k1 иии1иииkm
n Nl1 иииli иииlm = ?
X (?1)n
n>1
n
k1 иии0иииkm
n Nl1 иииli иииlm
= 0.
(38)
? ??????? ???????? ?? ???????? ???????? ????? (34):
l
X (?1)n
1 X (?1)n X l?i i
k ? 1 X (?1)n
k?1
k
;
Cn?i Cn n?i Nlk?1 ?
n Nl =
n Nl
n(n
?
1)
k
n(n
?
1)
k
n(n
?
1)
n>1
n>1
n>1
i=0
1
1
Cni =
Ci ;
n(n ? 1)
(n ? i)(n ? i ? 1) n?2
l
l
X (?1)n X
X (?1)n
X
l?i i
k?1
k?1
i
Cn?i Cn n?i Nl
=
(?1)i Cnl?i Cn+i?2
;
n Nl
n(n
?
1)
n(n
?
1)
n>1
n
i=0
i=0
14
?. ?. ????????????
l
P
i
=
(?1)i Cnl?i Cn+i?2
l
P
i
= C1l =
Cnl?i C?n+1
i=0
i=0
1, ???? l = 1,
0, ???? l > 1.
??? k = 1 ? l > 1
X (?1)n
(?1)l
(?1)l
1
1
.
n Nl =
l Nl =
n(n ? 1)
l(l ? 1)
l(l ? 1)
n>1
??? l = 1
X (?1)n
k ? 2 X (?1)n
(?1)k
k
k?1
=
.
n N1 = ?
n N1
n(n ? 1)
k n>1 n(n ? 1)
k(k ? 1)
n>1
????????????:
?
?
?
?
(?1)k
, ???? l = 1,
X (?1)n
k(k ? 1)
k
N
=
n l
(?1)k+l?1
?
n(n ? 1)
?
n>1
?
, ???? l > 1.
kl(l ? 1)
????????? ????????, ??????????? (38), ???????, ??? ??? m > 1 ????? (34) ????? 0:
X (?1)n
k1 k2 иииkm
n Nl1 l2 иииlm = 0.
n(n
?
1)
n>1
4. ??????? ??????
?????????? ??????? ?????? ????????????? ????? (13), ????? ?? ????????????
?????? ??? ??????? ????????????? ?????????????.
l
? ????????? (19) ???????? ?????? ???? ?????????:
??? k > Cn?1
l
k > Cn?1
? n Nlk = CCk nl .
?? ???? k ??????????? ???????? l ?? ????? ???????? ????????? ?? ?????? ???????????? ???????????? ????????? ????????? (??? ??????? ????????? ???? k ???????????
lj
? ??????????? ????????????). ?????????? ? ????????? (21): ???? kj > Cn?1
???? ??
??? ?????? ?? ????????????? kj , ??
k1 иииkj иииkm
n Nl1 иииlj иииlm
=
m
Q
i=1
C kili .
Cn
?? ????? ????????? ???????, ??? ???? ? ????????????? ????? n N (k1 , k2 , . . . , kn ) ????????? ??????????? ????? 1, ??
n N (k1 , k2 , . . . , kn?1 , 1)
=
n?1
Q
i=1
CCkii .
n
????????????? ??? ????????????? ????? ???? n N (k1 , k2 , . . . , kn?1 , 1), ???????
P
2n ?2
,
n N (k1 , k2 , . . . , kn?1 , 1) = 2
k>0
??? ????? ?????????? ???? ???????? ????????? ???????? n, ?????????? ? ???? ???????? ?????????. ????? ??? ????? ?? ?????? ????? ???????? ????????? ???????? n,
??????? ????????? (7).
15
????? ??????????????? ???????? ????????? ?????????
????????? ????????? (8) ? ????? ????????????? ????? ? ?????????? ??????????? ??????????? ? ????????, ????? ??????? ???????????
P
P
ki =k
k1 k2 иииkm
n Nl1 l2 иииlm
=
n
1P
(?1)i Cni C2kn?i ?1 .
2 i=0
??? ???????? ???? ????????????? ????? ??? k = Cnl ?? (19) ????????
k = Cnl ? n Nlk = 1.
P
???? n = ki li , ?? ?????? ??????? ????????? X ??????????? ?????? ?????? ??
??????????? ????????. ????? ???????, ??? ???????? ???????????? ????? ??????????????? ????????? ????????? X ?? ???????????? ?????????????? ??????? [3 ? 5]:
n=
m
P
2 иииkm
=
ki li ? n Nlk11l2kиииl
m
i
(l1 !)k1 (l2 !)k2
n!
.
и и и (lm !)km k1 !k2 ! и и и km !
(39)
??? m = 1 ???????
(kl)!
.
(l!)k k!
?????????? ???? ??????????????? ????????? n-??????????? ????????? ???????? ?????? ?????
P Bn [3]. ????? ???????, ????? ???? ????? ????????????? ?????, ??? ??????? n =
ki li , ????? Bn . ?????????? ????? ???????? ??????????? ????? ??????????
?????????????? ???????:
P
k1 k2 иииkm
Bn = P
n Nl1 l2 иииlm ,
k
kl Nl
=
ki li =n
Bn = n!P
k1
(l1 !) (l2 !)k2 и и и (lm !)km k1 !k2 ! и и и km !
P
?1
.
ki li =n
P
???? n = ki li ?1, ?? ???? ? ?????? ???? ??????? ????????? X ??????????? ????
????????????? ????????. ???????? ???? ?? ??? ?? ????????. ????? ???????? ?????
???????? li . ????? ?????????? ????????? ??????????? ????? ???????? ????????? ???
???????????? ???????? n ? li + 1, ?????? ??????? ???????? ????? ????????????
?????? ?????? ???????????? ????????. ????? ????? ??????????? ? ????????? X
?????
Cnn?li +1 = Cnli ?1 .
????? ?? n ? li + 1 ????????? ???????????? ????? ???? ? ??????????? ????????????. ????? ???????, ?????????? ????????? ?????????? ?? ???????? ????????????
???????? n ? li + 1 ???????? ????????? X ?????
иииki ?1иииkm
(n ? li + 1)Cnli ?1 n?li +1 Nlk11иииl
.
i иииlm
????? ?????????? ????????? ?????????? ???????? ????????? X ?? ???????? ??????????? ?????
m
P
иииki ?1иииkm
(n ? li + 1)Cnli ?1 n?li +1 Nlk11иииl
.
i иииlm
i=1
??? ??? ???? ??????? ??????????? ???? ????????????? ? ????????, ?? ?????? ???????? ????????? ??? ????. ????? ???????, ???????????? ????????
k1 иииkm
n Nl1 иииlm =
m
1P
иииki ?1иииkm
(n ? li + 1)Cnli ?1 n?li +1 Nlk11иииl
.
i иииlm
2 i=1
(40)
16
?. ?. ????????????
P
???????? ????????? (40), ????????, ??? n =
kj lj ? 1, ?
P
kj lj + (ki ? 1)li .
n ? li + 1 =
j6=i
?? ???? ??? ????????????? ?????, ??????? ??? ?????? ????? ? (40), ????? ?????????
????????? (39):
k1 иииkm
n Nl1 иииlm
=
m
X
i=1
m
X
(n ? li + 1)n!
(n ? li + 1)!
=
k
k
?1
1
i
2(li ? 1)!(n ? li + 1)! (l1 !) и и и (li !)
и и и (lm !)km k1 ! и и и (ki ? 1)! и и и km !
(n + 1)!
(n ? li + 1)ki li
=
k1 и и и (l !)ki и и и (l !)k k ! и и и k ! и и и k !
2(n
+
1)
(l
!)
1
i
m
1
i
m
m
i=1
m
m
P
P
1
k1 иииkm
2
(n + 1) ki li ?
ki (li ) =
=
n+1 Nl1 иииlm
2(n + 1)
i=1
i=1
m
P
1
k1 иииkm
2
= n+1 Nl1 иииlm
(n + 1) ?
ki (li )2 .
2(n + 1)
i=1
=
??? m = 1 ???????
k
kl?1 Nl
=
l(k ? 1)
l(k ? 1) (kl)!
k
.
kl Nl =
2
2
(l!)k k!
?????? ????? ?????????? ????????, ? ??????? ??? ???????????? ????? ????????,
?? ???? ?????
P
k
n Nl .
k
????????? ????????? ??? ??????? ????????????? ????? (19) ? ???????????:
l
P
PP k
P i
P k
P i
Cn?i
k
i
i
i
i
N
=
C
C
(?1)
=
C
(?1)
C
=
C
(?1)
2
?
1
.
n l
n
n
n
Cl
Cl
k
k
i
n?i
i
????????? ?????? ? ????????, ???
P
k
n?i
i
Cni (?1)i = 0, ???????????? ????????
i
P
k
k
n Nl
=
n
P
l
Cni (?1)i 2Cn?i .
i=0
??? k = 2 ???????? ????????????? ?????????????????? A006129 ? OEIS [6].
5. ?????????????
????? ????????????? ?????, ??????????? ?????????? ??????????????? ???????? ????????? ????????? ?????????????? ? ?????????????? ??????????, ?????
????????? ? ????????? ????????:
1) ???????? ?????????, ???????? ????????. ? ??????? ????? ?????????????
????? (12) ? (13) ????? ????????? ?????????? ???????? ???????? ????????
? ?????????? ?????????????: ???????????? ????????? ??????????? ????????, ?????????????? ??????????? ??? ?????????? ??????????? ? ????????,
????? ??????? ?? ???????? ? ?????????? ???????????. ?????? ??????? ???????? ???????????? ????????? ???????? ????????, ????????????? ????? ?????????? ?? ?????? ????? ????????, ?? ??????????????? ???????? ???????? [5],
????? ????????? ???????? ? ??????? ???????????? ????? ?????????????
?????, ??????????? ????????? ????.
????? ??????????????? ???????? ????????? ?????????
17
2) ????????????? ????????? ?? ???????. ???????? ????????? ????????? ???????? ?????? ??????????? ? ????????????? ?????????? ????? ???????????????? ??? ????????????? ????????? ????????? ?? ??????? ? ?????????, ???
??????? ????? ???????????? ?????????? ???????, ??? ???? ?? ?????? ???????????? ???? ?? ?????? ??????, ? ????? ??? ?????????? ???? ????? ???????.
????? ????????????? ????? ????? ????????? ??? ?????????? ?????????? ????????????? ?? ??????? ? ????????? ???????????????? (?????????? ? ????????
???????) [7, 8].
3) ????????? ?????? ? ?????. ? ???????? ?????????? ?????????????, ? ???????
???????? ????? ?????????? ????????? ????? ?????????????? ??? ????????
?????????, ??????? ???????????? ????????? ?????? ? ?????. ??? ?????????? ????????? ????????????? ????????? ?? ?????????? ????? ??????? ?????
????????????? ????? [9].
4) ?????????? ????? [10]. ???????? ????????? ????????? ?????????? ????????????? ??????????? ????? ???????????????? ??? ??????? ?????? ???????????
????? G(X ? S, E), ? ??????? ?????? ??????? (???????) ?? X ?????? ??????
???? ?? ? ????? ????????? (????????) ?? S ? ???????: ??? ?????? ??????? S
???? ???? ?? ???? ?????, ??????????? ??????? ?? X ? ?????? ????????. ????? ????, ????? ???? ?????? ?? X ? S ????????? ?????? ???? ?????. ??? ????
???? ???????, ??? ??? ????? ???? ?????? ?? S ?????? ?????? ?? X ?? ??????
?????????. ??? ???????? ????? ?????????? ?????? ? ??????????????? ??????????? ????? ????? ???????????? ????????????? ????? (12) ? (13).
??????????
1. Comtet L. Advanced Combinatorics. The Art of Finite and Infinate Expansions. Dordrecht,
Holland: D. Reidel Publishing Company, 1974.
2. Macula A. J. Covers of a finite set // Mathematics Magazine. 1994. V. 67. No. 2. P. 141?144.
3. ???? ?., ?????? ?., ???????? ?. ?????????? ??????????. ????????? ???????????.
?.: ???, 2006.
4. ?????? ?. ?????? ?????????. ?.: ?????, 1982.
5. Stanley R. P. Enumerative Combinatorics. V. I. Cambridge University Press, 2002.
6. http://oeis.org/classic/A006129 ? On-Line Encyclopedia of Integer Sequences ? ???????????? ????????????? ???????????????????.
7. ???? ?. ?????????????. ?.: ???, 1970.
8. ??????? ?. ???????? ? ????????????? ??????. ?.: ??, 1963.
9. Burger A. P., van Vuuren J. H. Balanced minimum covers of a finite set // Discrete
Mathematics. 2007. V. 307. No. 22. P. 2853?2860.
10. ?????? ?. ????????????? ??????. ?.: ???, 1982.