Kombinatorischer Beweis bezüglich fallender Fakultäten und Summen fallender Fakultäten

Question

Kombinatorischer Beweis bezüglich fallender Fakultäten und Summen fallender Fakultäten

Fakultät
Summe
Mathematik
Kombinatorik
Kombinatorische Beweise

Benutzer963900

Beweisen Sie das für jeden $n$ Und $k$ befriedigend $1 \le k \le n$ ,

(N)_{k} = \sum_{ich = k}^{N} k \cdot (ich - 1)_{k - 1}

$(n)_k = \sum_{i = k}^n k \cdot (i-1)_{k-1}$

Wo $(n)_k$ ist die fallende Fakultät.

Ich habe versucht, einen kombinatorischen Beweis wie folgt zu verwenden:

Angenommen, wir wollen auswählen $k$ verschiedene Bälle aus einer Gruppe von $n$ Bälle. Die LHS zählt offensichtlich die Anzahl der Möglichkeiten, wie wir dies tun können.

Die RHS ist die Summe der Möglichkeiten, die wir auswählen können $k-1$ Bälle aus kleineren Sätzen von Bällen und inkrementelles Hinzufügen zum Satz, bis wir unsere ursprüngliche Größe von haben $n$ .

An meiner Interpretation der rechten Seite sind zwei Dinge falsch:

Ich ignoriere die komplett $k$ vor $(i-1)$ . Ich bin mir nicht sicher, ob es relevant ist und warum es funktioniert. Ich dachte ursprünglich, wir multiplizieren mit der Anzahl der Möglichkeiten, wie wir die Bälle neu anordnen können, aber mir wurde schnell klar, dass das in erledigt ist $(i-1)_{k-1}$ Begriff.
Meine Interpretation sagt im Kontext des Problems wirklich nichts aus. Speziell die $k-1$ und warum es uns ermöglicht, aus einer kleineren Gruppe von Bällen zu wählen, um zu unserer Gesamtzahl von Möglichkeiten zu gelangen.

Ich würde mich freuen, wenn jemand etwas Intuition geben könnte, um zu verstehen, was die rechte Seite mir sagt, und einige Schritte in die richtige Richtung.

BEARBEITEN:

Ich konnte die Gleichung wie folgt umschreiben:

(N)_{k} = k \sum_{ich = k}^{N} \frac{(ich - 1)!}{(ich - k)!}

$(n)_k = k\sum_{i = k}^n \frac{(i-1)!}{(i-k)!}$

Antworten (1)

Kombinatorischer Beweis bezüglich fallender Fakultäten und Summen fallender Fakultäten

Mathe-Liebhaber · Answer 1

$\displaystyle (n)_k = \sum_{i = k}^n k \cdot (i-1)_{k-1}$

$= k(n-1)_{k-1} + \sum \limits_{i = k}^{n-1} k \cdot (i-1)_{k-1} = k(n-1)_{k-1} + (n-1)_k$

Die Identität, $\displaystyle n_k = k(n-1)_{k-1} + (n-1)_k$ kann wie folgt erklärt werden -

Sagen wir, wir haben $k$ markierte Stellen hintereinander auf dem Boden und treffen nun verschiedene Anordnungen $k$ Bälle an diesen Stellen nehmen ab $n$ verschiedene Bälle, die wir haben. Dies kann in erfolgen $n_k$ Möglichkeiten, aber wir können auch einen der Bälle beiseite lassen $b_1$ und zähle dann erstmal alle Arrangements mit $(n-1)$ Bälle was ist $(n-1)_k$ . Wir zählen dann Arrangements mit Ball $b_1$ das wurde beiseite gelassen, Ort $b_1$ in einem der $k$ Flecken und dann Rest füllen $(k-1)$ Flecken nehmen von $(n-1)$ Bälle.

Jetzt könnten wir das wiederholen. Einmal bleiben wir beiseite $b_1$ und wir zählen Wege mit $(n-1)$ Bälle zuerst, wir können wieder einen Ball haben $b_2$ beiseite gelegt und Wege mit gezählt $(n-2)$ Bälle zuerst.

Ich hoffe das erklärt.

können Sie bitte erklären, wie $\sum \limits_{i = k}^{n-1} k \cdot (i-1)_{k-1} = (n-1)_k$ ?
Verwenden Sie dieselbe Identität, die Sie zu beweisen versuchen, und sobald wir in der Lage sind, sie zu zeigen $n_k$ das gleiche wiederholt sich für $(n-1)_k$ . Das habe ich am Ende erklärt.

Kombinatorischer Beweis bezüglich fallender Fakultäten und Summen fallender Fakultäten

Benutzer963900

Antworten (1)

Mathe-Liebhaber

Benutzer963900

Mathe-Liebhaber

Kombinatorischer Beweis der Identität 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Beweis Binomialkoeffizient Identität: ∑nk=0kk!nk(nk)=n∑k=0nkk!nk(nk)=n\sum_{k=0}^n\frac{kk!}{n^k}\binom{ n}{k}=n

Kombinatorischer Beweis für die Identität ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

Multiplizieren von drei Fakultäten mit drei Binomen in polynomialer Identität

Lösungsverifikation: Zeigen Sie, dass ∑ni=0(n+an−i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)∑i=0n(n+an−). i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)\sum_{i=0}^{n}{\binom{n+a}{ni}\ binom{i+a+1}{i}}=2^{n}\binom{n+a}{a}+2^{n-1}\binom{n+a}{a+1} für n ≥1n≥1n\geq 1

Kombinatorischer Beweis von ∑k=0n(nk)3k=4n∑k=0n(nk)3k=4n\sum\limits_{k=0}^n {n \choose k}3^k=4^n

Kombinatorische Interpretation für die Identität ∑i(mi)(nj−i)=(m+nj)∑i(mi)(nj−i)=(m+nj)\sum\limits_i\binom{m}{i}\ binom{n}{ji}=\binom{m+n}{j}?

Zeigen Sie, dass für r,n∈Nr,n∈Nr,n\in\mathbb{N} mit r≥nr≥nr\geq n, ∑n−1i=0(−1)i(ni)(r+n−). i−1r)=(r−1n−1)∑i=0n−1(−1)i(ni)(r+n−i−1r)=(r−1n−1)\sum_{i=0} ^{n-1} (-1)^i \binom{n}{i} \binom{r+ni-1}{r} = \binom{r-1}{n-1}

Beweis einer interessanten (fallenden) faktoriellen Identität

Warum entsteht diese Wiederholungsbeziehung, wenn nnn kkk wählt? [Duplikat]