Antichains in the set of subsets of a multiset (Q790113)

From MaRDI portal





scientific article; zbMATH DE number 3847394
Language Label Description Also known as
default for all languages
No label defined
    English
    Antichains in the set of subsets of a multiset
    scientific article; zbMATH DE number 3847394

      Statements

      Antichains in the set of subsets of a multiset (English)
      0 references
      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

      Identifiers