OFFSET
1,5
COMMENTS
More generally, we have the following related identity.
Given functions F and G with F(0)=0, F'(0)=1, G(0)=0, G'(0)=0,
if F(x - y*G(x)) = x + (1-y)*G(x), then
(C1) F(x) = x + G( y*F(x) + (1-y)*x ),
(C2) y*F(x) + (1-y)*x = Series_Reversion(x - y*G(x)),
(C3) F(x) = x + G(x + y*G(x + y*G(x + y*G(x +...)))),
(C4) F(x) = x + Sum_{n>=1} y^(n-1) * d^(n-1)/dx^(n-1) G(x)^n / n!.
The g.f. A(x,y) of this sequence equals F(x) in the above when G(x) = x*F(x).
LINKS
FORMULA
G.f. A(x,y) also satisfies:
(G1) A(x,y) = x + A( y*A(x,y) + x*(1-y), y).
(G2) y*A(x,y) + x*(1-y) = Series_Reversion( x - x*y*A(x,y) ).
(G3) x*y + (1-y)*B(x,y) = Series_Reversion( x + x*(1-y)*A(x,y) ), where B( A(x,y), y) = x.
(G4) A(x,y) = x + Sum_{n>=1} y^(n-1) * d^(n-1)/dx^(n-1) A(x,y)^n * x^n / n!.
In formulas 2 and 3, the series reversion is taken with respect to variable x.
Formulas for terms:
(T1) T(n,0) = 1.
(T2) T(n,1) = (n-1)*n*(n+4)/6. for n>=1.
(T3) T(n+1,n-1) = binomial(2*n,n)/(n+1) = A000108(n) for n>=1.
Row sums:
(S1) Sum_{k=0..n-1} T(n,k) = A088714(n-1).
(S2) Sum_{k=0..n-1} T(n,k) * 2^(n-k-1) = A276358(n).
(S3) Sum_{k=0..n-1} T(n,k) * 3^(n-k-1) = A291744(n).
(S4) Sum_{k=0..n-1} T(n,k) * 2^k * 3^(n-k-1) = A291743(n).
(S5) Sum_{k=0..n-1} T(n,k) * 2^k = A291813(n).
(S6) Sum_{k=0..n-1} T(n,k) * 3^k = A291814(n).
(S7) Sum_{k=0..n-1} T(n,k) * 4^k = A291815(n).
(S8) Sum_{k=0..n-1} T(n,k) * 3^k * 2^(n-k-1) = A291816(n).
(S9) Sum_{k=0..n-1} T(n,k) * 3^k * 4^(n-k-1) = A291817(n).
(S10) Sum_{k=0..n-1} T(n,k) * 4^k * 3^(n-k-1) = A291818(n).
(S11) Sum_{k=0..n-1} T(n,k) * 4^(n-k-1) = A291819(n).
EXAMPLE
G.f.: A(x,y) = x + x^2 + (2*y + 1)*x^3 + (5*y^2 + 7*y + 1)*x^4 +
(14*y^3 + 38*y^2 + 16*y + 1)*x^5 +
(42*y^4 + 189*y^3 + 157*y^2 + 30*y + 1)*x^6 +
(132*y^5 + 904*y^4 + 1245*y^3 + 477*y^2 + 50*y + 1)*x^7 +
(429*y^6 + 4242*y^5 + 8791*y^4 + 5616*y^3 + 1197*y^2 + 77*y + 1)*x^8 +
(1430*y^7 + 19723*y^6 + 57854*y^5 + 55566*y^4 + 19881*y^3 + 2632*y^2 + 112*y + 1)*x^9 +
(4862*y^8 + 91366*y^7 + 363880*y^6 + 491947*y^5 + 265204*y^4 + 59327*y^3 + 5250*y^2 + 156*y + 1)*x^10 +
(16796*y^9 + 423124*y^8 + 2220933*y^7 + 4039551*y^6 + 3062271*y^5 + 1035442*y^4 + 155783*y^3 + 9714*y^2 + 210*y + 1)*x^11 +
(58786*y^10 + 1963169*y^9 + 13285415*y^8 + 31463341*y^7 + 31979723*y^6 + 15217674*y^5 + 3472513*y^4 + 370205*y^3 + 16929*y^2 + 275*y + 1)*x^12 +...
such that
A( x - x*y*A(x,y), y) = x + x*(1-y)*A(x,y).
Also,
A(x,y) = x + Z*A(Z, y) where Z = y*A(x,y) + (1-y)*x.
...
This triangle of coefficients T(n,k) of x^n*y^k in g.f. A(x,y) begins:
1;
1, 0;
1, 2, 0;
1, 7, 5, 0;
1, 16, 38, 14, 0;
1, 30, 157, 189, 42, 0;
1, 50, 477, 1245, 904, 132, 0;
1, 77, 1197, 5616, 8791, 4242, 429, 0;
1, 112, 2632, 19881, 55566, 57854, 19723, 1430, 0;
1, 156, 5250, 59327, 265204, 491947, 363880, 91366, 4862, 0;
1, 210, 9714, 155783, 1035442, 3062271, 4039551, 2220933, 423124, 16796, 0;
1, 275, 16929, 370205, 3472513, 15217674, 31979723, 31463341, 13285415, 1963169, 58786, 0;
1, 352, 28094, 811877, 10331673, 63678254, 197983540, 310618856, 235959185, 78419541, 9138416, 208012, 0;
1, 442, 44759, 1666522, 27896583, 232505790, 1014785477, 2355151627, 2859824058, 1721756609, 458956233, 42718416, 742900, 0; ...
RELATED SEQUENCES.
Given T(n,k) is the coefficient of x^n*y^k in g.f. A(x,y),
if b(n) = Sum_{k=0..n-1} T(n,k) * p^k * q^(n-k-1)
then B(x) = Sum_{n>=1} b(n)*x^n satisfies
(E1) B(x - p*x*B(x)) = x + (q-p)*x*B(x)
(E2) B(x) = x + Z*B(Z) where Z = p*B(x) + (q-p)*x.
...
G.f.s of columns of this triangle begin:
C.0: 1/(1-x)
C.1: (2 - x)/(1-x)^4
C.2: (5 + 3*x - 4*x^2 + x^3)/(1-x)^7
C.3: (14 + 49*x - 15*x^2 - 9*x^3 + 6*x^4 - x^5)/(1-x)^10
C.4: (42 + 358*x + 315*x^2 - 217*x^3 + 30*x^4 + 18*x^5 - 8*x^6 + x^7)/(1-x)^13
C.5: (132 + 2130*x + 5822*x^2 + 1403*x^3 - 1681*x^4 + 602*x^5 - 50*x^6 - 30*x^7 + 10*x^8 - x^9)/(1-x)^16
C.6: (429 + 11572*x + 62502*x^2 + 82763*x^3 + 2951*x^4 - 9760*x^5 + 5395*x^6 - 1329*x^7 + 75*x^8 + 45*x^9 - 12*x^10 + x^11)/(1-x)^19
C.7: (1430 + 59906*x + 541211*x^2 + 1506161*x^3 + 1217687*x^4 + 16416*x^5 - 35746*x^6 + 36682*x^7 - 13502*x^8 + 2550*x^9 - 105*x^10 - 63*x^11 + 14*x^12 - x^13)/(1-x)^22
C.8: (4862 + 301574*x + 4165915*x^2 + 19578410*x^3 + 34788033*x^4 + 20899306*x^5 + 1681742*x^6 + 174039*x^7 + 195964*x^8 - 103084*x^9 + 28953*x^10 - 4444*x^11 + 140*x^12 + 84*x^13 - 16*x^14 + x^15)/(1-x)^25
...
Thus A(x, y*(1-x)^3)*(1-x) = x + 2*y*x^3 + (5*y^2 - y)*x^4 + (14*y^3 + 3*y^2)*x^5 + (42*y^4 + 49*y^3 - 4*y^2)*x^6 + (132*y^5 + 358*y^4 - 15*y^3 + y^2)*x^7 +...
MATHEMATICA
nmax = 13; A[x_] = x;
Do[A[x_] = x + (y A[x] + (1-y) x) A[y A[x] + (1-y) x] + x O[x]^n // Normal // Expand // Collect[#, x]&, {n, nmax}];
T[n_, k_] := SeriesCoefficient[A[x], {x, 0, n}, {y, 0, k}];
Table[T[n, k], {n, 1, nmax}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Oct 20 2019 *)
PROG
(PARI) {T(n, k) = my(A=x); for(i=1, n, A = x + subst(x*A, x, y*A + (1-y)*x +x*O(x^n)) ); polcoeff(polcoeff(A, n, x), k, y)}
for(n=1, 12, for(k=0, n-1, print1(T(n, k), ", ")); print(""))
CROSSREFS
Cf. A277295 (variant).
KEYWORD
nonn,tabl
AUTHOR
Paul D. Hanna, Sep 01 2017
STATUS
approved