A077028 The rascal triangle, read by rows: T(n,k) (n >= 0, 0 <= k <= n) = k(n-k) + 1.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 4, 1, 1, 5, 7, 7, 5, 1, 1, 6, 9, 10, 9, 6, 1, 1, 7, 11, 13, 13, 11, 7, 1, 1, 8, 13, 16, 17, 16, 13, 8, 1, 1, 9, 15, 19, 21, 21, 19, 15, 9, 1, 1, 10, 17, 22, 25, 26, 25, 22, 17, 10, 1, 1, 11, 19, 25, 29, 31, 31, 29, 25, 19, 11, 1, 1, 12, 21, 28, 33, 36, 37, 36, 33, 28, 21, 12, 1

Offset

0,5

Comments

Pascal's triangle is formed using the rule South = West + East, whereas the rascal triangle uses the rule South = (West*East+1)/North. [Anggoro et al.]

The n-th diagonal is congruent to 1 mod n-1.

Row sums are the cake numbers, A000125. Alternating sum of row n is 0 if n even and (3-n)/2 if n odd. Rows are symmetric, beginning and ending with 1. The number of occurrences of k in this triangle is the number of divisors of k-1, given by A000005.

The triangle can be generated by numbers of the form k*(n-k) + 1 for k = 0 to n. Conjecture: except for n = 0,1 and 6 every row contains a prime. - Amarnath Murthy, Jul 15 2005

Above conjecture needs more exceptions, rows 30 and 54 do not contain primes. - Alois P. Heinz, Aug 31 2017

From Moshe Shmuel Newman, Apr 06 2008: (Start)

Consider the semigroup of words in x,y,q subject to the relationships: yx = xyq, qx = xq, qy = yq.

Now take words of length n in x and y, with exactly k y's. If there had been no relationships, the number of different words of this type would be n choose k, sequence A007318. Thanks to the relationships, the number of words of this type is the k-th entry in the n-th row of this sequence (read as a triangle, with the first row indexed by zero and likewise the first entry in each row.)

For example: with three letters and one y, we have three possibilities: xxy, xyx = xxyq, yxx = xxyqq. No two of them are equal, so this entry is still 3, as in Pascal's triangle.

With four letters, two y's, we have the first reduction: xyyx = yxxy = xxyyqq and this is the only reduction for 4 letters. So the middle entry of the fourth row is 5 instead of 6, as in the Pascal triangle. (End)

Main diagonals of this triangle sum to polygonal numbers. See A057145. - Raphie Frank, Oct 30 2012

T(n,k) gives the number of distinct sums of k elements in {1,2,...,n}, e.g., T(5,4) = the number of distinct sums of 4 elements in {1,2,3,4,5}, which is (5+4+3+2) - (4+3+2+1) + 1 = 5. - Derek Orr, Nov 26 2014

Conjecture: excluding the starting and ending 1's in each row, those that contain only prime numbers are n = 2, 3, 5, 7, 13, and 17. Tested up to row 10^9. - Rogério Serôdio, Sep 20 2017

The rascal triangle also uses the rule South = (West+East+1)-North. [Abstracts of AMS, Winter 2019, p. 526, 1145-VS-280, refers to Julian Fleron] - Michael Somos, Jan 12 2019

As a square array read by antidiagonals, selecting terms that give a remainder of 1 when divided by a prime gives evenly sized squares. For example, when each term is divided by 2, showing the remainder looks like:

1 1 1 1 1

1 0 1 0 1

1 1 1 1 1

1 0 1 0 1

1 1 1 1 1 - Nathaniel J. Strout, Jan 01 2020

T(n,k) is the number of binary words of length n which contain exactly k 1s and have at most 1 ascent. T(n,k) is also the number of ascent sequences avoiding 001 and 210 with length n+1 and exactly k ascents. - Amelia Gibbs, May 21 2024

Links

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows 0 <= n <= 150, flattened).

A. Anggoro, E. Liu and A. Tulloch, The Rascal Triangle, College Math. J., Vol. 41, No. 5, Nov. 2010, pp. 393-395.

D. C. Fielder & C. O. Alford, An investigation of sequences derived from Hoggatt Sums and Hoggatt Triangles, Application of Fibonacci Numbers, 3 (1990) 77-88. Proceedings of 'The Third Annual Conference on Fibonacci Numbers and Their Applications,' Pisa, Italy, July 25-29, 1988. (Annotated scanned copy)

Julian Fleron, Tackling Rascals’ Triangle - How Inquiry Challenges What We Know and How We Know It, Discovering the Art of Mathematics, December 15 2015.

Amelia Gibbs and Brian K. Miceli, Two Combinatorial Interpretations of Rascal Numbers, arXiv:2405.11045 [math.CO], 2024.

Zachary Hoelscher and Eyvindur Ari Palsson, Counting Restricted Partitions of Integers into Fractions: Symmetry and Modes of the Generating Function and a Connection to omega(t), arXiv:2011.14502 [math.NT], 2020.

Brian Hopkins, Editorial: Anonymity and Youth, The College Mathematics Journal, 45 (Number 2, 2014), 82. - From N. J. A. Sloane, Apr 05 2014

Philip K. Hotchkiss, Generalized Rascal Triangles, arXiv:1907.11159 [math.HO], 2019.

Philip K. Hotchkiss, Student Inquiry and the Rascal Triangle, arXiv:1907.07749 [math.HO], 2019.

Iva Kodrnja and Helena Koncul, Number of Polynomials Vanishing on a Basis of S_m(Gamma_0(N)), arXiv:2405.10747 [math.NT], 2024. See p. 10.

L. McHugh, CMJ Article Shows Collaboration Is Not Limited by Geography ... or Age, MAA Focus (Magazine), Vol. 31, No. 1, 2011, p. 13.

