组合计数——数三角形
百度知道中的一个提问，解答五花八门。如图，三角形网格中大大小小的正三角形共有多少个？
本帖最后由 qianyb 于 2011-5-12 09:51 编辑
是411个,刚才没考虑有些倒三角不成立的情况 2# qianyb
好像411个，
$"Floor"((n(n+2)(2n+1))/8)$
http://oeis.org/A002717 这道题好像小学生也可以做，它的题点就是按三角形的大小以及正三角和倒三角分别计数。
正三角与奇偶无关，总数为$C_(n+2)^3$。
倒三角，n=2k+1，总数为$2C_(k+2)^3+2C_(k+1)^3+C_(k+1)^2$
n=2k，总数为$2C_(k+2)^3+2C_(k+1)^3-C_(k+1)^2$ 综合
当n=2k+1时
$f(n)=((n+2)(n+1)n)/6+(2(k+2)(k+1)k)/6+(2(k+1)k(k-1))/6+((k+1)k)/2$
$=((2k+3)(2k+2)(2k+1))/6+(2(2k+1)(k+1)k)/6+((k+1)k)/2$
$=(2k+1)(k+1)^2+((k+1)k)/2=(2n(n+1)^2+(n-1)(n+1))/8$
$=((2n^3+5n^2+2n-1))/8=(n(n+2)(2n+1)-1)/8$
当n=2k时
$f(n)=((n+2)(n+1)n)/6+(2(k+2)(k+1)k)/6+(2(k+1)k(k-1))/6-((k+1)k)/2$
$=(2k(2k+2)(2k+1))/6+(2(2k+1)(k+1)k)/6-((k+1)k)/2$
$=k(2k+1)(k+1)-((k+1)k)/2=(2n(n+1)(n+2)-n(n+2))/8$
$=(n(n+2)(2n+1))/8$
所以对任意n有
$f(n)=(n(n+2)(2n+1)-(n mod 2))/8="Floor"((n(n+2)(2n+1))/8)$ 好强的分析，顶一个
页:
[1]