Anzahl von Möglichkeiten zur Auswahl von Mengen ganzer Zahlen

Lassen$k$eine nichtnegative ganze Zahl sein. Bestimmen Sie die Anzahl der Auswahlmöglichkeiten$(k+1)^2$setzt$S_{i,j}\subseteq [2k] := \{1,2,\cdots ,2k\}$für ganze Zahlen$i,j$mit$0\leq i, j \leq k$damit für alle$0\leq i\leq c\leq k, 0\leq j\leq d \leq k, S_{i,j}\subseteq S_{c,d}.$

Die Anzahl der Teilmengen von$\{1,2,\cdots, 2k\}$Ist$2^{2k}$. Es gibt also$2^{2k}$Möglichkeiten zur Auswahl der Teilmenge$S_{0,0}$. Angenommen, es hat$a_0$Elemente. Dann der Satz$S_{1,0}$müssen diese enthalten$a_0$Elemente und eine Teilmenge des Komplements von diesen$a$Elemente hinein$\{1,2,\cdots, 2k\}$. Im Allgemeinen, wenn$S_{i,0}$hat$a_i$Elemente dann$S_{i+1, 0}$muss man mindestens haben$a_i$Elemente und die Menge der Elemente in$S_{i+1,0}\backslash S_{i,0}$ist eine Teilmenge von$[2k]\backslash S_{i,0}$. Diese Argumentationskette scheint jedoch nicht sehr nützlich zu sein, da sie weitgehend von der Größe der Sets abhängt$S_{i,j}$Sind. Wäre das Generieren von Funktionen nützlich und wenn ja, wie? Natürlich kann man sich nicht einfach aussuchen$(k+1)^2$Teilmengen aus der Menge aller Teilmengen von$[2k]$und ordnen sie, weil Teilmengen nur eine Teilordnung unter Inklusion bilden; einige sind nicht einmal vergleichbar.