kombinatorischer Identitätsnachweis mit Multisets

Ich habe$k$Kisten u$n$Bälle. Für einige$j$mit$0\le j\le\lfloor n/2\rfloor$Ich verteile$j$Bälle zwischen den Kisten, und dann verdopple ich die Anzahl der Bälle in jeder Kiste; Ich kann das in$\binom{j+k-1}{k-1}$Wege. An diesem Punkt habe ich$n-2j$Kugeln links, und ich wähle$n-2j$Kisten und legen Sie eine der restlichen Kugeln in jede dieser Kisten; Ich kann das in$\binom{k}{n-2j}$Wege. Ich behaupte, dass jeder der$\binom{n+k-1}{k-1}$Verteilungen der$n$Bälle unter den$k$Boxen können durch dieses Verfahren auf genau eine Weise erhalten werden.

Nehmen Sie insbesondere eine Verteilung der$n$Bälle zum$k$Boxen. Lassen$A$sei der Satz von Kisten, die eine ungerade Anzahl von Bällen enthalten. Wenn wir aus jeder dieser Boxen eine Kugel entfernen,$n-|A|$Bälle bleiben die$k$Boxen insgesamt, und die verbleibende Anzahl ist beispielsweise gerade$2k$für einige$k$, wo klar$0\le k\le\lfloor n/2\rfloor$. Daher,$|A|=n-2k$, und diese bestimmte Verteilung wird einmal in der Laufzeit gezählt$j=k$. Allgemein der Begriff$\binom{k}{n-2j}\binom{j+k-1}{k-1}$zählt die Verteilungen, die haben$n-2j$Schachteln mit einer ungeraden Anzahl von Bällen.