tag:blogger.com,1999:blog-3722233.post3919962201160286520..comments2023-12-07T03:00:23.146-06:00Comments on Computational Complexity: An interesting summation- new?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-7065642814848928332008-07-15T22:37:00.000-05:002008-07-15T22:37:00.000-05:00As previously mentioned see Concrete Math (my favo...As previously mentioned see Concrete Math (my favorite book). Kind of reminds me of the sieve formula for poly-Bernoulli numbers. <A HREF="http://www.integers-ejcnt.org/vol8.html" REL="nofollow">http://www.integers-ejcnt.org/vol8.html</A> (A2, Page 4, equation 1)Chad Brewbakerhttps://www.blogger.com/profile/10443154815748267611noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11894087482798625992008-07-15T18:39:00.000-05:002008-07-15T18:39:00.000-05:00This turns out to be a familiar fact in disguise, ...This turns out to be a familiar fact in disguise, from the calculus of finite differences: the k-th difference of the k-th power function is k! (no matter which point a you evaluate it at). So it's definitely well known, although I don't know a formal name for it. It all comes down to the alternating binomial coefficient expansion of the k-th difference of a function.<BR/><BR/>One can also give a combinatorial proof (when a is a positive integer, that is). Here's a sketch. Suppose we want to choose an ordered k-tuple of elements of {1,2,...,k+a} such that each element of {1,2,...,k} is used at least once. Of course, there are k! ways to do this. Suppose we try to calculate this by inclusion-exclusion. There are (a+k)^k sequences with no constraint. For each element of {1,2,...,k}, there are (a+k-1)^k that don't use it, so we'd better subtract off (k choose 1)*(a+k-1)^k. However, now we've oversubtracted, so we'd better add back in (k choose 2)*(a+k-2)^k to compensate. Carrying this out until the end gives the desired identity.<BR/><BR/>However, I think the calculus of finite differences interpretation is the simplest and clearest.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64865446349155656412008-07-15T15:24:00.000-05:002008-07-15T15:24:00.000-05:00It's hard to come up with any sort of identity tha...It's hard to come up with any sort of identity that's not already been published in Concrete Mathematics (albeit probably in a more general form)!Anonymoushttps://www.blogger.com/profile/10349419938002960339noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85563779666650176132008-07-15T13:41:00.000-05:002008-07-15T13:41:00.000-05:00You can poke around at the online encyclopedia of ...You can poke around at the online encyclopedia of integer sequences for related results.<BR/><BR/>http://www.research.att.com/~njas/sequences/<BR/><BR/>You can look up sequences by entering the first few numbers in the sequence.<BR/><BR/>NealAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24649004711723980432008-07-15T13:15:00.000-05:002008-07-15T13:15:00.000-05:00Hi Bill,A more general version of this sum is in C...Hi Bill,<BR/><BR/>A more general version of this sum is in Concrete Mathematics (Knuth et al., Concrete Mathematics, 2nd Edition, page 190):<BR/><BR/>Identity 5.42:<BR/><BR/>\sum (n choose k) * (-1)^k * (a_0 + a_1*k + a_2 + ... + a_n*k^n) = (-1)^n * n! * a_n<BR/><BR/>where a_0,...,a_n are arbitrary coefficients.marianhttps://www.blogger.com/profile/17087695870672284058noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65121641402102848332008-07-15T12:22:00.000-05:002008-07-15T12:22:00.000-05:00YES that should bef_{j+1} = xf_j'(x).I have fixed ...YES that should be<BR/>f_{j+1} = xf_j'(x).<BR/><BR/>I have fixed it.<BR/><BR/>As for SUMS wiki: might<BR/>be a good idea, but first<BR/>check that the sum is not<BR/>in the A=B class, since those<BR/>can ALL be done.<BR/><BR/>Bill G.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70020421703912515352008-07-15T11:52:00.000-05:002008-07-15T11:52:00.000-05:00In your proof, did you figure f '_j(x) = f_j(x)? ...In your proof, did you figure f '_j(x) = f_j(x)? I think there's a " ' " somewhere missing. Haven't seen this one before. I second the vote for a "sums" wikiTeutschhttps://www.blogger.com/profile/04848264673734802964noreply@blogger.com