[math-fun] Superfluous Multinomials
dear funsters, when posting stuff like this, I presume it is generally known, or at least could be. Motivation: just fun and beauty. 1/. Intro consider the expansion of (a+b+c+d)^3 it is the sum over M(u,v,w,x) a^u b^v c^w d^x with positive or zero integers u+v+w+x=3 and M(u,v,w,x) is the multinomial u! v! w! x! /(u+v+w+x)! When we drop the multinomial coefficients, then we get the 'compositions' of 4 elements in groups of three. in Mma: Expand[(a+b+c+d)^3 /3! ]/. q_^n_ ->q^n n! gives a^3 + a^2*b + a*b^2 + b^3 + a^2*c + a*b*c + b^2*c + a*c^2 + b*c^2 + c^3 + a^2*d + a*b*d + b^2*d + a*c*d + b*c*d + c^2*d + a*d^2 + b*d^2 + c*d^2 + d^3 this is equivalent to Plus @@ Apply[Times,{a,b,c,d}^#& /@Compositions[3,4],{1}] 2/. Generalise replace the (a+b+c+d) above by Sum(j=1..n, t[ j ] ) , t stands for 'temporary', now replace t[j] with E^(2 Pi I j/n) and it's obvious that this sum equals zero. And that any power of zero is also zero. But now, dropping multinomials, we find: Table[ Plus@@ Apply[Times,(Exp[2 Pi I/n]^Range[n])^#& /@ Compositions[k,n],{1}],{n,5},{k,n}] and we find that it's also zero, except it's 1 when k equals n, that is, we take all n roots of (-1) and put it to the n-th (multinomial-less) power. 3/. an instructive typo : Exp[2 Pi I/k] instead of Exp[2 Pi I/n]: Table[ Plus@@ Apply[Times,(Exp[2 Pi I/k]^Range[n])^#& /@ Compositions[k,n],{1}],{n,5},{k,n}] equals Table[Ceiling[n/m],{n,9},{m,n}] alias A120885 That leads to this silly remark: Table[ Plus@@ (Exp[2 Pi I/k]^Range[n])^k ,{n,16},{k,n}] is integer, except for the following couples of {n,k} : {7, 5}, {8, 5}, {9, 7}, {10, 7}, {10, 8}, {11, 7}, {11, 8}, {11, 9}, {12, 5}, {12, 7}, {12, 8}, {12, 9}, {12, 10}, {13, 5}, {13, 8}, {13, 9}, {13, 10}, {13, 11}, {14, 8}, {14, 9}, {14, 10}, {14, 11}, {14, 12}, {15, 9}, {15, 10}, {15, 11}, {15, 12}, {15, 13}, {16, 7}, {16, 9}, {16, 10}, {16, 11}, {16, 12}, {16, 13}, {16, 14}, ... and, where's the system in *this* madness? Wouter.
now with some more standard notation to clarifiy the Mathematica-formulas. see text. Hope not to vex or annoy anyone excessively, W. ----- Original Message ----- From: "wouter meeussen" <wouter.meeussen@pandora.be> To: "math-fun" <math-fun@mailman.xmission.com> Cc: "Wouter Meeussen" <wouter.meeussen@vandemoortele.com> Sent: Sunday, May 25, 2008 2:37 PM Subject: [math-fun] Superfluous Multinomials
dear funsters,
when posting stuff like this, I presume it is generally known, or at least could be. Motivation: just fun and beauty.
1/. Intro
consider the expansion of (a+b+c+d)^3 it is the sum over M(u,v,w,x) a^u b^v c^w d^x with positive or zero integers u+v+w+x=3 and M(u,v,w,x) is the multinomial u! v! w! x! /(u+v+w+x)!
When we drop the multinomial coefficients, then we get the 'compositions' of 4 elements in groups of three. in Mma: Expand[(a+b+c+d)^3 /3! ]/. q_^n_ ->q^n n! gives
the part after "/." is a rule, replacing q^n by q^n * n! In this example, I used a 3rd power of 4 terms
a^3 + a^2*b + a*b^2 + b^3 + a^2*c + a*b*c + b^2*c + a*c^2 + b*c^2 + c^3 + a^2*d + a*b*d + b^2*d + a*c*d + b*c*d + c^2*d + a*d^2 + b*d^2 + c*d^2 + d^3
this is equivalent to Plus @@ Apply[Times,{a,b,c,d}^#& /@Compositions[3,4],{1}]
this goes as follows: with a, b, c and d as input parameters, as yet unspecified, do Sum(sets of u,v,w,x from all compositions C(3,4) ; a^u b^v c^w d^x ) where C(3,4) specifies the {u,v,w,x}as {3,0,0,0}, {2,1,0,0}, {2,0,1,0}, ...
2/. Generalise
replace the (a+b+c+d) above by Sum(j=1..n, t[ j ] ) , t stands for 'temporary', now replace t[j] with E^(2 Pi I j/n) and it's obvious that
this
sum equals zero. And that any power of zero is also zero.
But now, dropping multinomials, we find: Table[ Plus@@ Apply[Times,(Exp[2 Pi I/n]^Range[n])^#& /@ Compositions[k,n],{1}],{n,5},{k,n}]
same as above, but now with {a,b,c,d} replaced by (Exp[2 Pi I/n]^Range[n]) which is {Exp[2 Pi I/n]^1 ,Exp[2 Pi I/n]^2, ..., Exp[2 Pi I/n]^n} so, we have not 4 but n terms, taken not to the 3rd, but to the k-th power.
and we find that it's also zero, except it's 1 when k equals n,
or a multiple of n,
that is, we take all n roots of (-1) and put it to the n-th (multinomial-less) power.
3/. an instructive typo : Exp[2 Pi I/k] instead of Exp[2 Pi I/n]:
Table[ Plus@@ Apply[Times,(Exp[2 Pi I/k]^Range[n])^#& /@ Compositions[k,n],{1}],{n,5},{k,n}] equals Table[Ceiling[n/m],{n,9},{m,n}] alias A120885 That leads to this silly remark:
since the multinomial-less power is so simple, what about the 'normal' power in this case?
Table[ Plus@@ (Exp[2 Pi I/k]^Range[n])^k ,{n,16},{k,n}] is integer, except for the following couples of {n,k} : {7, 5}, {8, 5}, {9, 7}, {10, 7}, {10, 8}, {11, 7}, {11, 8}, {11, 9}, {12, 5}, {12, 7}, {12, 8}, {12, 9}, {12, 10}, {13, 5}, {13, 8}, {13, 9}, {13, 10}, {13, 11}, {14, 8}, {14, 9}, {14, 10}, {14, 11}, {14, 12}, {15, 9}, {15, 10}, {15, 11}, {15, 12}, {15, 13}, {16, 7}, {16, 9}, {16, 10}, {16, 11}, {16, 12}, {16, 13}, {16, 14}, ... and, where's the system in *this* madness?
Wouter.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Two recent threads, on floating point precision and on the elegance of asinh, got me to try to play in my favorite interpreted programming language--PostScript. Of course, PS doesn't standardly provide any hyperbolic functions, but they are trivially defined in terms of exp and ln. The problem is with [lack of] precision. PS starts out with only single precision floating point, and then a lot more precision gets thrown away for values near zero. I suppose I could use a power series for values near zero, or maybe use the hyperbolic version of what I think is Gosper's recursive sin function (based on sin(3x) = 3 sin(x) - 4 sin^3(x)) (hyperbolic equivalent: sinh(3x) = 3 sinh(x) + 4 sinh^3(x)). But I wondered why the standard floating point math libraries (at least the ones I know about) don't provide exp(x)-1 and ln(1+x). Each of these functions is approximately x for small x, and so would avoid the loss of precision when adding 1 to a small number. (If one already has hyperbolic functions, then I suppose exp(x)-1 = sinh(x) (1 + sinh(x)/(cosh(x)+1)), and log(1+x) = 2 atanh(x/(2+x)).) --ms
You are correct! However, Apple's original "SANE" library, on which Kahan consulted (I believe), _did_ have exp1(x) & log1(x), because without them, it is nearly impossible to get decent results when computing compound interest. http://developer.apple.com/documentation/mac/PPCNumerics/PPCNumerics-168.htm... I believe that Kahan also consulted on the Intel 80387 floating point coprocessor, which I believe also has these two functions. The sad part is that these two functions haven't made it into high school curricula, so that students can learn a little about numerical analysis. At 07:15 PM 8/1/2008, Mike Speciner wrote:
But I wondered why the standard floating point math libraries (at least the ones I know about) don't provide exp(x)-1 and ln(1+x). Each of these functions is approximately x for small x, and so would avoid the loss of precision when adding 1 to a small number. (If one already has hyperbolic functions, then I suppose exp(x)-1 = sinh(x) (1 + sinh(x)/(cosh(x)+1)), and log(1+x) = 2 atanh(x/(2+x)).)
--ms
Thanks for the pointer. I see that these functions are now called expm1 and log1p, and are available in many (but sadly not all) math libraries and languages, and people know enough to complain when they're not present. Were I still writing PostScript clones, I'd make sure to include them, even though it wouldn't be quite Adobe compatible. --ms -----Original Message----- From: Henry Baker [mailto:hbaker1@pipeline.com] Sent: Saturday, August 02, 2008 10:39 To: ms@alum.mit.edu; math-fun Subject: Re: [math-fun] floating point precision and hyperbolic functions You are correct! However, Apple's original "SANE" library, on which Kahan consulted (I believe), _did_ have exp1(x) & log1(x), because without them, it is nearly impossible to get decent results when computing compound interest. http://developer.apple.com/documentation/mac/PPCNumerics/PPCNumerics-168.htm l I believe that Kahan also consulted on the Intel 80387 floating point coprocessor, which I believe also has these two functions. The sad part is that these two functions haven't made it into high school curricula, so that students can learn a little about numerical analysis. At 07:15 PM 8/1/2008, Mike Speciner wrote:
But I wondered why the standard floating point math libraries (at least the ones I know about) don't provide exp(x)-1 and ln(1+x). Each of these functions is approximately x for small x, and so would avoid the loss of precision when adding 1 to a small number. (If one already has hyperbolic functions, then I suppose exp(x)-1 = sinh(x) (1 + sinh(x)/(cosh(x)+1)), and log(1+x) = 2 atanh(x/(2+x)).)
--ms
* Mike Speciner <ms@alum.mit.edu> [Aug 03. 2008 21:08]:
Thanks for the pointer. I see that these functions are now called expm1 and log1p, and are available in many (but sadly not all) math libraries and languages, and people know enough to complain when they're not present. Were I still writing PostScript clones, I'd make sure to include them, even though it wouldn't be quite Adobe compatible.
--ms
[...]
Seems at least ISO C99 (and new versions of XOPEN) require that: from the man pages: expm1(), expm1f(), expm1l(): _BSD_SOURCE || _SVID_SOURCE || _XOPEN_SOURCE >= 500 || _ISOC99_SOURCE; or cc -std=c99 very same for log1p()
An interesting choice for a binary sinh & asinh would be 2^x-2^(-x) [define as sinh2(x)?] and its inverse. Look at the bit patterns for 2^n-2^(-n) for n a positive integer: n bit pattern 0 0.0 1 01.10 2 011.110 3 0111.1110 etc. The "area" under the pulse/curve is 2*n. Perhaps a slightly different number representation would enable (2^n-2^(-n))/2 to work better, and to have an "area" of 1*n. Since multiplication acts like convolution, (sinh2(x))^n for large n should approach a normal distribution. The bit patterns for an analogous cosh2(n)=2^n+2^(-n) are n bit pattern 0 10.00 1 01.10 2 010.010 3 0100.0010 4 01000.00010 Once again, a slightly different number representation would enable (2^n+2^(-n))/2 to look prettier. (cosh2(x))^n should generate Pascal's triangle. At 11:18 PM 8/3/2008, Joerg Arndt wrote:
* Mike Speciner <ms@alum.mit.edu> [Aug 03. 2008 21:08]:
Thanks for the pointer. I see that these functions are now called expm1 and log1p, and are available in many (but sadly not all) math libraries and languages, and people know enough to complain when they're not present. Were I still writing PostScript clones, I'd make sure to include them, even though it wouldn't be quite Adobe compatible.
--ms
[...]
Seems at least ISO C99 (and new versions of XOPEN) require that: from the man pages:
expm1(), expm1f(), expm1l(): _BSD_SOURCE || _SVID_SOURCE || _XOPEN_SOURCE >= 500 || _ISOC99_SOURCE; or cc -std=c99
very same for log1p()
participants (4)
-
Henry Baker -
Joerg Arndt -
Mike Speciner -
wouter meeussen