【更新中】随笔

前言

随便记录一些平常看到的东西,仅作备忘录使用。


带下取整的和式

通常引入一个新的变量来规避下取整。

下取整根式求和

对于正整数 nn :令 a=na=\left\lfloor\sqrt n\right\rfloor

k=0n1k=na13a312a216a\sum_{k=0}^{n-1}{\left\lfloor\sqrt k\right\rfloor}=na-\frac13a^3-\frac12a^2-\frac16a

证明如下:

k=0n1k=k,m0m[k<n][m=k]=k,m0m[k<n][mk]=k,m0m[k<n][m2k<(m+1)2]=k,m0m[m2k<(m+1)2n]+k,m0m[m2k<n<(m+1)2]\begin{aligned}\sum_{k=0}^{n-1}{\left\lfloor\sqrt k\right\rfloor}&=\sum_{k,m\geqslant0}{m[k<n]\left[m=\left\lfloor\sqrt k\right\rfloor\right]}\\&=\sum_{k,m\geqslant0}{m[k<n][m\leqslant\sqrt{k}]}\\&=\sum_{k,m\geqslant0}{m[k<n][m^2\leqslant k<(m+1)^2]}\\&=\sum_{k,m\geqslant0}{m[m^2\leqslant k<(m+1)^2\leqslant n]}\\&+\sum_{k,m\geqslant0}{m[m^2\leqslant k<n<(m+1)^2]}\end{aligned}

我们令 a=na=\left\lfloor\sqrt n\right\rfloor ,则有:

k=0n1k=k=0a21k+k=a2n1k=k,m0m[m2k<(m+1)2a2]+k,m0m[m2k<a2<(m+1)2]+(na2)a\begin{aligned}\sum_{k=0}^{n-1}{\left\lfloor\sqrt k\right\rfloor}&=\sum_{k=0}^{a^2-1}{\left\lfloor\sqrt k\right\rfloor}+\sum_{k=a^2}^{n-1}{\left\lfloor\sqrt k\right\rfloor}\\&=\sum_{k,m\geqslant0}{m[m^2\leqslant k<(m+1)^2\leqslant a^2]}\\&+\sum_{k,m\geqslant0}{m[m^2\leqslant k<a^2<(m+1)^2]}\\&+(n-a^2)a\end{aligned}

显然有:

k,m0m[m2k<a2<(m+1)2]=0\sum_{k,m\geqslant0}{m[m^2\leqslant k<a^2<(m+1)^2]}=0

k,m0m[m2k<(m+1)2a2]=m0m((m+1)2m2)[m+1a]=m=0a12m2+m=23a312a216a\begin{aligned}&\sum_{k,m\geqslant0}{m[m^2\leqslant k<(m+1)^2\leqslant a^2]}\\&=\sum_{m\geqslant0}{m((m+1)^2-m^2)[m+1\leqslant a]}\\&=\sum_{m=0}^{a-1}{2m^2+m}\\&=\frac23a^3-\frac12a^2-\frac16a\end{aligned}

因此

k=0n1k=23a312a216a+(na2)a=na13a312a216a\sum_{k=0}^{n-1}{\left\lfloor\sqrt k\right\rfloor}=\frac23a^3-\frac12a^2-\frac16a+(n-a^2)a=na-\frac13a^3-\frac12a^2-\frac16a

下取整等差数列求和

对于正整数 mm 和整数 nn :令 d=gcd(m,n)d=\gcd(m,n)

k=0m1nk+xm=dxd+m12n+dm2=dxd+(m1)(n1)2+d12\begin{aligned}\sum_{k=0}^{m-1}{\left\lfloor\frac{nk+x}{m}\right\rfloor}&=d\left\lfloor\frac{x}{d}\right\rfloor+\frac{m-1}{2}n+\frac{d-m}{2}\\&=d\left\lfloor\frac{x}{d}\right\rfloor+\frac{(m-1)(n-1)}{2}+\frac{d-1}{2}\end{aligned}

同时,对于正整数 m,nm,n

k=0m1nk+xm=k=0n1mk+xn\sum_{k=0}^{m-1}{\left\lfloor\frac{nk+x}{m}\right\rfloor}=\sum_{k=0}^{n-1}{\left\lfloor\frac{mk+x}{n }\right\rfloor}


二项式瞎谈

几个比较重要的恒等式:

(nk)=n!k!(nk)!,整数nk0\binom{n}{k}=\frac{n!}{k!(n-k)!},\ \text{整数}n\geqslant k\geqslant0

(nk)=(nnk),整数n0,k是整数\binom{n}{k}=\binom{n}{n-k},\ \text{整数}n\geqslant0,k\text{是整数}

(rk)=rk(r1k1),整数k0\binom{r}{k}=\frac rk\binom{r-1}{k-1},\ \text{整数}k\ne0

