right-half-sum triangle - Recursion
Paul D. Hanna
pauldhanna at juno.com
Wed May 25 05:58:51 CEST 2005
Dear Max and Seqfans,
As Ralf indicated, a closed form may not exist ...
but here is a nice recursion:
a(0)=1
a(n) = C(2^(n-1)+n-2,n-1) - Sum_{k=1..n-2} a(k)*C(2^(n-1)-2^k+n-k-1,n-k)
where C(n,k)=binomial(n,k).
EXAMPLE.
a(5) = 516 = C(19,4) - ( 1*C(17,4) + 2*C(14,3) + 7*C(9,2) )
= C(16+4-1,4) - (1*C(16-2+4-1,4) + 2*C(16-4+3-1,3) + 7*C(16-8+2-1,2) ).
PARI CODE.
{a(n)=if(n==0,1,C(2^(n-1)+n-2,n-1)-
sum(k=1,n-2,a(k)*C(2^(n-1)-2^k+n-k-1,n-k)))}
Nice sequence.
Paul
On Mon, 23 May 2005 18:39:01 -0700 Max <relf at unn.ac.ru> writes:
> Hello!
>
> I'm going to add the following sequence to OEIS.
>
> 1 1 2 7 44 516 11622 512022 44588536 7718806044 2664170119608
> 1836214076324153 2529135272371085496 6964321029630556852944
> 38346813253279804426846032 422247020982575523983378003936
> 9298487213328788062025571134762096
>
> which is computed as follows.
>
> To compute a(n) we first write down 2^n units in a line. Each next
> line takes the right half of the previous, and each element in it
> equals sum of the elements above starting with the middle. The only
> element in the last line is a(n).
>
> For example, for a(4) computed "triangle" looks like:
>
> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> . . . . . . . . 1 2 3 4 5 6 7 8
> . . . . . . . . . . . . 5 11 18 26
> . . . . . . . . . . . . . . 18 44
> . . . . . . . . . . . . . . . 44
>
> Therefore, a(n)=44.
>
> I'm mostly interested in a closed formula for this sequence.
> Do you have any idea how to find it?
>
> Thanks,
> Max
>
>
More information about the SeqFan
mailing list