login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004070 Table of Whitney numbers W(n,k) read by antidiagonals, where W(n,k) is maximal number of pieces into which n-space is sliced by k hyperplanes, n >= 0, k >= 0. 25
1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 4, 1, 1, 2, 4, 7, 5, 1, 1, 2, 4, 8, 11, 6, 1, 1, 2, 4, 8, 15, 16, 7, 1, 1, 2, 4, 8, 16, 26, 22, 8, 1, 1, 2, 4, 8, 16, 31, 42, 29, 9, 1, 1, 2, 4, 8, 16, 32, 57, 64, 37, 10, 1, 1, 2, 4, 8, 16, 32, 63, 99, 93, 46, 11, 1, 1, 2, 4, 8, 16, 32, 64, 120, 163 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

As a number triangle, this is given by T(n,k)=sum{j=0..n, C(n,j)(-1)^(n-j)sum{i=0..j, C(j+k,i-k)}}. - Paul Barry, Aug 23 2004

As a number triangle, this is the Riordan array (1/(1-x), x(1+x)) with T(n,k)=sum{i=0..n, binomial(k,i-k)}. Diagonal sums are then A023434(n+1). - Paul Barry, Feb 16 2005

Form partial sums across rows of square array of binomial coefficients A026729; see also A008949. - Philippe Deléham, Aug 28 2005

Square array A026729 -> Partial sums across rows

1 0 0 0 0 0 0 . . . . 1 1 1 1 1 1 1 . . . . . .

1 1 0 0 0 0 0 . . . . 1 2 2 2 2 2 2 . . . . . .

1 2 1 0 0 0 0 . . . . 1 3 4 4 4 4 4 . . . . . .

1 3 3 1 0 0 0 . . . . 1 4 7 8 8 8 8 . . . . . .

For other Whitney numbers see A007799.

W(n,k) is the number of length k binary sequences containing no more than n 1's. - Geoffrey Critzer, Mar 15 2010

From Emeric Deutsch, Jun 15 2010: (Start)

Viewed as a number triangle, T(n,k) is the number of internal nodes of the Fibonacci tree of order n+2 at level k. A Fibonacci tree of order n (n>=2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node.

(End)

REFERENCES

D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417. [Emeric Deutsch, Jun 15 2010]

LINKS

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

Gustav Burosch, Hans-Dietrich O.F. Gronau, Jean-Marie Laborde, Ingo Warnke, On posets of m-ary words, Discrete Math.152 (1996), no. 1-3, 69--91. MR1388633 (97e:06002)

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

Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178. [From Emeric Deutsch, Jun 15 2010]

R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 233

FORMULA

W(n, k) = Sum_{i=0..n} binomial(k, i). - Bill Gosper

W(n, k) = if k=0 or n=0 then 1 else W(n, k-1)+W(n-1, k-1). - David Broadhurst, Jan 05 2000

The table W(n,k) = A000012 * A007318(transform), where A000012 = (1; 1,1; 1,1,1;...). - Gary W. Adamson, Nov 15 2007

E.g.f. for row n: (1 + x + x^2/2! + ... + x^n/n!)* exp(x). - Geoffrey Critzer, Mar 15 2010

G.f.: 1 / (1 - x - x*y*(1 - x^2)) = Sum_{0 <= k <= n} x^n * y^k * T(n, k). - Michael Somos, May 31 2016

W(n, n) = 2^n. - Michael Somos, May 31 2016

EXAMPLE

Table W(n,k) begins:

  1 1 1 1  1  1  1 ...

  1 2 3 4  5  6  7 ...

  1 2 4 7 11 16 22 ...

  1 2 4 8 15 26 42 ... - Michael Somos, Apr 28 2000

W(2,4) = 11 because there are 11 length 4 binary sequences containing no more than 2 1's: {0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 0}, {0, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}, {0, 1, 1, 0}, {1, 0, 0, 0}, {1, 0, 0, 1}, {1, 0, 1, 0}, {1, 1, 0, 0}. - Geoffrey Critzer, Mar 15 2010

Table T(n, k) begins:

  1

  1  1

  1  2  1

  1  2  3  1

  1  2  4  4  1

  1  2  4  7  5  1

  1  2  4  8 11  6  1

... - Michael Somos, May 31 2016

MATHEMATICA

Transpose[ Table[Table[Sum[Binomial[n, k], {k, 0, m}], {m, 0, 15}], {n, 0, 15}]] // Grid (* Geoffrey Critzer, Mar 15 2010 *)

T[ n_, k_] := Sum[ Binomial[n, j] (-1)^(n - j) Sum[ Binomial[j + k, i - k], {i, 0, j}], {j, 0, n}]; (* Michael Somos, May 31 2016 *)

PROG

(PARI) /* array read by antidiagonals up coordinate index functions */

t1(n) = binomial(floor(3/2 + sqrt(2+2*n)), 2) - (n+1); /* A025581 */

t2(n) = n - binomial(floor(1/2 + sqrt(2+2*n)), 2); /* A002262 */

/* define the sequence array function for A004070 */

W(n, k) = sum(i=0, n, binomial(k, i));

/* visual check ( origin 0, 0 ) */

printp(matrix(7, 7, n, k, W(n-1, k-1)));

/* print the sequence entries by antidiagonals going up ( origin 0, 0 ) */

print1("S A004070 "); for(n=0, 32, print1(W(t1(n), t2(n))", "));

print1("T A004070 "); for(n=33, 61, print1(W(t1(n), t2(n))", "));

print1("U A004070 "); for(n=62, 86, print1(W(t1(n), t2(n))", ")); /* Michael Somos, Apr 28 2000 */

CROSSREFS

Cf. A007799.

Rows converge to powers of two (A000079). Subdiagonals include A000225, A000295, A002662, A002663, A002664, A035038, A035039, A035040, A035041, A035042. Antidiagonal sums are A000071.

Rows are: A000012, A000027, A000124, A000125, A000127, A006261, A008859, A008860, A008861, A008862, A008863. - Geoffrey Critzer, Mar 15 2010

Cf. A178522, A178524. - Emeric Deutsch, Jun 15 2010

Sequence in context: A104763 A027751 A181322 * A180562 A199711 A048887

Adjacent sequences:  A004067 A004068 A004069 * A004071 A004072 A004073

KEYWORD

tabl,nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Larry Reeves (larryr(AT)acm.org), Mar 20 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 13:38 EDT 2018. Contains 316361 sequences. (Running on oeis4.)