A001924 -id:A001924 - cp's OEIS frontend

A104732 Square array T[i,j]=T[i-1,j]+T[i-1,j-1], T[1,j]=j, T[i,1]=1, read by antidiagonals.

1, 2, 1, 3, 3, 1, 4, 5, 4, 1, 5, 7, 8, 5, 1, 6, 9, 12, 12, 6, 1, 7, 11, 16, 20, 17, 7, 1, 8, 13, 20, 28, 32, 23, 8, 1, 9, 15, 24, 36, 48, 49, 30, 9, 1, 10, 17, 28, 44, 64, 80, 72, 38, 10, 1, 11, 19, 32, 52, 80, 112, 129, 102, 47, 11, 1, 12, 21, 36, 60, 96, 144, 192, 201, 140, 57, 12, 1

Offset: 1

Gary W. Adamson, Mar 20 2005

Original definition was "Triangle, row sums are A001924". Reading the rows of the triangle as antidiagonals of a square array allows a precise, yet simple definition and a method for computing the terms. - M. F. Hasler, Apr 26 2008

When formatted as a triangle, row sums are A001924: 1, 3, 7, 14, 26...(apply the partial sum operator twice to the Fibonacci sequence).

			The first few rows of the triangle (= rising diagonals of the square array) are:
1;
2, 1;
3, 3, 1;
4, 5, 4, 1;
5, 7, 8, 5, 1;
6, 9, 12, 12, 6, 1;
...

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A001924, A026729.

A104732 := proc(i,j) coeftayl(coeftayl(x*y/(1-x)^2/(1-y*(1+x)),y=0,i),x=0,j) ; end: for d from 1 to 20 do for j from d to 1 by -1 do printf("%d,",A104732(d-j+1,j)) ; od: od: # R. J. Mathar, May 04 2008

nn = 10; Map[Select[#, # > 0 &] &,Drop[CoefficientList[
    Series[y x/(1 - x - y x + y x^3)/(1 - x), {x, 0, nn}], {x, y}],
1]] // Grid (* Geoffrey Critzer, Mar 17 2015 *)

def A104732_rows(n):
    """Produces n rows of A104732 triangle"""
    from operator import iadd
    a,b,c = [], [1], [1]
    for i in range(2,n+1):
            a,b = b, [i]+list(map(iadd,a,b[:-1]))+[1]
            c+=b
    return c
# Alec Mihailovs (alec(AT)mihailovs.com), May 04 2008

The triangle is extracted from A * B; where A = [1; 2, 1; 3, 2, 1;...], B = [1; 0, 1; 0, 1, 1; 0, 0, 2, 1;...]; both infinite lower triangular matrices with the rest of the terms zeros. The sequence in "B" (1, 0, 1, 0, 1, 1, 0, 0, 2, 1...) = A026729.

As a square array, g.f. Sum T[i,j] x^j y^i = xy/((1-(1+x)y)*(1-x)^2). - Alec Mihailovs (alec(AT)mihailovs.com), Apr 26 2008

Edited by M. F. Hasler, Apr 26 2008

More terms from R. J. Mathar and Alec Mihailovs (alec(AT)mihailovs.com), May 04 2008

A109263 A Catalan transform of F(n-1)-0^n.

Original entry on oeis.org

0, 0, 1, 3, 10, 34, 118, 416, 1485, 5355, 19473, 71313, 262735, 973027, 3619955, 13521307, 50684778, 190597594, 718788034, 2717755820, 10300186824, 39121645886, 148884623768, 567643844338, 2167882951110, 8292331115104

Offset: 0

Paul Barry, Jun 24 2005

A column of A109267.

Define a triangle by T(n,0)=A000045(n) and T(n,k)=sum_{r=k-1..n} T(r,k-1). (The column k=1 is A000071, the column k=2 is A001924 etc). Then T(n,n)=a(n+1). - J. M. Bergot, May 22 2013

