[科普中国]-填充设计

填充设计(packing design)是t设计的一种推广，设X为v元集，B为X的某些k元子集的族，若X的任一t元子集至多包含在B的λ个成员(区组)中，则称(X，B)为t-(v，k，λ)填充设计，t-(v，k，λ)设计也是一个填充设计。对给定的参数t，v，k，λ，使t-(v，k，λ)填充设计存在的最大区组数称为填充数，记为Dλ(v，k，t)。填充设计对编码理论有重要的应用，事实上，填充数D1(v，k，2)就是字长v，极小距离为2(k-1)且码字重量均为k的二元码的最大码字个数，当t=2及k=3，4时，填充数Dλ(v，k，t)的确切值已经得到。

基本介绍定义 给定正整数t，v，k，λ，设X为一个v元集，A为由X的k元子集(称为区组)所组成的子集族，若X的任意一个t元子集都至多包含在λ个区组中，则称(X，A)为一个t-(v，k，λ)填充设计(packing design)。令

Pλ(v，k，t)={max b |存在区组数为b的t-(v，k，λ)填充设计)， (1)

Pλ(v，k，t)叫做填充数(packing number)。若(X，A)是区组数为Pλ(v，k，t)的t-(v，k，λ)填充设计，则叫做最大(或最优)t-(v，k，λ)填充设计，通常将P1(v，k，t)记作P(v，k，t)。1

例题解析【例1】设X=Z10，

A：{0，1，2，3}，{o，4，5，6}，{1，4，7，8}，{2，5，7，9}，{3，6，8，9}，

B：{0，1，2，9}，{0，3，4，8}，{0，5，6，7}，{1，2，3，4}，{1，2，5，6}，

{1，2，7，8}，{3，4，5，6}，{3，4，7，9}，{5，6，8，9}.

则(X,A)是一个2-(10，4，1)填充设计，(X，B)是一个2-{10，4，1}覆盖设计，设A'为A的任一子集，则(X，A')也是2-(10，4，1)填充设计。设B'为在B中添加X的若干4元子集而得，则(X，B')也是2-(10，4，1)覆盖设计。

【例2】若t-(v，k，λ)设计存在，则它既是最大t-(v，k，λ)填充设计，又是最小t-(v，k，λ)覆盖设计1。

设x为实数，用[x]表示不超过x的最大整数，[x]为不小于x的最小整数，令

当λ=1时，将U1(v，k，t)记作U(v，k，t)，将L1(v，k，t)记作L(v，k，t)。

相关定理关于填充数Pλ(v，k，t)的上界和覆盖数Cλ(v，k，t)的下界。我们有如下结果1。

定理1(Schönheim界)

证明 显然有

即当t=1时结论成立，今设t≥2，(X，A)为一个t-(v，k，λ)填充设计。对任意x∈X，A中包含x的全体区组去掉点x后作成上的一个填充设计，因此其区组数。因此有

,从而由式(3)及归纳法即得式(1)，同理可得 由式(4)及归纳法得式(2)，从而即得结论。

当t=2时，H.Hanani进一步证明了以下结论。1

定理2 设。

(i)若，则

(ii)若，则

本词条内容贡献者为:

王海侠 - 副教授 - 南京理工大学