A008949 -id:A008949 - cp's OEIS frontend

A110570 Triangle read by rows: T(n,0) = T(n,n) = 1 and for 0

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 2, 4, 1, 1, 5, 4, 4, 5, 1, 1, 6, 3, 2, 3, 6, 1, 1, 7, 5, 5, 5, 5, 7, 1, 1, 8, 4, 5, 2, 5, 4, 8, 1, 1, 9, 6, 3, 6, 6, 3, 6, 9, 1, 1, 10, 5, 6, 4, 2, 4, 6, 5, 10, 1, 1, 11, 7, 6, 6, 7, 7, 6, 6, 7, 11, 1, 1, 12, 6, 4, 3, 6, 2, 6, 3, 4, 6, 12, 1, 1, 13, 8, 7, 7, 6, 8, 8, 6, 7, 7

Offset: 1

Reinhard Zumkeller, Jul 28 2005

T(n,k) = T(n,n-k);
row sums give A110571;
T(n,2) = A030451(n) for n>1;
T(n,k)=(1-0^A004197(n,k))*T(n-A004197(n,k),A004197(n,k))+1.

			. . . . . . . . . . 1 . . . . . . . . . . . .
. . . . . . . . . 1 . 1 . . . . . . . . . . .
. . . . . . . . 1 . x . 1 . . . . B = 1 + A .
. . . . . . . 1 . x . x . 1 . . . . . . . . .
. . . . . . 1 . x . x . x . 1 . . F = E + 1 .
. . . . . 1 . x . E . - . - . 1 . . . . . . .
. . . . 1 . x . x . \ . x . / . 1 . . . . . .
. . . 1 . x . x . x . \ . / . x . 1 . . . . .
. . 1 . - . A . x . x . F . x . x . 1 . . . .
. 1 . \ . / . x . x . x . x . x . x . 1 . . .
1 . x . B . x . x . x . x . x . x . x . 1 . .

Cf. A008949, A007318.

T[n_, k_] := T[n, k] = If[Min[k, n - k] == 0, 1, 1 + T[n - Min[k, n - k], Min[k, n - k]]]; Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Aug 31 2017 *)

T(n, k) = if s=0 then 1 else T(n-s, s)+1, where s=Min{k, n-k}.

A112358 The following triangle is based on Pascal's triangle. The r-th term of the n-th row is sum of C(n,r) successive integers so that the sum of all the terms of the row is (2^n)*(2^n+1)/2, the 2^n -th triangular number. Sequence contains the triangle read by rows.

Original entry on oeis.org

1, 1, 2, 1, 5, 4, 1, 9, 18, 8, 1, 14, 51, 54, 16, 1, 20, 115, 215, 145, 32, 1, 27, 225, 650, 750, 363, 64, 1, 35, 399, 1645, 2870, 2310, 868, 128, 1, 44, 658, 3668, 8995, 10724, 6538, 2012, 256, 1, 54, 1026, 7434, 24381, 40257, 35658, 17442, 4563, 512, 1, 65, 1530, 13980, 59115, 129150, 156135, 109020, 44595, 10185, 1024

Offset: 0

Amarnath Murthy, Sep 05 2005

The leading diagonal contains 2^n.

			Row for n = 3 is 1, (2+3+4), (5+6+7), 8.
Triangle begins:
  1
  1 2
  1 5 4
  1 9 18 8
  1 14 51 54 16
  ...

Cf. A112356, A112357, A112359.

Cf. A008949.

