A005718 -id:A005718 - cp's OEIS frontend

A071675 Array read by antidiagonals of trinomial coefficients.

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

Offset: 0

Henry Bottomley, May 30 2002

Read as a number triangle, this is the Riordan array (1, x(1+x+x^2)) with T(n,k) = Sum_{i=0..floor((n+k)/2)} C(k,2i+2k-n)*C(2i+2k-n,i). Rows start {1}, {0,1}, {0,1,1}, {0,1,2,1}, {0,0,3,3,1},... Row sums are then the trinomial numbers A000073(n+2). Diagonal sums are A013979. - Paul Barry, Feb 15 2005

Let {a_(k,i)}, k>=1, i=0,...,k, be the k-th antidiagonal of the array. Then s_k(n)=sum{i=0,...,k}a_(k,i)* binomial(n,k) is the n-th element of the k-th column of A213742. For example, s_1(n)=binomial(n,1)=n is the first column of A213742 for n>1, s_2(n)=binomial(n,1)+binomial(n,2)is the second column of A213742 for n>1, etc. In particular (see comment in A213742) in cases k=4,5,6,7,8, s_k(n) is A005718(n+2), A005719(n), A005720(n), A001919(n), A064055(n+3), respectively. - Vladimir Shevelev and Peter J. C. Moses, Jun 22 2012

			Rows start
1, 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, 0, ...;
1, 4, 10, 16, 19, 16, 10, 4, 1, ...; etc.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3

Visible version of A027907. Row sums are 3^n, i.e. A000244. Central diagonal is A002426. Cf. A071676 for a slight variation.

T[n_, k_] := Sum[Binomial[n - k - j, j]*Binomial[k, n - k - j], {j, 0,
Floor[(n - k)/2]}]; Table[T[n, k], {n,0,10}, {k,0,n}] // Flatten (* G. C. Greubel, Feb 28 2017 *)

T(n, k) = T(n-1, k) + T(n-1, k-1) + T(n-1, k-2) starting with T(0, 0)=1. See A027907 for more.

As a number triangle, T(n, k) = Sum_{i=0..floor((n-k)/2)} C(n-k-i, i) * C(k, n-k-i). - Paul Barry, Apr 26 2005

A062745 Generalized Catalan array FS(3; n,r).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 3, 3, 1, 3, 6, 9, 12, 12, 12, 1, 4, 10, 19, 31, 43, 55, 55, 55, 1, 5, 15, 34, 65, 108, 163, 218, 273, 273, 273, 1, 6, 21, 55, 120, 228, 391, 609, 882, 1155, 1428, 1428, 1428, 1, 7, 28, 83, 203, 431, 822, 1431, 2313, 3468, 4896, 6324, 7752, 7752

Offset: 0

Wolfdieter Lang, Jul 12 2001

In the Frey-Sellers reference this array appears in Table 2, p. 143 and is called {n over r}_{m-1}, with m=3.
The step width sequence of this staircase array is [1,2,2,2,....], i.e., the degree of the row polynomials is [0,2,4,6,...] = A005843.
The columns r=0..5 give A000012 (powers of 1), A000027 (natural), A000217 (triangular), A062748, A005718, A062749.
Number of lattice paths from (0,0) to (r,n) using steps h=(1,0), v=(0,1) and staying on or above the line y = x/2. Example: a(3,2)=6 because from (0,0) to (2,3) we have the following valid paths: vvvhh, vvhvh, vvhhv, vhvvh, vhvhvh and vhvvh (see the Niederhausen reference). - Emeric Deutsch, Jun 24 2005

			Array begins:
  {1};
  {1,1,1};
  {1,2,3,3,3};
  {1,3,6,9,12,12,12};
  ...;