G.f.: x^2c(x)^2/(1-xc(x)-x^2c(x)^2) where c(x) is the g.f. of A000108; a(n)=sum{k=0..n, (k/(2n-k))binomial(2n-k, n-k)(F(k-1)-0^k)}.

Conjecture: n*(n-3)*a(n) +2*(-4*n^2+15*n-10)*a(n-1) +(15*n^2-69*n+80)*a(n-2) +2*(n-2)*(2*n-5)*a(n-3)=0. - R. J. Mathar, Nov 09 2012

A153346 Triangle read by rows: A000012 * A153345.

Original entry on oeis.org

1, 3, 0, 7, 1, 0, 14, 5, 1, 0, 26, 16, 6, 1, 0, 46, 42, 23, 7, 1, 0, 79, 98, 71, 31, 8, 1, 0, 133, 212, 192, 109, 40, 9, 1, 0, 221, 435, 475, 332, 157, 50, 10, 1, 0, 364, 859, 1102, 916, 529, 216, 61, 11, 1, 0, 596, 1648, 2436, 2350, 1602, 795, 287, 73, 12, 1, 0, 972, 3092, 5186, 5702, 4481, 2613, 1143, 371, 86, 13, 1, 0

Offset: 0

Gary W. Adamson, Dec 24 2008

Row sums = A048739: (1, 3, 8, 20, 49, 119, 288, ...).

Left border = A001924.

			First few rows of the triangle:
    1;
    3,    0;
    7,    1,    0;
   14,    5,    1,    0;
   26,   16,    6,    1,    0;
   46,   42,   23,    7,    1,   0
   79,   98,   71,   31,    8,   1,   0;
  133,  212,  192,  109,   40,   9,   1,  0;
  221,  435,  475,  332,  157,  50,  10,  1,  0;
  364,  859, 1102,  916,  529, 216,  61, 11,  1, 0;
  596, 1648, 2436, 2350, 1602, 795, 287, 73, 12, 1, 0;
  ...

Cf. A001924, A048739, A153345.

a(44) = 0 corrected and more terms from Georg Fischer, Jun 05 2023

A180975 Array of the "egg-drop" numbers, read by downwards antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 1, 3, 6, 4, 1, 3, 7, 10, 5, 1, 3, 7, 14, 15, 6, 1, 3, 7, 15, 25, 21, 7, 1, 3, 7, 15, 30, 41, 28, 8, 1, 3, 7, 15, 31, 56, 63, 36, 9, 1, 3, 7, 15, 31, 62, 98, 92, 45, 10

Offset: 1

Francis Carr (fcarr(AT)alum.mit.edu), Sep 30 2010

The egg-drop problem is as follows. We wish to determine the highest floor in a building such that an egg dropped from that floor will not shatter. We have a set of k identical eggs for dropping; note that an egg that does not shatter can be reused to test higher floors. Then T(n,k) is the largest number of floors that can be tested using at most n drops and k eggs.
Suppose one is given k eggs and a building of f floors. Then the worst-case number of drops WC(k,f) to test all the floors satisfies the dynamic programming equation
. WC(k,f) = 1 + max_{g in 1..f} { WC(k-1, g-1), WC(k, f-g) }
with boundary conditions
. WC(1,f) = f and WC(k,0) = 0
where g is the floor chosen for the next drop. One can substitute f -> T(n,k) and g -> T(n-1,k-1)+1 = f-T(k-1,j). Then by an inductive argument, it is verified that WC(j,T(n,j)) = n as expected.
T(n,2) = n(n+1)/2. This leads to the commonly-used heuristic solution for 2 eggs of dropping from the sqrt(f), 2*sqrt(f), 3*sqrt(f) etc. floors until the first egg breaks. T(n,j) is a j-th order polynomial in n, and so this heuristic may be generalized: drop from multiples of f^((j-1)/j) until the j-th egg breaks.

			T(n,1) = n. With only a single egg, one must drop the egg from the first floor, then the second, and so on until it finally breaks. At most n floors may be tested this way.
