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
Examples
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 ...
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
...
References
- Donald E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
Links
- 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.
- 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.
Crossrefs
Programs
-
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 *) -
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
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)
Extensions
More terms from Larry Reeves (larryr(AT)acm.org), Mar 20 2000
Comments