A002449 as Solution to System of Equations?

Fri Mar 16 00:08:27 CET 2007

Dean (and SeqFans), 
      Great insights, Dean!   I like your formula. 
Here is my formula for the solution using powers of 
a special triangular matrix. 

Consider triangle A098539.  
It has the following nice recurrence. 
Define 
   G(n) =  g.f. of column 0 of matrix power A098539^n 
then 
   G(n) = G(n-1) + x*G(2n)  for n>0 
with 
   G(0) = 1. 

Thus, G(n) equals your p(n), so that  
A = G(1)/G(0) 
B = G(2)/G(1) 
C = G(3)/G(2) 
D = G(4)/G(3) 
... 
The table where G(n) = g.f. of row n, n>=1, begins: 
1,1,2,6,26,166,1626,25510,664666,29559718,...
1,2,6,26,166,1626,25510,664666,29559718,2290267226,...
1,3,12,68,572,7492,159420,5698884,350988988,37958333764,...
1,4,20,140,1460,23884,639156,28895052,2260707508,311748794188,...
1,5,30,250,3110,60954,1962214,107056410,10134502118,1694544254234,...
1,6,42,406,5866,133910,5034218,321429270,35668066538,7000281120534,...
1,7,56,616,10136,264040,11348120,829562728,105514033304,23757895720808,..
.
1,8,72,888,16392,479736,23196168,1909718520,273790460424,69532461669880,.
..
1,9,90,1230,25170,817518,43914642,4019928174,641203506066,181261698262126
,...
1,10,110,1650,37070,1323058,78161358,7873794610,1382795460046,43055479757
2658,...
...  
Thus the table where A is g.f of row 1, B is g.f of row 2, etc., begins: 
1,1,2,6,26,166,1626,25510,664666,29559718,...
1,1,3,15,113,1273,22051,611367,28196129,2230338897,...
1,1,4,28,300,4828,119436,4721916,310281260,34981845276,...
1,1,5,45,625,13065,419629,21515381,1832057785,267608754737,...
1,1,6,66,1126,28946,1142870,71974498,7523036486,1348558405682,...
1,1,7,91,1841,56161,2630495,196403403,24326528073,5166205164609,...
1,1,8,120,2808,99128,5371640,463790776,66403123320,16297734650936,...
1,1,9,153,4065,162993,10029945,983039241,159719775057,44477857100193,...
1,1,10,190,5650,253630,17470258,1916061022,348276030610,108485395435774,.
..
1,1,11,231,7601,377641,28785339,3492739855,702218963281,241912089910513,.
..
...

Thanks, 
     Paul 

On Thu, 15 Mar 2007 10:09:25 -0700 Dean Hickerson <dean at math.ucdavis.edu>
writes:
> Mostly to Paul D. Hanna:
> 
> > Help is needed to simplify the following problem.
> >  
> > Consider the infinite system of simultaneous equations:
> > A = 1 + xAB
> > B = 1 + xBCD
> > C = 1 + xCDEF
> > D = 1 + xDEFGH
> > E = 1 + xEFGHIJ
> > F = 1 + xFGHIJKL
> > ... 
> > What is the unique solution to the variables A,B,C,... as 
> functions in x?
> 
> First, they're not really functions, since the power series don't 
> converge
> for x!=0.  But the question makes sense for formal power series.
> 
> Let a(1) = A, a(2) = B, a(3) = C, ...  Then the equations say that
> 
>     a(n) = 1 + x a(n) a(n+1) ... a(2n)
> 
> for n>=1.  Let p(n) be the product a(1)*...*a(n); in particular p(0) 
> = 1.
> Then
> 
>     p(n) = p(n-1) + x p(2n).
> 
> Now let p(n) = sum_{i>=0} c(n,i) x^i.  The c's can be computed by
> the recurrence
> 
>     c(n,i) = c(n-1,i) + c(2n,i-1)    for n>=1, i>=1,
> 
> with the initial conditions
> 
>     c(n,0) = 1    for n>=0,
> 
>     c(0,i) = 0    for i>=1.
> 
> Since A = a(1) = p(1), you want the terms c(1,i).
> 
> As you said, computing c(1,i) takes about 2^i steps.  But it turns 
> out
> that, for fixed i, c(n,i) is a polynomial in n, of degree i:
> 
>     c(n,i) = sum_{0<=j<=i} d(i,j) n^j.
> 
> Getting a recurrence for the d's is straightforward but messy.  
> (I.e. it
> took me a few tries to get it right.)  We find:
> 
>     d(0,0) = 1,
> 
>     d(i,0) = 0    for i>=1,
> 
> and
> 
>     d(i,j) = 1/j [2^(j-1) d(i-1,j-1) -
>              sum_{j+1<=m<=i} (-1)^(j+m) binomial(m,j-1) d(i,m)]   
> for 1<=j<=i.
> 
> Using this, we can compute the c's much more quickly.  In 
> Mathematica:
> 
>     d[0,0]=1;
>     d[i_,0]:=0;
>     d[i_,j_]:= d[i,j] = 1/j (2^(j-1) d[i-1,j-1] -
>                         Sum[(-1)^(j+m) Binomial[m,j-1] d[i,m], 
> {m,j+1,i}] );
> 
>     c[0,i_]:=d[i,0];
>     c[n_,i_]:=Sum[d[i,j] n^j,{j,0,i}];
> 
>     Table[c[1,i],{i,0,20}]
> 
> :
> 
>     {1, 1, 2, 6, 26, 166, 1626, 25510, 664666, 29559718, 
[...]
> > Could someone calculate more coefficients of A 
> > to see if they continue to agree with A002449? 
> 
> They agree at least up to A002499(50).
> 
> Dean Hickerson
> dean at math.ucdavis.edu
> 
> 

Is A57745 an incorrect version of A83276?  The comment to A83276 
describes how a term is different because of an illegal move in the 
other sequence.

Dear Seqfans:

Can anyone figure this out?

%I A109636
%S A109636 2,3,9,10,27,28,30,81,84,88,90,100,104,243,252,264,270,272,280,300,304,
%T A109636 312,729,736,756,784,792,810,816,840,880,900,912,928,936,992,1000,1040,
%U A109636 2187,2208,2268,2352,2368,2376
%N A109636 Minimal numbers in k-almost prime numbers massiv of (n,k) such that number of (n,k+l) is equal 2^l times the number of (n,k) for any l>0.
%H A109636 Wikipedia, <a href="http://en.wikipedia.org/wiki/Almost_prime">k-almost prime numbers</a>.
%Y A109636 Cf. A000040, A001358, A014612, A014613, A014614.
%Y A109636 Sequence in context: A047358 A003140 A057234 this_sequence A057236 A063257 A103039
%Y A109636 Adjacent sequences: A109633 A109634 A109635 this_sequence A109637 A109638 A109639
%K A109636 nonn,uned,obsc
%O A109636 1,1
%A A109636 Yury V. Shlapak (shlapak(AT)imp.kiev.ua), Aug 04 2005

Possibly one of the Russian-speaking members of the list can
help by translating it to Russian, where it might be clearer?
What does "(n,k)" mean???

Neil

PS The "binary splitting" mystery sequence A126119 of the other day remains
a mystery