If one is allowed fewer drops than eggs, a simple binary search is optimal. Hence T(n,k) = 2^n-1 for n <= k. Note that one cannot test 2^n floors in this case. For example, suppose one had 2 drops and a 4-story building; dropping from either the second or third floor could leave another two floors to test, but only one drop remaining.
The square array starts in row n=1 with columns k >= 1:
  1:  1  1  1  1  1  1  1  1  1
  2:  2  3  3  3  3  3  3  3  3
  3:  3  6  7  7  7  7  7  7  7
  4:  4 10 14 15 15 15 15 15 15
  5:  5 15 25 30 31 31 31 31 31
  6:  6 21 41 56 62 63 63 63 63

J. Kleinberg and E. Tardos, "Algorithm Design", Addison-Wesley Longman Publishing Co. Inc., 2005. Problem 2.8.
D. Velleman, "Which Way Did The Bicycle Go? And Other Intriguing Mathematical Mysteries (Dolciani Mathematical Expositions)", The Mathematical Association of America, 1996, "166. An Egg-Drop Experiment" pages 53 and 204-205.

G. C. Greubel, Antidiagonals n = 1..100 of array, flattened
Michael Boardman, The Egg-Drop Numbers, Mathematics Magazine, 77 (2004), 368-372.

Cf. A004070, A117670.
Cf. A131251 (transpose).
Cf. A001924 (antidiagonal sums).

nmax:=11;; T:=List([1..nmax],n->List([1..nmax],k->Sum([1..k],j->Binomial(n,j))));;
b:=List([2..nmax],n->OrderedPartitions(n,2));;
a:=Flat(List([1..Length(b)],i->List([1..Length(b[i])],j->T[b[i][j][1]][b[i][j][2]]))); # Muniru A Asiru, Oct 09 2018

[[(&+[Binomial(k,j): j in [1..n-k]]): k in [1..n-1]]: n in [2..15]]; // G. C. Greubel, Oct 09 2018

T:= proc(n,k) option remember;
if n = 0 or k = 0 then 0
else T(n-1,k-1) + 1 + T(n-1,k)
fi
end proc:
seq(seq(T(i,m-i),i=1..m-1),m=1..20); # Robert Israel, Jan 20 2015

T[n,k] = Sum[Binomial[n, j], {j, 1, k}]; Table[T[k, n-k], {n, 2, 15}, {k, 1, n-1}]//Flatten (* modified by G. C. Greubel, Oct 09 2018 *)

for(n=2, 15, for(k=1,n-1, print1(sum(j=1, n-k, binomial(k,j)), ", "))) \\ G. C. Greubel, Oct 09 2018

from functools import lru_cache
@lru_cache(maxsize=None)
def T(n, k): return 0 if n*k == 0 else T(n-1, k-1) + 1 + T(n-1, k)
print([T(k, n-k) for n in range(1, 12) for k in range(1, n)]) # Michael S. Branicky, Apr 04 2021

Recursive formula: T(n,k) = T(n-1,k-1) + 1 + T(n-1,k) with boundary conditions T(0,k) = T(n,0) = 0.
T(n,k) = Sum_{j=1..k} binomial(n,j).
From the journal article by Boardman, the generating function for a fixed value of n is g_n(x) = ((1+x)^n - 1) / (1-x).
G.f.: x*y/((1-y)*(1-x)*(1-x-x*y)). - Vladimir Kruchinin, Oct 09 2018

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

Original entry on oeis.org

0, 1, 6, 17, 38, 75, 138, 243, 416, 699, 1160, 1909, 3124, 5093, 8282, 13445, 21802, 35327, 57214, 92631, 149940, 242671, 392716, 635497, 1028328, 1663945, 2692398, 4356473, 7049006, 11405619, 18454770, 29860539, 48315464, 78176163

