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.

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

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)

Named after the American mathematician Hassler Whitney (1907-1989). - Amiram Eldar, Jun 13 2021

References

Donald 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 and Ingo Warnke, On posets of m-ary words, Discrete Math., Vol. 152, No. 1-3 (1996), pp. 69-91. MR1388633 (97e:06002)

Matteo Cervetti and Luca Ferrari, Pattern avoidance in the matching pattern poset, arXiv:2009.01024 [math.CO], 2020.

Matteo Cervetti and Luca Ferrari, Enumeration of Some Classes of Pattern Avoiding Matchings, with a Glimpse into the Matching Pattern Poset, Annals of Combinatorics (2022).

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

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

Robin Pemantle and Mark C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., Vol. 50, No. 2 (2008), pp. 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

From Jianing Song, May 30 2022: (Start)

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

T(n, k) = Sum_{m=0..n-k} binomial(k, m).

T(n,k) = 2^k for 0 <= k <= floor(n/2). (End)

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 */
(PARI) T(n, k)=sum(m=0, n-k, binomial(k, m)) \\ Jianing Song, May 30 2022

Crossrefs

Cf. A007799. As a triangle, mirror A052509.

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