组合数C_n^n-k是不是多项式？

姜咏江

在P/NP的问题中，多项式的概念成为了探讨P是否等于NP问题的关键。关于多项式我在博文《关于多项式时间的辨析》http://blog.sciencenet.cn/blog-340399-895336.html、《算法多项式时间复杂度不靠谱的证明》http://blog.sciencenet.cn/blog-340399-898296.html、《有限元线性过程计数原理》http://blog.sciencenet.cn/blog-340399-896333.html和《算法多项式时间复杂度是天大的笑话！》http://blog.sciencenet.cn/blog-340399-895858.html当中提出了自己的看法，并提出了从等式2ⁿ=来看，所谓O(n^k)的多项式时间是一个悖论。

从组合数计数公式C_n^k=n(n-1)(n-2)…(n-k+1)/k!来看，这是一个k次多项式，其中k≤n。在此等式中总有C_n^k=C_n^n-k这个相等的关系式，那么我们不禁要问：“C_n^n-k是不是多项式？”

多项式有一个很重要的性质：任何有限个多项式之和都是多项式。

我用组合多项式的方式求出了n个数的全部子集，并且求出了任何子集的和（请见博文http://blog.sciencenet.cn/blog-340399-849597.html）。如果你承认了求子集和的这一过程是多项式过程，那么2ⁿ不是多项式就成了错误的认识；如果你不承认这是一个多项式过程，那么“任何有限个多项式之和都是多项式”这个性质也就不存在了，也就是说所谓的多项式概念也不存在了。这不是个悖论吗？

归根结底，我们要回答C_n^n-k是不是多项式？

2015-8-26