N(3; 1,x) = 3-3*x+x^2.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
D. D. Frey and J. A. Sellers, Generalizing Bailey's generalization of the Catalan numbers, The Fibonacci Quarterly, 39 (2001) 142-148.
Wolfdieter Lang, First 10 rows.
Toufik Mansour and I. L. Ramirez, Enumerations of polyominoes determined by Fuss-Catalan words, Australas. J. Combin. 81 (3) (2021) 447-457.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (Table 2).
Heinrich Niederhausen, Catalan Traffic at the Beach, Electronic Journal of Combinatorics, Volume 9 (2002), #R33.

Cf. A009766, A280759 (rows reversed).
Cf. A062746, A062747, A062748, A062749.
Cf. A005843, A000012, A000027, A000217, A005718.

a:=proc(n,r) if r<=2*n then binomial(n+r,r)-(-1)^(r-1)*sum(binomial(3*i,i)*binomial(i-n-1,r-1-2*i)/(2*i+1),i=0..floor((r-1)/2)) else 0 fi end: for n from 0 to 8 do seq(a(n,r),r=0..2*n) od; # yields sequence in triangular form # Emeric Deutsch, Jun 24 2005

a[0, 0] = 1; a[, -1] = 0; a[n, r_] /; r > 2*n = 0; a[n_, r_] := a[n, r] = a[n, r-1] + a[n-1, r]; Table[a[n, r], {n, 0, 7}, {r, 0, 2*n}] // Flatten (* Jean-François Alcover, Jun 21 2013 *)

a(0,0)=1, a(n,-1)=0, n >= 1; a(n,r) = a(n, r-1) + a(n-1, r) if r <= 2n, 0 otherwise.
G.f. for column r = 2*k+j, k >= 0, j=1, 2: (x^(k+1))*N(3; k, x)/ (1-x)^(2*k+1+j), with row polynomials N(3; k, x) of array A062746; for column r=0: 1/(1-x).
a(n,r) = binomial(n+r, r) - (-1)^(r-1)*Sum_{i=0..floor((r-1)/2)} binomial(3i, i)*binomial(i-n-1, r-1-2i)/(2i+1), 0 <= r <= 2n (see the Niederhausen reference, eq. (17)). - Emeric Deutsch, Jun 24 2005

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003

A213742 Triangle of numbers C^(3)(n,k) of combinations with repetitions from n different elements over k for each of them not more than three appearances allowed.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 6, 10, 1, 4, 10, 20, 31, 1, 5, 15, 35, 65, 101, 1, 6, 21, 56, 120, 216, 336, 1, 7, 28, 84, 203, 413, 728, 1128, 1, 8, 36, 120, 322, 728, 1428, 2472, 3823, 1, 9, 45, 165, 486, 1206, 2598, 4950, 8451, 13051, 1, 10

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Jun 19 2012

The left side of triangle consists of 1's, while the right side is formed by A005725. Further, T(n,0)=1, T(n,1)=n, T(n,2)=A000217(n) for n>1, T(n,3)=A000292(n) for n>=3, T(n,4)=A005718(n) for n>=2, T(n,5)=A005719(n) for n>=5, T(n,6)=A005720(n) for n>=6, T(n,7)=A001919(n) for n>=7, T(n,8)=A064055(n) for n>=5.

			Triangle begins
n/k.|..0.....1.....2.....3.....4.....5.....6.....7
==================================================
.0..|..1
.1..|..1.....1
.2..|..1.....2.....3
.3..|..1.....3.....6....10
.4..|..1.....4....10....20....31
.5..|..1.....5....15....35....65....101
.6..|..1.....6....21....56...120....216...336
.7..|..1.....7....28....84...203....413...728....1128

Peter J. C. Moses, Rows n = 0..50 of triangle, flattened

Cf. A007318, A005725, A111808, A000217, A000292, A005718, A005719, A005720, A001919, A064055.

