母函数

nttz

求推导，第一个可以用等比数列吧，n次为啥是这个组合序列

kuing

\begin{align*}
f(x)&=\frac1{(1-x)^n},\\
f'(x)&=n\cdot\frac1{(1-x)^{n+1}},\\
f''(x)&=n(n+1)\cdot\frac1{(1-x)^{n+2}},\\
&\vdots\\
f^{(k)}(x)&=n(n+1)\cdots(n+k-1)\cdot\frac1{(1-x)^{n+k}},\\
\riff f(x)&=f(0)+\frac{f'(0)}{1!}x+\frac{f''(0)}{2!}x^2+\frac{f'''(0)}{3!}x^3+\cdots\\
&=1+\frac n{1!}x+\frac{n(n+1)}{2!}x^2+\frac{n(n+1)(n+2)}{3!}x^3+\cdots
\end{align*}

nttz

kuing 发表于 2022-9-12 12:31
\begin{align*}
f(x)&=\frac1{(1-x)^n},\\
f'(x)&=n\cdot\frac1{(1-x)^{n+1}},\\

初等方法可以做到么，这个是泰勒展开吧

kuing

nttz 发表于 2022-9-12 17:05
初等方法可以做到么，这个是泰勒展开吧

那就归纳法呗，假设
\[\frac1{(1-x)^n}=1+nx+C_{n+1}^2x^2+C_{n+2}^3x^3+\cdots,\]
则
\[\frac1{(1-x)^{n+1}}=(1+nx+C_{n+1}^2x^2+C_{n+2}^3x^3+\cdots)(1+x+x^2+x^3+\cdots),\]
右边展开后 `x^k` 的系数为
\[1+n+C_{n+1}^2+C_{n+2}^3+\cdots+C_{n+k-1}^k,\]
利用 `C_{n+r-1}^r=C_{n+r}^r-C_{n+r-1}^{r-1}` 可知上式就是 `C_{n+k}^k`，即得。

isee

nttz 发表于 2022-9-12 17:05
初等方法可以做到么，这个是泰勒展开吧

你主楼的过程，可能就是初等的展开合并

nttz

isee 发表于 2022-9-12 19:34
你主楼的过程，可能就是初等的展开合并

怎么合并法，最后为啥是那个结果

nttz

kuing 发表于 2022-9-12 18:25
那就归纳法呗，假设
\[\frac1{(1-x)^n}=1+nx+C_{n+1}^2x^2+C_{n+2}^3x^3+\cdots,\]
则

看懂了，有点小复杂，还要用到组合公式，不知道的话没有法子做啊，还有哪些组合公式

hbghlyj

en.wikipedia.org/wiki/Binomial_series#Special_cases
for arbitrary complex $β$
in terms of the multiset coefficient
\[\frac {1}{(1-z)^{\beta }}=\sum _{k=0}^{\infty }\left(\!\!{\beta  \choose k}\!\!\right)z^{k}\]
in terms of the binomial coefficient
\[\frac {1}{(1-z)^{\beta }}=\sum _{k=0}^{\infty }{k+\beta -1 \choose k}z^{k}.\]

hbghlyj

Whether (1) converges depends on the values of the complex numbers α and x. More precisely:

1. If |x| < 1, the series converges absolutely for any complex number α.
2. If |x| = 1, the series converges absolutely if and only if either Re(α) > 0 or α = 0, where Re(α) denotes the real part of α.
3. If |x| = 1 and x ≠ −1, the series converges if and only if Re(α) > −1.
4. If x = −1, the series converges if and only if either Re(α) > 0 or α = 0.
5. If |x| > 1, the series diverges, unless α is a non-negative integer (in which case the series is a finite sum).

In particular, if $α$ is not a non-negative integer, the situation at the boundary of the disk of convergence, $|x|=1$, is summarized as follows:

• If Re(α) > 0, the series converges absolutely.
• If −1 < Re(α) ≤ 0, the series converges conditionally if x ≠ −1 and diverges if x = −1.
• If Re(α) ≤ −1, the series diverges.

hbghlyj

Brilliant wiki–Negative Binomial Theorem

forum.php?mod=viewthread&tid=9244

forum.php?mod=viewthread&tid=8626

战巡

这就是负二项分布的PMF啊

负二项分布：
假设某种试验失败概率为$x$，且每次试验均独立，不断进行该种试验，直到成功$n$次为止，试验失败的次数$X$服从负二项分布，有
\[P(X=k)=C_{k+n-1}^{n-1}x^k(1-x)^n\]
当然负二项分布不止这一种表示方式，有设成功概率为$p$的，有以试验总数为主元的，都无所谓了

这就有
\[\sum_{k=0}^{\infty}P(X=k)=\sum_{k=0}^{\infty}C_{k+n-1}^{n-1}x^k(1-x)^n=1\]

hbghlyj

nttz 发表于 2022-9-12 15:08
还有哪些组合公式 ...

母函数 史济怀 初等数学小丛书 上海教育出版社 1981

hbghlyj

