(Oral X Mp/Mpi)
Soit {E} un ensemble fini de cardinal {n}. Une antichaîne de longueur {q} de {E} est un ensemble {\{A_1,\ldots,A_q\}} de parties de {E} tel que, pour tout {i\neq j}, {A_i\not\subset A_j} et {A_j\not\subset A_i}.
| Question a) Donner des exemples d’antichaînes. |
| Question b) Dénombrer le nombre de bijections de {E} sur {\{1,\ldots,n\}} envoyant une partie {A} de {E} de cardinal {m} sur {\{1,\ldots,m\}}. |
| Question c) Montrer que si {\{A_1,\ldots,A_q\}} est une antichaîne de {E} avec {|A_1|=m_1,\ldots,|A_q|=m_q}, alors : {\sum_{i=1}^q\frac1{\binom n{m_i}}\leqslant1.} |
| Question d) Déterminer la longueur maximale d’une antichaîne de {E}. |