Offset: 0

Clark Kimberling, Jul 09 2011

nonn

The titular polynomial is defined recursively by p(n,x)=x*(n-1,x)+5n for n>0, where p(0,x)=1. For discussions of polynomial reduction, see A192232 and A192744.

Cf. A192744, A192232.

q = x^2; s = x + 1; z = 40;
p[0, n_] := 1; p[n_, x_] := x*p[n - 1, x] + 5 n;
Table[Expand[p[n, x]], {n, 0, 7}]
reduce[{p1_, q_, s_, x_}] :=
FixedPoint[(s PolynomialQuotient @@ #1 +
       PolynomialRemainder @@ #1 &)[{#1, q, x}] &, p1]
t = Table[reduce[{p[n, x], q, s, x}], {n, 0, z}];
u1 = Table[Coefficient[Part[t, n], x, 0], {n, 1, z}]
(* A166863 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]
(* A192756 *)

Conjecture: G.f.: -x*(1+3*x+x^2) / ( (x^2+x-1)*(x-1)^2 ). a(n) = A001924(n)+3*A001924(n-1)+A001924(n-2). Partial sums of A166863. - R. J. Mathar, May 04 2014

A210677 a(n) = a(n-1) + a(n-2) + n + 1, a(0) = a(1) = 1.

Original entry on oeis.org

1, 1, 5, 10, 20, 36, 63, 107, 179, 296, 486, 794, 1293, 2101, 3409, 5526, 8952, 14496, 23467, 37983, 61471, 99476, 160970, 260470, 421465, 681961, 1103453, 1785442, 2888924, 4674396, 7563351, 12237779, 19801163, 32038976, 51840174, 83879186, 135719397, 219598621, 355318057

Offset: 0

Alex Ratushnyak, May 09 2012

Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A081659: a(n)=a(n-1)+a(n-2)+n-5, a(0)=a(1)=1 (except first 2 terms and sign).
Cf. A001924: a(n)=a(n-1)+a(n-2)+n-4, a(0)=a(1)=1 (except first 4 terms).
Cf. A000126: a(n)=a(n-1)+a(n-2)+n-2, a(0)=a(1)=1 (except first term).
Cf. A066982: a(n)=a(n-1)+a(n-2)+n-1, a(0)=a(1)=1.
Cf. A030119: a(n)=a(n-1)+a(n-2)+n, a(0)=a(1)=1.
Cf. A210678: a(n)=a(n-1)+a(n-2)+n+2, a(0)=a(1)=1.

LinearRecurrence[{3, -2, -1, 1}, {1, 1, 5, 10}, 39] (* Jean-François Alcover, Oct 05 2017 *)

From Colin Barker, Jun 30 2012: (Start)
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4).
G.f.: (1 - 2*x + 4*x^2 - 2*x^3)/((1 - x)^2*(1 - x - x^2)). (End)
E.g.f.: exp(x/2)*(25*cosh(sqrt(5)*x/2) + 7*sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x)*(4 + x). - Stefano Spezia, Feb 24 2023

A257838 Main diagonal of iterated partial sums array of Fibonacci numbers (starting with the first partial sums).

Original entry on oeis.org

0, 1, 4, 16, 63, 247, 967, 3785, 14820, 58060, 227612, 892926, 3505386, 13770404, 54129602, 212904952, 837885495, 3299264407, 12997784803, 51230474669, 202014314769, 796928589755, 3145066003589, 12416625685891, 49037912997003, 193734379979677, 765632076098287, 3026670770970925, 11968378998073935

Offset: 0

Luciano Ancora, May 10 2015

The array used here starts in row n=0 with the first partial sums of A000045. The array which starts with the Fibonacci numbers in row k=0 is shown in A136431. The diagonal of that array is given in A176085. - Wolfdieter Lang, Jun 03 2015

			This sequence is the main diagonal of the following array (see the comment and Example field of A136431):
0, 1, 2,  4,  7,  12, ...  A000071
0, 1, 3,  7, 14,  26, ...  A001924
0, 1, 4, 11, 25,  51, ...  A014162
0, 1, 5, 16, 41,  92, ...  A014166
0, 1, 6, 22, 63, 155, ...  A053739
0, 1, 7, 29, 92, 247, ...  A053295

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A000045, A000071, A001924, A014162, A014166, A136431, A176085.

Table[DifferenceRoot[Function[{a, n},{(2*n + 4*n^2)*a[n] + (2 + 7*n + 15*n^2)*a[1 + n] + (8 - 6*n - 8*n^2)*a[2 + n] + (-2 + n + n^2)*a[3 + n] == 0, a[1] == 0, a[2] == 1, a[3] == 4, a[4] == 16}]][n], {n, 30}]

a(n):=sum(binomial(2*n-k,n-k)*fib(k),k,0,n); /* Vladimir Kruchinin, Oct 09 2016 */

x='x+O('x^50); concat([0], Vec(-(4*x+sqrt(1-4*x)-1)/(8*x^2+sqrt(1-4*x)*(8*x-2)-2*x))) \\ G. C. Greubel, Apr 08 2017