Franck Ramaharo, A generating polynomial for the two-bridge knot with Conway's notation C(n,r), arXiv:1902.08989 [math.CO], 2019.

Formula

As a square array read by antidiagonals, a(n, k) = 1 + n*k. a(n, k) = a(n-1, k) + k. Row n has g.f. (1+(n-1)x)/(1-x)^2, n >= 0. - Paul Barry, Feb 22 2003

Still thinking of square arrays. Let f:N->Z and g:N->Z be given and I an integer, then define a(n, k) = I + f(n)*g(k). Then a(n, k)*a(n-1, k-1) = a(n-1, k)*a(n, k-1) + I*(f(n) - f(n-1))*(g(k) - g(k-1)) for suitable n and k. S= (E*W + 1)/N. arises with I = 1, and f = g = id. - Terry Lindgren, Apr 10 2011

Using the above: Having just read J. Fleron's nice article in Discovering the Art of Mathematics on the rascal triangle, it is neat to note and straightforward to show that when I = 1, a(n, k) + a(n-1, k-1) = a(n-1, k) + a(n, k-1) + (f(n) - f(n-1))*(g(k) - g(k-1)), so with I = 1, and f = g = id, we have S+N = E+W + 1, as his students discovered. - Terry Lindgren, Nov 28 2016

T(n, k) = A128139(n-1, k-1). - Gary W. Adamson, Jul 02 2012

O.g.f. (1 - x*(1 + t) + 2*t*x^2)/((1 - x)^2*(1 - t*x)^2) = 1 + (1 + t)*x + (1 + 2*t + t^2)*x^2 + .... Cf. A105851. - Peter Bala, Jul 26 2015

T(n, k) = 0 if n < k, T(n, 0) = 1, T(n,n) = 1, for n >= 0, and T(n, k) = (T(n-1, k-1)*T(n-1, k) + 1)/(T(n-2, k-1)) for 0 < k < n. See the first comment referring to the triangle with its apex in the middle. - Wolfdieter Lang, Dec 19 2017

Example

Third diagonal (1,3,5,7,...) consists of the positive integers congruent to 1 mod 2.
The triangle T(n, k) begins:
n\k  0  1  2  3  4  5  6  7  8  9 10 ...
0:   1
1:   1  1
2:   1  2  1
3:   1  3  3  1
4:   1  4  5  4  1
5:   1  5  7  7  5  1
6:   1  6  9 10  9  6  1
7:   1  7 11 13 13 11  7  1
8:   1  8 13 16 17 16 13  8  1
9:   1  9 15 19 21 21 19 15  9  1
10:  1 10 17 22 25 26 25 22 17 10  1
... reformatted. - Wolfdieter Lang, Dec 19 2017
As a square array read by antidiagonals, the first rows are:
  1,  1,  1,  1,  1,  1, ...
  1,  2,  3,  4,  5,  6, ...
  1,  3,  5,  7,  9, 11, ...
  1,  4,  7, 10, 13, 16, ...
  1,  5,  9, 13, 17, 21, ...

Maple

A077028 := proc(n, k)
   if n <0 or k<0 or k > n then
       0;
   else
       k*(n-k)+1 ;
   end if;
end proc: # R. J. Mathar, Jul 28 2016

Mathematica

