Antichains in the set of subsets of a multiset (Q790113)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Antichains in the set of subsets of a multiset |
scientific article |
Statements
Antichains in the set of subsets of a multiset (English)
0 references
1984
0 references
Let M be a multiset on \(\{\) 1,2,...,\(n\}\) with i occuring \(k_ i\) times, \(k_ n\leq...\leq k_ 1.\) S is the family of subsets, i.e. sequences \(\underline x=(x_ n,...,x_ 1)\) with \(0\leq x_ i\leq k_ i.\) A c- chain is a sequence \(\underline x_ 0\subset ...\subset \underline x_ c\) from S. A c-antichain is an \(F\subseteq S\) without a c-chain. For \(\underline x=(x_ n,...,x_ 1)\) put \(| \underline x| =x_ n+...+x_ 1.\) The weight of \(F\subseteq S\) is \(wF=\sum \{| \underline x|:\underline x\in F\}.\) In this paper min wF is calculated when F ranges the f-element c-antichains. The formula uses a certain binomial coefficient-like representation of integers. The proof is modeled after \textit{D. E. Daykin's} [Nanta Math. 8, 84-94 (1975; Zbl 0332.05002)] proof of the special case for sets, i.e. \(k_ 1=1\).
0 references
subsets
0 references
multisets
0 references
c-antichain
0 references
Kruskal-Katona theorem
0 references
binomial coefficient
0 references