维基
在负二项分布的概率质量函数中，由于k+r次伯努利试验为独立同分布，每个成功r次、失败k次的事件的概率为$(1 − p)^kp^r$。由于第r次成功一定是最后一次试验，所以应该在k+r-1次试验中选择r-1次成功，使用排列组合二项系数获取所有可能的选择数。

hbghlyj

A finite negative binomial identity

One statement of the Binomial Theorem for negative exponents is

$$\sum_{m=0}^\infty \binom{m+k-1}{m} x^m = \frac{1}{(1-x)^k}$$

The combinatorial interpretation is that $\binom{m+k-1}{m}$ is the number of ways to place $m$ indistinguishable balls into $k$ numbered urns: expanding $1/(1-x)^k = (1+x+x^2 + \cdots )^k$ by choosing $x^{m_i}$ from the $i$th factor corresponds to a placement having $m_i$ balls in urn $i$.

Identity (1.16) in Volume 2 of Gould’s Tables is introduced as a finite version of the Binomial Theorem for negative exponents. It states that

$$\sum_{r=0}^n \binom{n+r}{r} \frac{1}{2^r} = 2^n$$

This identity is not of the most basic kind, but the most obvious proof works (although maybe not in the most obvious way). Use induction on $n$ and the Pascal recurrence $\binom{n+r}{r} = \binom{n+r-1}{r} + \binom{n+r-1}{r-1}$ to rewrite the left-hand side: if $R$ is the right-hand side, it follows in a few lines that $R = 2^{n-1} + R/2$, hence the result.

Replace $n$ with $n-1$ and multiply through by $2^{n-1}$ to get the equivalent form

$$\sum_{r=0}^{n-1} \binom{n+r-1}{r} 2^{n-1-r} = 2^{2(n-1)}.$$

Bijective proof. There is a well-known bijection between ways to place $r$ indistinguishable balls into $n$ numbered urns and binary sequences of length $n+r-1$ with exactly $r$ zeros and $n-1$ ones: the zeros correspond to balls, and the ones to urn walls after every right urn wall, and the left wall of urn number $1$ are deleted. For example, $0010110$ encodes the placement with two balls in urn $1$, one ball in urn $2$, no balls in urn $3$, and one ball in urn $4$. Let $S_r$ be the set of sequences of length $2(n-1)$ obtained by extending each such sequence by a further $n-r-1$ bits.

This gives sequences of length $2(n-1)$, but as it stands, only sequences with at least $n-1$ ones appear. So some sequences appear several times as extended ball-and-urn sequences, while others never appear. This can be corrected as follows.

First consider $S_0$. It consists of all sequences of the form $1\ldots 1s_n s_{n+1} \ldots s_{2(n-1)}$. Such a sequence lies in $S_1$ if and only if $s_n=0$. More generally, if $r < n-1$ then a sequence $s \in S_r$ lies in $S_{r+1}$ if and only if $s_{n+r}=0$. Say that such sequences are $r$–flippable. Let $F_r$ be the set of flippable sequences in $S_r$ and let $T_r$ be the set of sequences obtained by flipping the first $n+r-1$ positions of each sequence in $F_r$. Note that the sequences in $T_r$ have their $n$th zero in position $n+r$, and at most $n-2$ ones. Set $T_{n-1} = \varnothing$.

Let $s$ be a binary sequence of length $2(n-1)$.

• Suppose that $s$ has at most $n-2$ ones. Then $s$ has at least $n$ zeros, and we can hope to obtain $s$ by flipping. Suppose that the $n$th zero is in position $n+r$. By the previous remark $s \in T_r$ and $s$ is in no other $T_t$; moreover, flipping the $n-1$ zeros and $r$ ones in positions $1$ up to $n+r-1$ of $s$ gives the corresponding $r$-flippable sequence in $F_r$.
• If $s$ has exactly $n-1$ ones then $s \in S_{n-1}$.
• Suppose that $s$ has at least $n$ ones, and that the $n$th one is in position $n+q$. Then $s \in S_q$ and in no other $S_t$. Moreover $s$ is not $r$-flippable.

The three cases therefore give a bijection

$$ \bigcup_{r=0}^{n-1} F_r \cup (S_r \backslash F_r) \longleftrightarrow \bigcup_{r=0}^{n-1} T_r \cup (S_r \backslash F_r) = \{0,1\}^{2(n-1)}. $$

The size of the left-hand side is $\sum_{r=0}^{n-1} \binom{n+r-1}{r} 2^{n-1-r}$, as required.

hbghlyj

hbghlyj 发表于 2023-3-31 18:03
The combinatorial interpretation is that $\binom{m+k-1}{m}$ is the number of ways to place $m$ indistinguishable balls into $k$ numbered urns: expanding $1/(1-x)^k = (1+x+x^2 + \cdots )^k$ by choosing $x^{m_i}$ from the $i$th factor corresponds to a placement having $m_i$ balls in urn $i$.

隔板法是组合数学的方法，用来处理$ n $个无差别的球放进$ k $个不同的盒子的问题。可一般化为求不定方程的解数，并利用母函数解决问题。