A078802 -id:A078802 - cp's OEIS frontend

A078803 Triangular array T given by T(n,k) = number of compositions of n into k parts, each in the set {1,2,3}.

1, 1, 1, 1, 2, 1, 0, 3, 3, 1, 0, 2, 6, 4, 1, 0, 1, 7, 10, 5, 1, 0, 0, 6, 16, 15, 6, 1, 0, 0, 3, 19, 30, 21, 7, 1, 0, 0, 1, 16, 45, 50, 28, 8, 1, 0, 0, 0, 10, 51, 90, 77, 36, 9, 1, 0, 0, 0, 4, 45, 126, 161, 112, 45, 10, 1, 0, 0, 0, 1, 30, 141, 266, 266, 156, 55, 11, 1, 0, 0, 0, 0, 15, 126

Offset: 1

Clark Kimberling, Dec 06 2002

Number of lattice paths from (0,0) to (n,k) using steps (1,1), (2,1), (3,1). - Joerg Arndt, Jul 05 2011
Reversing the rows produces A078802. Row sums: A000073.
Number of tribonacci binary words of length n-1 having k-1 1's. A tribonacci binary word is a binary word having no three consecutive 0's. Example: T(6,3)=7 because we have 00101,00110,01001,01010,01100,10010 and 10100. - Emeric Deutsch, Jun 16 2007
This is the Riordan array (1,x+x^2+x^3)(A071675) without its column k=0. - Vladimir Kruchinin, Feb 10 2011

			T(5,2) = 2 counts the compositions 2+3 and 3+2.
Triangle begins
  1;
  1, 1;
  1, 2, 1;
  0, 3, 3, 1;
  0, 2, 6, 4, 1;
  0, 1, 7, 10, 5, 1;
  0, 0, 6, 16, 15, 6, 1;
  0, 0, 3, 19, 30, 21, 7, 1;
  0, 0, 1, 16, 45, 50, 28, 8, 1;
  0, 0, 0, 10, 51, 90, 77, 36, 9, 1;
  0, 0, 0, 4, 45, 126, 161, 112, 45, 10, 1;
  0, 0, 0, 1, 30, 141, 266, 266, 156, 55, 11, 1;

Clark Kimberling, Binary words with restricted repetitions and associated compositions of integers, in Applications of Fibonacci Numbers, vol.10, Proceedings of the Eleventh International Conference on Fibonacci Numbers and Their Applications, William Webb, editor, Congressus Numerantium, Winnipeg, Manitoba 194 (2009) 141-151.

Alois P. Heinz, Rows n = 1..141, flattened
Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 18.
Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.

Cf. A027907, A078802, A030528 (parts <=2), A213887 (parts <=4), A213888 (parts <=5), A061676 and A213889 (parts <=6).

A078803 := proc(n,k) add( binomial(j,n-3*k+2*j)*binomial(k,j),j=0..k) ; end proc:
# R. J. Mathar, Feb 22 2011

nn=8;CoefficientList[Series[1/(1-y(x+x^2+x^3)),{x,0,nn}],{x,y}]//Grid (* Geoffrey Critzer, Jan 08 2013 *)

T(n, k) = t(n-1, n-k), for 1<=k<=n, for n>=1, where the array t is given by A078802.
G.f.: 1/(1-t*z*(1+z+z^2))-1. - Emeric Deutsch, Mar 10 2004
T(n,k) = Sum_{j=0..k} C(j,n-3*k+2*j)*C(k,j). - Vladimir Kruchinin, Feb 10 2011

More terms from Emeric Deutsch, Jun 16 2007

A082601 Tribonacci array: to get the next row, right-adjust the previous 3 rows and add them, then append a final 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 0, 0, 1, 4, 6, 2, 0, 0, 1, 5, 10, 7, 1, 0, 0, 1, 6, 15, 16, 6, 0, 0, 0, 1, 7, 21, 30, 19, 3, 0, 0, 0, 1, 8, 28, 50, 45, 16, 1, 0, 0, 0, 1, 9, 36, 77, 90, 51, 10, 0, 0, 0, 0, 1, 10, 45, 112, 161, 126, 45, 4, 0, 0, 0, 0, 1, 11, 55, 156, 266, 266, 141, 30, 1, 0

Offset: 0

Gary W. Adamson, May 24 2003