(rk)=(r1k)+(r1k1),k是整数\binom{r}{k}=\binom{r-1}{k}+\binom{r-1}{k-1},\ k\text{是整数}

(rk)=(1)k(kr1k),k是整数\binom{r}{k}=(-1)^k\binom{k-r-1}{k},\ k\text{是整数}

(rm)(mk)=(rk)(rkmk),m,k是整数\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k},\ m,k\text{是整数}

k(rk)xkyrk=(x+y)r,整数r0或者xy<1\sum_{k}{\binom{r}{k}x^ky^{r-k}}=(x+y)^r,\ \text{整数}r\geqslant0\text{或者}\left\vert\frac xy\right\vert<1

kn(r+kk)=(r+n+1n),n是整数\sum_{k\leqslant n}{\binom{r+k}{k}}=\binom{r+n+1}{n},\ n\text{是整数}

0kn(km)=(n+1m+1),整数m,n0\sum_{0\leqslant k\leqslant n}{\binom km}=\binom{n+1}{m+1},\ \text{整数}m,n\geqslant0

k(rk)(snk)=(r+sn),n是整数\sum_{k}{\binom rk\binom{s}{n-k}}=\binom{r+s}{n},\ n\text{是整数}

简单的练习

k=0m(mk)(nk),整数nm0\sum_{k=0}^{m}{\frac{\binom mk}{\binom nk}},\ \text{整数}n\geqslant m\geqslant0

显然:

k=0m(mk)(nk)=1(nm)k=0m(nkmk)=(n+1m)(nm)=n+1n+1m\sum_{k=0}^{m}{\frac{\binom mk}{\binom nk}}=\frac{1}{\binom nm}\sum_{k=0}^{m}{\binom{n-k}{m-k}}=\frac{\binom{n+1}{m}}{\binom{n}{m}}=\frac{n+1}{n+1-m}

仍然简单的练习

k=0nk(mk1mn1),整数m>n0\sum_{k=0}^{n}{k\binom{m-k-1}{m-n-1}},\ \text{整数}m>n\geqslant0

未完待续…

斯特林数初探

斯特林数与二项式系数关系比较密切。

斯特林数分为第一类斯特林数(斯特林轮换数)和第二类斯特林数(斯特林子集数),我将使用 [nk]\begin{bmatrix}n\\k\end{bmatrix} 记第一类斯特林数,用 {nk}\begin{Bmatrix}n\\k\end{Bmatrix} 记第二类斯特林数,这个记法与 Jovan Karamata 的做法一致。

第一类斯特林数

第一类斯特林数 [nk]\begin{bmatrix}n\\k\end{bmatrix} 表示将 nn 个元素排成 kk 个轮换的方案数。

由这个定义我们可以得到递推式:

[nk]=(n1)[n1k]+[n1k1],整数n>0\begin{bmatrix}n\\k\end{bmatrix}=(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}+\begin{bmatrix}n-1\\k-1\end{bmatrix},\ \text{整数}n>0

还有一些容易得到的结论:

[n1]=(n1)!,整数n>0\begin{bmatrix}n\\1\end{bmatrix}=(n-1)!,\ \text{整数}n>0

[nn]=1\begin{bmatrix}n\\n\end{bmatrix}=1

[nn1]=(n2)\begin{bmatrix}n\\n-1\end{bmatrix}=\binom n2

k=0n[nk]=n!,整数n0\sum_{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}=n!,\ \text{整数}n\geqslant0

第二类斯特林数

第二类斯特林数 {nk}\begin{Bmatrix}n\\k\end{Bmatrix} 表示将一个有 nn 件物品的集合划分成 kk 个非空子集的方案数。

由这个定义我们可以得到递推式:

{nk}=k{n1k}+{n1k1},整数n>0\begin{Bmatrix}n\\k\end{Bmatrix}=k\begin{Bmatrix}n-1\\k\end{Bmatrix}+\begin{Bmatrix}n-1\\k-1\end{Bmatrix},\ \text{整数}n>0

还有一些容易得到的结论:

{n1}=1,整数n>0\begin{Bmatrix}n\\1\end{Bmatrix}=1,\ \text{整数}n>0

{n2}=2n11,整数n>0\begin{Bmatrix}n\\2\end{Bmatrix}=2^{n-1}-1,\ \text{整数}n>0

{nn}=1\begin{Bmatrix}n\\n\end{Bmatrix}=1

{nn1}=(n2)\begin{Bmatrix}n\\n-1\end{Bmatrix}=\binom n2

两类斯特林数的关系

首先定义:

[nk]={nk}=0,k<0n0\begin{bmatrix}n\\k\end{bmatrix}=\begin{Bmatrix}n\\k\end{Bmatrix}=0,\ k<0\text{且}n\geqslant0

[nk]={nk}=0,k>n\begin{bmatrix}n\\k\end{bmatrix}=\begin{Bmatrix}n\\k\end{Bmatrix}=0,\ k>n

未完待续…