On the Right-Half Sum Sequence

[Paul D Hanna]

    Yes, k=3 is a natural extension, with the now obvious 
recurrence:
a(0)=1
 
a(n) = C(3^n+n-1,n) - Sum_{k=0..n-1} a(k)*C(3^n-3^k+n-k-1,n-k)
 
where  C(n,k) = binomial(n,k) .
 
 
Also k=3 has the generating function: 
 
G.f.: 1 = Sum_{n>=0} a(n)*x^n*(1-x)^(3^n)
 
e.g.,
  
1 = 1*(1-x) + 1*x*(1-x)^3 + 3*x^2*(1-x)^9 + 24*x^3*(1-x)^27 + 541*x^4*(1-x)^81 +...
 
PARI code:
a(n)=polcoeff(1-sum(k=0,n-1,a(k)*x^k*(1-x+x*O(x^n))^(3^k)),n)
 
gives:
1,1,3,24,541,35649,6979689,4085743032,7166723910237,
37698139930450365,594816080266215640710,
28154472624850002001979592,
3997853576535778666975681355079,
1703042427700923785323670557504832751,
 
I have experimented with other variations as well,
and found some very nice matrix relations 
for the general case. 
 
In fact, these sequences have somewhat similar behavior 
as that of Valery Liskovets' automata with k inputs.  
 
I would not be surprised if A107354 is found to have 
some enumerative or combinatorial interpretation. 
 
Paul
 

-- Augustine Munagi <aomunagi at gmail.com> wrote:
SeqFansTo the rapid developments of this nice sequence (i.e., A107354) I wishto add a natural generalization.We can speak of right-(k-th)-sum sequences, for any positive integerk>1, so that the right-half-sum case uses k=2.Max's original definition then generalizes to"To compute a(n) we first write down k^n units in a line. Each nextline takes the rightmost kth part of the previous, and each element init equals sum of the elements above starting with the first of therightmost kth part. The only element in the last line is a(n)".If a(n)=T(n,k) then the right-half sum sequence is T(n,2), n>=0: 1, 1, 2, 7, 44, 516, 11622, 512022, 44588536,………..The sequences T(n,k), n>=0, then continue as follows;T(n,3): 1, 1, 3, 24, 541, 35649, 6979689, 4085743032, 7166723910237,….T(n,4):1, 1, 4, 58, 3236, 713727, 627642640, 2205897096672,………… T(n,5):1, 1, 5, 115, 12885, 7173370, 19940684251,………..T(n,6):1, 1, 6, 201, 39656, 46769781, 330736663032,………….T(n,7):1, 1, 7, 322, 102249, 226742516, 351!
8406903403,………..........and so onFor example T(3,3)=24 is computed from the "triangle"1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 1   1    1………………………………………………1  2  3  4  5  6  7   8    9    ………………………………………………………………7  15  24……………………………………………………………………..24If the above list is viewed as a table then the cross-sequences ofcolumns also look interesting for n>2:T(n,k), k>=1T(2,k):1,2,3,4,5,6,7,..........T(3,k):1, 7, 24, 58, 115, 201, 322,..T(4,k):1, 44, 541, 3236, 12885, 39656, 102249,....T(5,k):1, 516, 35649, 713727, 7173370, 46769781, 226742516,...T(6,k):1, 11622, 6979689, 627642640, 19940684251, 330736663032,...…………….and so on.These sequences are new for n>3. Incidentally T(3,k) is A081436.The following simple maple procedure computes a(n)= rksum(n,k) fromthe definition, for fixed k:rksum:=proc(n::integer,k::posint)local f,a;if n<0 then return 0; elif n=0 or n=1 or k=1 then return 1; end if;f:=L->[seq(add(L[i],i=(k-1)*nops(L)/k+1..j),j=(k-1)*nops(L)/k+!
1..nops(L))];a:=f([seq(1,j=1..k**n)]);while nops(a)>k do a:=f!
(a) end do;return a[k];end procThanks,Augustine.