a(n) = F^{n+1}(n), n >= 0, with the k-th iterated partial sum F^{k} of the Fibonacci number A000045. - Wolfdieter Lang, Jun 03 2015
Conjecture: n*(n-3)*a(n) +2*(-4*n^2+13*n-6)*a(n-1) +(15*n^2-53*n+48)*a(n-2) +2*(2*n-3)*(n-2)*a(n-3)=0. - R. J. Mathar, Dec 10 2015
G.f.: -(4*x+sqrt(1-4*x)-1)/(8*x^2+sqrt(1-4*x)*(8*x-2)-2*x). - Vladimir Kruchinin, Oct 09 2016
a(n) = Sum_{k=0..n} binomial(2*n-k,n-k)*F(k), where F(k) = A000045(k). - Vladimir Kruchinin, Oct 09 2016
a(n) ~ 2^(2*n+1)/sqrt(Pi*n). - Vaclav Kotesovec, Oct 09 2016

Name edited by Wolfdieter Lang, Jun 03 2015

A048516 Array T read by diagonals: T(m,n)=number of subsets S of {1,2,3,...,m+n-1} such that |S|>1 and |a-b|>=m for all distinct a and b in S, m=1,2,3,...; n=1,2,3,...

Original entry on oeis.org

0, 0, 1, 0, 4, 1, 0, 11, 3, 1, 0, 26, 7, 3, 1, 0, 57, 14, 6, 3, 1, 0, 120, 26, 11, 6, 3, 1, 0, 247, 46, 19, 10, 6, 3, 1, 0, 502, 79, 31, 16, 10, 6, 3, 1, 0, 1013, 133, 49, 25, 15, 10, 6, 3, 1, 0, 2036, 221, 76, 38, 22, 15, 10, 6, 3, 1, 0, 4083, 364

Offset: 1

Clark Kimberling

			Diagonals: {0}; {1,0}; {4,1,0}; ...

Sean A. Irvine, Java program (github)

A000295 (row 1), A001924 (row 2), A050228 (row 3).

T(m,n) = [x^m] 1/((1-x^2)*(1-x-x^n)). - Sean A. Irvine, Jun 19 2021

A079921 Solution to the Dancing School Problem with n girls and n+2 boys: f(n,2).

Original entry on oeis.org

3, 7, 14, 26, 46, 79, 133, 221, 364, 596, 972, 1581, 2567, 4163, 6746, 10926, 17690, 28635, 46345, 75001, 121368, 196392, 317784, 514201, 832011, 1346239, 2178278, 3524546, 5702854, 9227431, 14930317, 24157781, 39088132, 63245948, 102334116, 165580101