A008949[n_, k_] := Sum[Binomial[n, j], {j, 0, k}];
A112358[n_, k_] := If[k == 0, 1, Binomial[A008949[n, k] + 1, 2] - Binomial[A008949[n, k - 1] + 1, 2]];
Table[A112358[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 01 2023 *)

T(n,0) = 1, T(n,k) = C(A008949(n,k)+1, 2) - C(A008949(n,k-1)+1, 2) = C(n,k)*(A008949(n+1,k)+1)/2 for k>0. - Franklin T. Adams-Watters, Sep 27 2006

More terms from Amber Reardon (alr5041(AT)psu.edu) and Vincent M. DelPrince (vmd5003(AT)psu.edu), Oct 04 2005

A112359 Product of n-th row of A112358.

Original entry on oeis.org

1, 2, 20, 1296, 616896, 2294480000, 68803020000000, 16921170978243840000, 34496793424028349312532480, 587395062985562798532990766497792, 84034508984208959408391703340160000000000, 101510206136861741998326287566434701976960000000000

Offset: 0

Amarnath Murthy, Sep 05 2005

Cf. A112356, A112357, A112358.

A008949 := proc(n,k) local i ; add(binomial(n,i),i=0..k) ; end: A112358 := proc(n,k) if k = 0 then 1 ; else binomial(n,k)*(A008949(n+1,k)+1)/2 ; fi ; end: A112359 := proc(n) local k ; mul( A112358(n,k),k=0..n ) ; end: for n from 0 to 15 do printf("%d, ",A112359(n)) ; od ; # R. J. Mathar, May 08 2007

A008949[n_, k_] := Sum[Binomial[n, j], {j, 0, k}];
A112358[n_, k_] := If[k == 0, 1, Binomial[A008949[n, k] + 1, 2] - Binomial[A008949[n, k - 1] + 1, 2]];
a[n_] := Product[A112358[n, k], {k, 0, n}];
Table[a[n], {n, 0, 11}] (* Jean-François Alcover, Aug 01 2023, after R. J. Mathar *)

More terms from R. J. Mathar, May 08 2007

A117670 Triangle read by rows: partial sums of the Pascal triangle minus 1.

Original entry on oeis.org

1, 2, 3, 3, 6, 7, 4, 10, 14, 15, 5, 15, 25, 30, 31, 6, 21, 41, 56, 62, 63, 7, 28, 63, 98, 119, 126, 127, 8, 36, 92, 162, 218, 246, 254, 255, 9, 45, 129, 255, 381, 465, 501, 510, 511, 10, 55, 175, 385, 637, 847, 967, 1012, 1022, 1023

Offset: 1

Arie Bos, Jul 06 2008, Jul 08 2008

Imagine that you are in a building with floors starting at floor 1, the lowest floor and you have a large number of eggs. For each floor in the building, you want to know whether or not an egg dropped from that floor will break.
If an egg breaks when dropped from floor i, then all eggs are guaranteed to break when dropped from any floor j > i. Likewise, if an egg doesn't break when dropped from floor i, then all eggs are guaranteed to never break when dropped from any floor j <= i.
a(n,k) is the maximum number of floors where you can determine whether or not an egg will break when dropped from any floor, with the following restrictions: you may drop a maximum of n eggs (one at a time, from any floors of your choosing) and you may break a maximum of k eggs.
Each row of the triangle is the running sum of the corresponding row with the first 1 omitted of Pascal's triangle (A007318), see A008949, A054143, A193820.
The k-th entry in the n-th row is the number of possible combinations of on/off switches after k attempts to turn on a switch in a set of n distinguishable switches. An attempt to turn on the same switch twice does not result in a new combination. See example. - Sergei Viznyuk, Jun 24 2012
T(n,k) is the number of nonempty subsets of the n-set with at most k elements, see example. - Joerg Arndt, May 04 2014

			Triangle a(n,k) begins:
n\k  1   2    3    4    5    6    7     8     9    10 ...
1:   1
2:   2   3
3:   3   6    7
4:   4  10   14   15
5:   5  15   25   30   31
6:   6  21   41   56   62   63
7:   7  28   63   98  119  126  127
8:   8  36   92  162  218  246  254   255
9:   9  45  129  255  381  465  501   510   511
10: 10  55  175  385  637  847  967  1012  1022  1023
...  Reformatted and extended by _Wolfdieter Lang_, Feb 07 2013
From _Sergei Viznyuk_, Jun 24 2012: (Start)
For example, we have n=3 distinguishable switches A,B,C (third row above). We attempt k=2 times to turn on a switch at random. The possible resulting combinations are:
A=on, B=off, C=off (the same A switch was turned on 2 times)
A=off, B=on, C=off (the same B switch was turned on 2 times)
A=off, B=off, C=on (the same C switch was turned on 2 times)
A=on, B=on, C=off  (switches A and B were turned on)
A=on, B=off, C=on  (switches A and C were turned on)
A=off, B=on, C=on  (switches B and C were turned on)
Thus, we have 6 different combinations, which is the number 6 at row n=3 column k=2 in the sequence above.
(End)
From _Joerg Arndt_, May 04 2014: (Start)
There are T(4,2) = 10 subsets of {0, 1, 2, 3}:
01:    1...    { 0 }
02:    11..    { 0, 1 }
03:    111.    { 0, 1, 2 }
04:    11.1    { 0, 1, 3 }
05:    1.1.    { 0, 2 }
06:    1.11    { 0, 2, 3 }
07:    1..1    { 0, 3 }
08:    .1..    { 1 }
09:    .11.    { 1, 2 }
10:    .111    { 1, 2, 3 }
11:    .1.1    { 1, 3 }
12:    ..1.    { 2 }
13:    ..11    { 2, 3 }
14:    ...1    { 3 }
(End)

Susanne Wienand, Table of n, a(n) for n = 1..1830
Google code.jam, Problem C. Egg Drop
Sergei Viznyuk, C-Program
Sergei Viznyuk, Local copy of C-Program

Table[Sum[Binomial[n, m], {m, k}], {n, 10}, {k, n}] // Flatten (* Michael De Vlieger, Nov 25 2015 *)

tabl(nrows) = {for (n=1, nrows, for (k=1, n, print1(sum(m=1,k,binomial(n,m)), ", ");); print(););} \\ Michel Marcus, May 21 2013

a(n,1) = n ; a(n,n) = 2^n-1; a(n+1,k+1) = 1 + a(n,k) + a(n,k-1), 0 < k < n.

a(n,k) = sum(binomial(n,m),m=1..k), 1 <= k <= n. (see the running sum comment above). - Wolfdieter Lang, Feb 07 2013

A219091 a(n) = floor((n + 1/2)^8).

Original entry on oeis.org

0, 25, 1525, 22518, 168151, 837339, 3186448, 10011291, 27249052, 66342043, 147745544, 305902286, 596046447, 1103240376, 1954087550, 3331605615, 5493783665, 8796388244, 13720622866, 20906286173, 31191114176, 45657032334

Offset: 0

Clark Kimberling, Jan 01 2013

a(n) is the number k such that {k^p} < 1/2 < {(k+1)^p}, where p = 1/8 and { } = fractional part. Equivalently, the jump sequence of f(x) = x^(1/8), in the sense that these are the nonnegative integers k for which round(k^p) < round((k+1)^p). It appears that the sequence is linearly recurrent with order 23. Compare its signature with row 9 of the triangle at A008949. For which values of p is there a match of this sort between the jump sequence of x^p and row p+1 of the triangle?

For details and a guide to related sequences, see A219085.

Clark Kimberling, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (9, -37, 93, -163, 219, -247, 255, -256, 256, -256, 256, -256, 256, -256, 256, -255, 247, -219, 163, -93, 37, -9, 1).

Cf. A219085, A008949.

Mathematica
```
Table[Floor[(n + 1/2)^8], {n, 0, 100}]
```

A258483 Numbers n such that partial sums of the n-th row of Pascal's triangle (A007318) are all nonprime.

Original entry on oeis.org

0, 9, 29, 33, 34, 37, 38, 39, 41, 45, 49, 65, 67, 69, 73, 74, 77, 85, 86, 92, 97, 98, 101, 105, 113, 114, 115, 117, 118, 121, 129, 133, 134, 137, 139, 141, 145, 146, 151, 154, 155, 158, 160, 161, 164, 165, 170, 173, 177, 182, 185, 186, 193, 194, 195, 199, 202, 205, 206, 209, 213, 214, 225, 227, 229, 230, 234, 241, 247, 257, 258, 259, 261, 263, 265, 266, 269, 272, 273, 277, 281

Offset: 0

Vladimir Shevelev, May 31 2015

nonn

It appears that a(n) ~ c*n, as n goes to infinity, where c is constant < 2.17. For heuristic argument, see Robert Israel link.

Peter J. C. Moses, Table of n, a(n) for n = 0..2499
Robert Israel, Re: a surprising property, SeqFan list, Jun 01 2015.

Cf. A007318, A008949, A258126, A258127.

T:= <1>:
res:= 0:
for n from 1 to 1000 do
  T:= <1, T[1..-2] + T[2..-1], 2^n>;
  if not ormap(isprime,T) then res:= res, n fi
od:
res; # Robert Israel, Jun 04 2015

isok(n) = {my(s = 0); for (k=0, n, s += binomial(n, k); if (isprime(s), return (0))); return (1);} \\ Michel Marcus, May 31 2015

A303735 a(n) is the metric dimension of the n-dimensional hypercube.

Original entry on oeis.org

1, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 8, 8

Offset: 1

Manuel E. Lladser, Apr 29 2018

The metric dimension of a graph is the least number of nodes needed to characterize uniquely any other vertex by its vector of distances to those nodes. Determining the metric dimension of a general graph is a known NP-complete problem. It is not known, however, whether or not the metric dimension of hypercubes is NP-complete.
The nondecreasing sequence a(n) provides the metric dimension of the n-dimensional hypercube (i.e., with 2^n vertices) for 1 <= n <= 10, computed by brute force. Using an approximation algorithm, Mladenović et al. claim that the next seven terms in the sequence are 8, 8, 8, 9, 9, 10, 10.
Observation: first 11 terms coincide with A187103. - Omar E. Pol, Apr 29 2018 [updated by Pontus von Brömssen, Apr 06 2023]
Independent Verfication: Using the MaxSat solver RC2 (Ignatiev et al., 2019), and symmetry breaking constraints, I have verified the first 10 terms. In the previous references given, it is not clear which of the terms have been verified and which only have upper bounds verified. - Victor S. Miller, Mar 27 2023

			The metric dimension of a complete graph on n vertices (denoted as K_n) is (n - 1). For n = 1 the hypercube is isomorphic to K_2, so a(1)=1.
For n = 2, the hypercube has vertices (0,0), (0,1), (1,0), and (1,1), which form a simple cycle. Since each of these nodes has two other nodes at the same distance from it, a(2) >= 2. Using nodes (0,1) and (1,1) to encode all nodes by their distance to these two nodes, we find that (0,0) <-> (1,2); (0,1) <-> (0,1); (1,0) <-> (2,1); and (1,1) <-> (1,0). Since the vectors of distances (1,2), (0,1), (2,1), and (1,0) are all different, a(2) = 2.

Harary, F. and Melter, R. A. "On the metric dimension of a graph." Ars Combinatoria, 2:191-195 (1976).

Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silva, RC2: an efficient MaxSAT solver, Journal on Satisfiability, Boolean Modelling and Computation 11 (2019), 53-64; alternative link.
Lucas Laird, Richard C. Tillquist, Stephen Becker, and Manuel E. Lladser, Resolvability of Hamming Graphs, arXiv:1907.05974 [cs.DM], 2019.
N. Mladenović, J. Kratica, V. Kovačević-Vujcic, and M. Čangalović, Variable neighborhood search for metric dimension and minimal doubly resolving set problems, European Journal of Operational Research, 220:328-337 (2012).
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Metric Dimension

Cf. A008949 (number of vertices on the hypercube graph Q_n whose distance from a reference vertex is <= k).
Cf. A066051 (number of automorphisms of hypercubes).
Cf. A187103.

a(11) from Victor S. Miller, Apr 04 2023

a(12)-a(13) from Victor S. Miller, May 03 2023

A061290 Square array read by antidiagonals of T(n,k) = T(n-1,k) + T(n-1, floor(k/2)) with T(0,0)=1.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 0, 0, 3, 8, 0, 0, 1, 7, 16, 0, 0, 1, 4, 15, 32, 0, 0, 0, 4, 11, 31, 64, 0, 0, 0, 1, 11, 26, 63, 128, 0, 0, 0, 1, 5, 26, 57, 127, 256, 0, 0, 0, 1, 5, 16, 57, 120, 255, 512, 0, 0, 0, 1, 5, 16, 42, 120, 247, 511, 1024, 0, 0, 0, 0, 5, 16, 42, 99, 247, 502, 1023, 2048, 0, 0

Offset: 0

Henry Bottomley, May 22 2001

Row sums give 3^n.

			T(9,3) = T(8,3) + T(8,floor(3/2)) = T(8,3) + T(8,1) = 247 + 255 = 502. Rows start (1,0,0,0,0,...), (2,1,0,0,0,...), (4,3,1,1,0,...), (8,7,4,4,1,...), etc.

Row sums are A000244. Columns are A000079, A000225, A000295 twice, A002662 four times, A002663 eight times, A002664 sixteen times, A035038 thirty two times, etc.

T(n, k) = C(n, 0) + C(n, 1) + ... + C(n, n-ceiling(log_2(k+1))) = 2^n - C(n, 0) - C(n, 1) - ... - C(n, floor(log_2(k))) = A008949(n, n-A029837(k+1)) = A000079(n) - A008949(n, A000523(k)).

A102517 Expansion of (1+x^2)/((1-x+x^2)(1+2x^2)).

Original entry on oeis.org

1, 1, -1, -2, 1, 3, -2, -5, 5, 10, -11, -21, 22, 43, -43, -86, 85, 171, -170, -341, 341, 682, -683, -1365, 1366, 2731, -2731, -5462, 5461, 10923, -10922, -21845, 21845, 43690, -43691, -87381, 87382, 174763, -174763, -349526, 349525, 699051, -699050, -1398101, 1398101, 2796202, -2796203, -5592405

Offset: 0

Paul Barry, Jan 13 2005

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

Cf. A001045, A078008.

CoefficientList[Series[(1+x^2)/((1-x+x^2)(1+2x^2)),{x,0,50}],x] (* or *) LinearRecurrence[{1,-3,2,-2},{1,1,-1,-2},50] (* Harvey P. Dale, Oct 28 2011 *)

G.f.: (1+x^2)^2/((1+x^2)^3+x^6)+x(1+x^2)/((1+x^2)^3+x^6).
a(n) = Sum_{k=0..floor(n/2)} T(n-k, k)*(-1)^k, T(n, k) = Sum_{i=0..k} C(n, i) (A008949).
a(n) = (-1)^(n/2)*(Sum_{k=0..floor(n/6)} C(n/2, 3*k))*(1+(-1)^n)/2 + (-1)^((n-1)/2)*(Sum_{k=0..floor((n+1)/6)} C((n+1)/2, 3*k+1))*(1-(-1)^n)/2.
a(n) = 2^(n/2)*(cos(Pi*n/2)/3+sqrt(2)*sin(Pi*n/2)/3)+cos(Pi*n/3+Pi/3)/3+sqrt(3)*sin(Pi*n/3+Pi/3)/3.
a(2*n) = (-1)^n*A024493(n); a(2*n+1) = (-1)^n*A024494(n).
a(0)=1, a(1)=1, a(2)=-1, a(3)=-2, a(n) = a(n-1)-3*a(n-2)+2*a(n-3)-2*a(n-4). - Harvey P. Dale, Oct 28 2011

A167024 Triangle read by rows: T(n, m) = binomial(n, m)* Sum_{k=0..m} binomial(n, k) for 0 <= m <= n.

Original entry on oeis.org

1, 1, 2, 1, 6, 4, 1, 12, 21, 8, 1, 20, 66, 60, 16, 1, 30, 160, 260, 155, 32, 1, 42, 330, 840, 855, 378, 64, 1, 56, 609, 2240, 3465, 2520, 889, 128, 1, 72, 1036, 5208, 11410, 12264, 6916, 2040, 256, 1, 90, 1656, 10920, 32256, 48132, 39144, 18072, 4599, 512

Offset: 0

Roger L. Bagula, Oct 27 2009

Row sums are A032443(n).

			1,
1, 2,
1, 6, 4,
1, 12, 21, 8,
1, 20, 66, 60, 16,
1, 30, 160, 260, 155, 32,
1, 42, 330, 840, 855, 378, 64,
1, 56, 609, 2240, 3465, 2520, 889, 128,
1, 72, 1036, 5208, 11410, 12264, 6916, 2040, 256,
1, 90, 1656, 10920, 32256, 48132, 39144, 18072, 4599, 512,
1, 110, 2520, 21120, 81060, 160776, 178080, 116160, 45585, 10230, 1024

Muniru A Asiru, Rows n=0..100 of triangle, flattened

Cf. A008949, A032443.

t:=Flat(List([0..10],n->List([0..n],m->Binomial(n,m)*Sum([0..m],k->Binomial(n,k)))));; Print(t); # Muniru A Asiru, Dec 28 2018

T:=(n, m)-> binomial(n, m)*add(binomial(n, k), k=0..m): seq(seq(T(n, m), m=0..n), n=0..9); # Muniru A Asiru, Dec 28 2018

T[m_, n_] = If[m == 0 && n == 0, 1, Sum[Binomial[m, n]*Binomial[m, k], {k, 0, n}]]
Flatten[Table[Table[T[m, n], {n, 0, m}], {m, 0, 10}]]
T[n_,k_] := Binomial[n, k] (2^n - Binomial[n, k + 1] Hypergeometric2F1[1, 1 -n + k, k + 2, -1]); Table[T[n,k], {n,0,8}, {k,0,n}] // Flatten (* Peter Luschny, Dec 28 2018 *)

T(n, m) = binomial(n,m)*A008949(n,m). [Nov 03 2009]
G.f.: (1/x)*d(arctanh(N(x,y)))/dy, where N(x,y) is g.f. of Narayana numbers (A001263). - Vladimir Kruchinin, Apr 11 2018
T(n, k) = binomial(n, k)*(2^n - binomial(n, 1+k)*hypergeom([1, 1+k-n], [k+2], -1)). - Peter Luschny, Dec 28 2018

Introduced OEIS notational standards in the definition - The Assoc. Editors of the OEIS, Nov 05 2009

cp's OEIS Frontend

A110570 Triangle read by rows: T(n,0) = T(n,n) = 1 and for 0

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A112358 The following triangle is based on Pascal's triangle. The r-th term of the n-th row is sum of C(n,r) successive integers so that the sum of all the terms of the row is (2^n)*(2^n+1)/2, the 2^n -th triangular number. Sequence contains the triangle read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A112359 Product of n-th row of A112358.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Extensions

A117670 Triangle read by rows: partial sums of the Pascal triangle minus 1.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

Formula

A219091 a(n) = floor((n + 1/2)^8).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A258483 Numbers n such that partial sums of the n-th row of Pascal's triangle (A007318) are all nonprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

A303735 a(n) is the metric dimension of the n-dimensional hypercube.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A061290 Square array read by antidiagonals of T(n,k) = T(n-1,k) + T(n-1, floor(k/2)) with T(0,0)=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A102517 Expansion of (1+x^2)/((1-x+x^2)(1+2x^2)).