Coefficients of tribonacci polynomials: t_0 = 1, t_1 = x, t_2 = x^2 + x, t_n = x*(t_{n-1} + t_{n-2} + t_{n-3}).
Row sums are tribonacci numbers.
From Petros Hadjicostas, Jun 10 2020: (Start)
To prove a Swamy inequality for the above tribonacci polynomials, we use Guilfoyle's (1967) technique. We write t_n as the determinant of an n X n matrix and then apply Hadamard's inequality.
Since x*t_{n-3} + x*t_{n-2} + x*t_{n-1} - t_n = 0 (with the above initial conditions), we may prove that for n >= 3, t_n = det(A_n), where A_n is the n X n matrix A_n = [[x,-1,0,0,0,...,0,0,0,0,0], [x,x,-1,0,0,...,0,0,0,0,0], [x,x,x,-1,0,...,0,0,0,0,0], [0,x,x,x,-1,...,0,0,0,0,0], ..., [0,0,0,0,0,...,x,x,x,-1,0], [0,0,0,0,0,...,0,x,x,x,-1], [0,0,0,0,0,...,0,0,x,x,x]]).
Using Hadamard's inequality, we obtain t_n^2 <= 3*x^2*(2*x^2 + 1)*(x^2 + 1)*(3*x^2 + 1)^(n-3) for all integers n >= 3 and all real x. (Of course, it is not true for n = 0, 1, 2.)
Guilfoyle's technique can be applied for Werner Schulte's polynomial sequence below, i.e., for p^2*U(n) + p*q*U(n+1) + q^2*U(n+2) - U(n+3) = 0. The first three rows and first three columns of the matrix A_n depend on the initial conditions. We omit the details. (End)

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
  1;
  1,  0;
  1,  1,  0;
  1,  2,  1,  0;
  1,  3,  3,  0,  0;
  1,  4,  6,  2,  0,  0;
  1,  5, 10,  7,  1,  0,  0;
  ...
From _Petros Hadjicostas_, Jun 10 2020: (Start)
The n-th tribonacci polynomial is t_n = Sum_{k=0..n} T(n,k)*x^(n-k), so, for example:
t_4 = x^4 + 3*x^3 + 3*x^2;
t_5 = x^5 + 4*x^4 + 6*x^3 + 2*x^2;
t_6 = x^6 + 5*x^5 + 10*x^4 + 7*x^3 + x^2;
t_7 = x^7 + 6*x^6 + 15*x^5 + 16*x^4 + 6*x^3.
We have
t_4 = det([[x,-1,0,0]; [x,x,-1,0]; [x,x,x,-1]; [0,x,x,x]]);
t_5 = det([[x,-1,0,0,0]; [x,x,-1,0,0]; [x,x,x,-1,0]; [0,x,x,x,-1]; [0,0,x,x,x]]);
t_6 = det([[x,-1,0,0,0,0]; [x,x,-1,0,0,0]; [x,x,x,-1,0,0]; [0,x,x,x,-1,0]; [0,0,x,x,x,-1]; [0,0,0,x,x,x]]);
t_7 = det([[x,-1,0,0,0,0,0]; [x,x,-1,0,0,0,0]; [x,x,x,-1,0,0,0]; [0,x,x,x,-1,0,0]; [0,0,x,x,x,-1,0]; [0,0,0,x,x,x,-1]; [0,0,0,0,x,x,x]]). (End)

Thomas Koshy, Fibonacci and Lucas numbers with Applications, Vol. 2, Wiley, 2019; see p. 33. [He gives Swamy inequalities for the Fibonacci and the Lucas polynomials. Vol. 1 was published in 2001. - Petros Hadjicostas, Jun 10 2020]

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
Richard Guilfoyle, Comment to the solution of Problem E1846, Amer. Math. Monthly, 74(5), 1967, 593.
Thomas Koshy, Fibonacci and Lucas Numbers with Applications, Wiley, 2001; Chapter 47: Tribonacci Polynomials: ("In 1973, V.E. Hoggatt, Jr. and M. Bicknell generalized Fibonacci polynomials to Tribonacci polynomials tx(x)"); Table 47.1, page 534: "Tribonacci Array".
M. N. S. Swamy and R. E. Giudici, Solution to Problem E1846, Amer. Math. Monthly, 74(5), 1967, 592-593.
Wikipedia, Hadamard's inequality.

Closely related to A078802. A better version of A082870. Cf. A000073.

Cf. A002426 (central terms).

a082601 n k = a082601_tabl !! n !! k
a082601_row n = a082601_tabl !! n
a082601_tabl = [1] : [1,0] : [1,1,0] : f [0,0,1] [0,1,0] [1,1,0]
   where f us vs ws = ys : f (0:vs) (0:ws) ys where
                      ys = zipWith3 (((+) .) . (+)) us vs ws ++ [0]
