cp's OEIS Frontend

A192744 Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.

%I A192744 #16 Dec 16 2015 04:29:03
%S A192744 1,1,3,8,29,133,762,5215,41257,369032,3676209,40333241,483094250,
%T A192744 6271446691,87705811341,1314473334832,21017294666173,357096406209005,
%U A192744 6424799978507178,122024623087820183,2439706330834135361,51219771117454755544
%N A192744 Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.
%C A192744 The titular polynomial is defined recursively by p(n,x)=x*p(n-1,x)+n! for n>0, where p(0,x)=1; see the Example.  For an introduction to polynomial reduction, see A192232.  The discussion at A192232 Comments continues here:
%C A192744 ...
%C A192744 Let R(p,q,s) denote the "reduction of polynomial p by q->s" as defined at A192232.  Suppose that q(x)=x^k for some k>0 and that s(x)=s(k,0)*x^(k-1)+s(k,1)*x^(k-2)+...+s(k,k-2)x+s(k,k-1).
%C A192744 ...
%C A192744 First, we shall take p(x)=x^n, where n>=0; the results will be used to formulate R(p,q,s) for general p.  Represent R(x^n,q,s) by
%C A192744 ...
%C A192744 R(x^n)=s(n,0)*x^(k-1)+s(n,1)*x^(k-2)+...+s(n,k-2)*x+s(n,k-1).
%C A192744 ...
%C A192744 Then each of the sequences u(n)=s(n,h), for h=0,1,...,k-1, satisfies this linear recurrence relation:
%C A192744 ...
%C A192744 u(n)=s(k,0)*u(n-1)+s(k,1)*u(n-2)+...+s(k,k-2)*u(n-k-1)+s(k,k-1)*u(n-k), with initial values tabulated here:
%C A192744 ...
%C A192744 n: ..s(n,0)...s(n,1)..s(n,2).......s(n,k-2)..s(n,k-1)
%C A192744 0: ....0........0.......0..............0.......1
%C A192744 1: ....0........0.......0..............1.......0
%C A192744 ...
%C A192744 k-2: ..0........1.......0..............0.......0
%C A192744 k-1: ..0........0.......0..............0.......0
%C A192744 k: ..s(k,0)...s(k,1)..s(k,2).......s(k,k-2)..s(k,k-1)
%C A192744 ...
%C A192744 That completes the formulation for p(x)=x^n.  Turning to the general case, suppose that
%C A192744 ...
%C A192744 p(n,x)=p(n,0)*x^n+p(n,1)*x^(n-1)+...+p(n,n-1)*x+p(n,n)
%C A192744 ...
%C A192744 is a polynomial of degree n>=0.  Then the reduction denoted by (R(p(n,x) by x^k -> s(x)) is the polynomial of degree k-1 given by the matrix product P*S*X, where P=(p(n,0)...p(n,1).........p(n-k)...p(n,n-k+1); X has all 0's except for main diagonal (x^(k-1), x^(k-2)...x,1); and S has
%C A192744 ...
%C A192744 row 1: ... s(n,0) ... s(n,1) ...... s(n,k-2) . s(n,k-1)
%C A192744 row 2: ... s(n-1,0) . s(n-1,1) .... s(n-1,k-2) s(n-1,k-1)
%C A192744 ...
%C A192744 row n-k+1: s(k,0).... s(k,1) ...... s(k,k-2) ..s(k,k-1)
%C A192744 row n-k+2: p(n,n-k+1) p(n,n-k+2) .. p(n,n-1) ..p(n,n)
%C A192744 *****
%C A192744 As a class of examples, suppose that (v(n)), for n>=0, is a sequence, that p(0,x)=1, and p(n,x)=v(n)+p(n-1,x) for n>0.  If q(x)=x^2 and s(x)=x+1, and we write the reduction R(p(n,x)) as u1(n)*x+u2(n), then the sequences u1 and u2 are convolutions with the Fibonacci sequence, viz., let F=(0,1,1,2,3,5,8,...)=A000045 and let G=(1,0,1,1,2,3,5,8...); then u1=G**v and u2=F**v, where ** denotes convolution.  Examples (with a few exceptions for initial terms):
%C A192744 ...
%C A192744 If v(n)=n! then u1=A192744, u2=A192745.
%C A192744 If v(n)=n+1 then u1=A000071, u2=A001924.
%C A192744 If v(n)=2n then u1=A014739, u2=A027181.
%C A192744 If v(n)=2n+1 then u1=A001911, u2=A001891.
%C A192744 If v(n)=3n+1 then u1=A027961, u2=A023537.
%C A192744 If v(n)=3n+2 then u1=A192746, u2=A192747.
%C A192744 If v(n)=3n then u1=A154691, u2=A192748.
%C A192744 If v(n)=4n+1 then u1=A053311, u2=A192749.
%C A192744 If v(n)=4n+2 then u1=A192750, u2=A192751.
%C A192744 If v(n)=4n+3 then u1=A192752, u2=A192753.
%C A192744 If v(n)=4n then u1=A147728, u2=A023654.
%C A192744 If v(n)=5n+1 then u1=A192754, u2=A192755.
%C A192744 If v(n)=5n then u1=A166863, u2=A192756.
%C A192744 If v(n)=floor((n+1)tau) then u1=A192457, u2=A023611.
%C A192744 If v(n)=floor((n+2)/2) then u1=A052952, u2=A129696.
%C A192744 If v(n)=floor((n+3)/3) then u1=A004695, u2=A178982.
%C A192744 If v(n)=floor((n+4)/4) then u1=A080239, u2=A192758.
%C A192744 If v(n)=floor((n+5)/5) then u1=A124502, u2=A192759.
%C A192744 If v(n)=n+2 then u1=A001594, u2=A192760.
%C A192744 If v(n)=n+3 then u1=A022318, u2=A192761.
%C A192744 If v(n)=n+4 then u1=A022319, u2=A192762.
%C A192744 If v(n)=2^n then u1=A027934, u2=A008766.
%C A192744 If v(n)=3^n then u1=A106517, u2=A094688.
%F A192744 G.f.: (1-x)/(1-x-x^2)/Q(0), where Q(k)= 1 - x*(k+1)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - _Sergei N. Gladkovskii_, May 20 2013
%F A192744 Conjecture: a(n) +(-n-2)*a(n-1) +2*(n-1)*a(n-2) +3*a(n-3) +(-n+2)*a(n-4)=0. - _R. J. Mathar_, May 04 2014
%F A192744 Conjecture: (-n+2)*a(n) +(n^2-n-1)*a(n-1) +(-n^2+3*n-3)*a(n-2) -(n-1)^2*a(n-3)
%F A192744 =0. - _R. J. Mathar_, Dec 16 2015
%e A192744 The first five polynomials and their reductions:
%e A192744 1 -> 1
%e A192744 1+x -> 1+x
%e A192744 2+x+x^2 -> 3+2x
%e A192744 6+2x+x^2+x^3 -> 8+5x
%e A192744 24+6x+2x^2+x^3+x^4 -> 29+13x, so that
%e A192744 A192744=(1,1,3,8,29,...) and A192745=(0,1,2,5,13,...).
%p A192744 A192744p := proc(n,x)
%p A192744     option remember;
%p A192744     if n = 0 then
%p A192744         1;
%p A192744     else
%p A192744         x*procname(n-1,x)+n! ;
%p A192744         expand(%) ;
%p A192744     end if;
%p A192744 end proc:
%p A192744 A192744 := proc(n)
%p A192744     local p;
%p A192744     p := A192744p(n,x) ;
%p A192744     while degree(p,x) > 1 do
%p A192744         p := algsubs(x^2=x+1,p) ;
%p A192744         p := expand(p) ;
%p A192744     end do:
%p A192744     coeftayl(p,x=0,0) ;
%p A192744 end proc: # _R. J. Mathar_, Dec 16 2015
%t A192744 q = x^2; s = x + 1; z = 40;
%t A192744 p[0, n_] := 1; p[n_, x_] := x*p[n - 1, x] + n!;
%t A192744 Table[Expand[p[n, x]], {n, 0, 7}]
%t A192744 reduce[{p1_, q_, s_, x_}] :=
%t A192744 FixedPoint[(s PolynomialQuotient @@ #1 +
%t A192744        PolynomialRemainder @@ #1 &)[{#1, q, x}] &, p1]
%t A192744 t = Table[reduce[{p[n, x], q, s, x}], {n, 0, z}];
%t A192744 u1 = Table[Coefficient[Part[t, n], x, 0], {n, 1, z}]
%t A192744   (* A192744 *)
%t A192744 u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]
%t A192744   (* A192745 *)
%Y A192744 Cf. A192232.
%K A192744 nonn
%O A192744 0,3
%A A192744 _Clark Kimberling_, Jul 09 2011