Offset: 1

Jaap Spies, Jan 28 2003

nonn

f(g,h) = per(B), the permanent of the (0,1)-matrix B of size g X g+h with b(i,j)=1 if and only if i <= j <= i+h. See A079908 for more information.

With offset 4, number of 132-avoiding two-stack sortable permutations which contain exactly one subsequence of type 123.

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
E. S. Egge and T. Mansour, 132-avoiding two-stack sortable permutations....
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A000045, A079908-A079928, A001924.

Cf. Essentially the same as A001924.

with(genfunc): Fz := 1/((-1+z)^2 * (1-z-z^2)); seq(rgf_term(Fz,z,n), n=1..30);

CoefficientList[Series[(-z^3 + z^2 + 2*z - 3)/((z - 1)^2 (z^2 + z - 1)), {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jul 08 2011 *)
LinearRecurrence[{3,-2,-1,1},{3,7,14,26},40] (* Harvey P. Dale, Oct 17 2022 *)

a(n) = a(n-1)+a(n-2)+n+1, a(1)=3, a(2)=7.
G.f.: 1/((1-x)^2*(1-x-x^2)).
F(n+5) - n - 4, F(n) = A000045(n).
a(n) = 3*a(n-1)-2*a(n-2)-a(n-3)+a(n-4). - Wesley Ivan Hurt, Dec 03 2021

More terms from Jaap Spies, Dec 15 2006

A104582 Triangle read by rows: T(i,j) is the (i,j)-entry (1 <= j <= i) of the product of the lower triangular matrix (Fibonacci(i-j+1)) and of the lower triangular matrix all of whose entries are equal to 1 (for j <= i).

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 7, 4, 2, 1, 12, 7, 4, 2, 1, 20, 12, 7, 4, 2, 1, 33, 20, 12, 7, 4, 2, 1, 54, 33, 20, 12, 7, 4, 2, 1, 88, 54, 33, 20, 12, 7, 4, 2, 1, 143, 88, 54, 33, 20, 12, 7, 4, 2, 1, 232, 143, 88, 54, 33, 20, 12, 7, 4, 2, 1, 376, 232, 143, 88, 54, 33, 20, 12, 7, 4, 2, 1, 609, 376, 232

Offset: 1

Gary W. Adamson, Mar 16 2005

			The first few rows of the triangle are:
   1;
   2, 1;
   4, 2, 1;
   7, 4, 2, 1;
  12, 7, 4, 2, 1;
  ...

Sum of row n = Fibonacci(n+4) - n - 3 (A001924). Columns (starting from the diagonal entries) are the Fibonacci numbers -1 (A000071).

with(combinat): for i from 1 to 13 do seq(fibonacci(i-j+3)-1,j=1..i) od; # yields sequence in triangular form # Emeric Deutsch, Mar 23 2005

T(i, j) = Fibonacci(i-j+3) - 1 for 1 <= j <= i and 0 otherwise. - Emeric Deutsch, Mar 23 2005

More terms from Emeric Deutsch, Mar 23 2005

cp's OEIS Frontend

A104732 Square array T[i,j]=T[i-1,j]+T[i-1,j-1], T[1,j]=j, T[i,1]=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A109263 A Catalan transform of F(n-1)-0^n.

Views

Author

Keywords

Comments

Formula

A153346 Triangle read by rows: A000012 * A153345.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A180975 Array of the "egg-drop" numbers, read by downwards antidiagonals.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A210677 a(n) = a(n-1) + a(n-2) + n + 1, a(0) = a(1) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A257838 Main diagonal of iterated partial sums array of Fibonacci numbers (starting with the first partial sums).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

A048516 Array T read by diagonals: T(m,n)=number of subsets S of {1,2,3,...,m+n-1} such that |S|>1 and |a-b|>=m for all distinct a and b in S, m=1,2,3,...; n=1,2,3,...

Views