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
    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
    0 references
    0 references
    0 references
    0 references
    subsets
    0 references
    multisets
    0 references
    c-antichain
    0 references
    Kruskal-Katona theorem
    0 references
    binomial coefficient
    0 references