Flatten[Table[Sum[(-1)^r Binomial[n,r] Binomial[n-# r+k-1,n-1],{r,0,Floor[k/#]}],{n,0,15},{k,0,n}]/.{0}->{1}]&[4] (* Peter J. C. Moses, Apr 16 2013 *)

C^(3)(n,k)=sum{r=0,...,floor(k/4)}(-1)^r*C(n,r)*C(n-4*r+k-1, n-1)

A213548 Rectangular array: (row n) = bc, where b(h) = h, c(h) = m(m+1)/2, m = n-1+h, n>=1, h>=1, and = convolution.

Original entry on oeis.org

1, 5, 3, 15, 12, 6, 35, 31, 22, 10, 70, 65, 53, 35, 15, 126, 120, 105, 81, 51, 21, 210, 203, 185, 155, 115, 70, 28, 330, 322, 301, 265, 215, 155, 92, 36, 495, 486, 462, 420, 360, 285, 201, 117, 45, 715, 705, 678, 630, 560, 470, 365, 253, 145, 55, 1001

Offset: 1

Clark Kimberling, Jun 16 2012

Principal diagonal: A213549.
Antidiagonal sums: A051836.
Row 1, (1,2,3,...)**(1,3,6,...): A000332.
Row 2, (1,2,3,...)**(3,6,10,...): A005718.
Row 3, (1,2,3,...)**(6,10,15,...): k*(k+1)*(k^2 + 13*k + 58)/24.
For a guide to related arrays, see A213500.

			Northwest corner (the array is read by falling antidiagonals):
.  1,  5,  15,  35,  70, ...
.  3, 12,  31,  65, 120, ...
.  6, 22,  53, 105, 185, ...
. 10, 35,  81, 155, 265, ...
. 15, 51, 115, 215, 360, ...
. 21, 70, 155, 285, 470, ...
...
T(5,1) = (1)**(15) = 15;
T(5,2) = (1,2)**(15,21) = 1*21 + 2*15 = 51;
T(5,3) = (1,2,3)**(15,21,28) = 1*28 + 2*21 + 3*15 = 115;
T(4,4) = (1,2,3,4)**(10,15,21,28) = 1*28 + 2*21 + 3*15 + 4*10 = 155.

Clark Kimberling, Antidiagonals n = 1..60

Cf. A213500.

b[n_] := n; c[n_] := n (n + 1)/2
t[n_, k_] := Sum[b[k - i] c[n + i], {i, 0, k - 1}]
TableForm[Table[t[n, k], {n, 1, 10}, {k, 1, 10}]]
Flatten[Table[t[n - k + 1, k], {n, 12}, {k, n, 1, -1}]]
r[n_] := Table[t[n, k], {k, 1, 60}]  (* A213548 *)
d = Table[t[n, n], {n, 1, 40}] (* A213549 *)
s[n_] := Sum[t[i, n + 1 - i], {i, 1, n}]
s1 = Table[s[n], {n, 1, 50}] (* A051836 *)

T(n,k) = 5*T(n,k-1) - 10*T(n,k-2) + 10*T(n,k-3) - 5*T(n,k-4) + T(n,k-5).

G.f. for row n: f(x)/g(x), where f(x) = n*(n+1) - 2*((n-1)^2)*x + n*(n-1)*x^2 and g(x) = 2*(1 - x)^5.

A180118 a(n) = Sum_{k=1..n} (k+2)!/k! = Sum_{k=1..n} (k+2)*(k+1).

Original entry on oeis.org

0, 6, 18, 38, 68, 110, 166, 238, 328, 438, 570, 726, 908, 1118, 1358, 1630, 1936, 2278, 2658, 3078, 3540, 4046, 4598, 5198, 5848, 6550, 7306, 8118, 8988, 9918, 10910, 11966, 13088, 14278, 15538, 16870, 18276, 19758, 21318, 22958, 24680, 26486, 28378, 30358

Offset: 0

Gary Detlefs, Aug 10 2010

In general, sequences of the form a(n) = sum((k+x+2)!/(k+x)!,k=1..n) have a closed form a(n) = n*(11+12*x+3*x^2+3*x*n+6*n+n^2)/3.
This sequence is related to A033487 by A033487(n) = n*a(n)-sum(a(i), i=0..n-1). - Bruno Berselli, Jan 24 2011
The minimal number of multiplications (using schoolbook method) needed to compute the matrix chain product of a sequence of n+1 matrices having dimensions 1 X 2, 2 X 3, ..., (n+1) X (n+2), respectively. - Alois P. Heinz, Jan 27 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
B. Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
Wikipedia, Matrix chain multiplication
Wikipedia, Schoolbook matrix multiplication
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A005718, A033487, A050534.

[n*(n^2+6*n+11)/3: n in [0..45]]; // Vincenzo Librandi, Jun 15 2011

f[n_]:=n*(n^2 + 6 n + 11)/3; f[Range[0,60]] (* Vladimir Joseph Stephan Orlovsky, Feb 10 2011*)
CoefficientList[Series[2*x*(3 - 3*x + x^2)/(1 - x)^4, {x, 0, 50}], x] (* Vaclav Kotesovec, May 10 2019 *)
Table[Sum[(k+1)(k+2),{k,n}],{n,0,50}] (* or *) LinearRecurrence[{4,-6,4,-1},{0,6,18,38},50] (* Harvey P. Dale, Apr 21 2020 *)

a(n) = +4*a(n-1)-6*a(n-2)+4*a(n-3)-1*a(n-4) for n>=4.
a(n) = n*(n^2+6*n+11)/3.
From Bruno Berselli, Jan 24 2011:  (Start)
G.f.: 2*x*(3-3*x+x^2)/(1-x)^4. [corrected by Georg Fischer, May 10 2019]
Sum(a(k), k=0..n) = 2*A005718(n) for n>0. (End)

A363256 Number of length n strings on the alphabet {0,1,2,3} with digit sum at most 4.

Original entry on oeis.org

1, 4, 13, 32, 66, 121, 204, 323, 487, 706, 991, 1354, 1808, 2367, 3046, 3861, 4829, 5968, 7297, 8836, 10606, 12629, 14928, 17527, 20451, 23726, 27379, 31438, 35932, 40891, 46346, 52329, 58873, 66012, 73781, 82216, 91354, 101233, 111892, 123371, 135711

Offset: 0

Daniel T. Martin, May 23 2023

			For n=2, the 13 strings are all possible 2-character strings of '0', '1', '2' and '3' except the four strings '33', '32', '23'.

Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A227259 (the same for {0,1,2} with digit sum <= 4).
Cf. A105163 (the same for {0,1,2} with digit sum <= 3, shifted by 2).
Cf. A005718.

f[n_, r_, l_] := If[r < 0, 0, If[r==0, 1, If[l < 0, 0, If[l == 0, 1, Sum[f[n, r-j, l-1], {j, 0, n}]]]]]; Table[f[3, 4,x], {x, 0, 40}]

a(n) = (((n + 10)*n + 35)*n + 26)*n/24 + 1.
G.f.: -(x^4 - 3*x^3 + 3*x^2 - x + 1)/(x - 1)^5.
a(n) = 1 + A005718(n-1) for n>=1.

cp's OEIS Frontend

A071675 Array read by antidiagonals of trinomial coefficients.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A062745 Generalized Catalan array FS(3; n,r).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A213742 Triangle of numbers C^(3)(n,k) of combinations with repetitions from n different elements over k for each of them not more than three appearances allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A213548 Rectangular array: (row n) = b**c, where b(h) = h, c(h) = m(m+1)/2, m = n-1+h, n>=1, h>=1, and ** = convolution.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A180118 a(n) = Sum_{k=1..n} (k+2)!/k! = Sum_{k=1..n} (k+2)*(k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A363256 Number of length n strings on the alphabet {0,1,2,3} with digit sum at most 4.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A213548 Rectangular array: (row n) = bc, where b(h) = h, c(h) = m(m+1)/2, m = n-1+h, n>=1, h>=1, and = convolution.