Witt vectors A006177 and A006173

Wed Aug 21 00:53:37 CEST 2002

Curiouser and curiouser...

this:
EULERi(A000108_shifted_left);
> 
> [1, 1, 3, 8, 25, 75, 245, 800, 2700, 9225, 32065, 112632, 400023,
> 
>     1432613, 5170575, 18783360, 68635477, 252085716, 930138521,
> 
>     3446158600, 12815663595, 47820414961, 178987624513, 671825020128,
> 
>     2528212128750, 9536894664375, 36054433807398, 136583760011496,
> 
>     518401146543811, 1971076356825975]

is really distinct sequence from A006177:

Matches (up to a limit of 30) found for       1 3 8 25 75 245 800 2700 9225 32065 112632 400023 : 
[It will take a few minutes to search the table (the second and later lookups are faster)]

ID Number: A022553
Sequence:  1,1,1,3,8,25,75,245,800,2700,9225,32065,112632,400023,
           1432613,5170575,18783360,68635477,252085716,930138521,
           3446158600,12815663595,47820414961,178987624513,
           671825020128,2528212128750,9536894664375
Name:      Lyndon words containing n letters of each type; periodic binary
              sequences of period 2n with n zeros and n ones in each period.
Comments:  Also number of asymmetric rooted plane trees of n+1 nodes (Christian
              Bower).
           Conjecturally, number of irreducible alternating Euler sums of depth
              n and weight 3n.
References F. Bergeron, G. Labelle and P. Leroux, and P. Leroux, Combinatorial
              Species and Tree-Like Structures, Cambridge, 1998, p. 336 (4.4.64)
Links:     Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
           D. J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory
           D. J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory
           Index entries for sequences related to rooted trees
           Index entries for sequences related to Lyndon words
Formula:   prod_n (1-x^n)^{a[ n ]} = 2/(1+\sqrt{1-4x}); a[ n ] = (1/2n) sum_{d|n}
              \mu(n/d) {2d \choose d}. Also Moebius transform of A003239 (Christian
              Bower).
See also:  Cf. A003239, A005354, A000740.
Keywords:  nonn
Offset:    0
Author(s): D.Broadhurst at open.ac.uk (David Broadhurst)

and indeed, the term 75 is the first differing from 72 in A006177:

ID Number: A006177 (Formerly M2750)
Sequence:  1,1,3,8,25,72,245,772,2692,8925,32065,109890,400023,1402723,
           5165327,18484746,68635477,248339122,930138521,3406231198
Name:      Witt vector *2!/2!.
References H. Gaudier, Relevement des coefficients binomiaux dans les vecteurs
              de Witt, S\'{e}minaire Lotharingien de Combinatoire. Institut de
              Recherche Math. Avanc\'{e}e, Universit\'{e} Louis Pasteur,
              Strasbourg, Actes 16 (1988), 358/S-18, pp. 93-108.
Keywords:  nonn
Offset:    1
Author(s): Simon Plouffe (plouffe at math.uqam.ca)

Hmm, necklaces and Witt vectors, I guess now Wouter is not telling us
all he knows about this...

-- Same

Antti Karttunen wrote:
> 
> Wouter Meeussen wrote:
> >
> > hi all,
> >
> > what follows is a resume of some mails in this forum
> > about a year ago (by accident numbered 000108 in seqfan's log)
> >
> > the sequence A006973 has a formula for its generation :
> >      a(n)=if(n<4,max(n-1,0),
> >      (n-1)!*(1+sumdiv(n,k,if(k<n,k*(-a(k)/k!)^(n/k)))))
> >
> > its variants A006177 and A006173 do not.
> > They carry a cryptic description like "Witt vectors *2!",
> > but a simple multipication by 2 is clearly not intended.
> >
> > They can be generated from the Catalans as follows:
> >
> > build the partitions of n,
> > within each partition of n, replace k with z[k] and multiply to get
> >     from (3),(2,1),(1,1,1) to (z[3],z[2]z[1], z[1]^3)
> > and add these to get somos[3]=z[1]^3+z[1]z[2]+z[3]
> > Now get the inverse of this transformation by solving
> > a[k]=somos[k] for the z[k].
> >
> > cat[n_]:=Binomial[2n,n]/(n+1)
> > somos = Table[Plus @@ Apply[Times, Map[z, Partitions[k], {2}], {1}], {k,
> > 28}];
> > invsomos=Array[z,28]/.Flatten[Last[ Solve[Thread[somos==Array[a,28]],Array[z
> > ,28]] ]];
> >
> > and then simply apply the inverse somos transform on the catalans:
> >
> > invsomos/.a[i_]:>cat[i]
> > gives A006177= 1, 1, 3, 8, 25, 72, 245, 772, 2692, 8925
> >
> > invsomos/.a[i_]:> cat[1+i]
> > gives A006173= 2,1,4,13,44,135,472,1492,5324,17405
> 
> How does these transforms, somos and invsomos differ from
> the transforms EULER and EULERi given in
> M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers,
> Linear Algebra and Its Applications, vol. 226-228, pp. 57-72, 1995
> http://www.research.att.com/~njas/doc/eigen.pdf
> but given earlier by
> P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
> where he calls it just "operator S". (on page 91) ?
> 
> After I load the transforms implemented in
> http://www.research.att.com/~njas/sequences/transforms.txt
> to my "student version" of Maple, and do:
> 
> A006177 := [1,1,3,8,25,72,245,772,2692,8925,32065,109890,400023,1402723,
>             5165327,18484746,68635477,248339122,930138521,3406231198];
> 
> EULER(A006177);
> [1, 2, 5, 14, 42, 129, 426, 1396, 4811, 16390, 58204, 203845, 736086,
> 
>     2626634, 9605866, 34823692, 128620528, 470947139, 1754081722,
> 
>     6485357850]
> 
> A000108_shifted_left := [seq(Cat(n),n=1..30)];
> A000108_shifted_left := [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,
> 
>     58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790,
> 
>     477638700, 1767263190, 6564120420, 24466267020, 91482563640,
> 
>     343059613650, 1289904147324, 4861946401452, 18367353072152,
> 
>     69533550916004, 263747951750360, 1002242216651368,
> 
>     3814986502092304]
> 
> EULERi(A000108_shifted_left);
> 
> [1, 1, 3, 8, 25, 75, 245, 800, 2700, 9225, 32065, 112632, 400023,
> 
>     1432613, 5170575, 18783360, 68635477, 252085716, 930138521,
> 
>     3446158600, 12815663595, 47820414961, 178987624513, 671825020128,
> 
>     2528212128750, 9536894664375, 36054433807398, 136583760011496,
> 
>     518401146543811, 1971076356825975]
> 
> And the result does not change, even if I apply the transform to the
> longer sequence, or make the decimal precision higher.
> 
> So, why the differences after the fifth term (129 != 132) in the
> first case, and after the seventh term (800 != 772) in the
> second case? Either it's not the question of the same transformation
> or my Maple implementation is buggy?
> 
> Yours,
> 
> Antti Karttunen
> 
> >
> > Result:
> > to expand a series without ability to generate from its original
> > description.
> >
> > Wouter Meeussen
> > ...sine ratio innovo...
> > wouter.meeussen at pandora.be