t[n_, k_] := k (n - k) + 1; t[0, 0] = 1; Table[ t[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Robert G. Wilson v, Jul 06 2012 *)

Prog

(PARI) {T(n, k) = if( k<0 || k>n, 0, k * (n - k) + 1)}; /* Michael Somos, Mar 20 2011 */

Crossrefs

Cf. A000125, A003991, A077029, A105851.

The maximum value for each antidiagonal is given by sequence A033638.

Equals A004247(n) + 1.

Keyword

nonn,tabl

Author

Clark Kimberling, Oct 19 2002

Extensions

Better definition based on Murthy's comment of Jul 15 2005 and the Anggoro et al. paper. - N. J. A. Sloane, Mar 05 2011

Status

approved

A134394 Triangle T(n,k) = Sum_{j=k..n} A077028(j,k), read by rows.

1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 9, 5, 1, 6, 15, 16, 12, 6, 1, 7, 21, 25, 22, 15, 7, 1, 8, 28, 36, 35, 28, 18, 8, 1, 9, 36, 49, 51, 45, 34, 21, 9, 1, 10, 45, 64, 70, 66, 55, 40, 24, 10, 1, 11, 55, 81, 92, 91, 81, 65, 46, 27, 11, 1, 12, 66, 100, 117, 120, 112, 96, 75, 52, 30, 12, 1, 13, 78, 121, 145, 153

Offset

1,2

Comments

Row sums = A055795: (1, 3, 7, 15, 30, 56, 98, ...).

Antidiagonal reading of A139600 without its left column. - R. J. Mathar, Apr 17 2011

Links

Table of n, a(n) for n=1..83.

Formula

A000012 * A077028 as infinite lower triangular matrices.

T(n,k) = (k-n-1)*(k*(k-n)-2)/2. - R. J. Mathar, Apr 17 2011

Example

First few rows of the triangle:
  1;
  2,  1;
  3,  3,  1;
  4,  6,  4,  1;
  5, 10,  9,  5,  1;
  6, 15, 16, 12,  6,  1;
  7, 21, 25, 22, 15,  7,  1;

Maple

A077028 := proc(n, k) if n < 0 or k<0 or k > n then 0; else k*(n-k)+1 ; end if; end proc:
A134394 := proc(n, k) add ( A077028(j, k), j=k..n) ; end proc:
seq(seq(A134394(n, k), k=0..n), n=0..15) ; # R. J. Mathar, Apr 17 2011

Crossrefs

Cf. A077028, A055795, A139600.

Keyword

nonn,tabl

Author

Gary W. Adamson, Oct 23 2007

Status

approved

A134395 A007318 * A077028.

1, 2, 1, 4, 4, 1, 8, 12, 6, 1, 16, 32, 23, 8, 1, 32, 80, 72, 37, 10, 1, 64, 192, 201, 132, 54, 12, 1, 128, 448, 522, 405, 216, 74, 14, 1, 256, 1024, 1291, 1128, 723, 328, 97, 16, 1, 512, 2304, 3084, 2941, 2154, 1191, 472, 123, 18, 1, 1024, 5120, 7181, 7316, 5920, 3788, 1850, 652, 152, 20, 1

Offset

0,2

Comments

Row sums = A134396: (1, 3, 9, 27, 80, 232, 656, ...).

Links

Table of n, a(n) for n=0..65.

Formula

A007318 * A077028 as infinite lower triangular matrices.

Example

First few rows of the triangle:
   1;
   2,  1;
   4,  4,  1;
   8, 12,  6,  1;
  16, 32, 23,  8,  1;
  32, 80, 72, 37, 10,  1;
  ...

Maple

A007318 := proc(n, k) binomial(n, k) ; end: A077028 := proc(i, j) if j <= i then (i-j)*(j-1)+1 ; else 0 ; fi ; end: A134395 := proc(n, m) add(A007318(n, k)*A077028(k+1, m+1), k=0..n) ; end: for n from 0 to 15 do for m from 0 to n do printf("%d, ", A134395(n, m)) ; od: od: # R. J. Mathar, Jun 08 2008

Crossrefs

Cf. A077028, A134396.

Keyword

nonn,tabl

Author

Gary W. Adamson, Oct 23 2007

Extensions

Corrected and extended by R. J. Mathar, Jun 08 2008

Status

approved

A110552 A triangular array related to A077028 and distributing the values of A007582.

1, 1, 2, 1, 5, 4, 1, 10, 17, 8, 1, 19, 51, 49, 16, 1, 36, 134, 196, 129, 32, 1, 69, 330, 650, 645, 321, 64, 1, 134, 783, 1940, 2575, 1926, 769, 128, 1, 263, 1813, 5411, 8995, 8981, 5383, 1793, 256, 1, 520, 4124, 14392, 28742, 35896, 28700, 14344, 4097, 512, 1, 1033, 9252, 36948, 86142, 129150, 129108, 86052, 36873, 9217, 1024

Offset

1,3

Comments

Let T(r,c) be the array A077028. Fill 2^k numbers in Gaussian templates conforming to the row lengths determined by T(r,c). A110552 results from summing the numbers on each row.

Links

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

P. Barry, A Note on a Family of Generalized Pascal Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.4.

Formula

Table entries appear to be given by T(n,k) = binomial(n-2,k-1) + 2^(n-1)*binomial(n-2,k-2), n,k >= 1, leading to the e.g.f. (exp((1+x)*u) - 1)*(x*exp((1+x)*u) + x + 2)/(2*(1+x)^2) = u + (1+2*x)*u^2/2! + (1+5*x+4*x^2)*u^3/3! + .... Cf. A111049. - Peter Bala, Jul 27 2012

Example

The filled templates begin
1
.1
.2
..1
..2.3
..4
....1
....2.3.5
....4.6.7
....8
therefore the sequence begins
1
1 2
1 5 4
1 10 17 8
...

Mathematica

T[n_, k_] := Binomial[n - 2, k - 1] + 2^(n - 1)*Binomial[n - 2, k - 2]; Table[T[n, k], {n, 1, 20}, {k, 1, n}] // Flatten (* G. C. Greubel, Aug 31 2017 *)

Prog

(PARI) for(n=1, 20, for(k=1, n, print1(binomial(n - 2, k - 1) + 2^(n - 1)*binomial(n - 2, k - 2), ", "))) \\ G. C. Greubel, Aug 31 2017

Crossrefs

Cf. A077028, A007051, A007582. A111049.

Keyword

nonn,tabl

Author

Alford Arnold, Jul 26 2005

Status

approved

A124326 T(n,m) = A007318(n,m) - A077028(n,m).

1, 3, 3, 6, 10, 6, 10, 22, 22, 10, 15, 40, 53, 40, 15, 21, 65, 105, 105, 65, 21, 28, 98, 185, 226, 185, 98, 28, 36, 140, 301, 431, 431, 301, 140, 36, 45, 192, 462, 756, 887, 756, 462, 192, 45, 55, 255, 678, 1246, 1673, 1673, 1246, 678, 255, 55, 66, 330, 960, 1956, 2954

Offset

1,2

Comments

First term of n-th row is n*(n+1)/2.

Row sum are A002663 (without initial zeros).

Appears to be the triangle resulting from adding the row number (first row numbered 0) of Pascal's triangle (A007318) to each entry in that row, subtracting the corresponding entries in the triangle formed by taking the finite diagonals in the multiplication table in order of increasing length (A003991), and removing the outer two layers, which consist entirely of 0's.

Each value of the sequence T(x,y) is equal to the sum of all values in A014430 that are in the rectangle defined by the tip (0,0) and the position (x,y). - Jon Perry, Sep 11 2013

Links

Table of n, a(n) for n=1..60.

Iva Kodrnja and Helena Koncul, Number of Polynomials Vanishing on a Basis of S_m(Gamma_0(N)), arXiv:2405.10747 [math.NT], 2024. See p. 10.

Formula

T(n,m) = A007318(n,m) - A077028(n,m) (skipping zeros).

Example

Table begins
   1;
   3,   3;
   6,  10,   6;
  10,  22,  22,  10;
  15,  40,  53,  40,  15;
  21,  65, 105, 105,  65,  21;
  28,  98, 185, 226, 185,  98,  28;
  36, 140, 301, 431, 431, 301, 140,  36;
  45, 192, 462, 756, 887, 756, 462, 192,  45;
  ...
If the zeros are included, the table begins
   0;
   0, 0;
   0, 0, 0;
   0, 0, 0, 0;
   0, 0, 1, 0, 0;
   0, 0, 3, 3, 0, 0;
   0, 0, 6, 10, 6, 0, 0;
   0, 0, 10, 22, 22, 10, 0, 0;
   ... - from Michael De Vlieger, May 27 2024

Mathematica

a = Table[Flatten[Table[If[Binomial[m, n] - (1 +n (m - n)) == 0, {}, Binomial[m, n] - (1 + n (m - n))], {n, 0, m}]], {m, 0, 14}]

Crossrefs

Cf. A077028, A007318, A002663, A014430.

Keyword

nonn,tabf,uned

Author

Roger L. Bagula, Jun 26 2007

Status

approved

A134392 A077028 * A000012, that is Rascal's triangle (as matrix) multiplied by a lower triangular matrix of ones (main diagonal of ones included).

1, 2, 1, 4, 3, 1, 8, 7, 4, 1, 15, 14, 10, 5, 1, 26, 25, 20, 13, 6, 1, 42, 41, 35, 26, 16, 7, 1, 64, 63, 56, 45, 32, 19, 8, 1, 93, 92, 84, 71, 55, 38, 22, 9, 1, 130, 129, 120, 105, 86, 65, 44, 25, 10, 1, 176, 175, 165, 148, 126, 101, 75, 50, 28, 11, 1

Offset

1,2

Comments

Left border = A000125.

Row sums = A134393.

Links

Table of n, a(n) for n=1..66.

Formula

A077028 * A000012 as infinite lower triangular matrices.

Triangle read by rows, partial sums starting from the right of A077028.

Example

First few rows of the triangle:
   1;
   2,  1;
   4,  3,  1;
   8,  7,  4,  1;
  15, 14, 10,  5,  1;
  26, 25, 20, 13,  6,  1;
  42, 41, 35, 26, 16,  7,  1;
  ...

Mathematica

rows = 11;
R[n_, k_] /; k <= n := k (n - k) + 1; R[0, 0] = 1; R[_, _] = 0;
MR = Table[R[n, k], {n, 0, rows-1}, {k, 0, rows-1}];
MB = Table[Boole[0 <= k <= n], {n, 0, rows-1}, {k, 0, rows -1}];
T = MR.MB;
Table[T[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 01 2020 *)

Crossrefs

Cf. A077028, A000125, A134393.

Keyword

nonn,tabl

Author

Gary W. Adamson, Oct 23 2007

Extensions

Typos corrected by Jean-François Alcover, Apr 01 2020

Status

approved

A338291 Matrix inverse of the rascal triangle (A077028), read across rows..

1, -1, 1, 1, -2, 1, -1, 3, -3, 1, 2, -6, 7, -4, 1, -6, 18, -21, 13, -5, 1, 24, -72, 84, -52, 21, -6, 1, -120, 360, -420, 260, -105, 31, -7, 1, 720, -2160, 2520, -1560, 630, -186, 43, -8, 1, -5040, 15120, -17640, 10920, -4410, 1302, -301, 57, -9, 1

Offset

0,5

Comments

The columns of this triangle are related to factorial numbers (A000142).

There is a family of triangles T(m;n,k) = 1 + m*k*(n-k) for some fixed integer m (for m >= 0 see A296180, Comments) and 0 <= k <= n. They satisfy the equation T(-m;n,k) = 2 - T(m;n,k). The corresponding matrices inverse M = T^(-1) are given by: M(m;n,n) = 1 for n >= 0, and M(m;n,n-1) = m*(1-n) - 1 for n > 0, and M(m;n,k) = (-1)^(n-k) * m * (m * k*(k+1) + 1) * Product_{i=k+1..n-2} (m*(i+1) - 1) for 0 <= k <= n-2. For special cases of the M(m;n,k) see A338817 (m=-1), and A167374 (m=0), and this triangle (m=1).

Links

Table of n, a(n) for n=0..54.

Werner Schulte, Proof of the Generalized Formula

Formula

T(n,n) = 1 for n >= 0, and T(n,n-1) = -n for n > 0, and T(n,n-2) = n^2 - 3*n + 3 for n > 1, and T(n,k) = (-1)^(n-k) * (k^2 + k + 1) * (n-2)! / k! for 0 <= k <= n-2.

T(n,k) = (2-n) * T(n-1,k) for 0 <= k < n-2.

T(n,k) = T(k+2,k) * (-1)^(n-k) * (n-2)! / k! for 0 <= k <= n-2.

Row sums are A000007(n) for n >= 0.

Example

The triangle T(n,k) for 0 <= k <= n starts:
n\k :      0      1       2      3      4     5     6   7   8  9
================================================================
  0 :      1
  1 :     -1      1
  2 :      1     -2       1
  3 :     -1      3      -3      1
  4 :      2     -6       7     -4      1
  5 :     -6     18     -21     13     -5     1
  6 :     24    -72      84    -52     21    -6     1
  7 :   -120    360    -420    260   -105    31    -7   1
  8 :    720  -2160    2520  -1560    630  -186    43  -8   1
  9 :  -5040  15120  -17640  10920  -4410  1302  -301  57  -9  1
etc.

Prog

(PARI) for(n=0, 10, for(k=0, n, if(k==n, print(" 1"), if(k==n-1, print1(-n, ", "), print1((-1)^(n-k)*(k^2+k+1)*(n-2)!/k!, ", ")))))
(PARI) 1/matrix(10, 10, n, k, n--; k--; if (n>=k, k*(n-k) + 1)) \\ Michel Marcus, Nov 11 2020

Crossrefs

Cf. A000007, A000142, A077028.

Keyword

sign,easy,tabl

Author

Werner Schulte, Oct 20 2020

Status

approved

A000125 Cake numbers: maximal number of pieces resulting from n planar cuts through a cube (or cake): C(n+1,3) + n + 1. (Formerly M1100 N0419)

1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160, 1351, 1562, 1794, 2048, 2325, 2626, 2952, 3304, 3683, 4090, 4526, 4992, 5489, 6018, 6580, 7176, 7807, 8474, 9178, 9920, 10701, 11522, 12384, 13288, 14235, 15226

Offset

0,2

Comments

Note that a(n) = a(n-1) + A000124(n-1). This has the following geometrical interpretation: Define a number of planes in space to be in general arrangement when

(1) no two planes are parallel,

(2) there are no two parallel intersection lines,

(3) there is no point common to four or more planes.

Suppose there are already n-1 planes in general arrangement, thus defining the maximal number of regions in space obtainable by n-1 planes and now one more plane is added in general arrangement. Then it will cut each of the n-1 planes and acquire intersection lines which are in general arrangement. (See the comments on A000124 for general arrangement with lines.) These lines on the new plane define the maximal number of regions in 2-space definable by n-1 straight lines, hence this is A000124(n-1). Each of this regions acts as a dividing wall, thereby creating as many new regions in addition to the a(n-1) regions already there, hence a(n) = a(n-1) + A000124(n-1). - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006

More generally, we have: A000027(n) = binomial(n,0) + binomial(n,1) (the natural numbers), A000124(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) (the Lazy Caterer's sequence), a(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) + binomial(n,3) (Cake Numbers). - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006

If Y is a 2-subset of an n-set X then, for n>=3, a(n-3) is the number of 3-subsets of X which do not have exactly one element in common with Y. - Milan Janjic, Dec 28 2007

a(n) is the number of compositions (ordered partitions) of n+1 into four or fewer parts or equivalently the sum of the first four terms in the n-th row of Pascal's triangle. - Geoffrey Critzer, Jan 23 2009

{a(k): 0 <= k < 4} = divisors of 8. - Reinhard Zumkeller, Jun 17 2009

a(n) is also the maximum number of different values obtained by summing n consecutive positive integers with all possible 2^n sign combinations. This maximum is first reached when summing the interval [n, 2n-1]. - Olivier Gérard, Mar 22 2010

a(n) contains only 5 perfect squares > 1: 4, 64, 576, 67600, and 75203584. The incidences of > 0 are given by A047694. - Frank M Jackson, Mar 15 2013

Given n tiles with two values - an A value and a B value - a player may pick either the A value or the B value. The particular tiles are [n, 0], [n-1, 1], ..., [2, n-2] and [1, n-1]. The sequence is the number of different final A:B counts. For example, with n=4, we can have final total [5, 3] = [4, _] + [_, 1] + [_, 2] + [1, _] = [_, 0] + [3, _] + [2, _] + [_, 3], so a(4) = 2^4 - 1 = 15. The largest and smallest final A+B counts are given by A077043 and A002620 respectively. - Jon Perry, Oct 24 2014

For n>=3, a(n) is also the number of maximal cliques in the (n+1)-triangular graph (the 4-triangular graph has a(3)=8 maximal cliques). - Andrew Howroyd, Jul 19 2017

a(n) is the number of binary words of length n matching the regular expression 1*0*1*0*. Coincidentally, A000124 counts binary words of the form 0*1*0*. See Alexandersson and Nabawanda for proof. - Per W. Alexandersson, May 15 2021

For n > 0, let the n-dimensional cube, {0,1}^n be provided with the Hamming distance, d. Given an element x in {0,1}^n, a(n) is the number of elements y in {0,1}^n such that d(x, y) <= 3. Example: n = 4. Let x = (0,0,0,0) be in {0,1}^4.

d(x,y) = 0: y in {(0,0,0,0)}.

d(x,y) = 1: y in {(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)}.

d(x,y) = 2: y in {(1,1,0,0), (1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1), (0,0,1,1)}.

d(x,y) = 3: y in {(1,1,1,0), (1,1,0,1), (1,0,1,1), (0,1,1,1)}.

All these y are at a distance <= 3 from (0,0,0,0), so a(4) = 15. (See Peter C. Heinig's formula). - Yosu Yurramendi, Dec 14 2021

For n >= 2, a(n) is the number of distinct least squares regression lines fitted to n points (j,y_j), 1 <= j <= n, where each y_j is 0 or 1. The number of distinct lines with exactly k 1's among y_1, ..., y_n is A077028(n,k). The number of distinct slopes is A123596(n). - Pontus von Brömssen, Mar 16 2024

References

V. I. Arnold (ed.), Arnold's Problems, Springer, 2004, comments on Problem 1990-11 (p. 75), pp. 503-510. Numbers N_3.

R. B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 27.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.

H. E. Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 177.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. H. Stickels, Mindstretching Puzzles. Sterling, NY, 1994 p. 85.

W. A. Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 30.

A. M. Yaglom and I. M. Yaglom: Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #45 (First published: San Francisco: Holden-Day, Inc., 1964)

Links

T. D. Noe, Table of n, a(n) for n = 0..1000

P. Alexandersson and O. Nabawanda, Peaks are preserved under run-sorting, arXiv:2104.04220 [math.CO], 2021.

A. M. Baxter and L. K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014.

M. L. Cornelius, Variations on a geometric progression, Mathematics in School, 4 (No. 3, May 1975), p. 32. (Annotated scanned copy)

F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.

R. K. Guy, Letter to N. J. A. Sloane

Zachary Hoelscher, Semicomplete Arithmetic Sequences, Division of Hypercubes, and the Pell Constant, arXiv:2102.07083 [math.NT], 2021. Mentions this sequence.

Marie Lejeune, On the k-binomial equivalence of finite words and k-binomial complexity of infinite words, Ph. D. Thesis, Université de Liège (Belgium, 2021).

D. A. Lind, On a class of nonlinear binomial sums, Fib. Quart., 3 (1965), 292-298.

Svante Linusson, The number of M-sequences and f-vectors, Combinatorica, vol 19 no 2 (1999) 255-266.

Toufik Mansour, Howard Skogman, and Rebecca Smith, Sorting inversion sequences, arXiv:2401.06662 [math.CO], 2024. See page 7.

R. J. Mathar, The number of binary mxm matrices with at most k 1's in each row or columna, (2014) Table 3 column 1.

Ângela Mestre and José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.

Sebastian Mizera and Sabrina Pasterski, Celestial Geometry, arXiv:2204.02505 [hep-th], 2022.

Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

D. J. Price, Some unusual series occurring in n-dimensional geometry, Math. Gaz., 30 (1946), 149-150.

L. Pudwell and A. Baxter, Ascent sequences avoiding pairs of patterns, 2014.

Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.

H. P. Robinson, Letter to N. J. A. Sloane, Aug 16 1971, with attachments

Eric Weisstein's World of Mathematics, Cake Number

Eric Weisstein's World of Mathematics, Cube Division by Planes

Eric Weisstein's World of Mathematics, Cylinder Cutting

Eric Weisstein's World of Mathematics, Maximal Clique

Eric Weisstein's World of Mathematics, Space Division by Planes

Eric Weisstein's World of Mathematics, Triangular Graph

Reinhard Zumkeller, Enumerations of Divisors

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Formula

a(n) = (n+1)*(n^2-n+6)/6 = (n^3 + 5*n + 6) / 6.

G.f.: (1 - 2*x + 2x^2)/(1-x)^4. - [Simon Plouffe in his 1992 dissertation.]

E.g.f.: (1 + x + x^2/2 + x^3/6)*exp(x).

a(n) = binomial(n,3) + binomial(n,2) + binomial(n,1) + binomial(n,0). - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006

Paraphrasing the previous comment: the sequence is the binomial transform of [1,1,1,1,0,0,0,...]. - Gary W. Adamson, Oct 23 2007

From Ilya Gutkovskiy, Jul 18 2016: (Start)

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4).

a(n) = Sum_{k=0..n} A152947(k+1).

Inverse binomial transform of A134396.

Sum_{n>=0} a(n)/n! = 8*exp(1)/3. (End)

a(n) = -A283551(-n). - Michael Somos, Jul 07 2022

Example

a(4)=15 because there are 15 compositions of 5 into four or fewer parts. a(6)=42 because the sum of the first four terms in the 6th row of Pascal's triangle is 1+6+15+20=42. - Geoffrey Critzer, Jan 23 2009
For n=5, (1, 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 25, 35) and their opposite are the 26 different sums obtained by summing 5,6,7,8,9 with any sign combination. - Olivier Gérard, Mar 22 2010
G.f. = 1 + 2*x + 4*x^2 + 8*x^3 + 15*x^4 + 26*x^5 + 42*x^6 + 64*x^7 + ... - Michael Somos, Jul 07 2022

Maple

A000125 := n->(n+1)*(n^2-n+6)/6;

Mathematica

Table[(n^3 + 5 n + 6)/6, {n, 0, 50}] (* Harvey P. Dale, Jan 19 2013 *)
LinearRecurrence[{4, -6, 4, -1}, {1, 2, 4, 8}, 50] (* Harvey P. Dale, Jan 19 2013 *)
Table[Binomial[n, 3] + n, {n, 20}] (* Eric W. Weisstein, Jul 21 2017 *)

Prog

(PARI) a(n)=(n^2+5)*n/6+1 \\ Charles R Greathouse IV, Jun 15 2011
(PARI) Vec((1-2*x+2*x^2)/((1-x)^4) + O(x^100)) \\ Altug Alkan, Oct 16 2015
(Magma) [(n^3+5*n+6)/6: n in [0..50]]; // Vincenzo Librandi, Nov 08 2014
(Python)
def A000125_gen():  # generator of terms
    a, b, c = 1, 1, 1
    while True:
        yield a
        a, b, c = a+b, b+c, c+1
it = A000125_gen()
A000125_list = [next(it) for _ in range(50)]  # Cole Dykstra, Aug 03 2022

Crossrefs

Bisections give A100503, A100504.

Row sums of A077028.

Cf. A000124, A003600, A005408, A016813, A086514, A058331, A002522, A161701-A161705, A000127, A161706-A161708, A080856, A161710-A161713, A161715, A006261, A063865, A051601, A077043, A002620, A123596.

Cf. A000027, A047694, A134396, A152947, A283551.

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Minor typo in comments corrected by Mauro Fiorentini, Jan 02 2018

Status

approved

A057145 Square array of polygonal numbers T(n,k) = ((n-2)*k^2 - (n-4)*k)/2, n >= 2, k >= 1, read by antidiagonals upwards.

1, 1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 9, 10, 5, 1, 6, 12, 16, 15, 6, 1, 7, 15, 22, 25, 21, 7, 1, 8, 18, 28, 35, 36, 28, 8, 1, 9, 21, 34, 45, 51, 49, 36, 9, 1, 10, 24, 40, 55, 66, 70, 64, 45, 10, 1, 11, 27, 46, 65, 81, 91, 92, 81, 55, 11, 1, 12, 30, 52, 75, 96, 112

Offset

2,3

Comments

The set of the "nontrivial" entries T(n>=3,k>=3) is in A090466. - R. J. Mathar, Jul 28 2016

T(n,k) is the smallest number that can be expressed as the sum of k consecutive positive integers that differ by n - 2. In other words: T(n,k) is the sum of k terms of the arithmetic progression with common difference n - 2 and 1st term 1, (see the example). - Omar E. Pol, Apr 29 2020

References

A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, p. 189, 1966.

J. H. Conway and R. K. Guy, The Book of Numbers, Springer-Verlag (Copernicus), p. 38, 1996.

Links

T. D. Noe, Rows n = 2..100, flattened

Lukas Andritsch, Boundary algebra of a GL_m-dimer, arXiv:1804.07243 [math.RT], 2018.

Index to sequences related to polygonal numbers

Formula

T(2n+4,n) = n^3. - Stuart M. Ellerstein (ellerstein(AT)aol.com), Aug 28 2000

T(n, k) = T(n-1, k) + k*(k-1)/2 [with T(2, k)=k] = T(n, k-1) + 1 + (n-2)*(k-1) [with T(n, 0)=0] = k + (n-2)k(k-1)/2 = k + A063212(n-2, k-1). - Henry Bottomley, Jul 11 2001

G.f. for row n: x*(1+(n-3)*x)/(1-x)^3, n>=2. - Paul Barry, Feb 21 2003

From Wolfdieter Lang, Nov 05 2014: (Start)

The triangle is a(n, m) = T(n-m+1, m) = (1/2)*m*(n*(m-1) + 3 - m^2) for n >= 2, m = 1, 2, ..., n-1 and zero elsewhere.

O.g.f. for column m (without leading zeros): (x*binomial(m,2) + (1+2*m-m^2)*(m/2)*(1-x))/(x^(m-1)*(1-x)^2). (End)

T(n,k) = A139600(n-2,k) = A086270(n-2,k). - R. J. Mathar, Jul 28 2016

Row sums of A077028: T(n+2,k+1) = Sum_{j=0..k} A077028(n,j), where A077028(n,k) = 1+n*k is the square array interpretation of A077028 (the 1D polygonal numbers). - R. J. Mathar, Jul 30 2016

G.f.: x^2*y*(1 - x - y + 2*x*y)/((1 - x)^2*(1 - y)^3). - Stefano Spezia, Apr 12 2024

Example

Array T(n k) (n >= 2, k >= 1) begins:
  1,  2,  3,  4,   5,   6,   7,   8,   9,  10,  11, ...
  1,  3,  6, 10,  15,  21,  28,  36,  45,  55,  66, ...
  1,  4,  9, 16,  25,  36,  49,  64,  81, 100, 121, ...
  1,  5, 12, 22,  35,  51,  70,  92, 117, 145, 176, ...
  1,  6, 15, 28,  45,  66,  91, 120, 153, 190, 231, ...
  1,  7, 18, 34,  55,  81, 112, 148, 189, 235, 286, ...
  1,  8, 21, 40,  65,  96, 133, 176, 225, 280, 341, ...
  1,  9, 24, 46,  75, 111, 154, 204, 261, 325, 396, ...
  1, 10, 27, 52,  85, 126, 175, 232, 297, 370, 451, ...
  1, 11, 30, 58,  95, 141, 196, 260, 333, 415, 506, ...
  1, 12, 33, 64, 105, 156, 217, 288, 369, 460, 561, ...
  1, 13, 36, 70, 115, 171, 238, 316, 405, 505, 616, ...
  1, 14, 39, 76, 125, 186, 259, 344, 441, 550, 671, ...
-------------------------------------------------------
From Wolfdieter Lang, Nov 04 2014: (Start)
The triangle a(k, m) begins:
  k\m 1  2  3  4  5   6   7   8   9  10  11  12 13 14 ...
  2:  1
  3:  1  2
  4:  1  3  3
  5:  1  4  6  4
  6:  1  5  9 10  5
  7:  1  6 12 16 15   6
  8:  1  7 15 22 25  21   7
  9:  1  8 18 28 35  36  28   8
  10: 1  9 21 34 45  51  49  36   9
  11: 1 10 24 40 55  66  70  64  45  10
  12: 1 11 27 46 65  81  91  92  81  55  11
  13: 1 12 30 52 75  96 112 120 117 100  66  12
  14: 1 13 33 58 85 111 133 148 153 145 121  78 13
  15: 1 14 36 64 95 126 154 176 189 190 176 144 91 14
  ...
-------------------------------------------------------
a(2,1) = T(2,1), a(6, 3) = T(4, 3). (End)
.
From Omar E. Pol, May 03 2020: (Start)
Illustration of the corner of the square array:
.
  1       2         3           4
  O     O O     O O O     O O O O
.
  1       3         6          10
  O     O O     O O O     O O O O
          O       O O       O O O
                    O         O O
                                O
.
  1       4         9          16
  O     O O     O O O     O O O O
          O       O O       O O O
          O       O O       O O O
                    O         O O
                    O         O O
                                O
                                O
.
  1       5        12          22
  O     O O     O O O     O O O O
          O       O O       O O O
          O       O O       O O O
          O       O O       O O O
                    O         O O
                    O         O O
                    O         O O
                                O
                                O
                                O
(End)

Maple

A057145 := proc(n, k)
    ((n-2)*k^2-(n-4)*k)/2 ;
end proc:
seq(seq(A057145(d-k, k), k=1..d-2), d=3..12); # R. J. Mathar, Jul 28 2016

Mathematica

nn = 12; Flatten[Table[k (3 - k^2 - n + k*n)/2, {n, 2, nn}, {k, n - 1}]] (* T. D. Noe, Oct 10 2012 *)

Prog

(Magma) /* As square array: */ t:=func<n, s | (n^2*(s-2)-n*(s-4))/2>; [[t(s, n): s in [1..11]]: n in [2..14]]; // Bruno Berselli, Jun 24 2013

Crossrefs

Many rows and columns of this array are in the database.

Cf. A055795 (antidiagonal sums), A064808 (main diagonal).

Cf. A063212, A077028, A086270, A090466, A139600.

Keyword

nonn,nice,tabl,easy

Author

N. J. A. Sloane, Sep 12 2000

Extensions

a(50)=49 corrected to a(50)=40 by Jean-François Alcover, Jul 22 2011

Edited: Name shortened, offset in Paul Barry's g.f. corrected and Conway-Guy reference added. - Wolfdieter Lang, Nov 04 2014

Status

approved

A287326 Triangle read by rows: T(n, k) = 6*k*(n-k) + 1; n >= 0, 0 <= k <= n.

1, 1, 1, 1, 7, 1, 1, 13, 13, 1, 1, 19, 25, 19, 1, 1, 25, 37, 37, 25, 1, 1, 31, 49, 55, 49, 31, 1, 1, 37, 61, 73, 73, 61, 37, 1, 1, 43, 73, 91, 97, 91, 73, 43, 1, 1, 49, 85, 109, 121, 121, 109, 85, 49, 1, 1, 55, 97, 127, 145, 151, 145, 127, 97, 55, 1, 1, 61, 109, 145, 169, 181, 181, 169, 145, 109, 61, 1

Offset

0,5

Comments

From Kolosov Petro, Apr 12 2020: (Start)

Let A(m, r) = A302971(m, r) / A304042(m, r).

Let L(m, n, k) = Sum_{r=0..m} A(m, r) * k^r * (n - k)^r.

Then T(n, k) = L(1, n, k), i.e T(n, k) is partial case of L(m, n, k) for m = 1.

T(n, k) is symmetric: T(n, k) = T(n, n-k).

(End)

Links

Georg Fischer, Table of n, a(n) for n = 0..495 [rows 0..10 and 12..30 from Kolosov Petro]

Petro Kolosov, On the link between Binomial Theorem and Discrete Convolution of Power Function, arXiv:1603.02468 [math.NT], 2016-2020.

Petro Kolosov, Polynomial identity involving binomial theorem and Faulhaber's formula, 2023.

Petro Kolosov, History and overview of the polynomial P_b^m(x), 2024.

Formula

T(n, k) = 6*k*(n-k) + 1.

G.f. of column k: n^k*(1+(6*k-1)*n)/(1-n)^2.

G.f.: (-1 + 8*y + 5*y^2 + x*(1 - 14*y + y^2))/((-1 + x)^2*(-1 + y)^3). - Stefano Spezia, Oct 09 2018

From Kolosov Petro, Jun 05 2019 (Start):

T(n, k) = 1/2 * T(A294317(n, k), k) + 1/2.

T(n+1, k) = 2*T(n, k) - T(n-1, k), for n >= k.

T(n, k) = 6*A077028(n, k) - 5.

T(2n, n) = A227776(n).

T(2n+1, n) = A003154(n+1).

T(2n+3, n) = A166873(n+1).

Sum_{k=0..n-1} T(n, k) = Sum_{k=1..n} T(n, k) = A000578(n).

Sum_{k=1..n-1} T(n, k) = A068601(n).

(n+1)^3 - n^3 = T(A000124(n), 1). (End)

Example

Triangle begins:
----------------------------------------
k=    0   1   2   3   4   5   6   7   8
----------------------------------------
n=0:  1;
n=1:  1,  1;
n=2:  1,  7,  1;
n=3:  1, 13, 13,  1;
n=4:  1, 19, 25, 19,  1;
n=5:  1, 25, 37, 37, 25,  1;
n=6:  1, 31, 49, 55, 49, 31,  1;
n=7:  1, 37, 61, 73, 73, 61, 37,  1;
n=8:  1, 43, 73, 91, 97, 91, 73, 43,  1;

Maple

T := (n, k) -> 6*k*(n-k) + 1:
seq(seq(T(n, k), k=0..n), n=0..11); # Muniru A Asiru, Oct 09 2018

Mathematica

T[n_, k_] := 6 k (n - k) + 1; Column[Table[T[n, k], {n, 0, 10}, {k, 0, n}], Center] (* Kolosov Petro, Jun 02 2019 *)

Prog

(PARI) t(n, k) = 6*k*(n-k)+1
trianglerows(n) = for(x=0, n-1, for(y=0, x, print1(t(x, y), ", ")); print(""))
/* Print initial 9 rows of triangle as follows */
trianglerows(9) \\ Felix Fröhlich, Jan 09 2018
(GAP) Flat(List([0..11], n->List([0..n], k->6*k*(n-k)+1))); # Muniru A Asiru, Oct 09 2018
(Magma) /* As triangle */ [[6*k*(n-k) + 1: k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Oct 26 2018

Crossrefs

Columns k=0..6 give A000012, A016921, A017533, A161705, A103214, A128470, A158065.

Column sums k=0..4 give A000027, A000567, A051866, A051872, A255185.

Row sums give A001093.

Various cases of L(m, n, k): This sequence (m=1), A300656(m=2), A300785(m=3). See comments for L(m, n, k).

Differences of cubes n^3 are T(A000124(n), 1).

Cf. A000578, A038593, A294317, A007318, A055012, A077028, A008458, A302971, A304042, A068601, A166873, A003154, A227776, A000124, A003215, A094053.

Keyword

nonn,tabl,easy

Author

Kolosov Petro, Aug 31 2017

Status

approved