-- Reinhard Zumkeller, Apr 13 2014

G:=x*y/(1-x-x^2*y-x^3*y^2): Gs:=simplify(series(G,x=0,18)): for n from 1 to 16 do P[n]:=sort(coeff(Gs,x^n)) od: seq(seq(coeff(P[i],y^j),j=1..i),i=1..16);

Table[SeriesCoefficient[x/(1 - x - x^2*y - x^3*y^2), {x, 0, n}, {y, 0, k}], {n, 13}, {k, 0, n - 1}] // Flatten (* Michael De Vlieger, Feb 22 2017 *)

G.f.: x/(1 - x - x^2*y - x^3*y^2). - Vladeta Jovovic, May 30 2003
From Werner Schulte, Feb 22 2017: (Start)
T(n,k) = Sum_{j=0..floor(k/2)} binomial(k-j,j)*binomial(n-k,k-j) for 0 <= k and k <= floor(2*n/3) with binomial(i,j) = 0 for iDennis P. Walsh at A078802).
Based on two integers p and q define the integer sequence U(n) by U(0) = 0 and U(1) = 0 and U(n+2) = Sum_{k=0..floor(2*n/3)} T(n,k)*p^k*q^(2*n-3*k) for n >= 0. That yields the g.f. f(p,q,x) = x^2/(1 - q^2*x - p*q*x^2 - p^2*x^3) and the recurrence U(n+3) = q^2*U(n+2) + p*q*U(n+1) + p^2*U(n) for n >= 0 with initial values U(0) = U(1) = 0 and U(2) = 1. For p = q = +/-1, you'll get tribonacci numbers A000073. For p = -1 and q = 1, you'll get A021913. (End)

Edited by Anne Donovan and N. J. A. Sloane, May 27 2003

More terms from Emeric Deutsch, May 06 2004

A082870 Tribonacci array.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 4, 6, 2, 1, 5, 10, 7, 1, 1, 6, 15, 16, 6, 1, 7, 21, 30, 19, 3, 1, 8, 28, 50, 45, 16, 1, 1, 9, 36, 77, 90, 51, 10, 1, 10, 45, 112, 161, 126, 45, 4, 1, 11, 55, 156, 266, 266, 141, 30, 1, 1, 12, 66, 210, 414, 504, 357, 126, 15, 1, 13, 78, 275, 615, 882

Offset: 0

Gary W. Adamson, May 24 2003

Row sums are tribonacci numbers.
From Gary W. Adamson, Nov 15 2016: (Start)
With an alternative format:
1, 0, 0, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, 0, ...
1, 2, 3, 2, 1, 0, 0, ...
1, 3, 6, 7, 6, 3, 1, ...
... (where the k-th row is (1 + x + x^2)^k), let q(x) = (r(x) * r(x^3) * r(x^9) * r(x^27) * ...). Then q(x) is the binomial sequence beginning (1, k, ...). Example: (1, 3, 6, 10, ...) = q(x) with r(x) = (1, 3, 6, 7, 3, 1, 0, 0, 0). (End)

			Triangle begins:
  1,
  1,
  1,  1,
  1,  2,  1,
  1,  3,  3,
  1,  4,  6,  2,
  1,  5, 10,  7,  1,
  1,  6, 15, 16,  6,

Thomas Koshy, <"Fibonacci and Lucas Numbers with Applications">, Wiley, 2001; Chapter 47: Tribonacci Polynomials: ("In 1973, V.E. Hoggat, Jr. and M. Bicknell generalized Fibonacci polynomials to Tribonacci polynomials tx(x)"); Table 47.1, page 534: "Tribonacci Array".

Reinhard Zumkeller, Rows n = 0..150 of triangle, flattened

A082601 is a better version. Cf. A000073, A078802.

Cf. A004396 (row lengths).

a082870 n k = a082870_tabf !! n !! k
a082870_row n = a082870_tabf !! n
a082870_tabf = map (takeWhile (> 0)) a082601_tabl
-- Reinhard Zumkeller, Apr 13 2014

G.f.: x/(1 - x - x^2*y - x^3*y^2). - Vladeta Jovovic, May 30 2003

More terms from Vladeta Jovovic, May 30 2003

cp's OEIS Frontend

A078803 Triangular array T given by T(n,k) = number of compositions of n into k parts, each in the set {1,2,3}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A082601 Tribonacci array: to get the next row, right-adjust the previous 3 rows and add them, then append a final 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A082870 Tribonacci array.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Formula

Extensions