|
%I #80 Sep 14 2022 16:52:08
%S 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,
%T 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,
%U 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
%N 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.
%C 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
%C 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
%C Form partial sums across rows of square array of binomial coefficients A026729; see also A008949. - _Philippe Deléham_, Aug 28 2005
%C Square array A026729 -> Partial sums across rows
%C 1 0 0 0 0 0 0 . . . . 1 1 1 1 1 1 1 . . . . . .
%C 1 1 0 0 0 0 0 . . . . 1 2 2 2 2 2 2 . . . . . .
%C 1 2 1 0 0 0 0 . . . . 1 3 4 4 4 4 4 . . . . . .
%C 1 3 3 1 0 0 0 . . . . 1 4 7 8 8 8 8 . . . . . .
%C For other Whitney numbers see A007799.
%C W(n,k) is the number of length k binary sequences containing no more than n 1's. - _Geoffrey Critzer_, Mar 15 2010
%C From _Emeric Deutsch_, Jun 15 2010: (Start)
%C 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.
%C (End)
%C Named after the American mathematician Hassler Whitney (1907-1989). - _Amiram Eldar_, Jun 13 2021
%D Donald E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417. [_Emeric Deutsch_, Jun 15 2010]
%H Gustav Burosch, Hans-Dietrich O.F. Gronau, Jean-Marie Laborde and Ingo Warnke, <a href="http://dx.doi.org/10.1016/0012-365X(94)00256-I">On posets of m-ary words</a>, Discrete Math., Vol. 152, No. 1-3 (1996), pp. 69-91. MR1388633 (97e:06002)
%H Matteo Cervetti and Luca Ferrari, <a href="https://arxiv.org/abs/2009.01024">Pattern avoidance in the matching pattern poset</a>, arXiv:2009.01024 [math.CO], 2020.
%H Matteo Cervetti and Luca Ferrari, <a href="https://doi.org/10.1007/s00026-022-00596-1">Enumeration of Some Classes of Pattern Avoiding Matchings, with a Glimpse into the Matching Pattern Poset</a>, Annals of Combinatorics (2022).
%H Richard K. Guy, <a href="/A003271/a003271.pdf">Letter to N. J. A. Sloane, Apr 1975</a>.
%H Yasuichi Horibe, <a href="http://www.fq.math.ca/Scanned/20-2/horibe.pdf">An entropy view of Fibonacci trees</a>, Fibonacci Quarterly, Vol. 20, No. 2 (1982), pp. 168-178. [From _Emeric Deutsch_, Jun 15 2010]
%H Robin Pemantle and Mark C. Wilson, <a href="http://dx.doi.org/10.1137/050643866">Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., Vol. 50, No. 2 (2008), pp. 199-272. See p. 233.
%F W(n, k) = Sum_{i=0..n} binomial(k, i). - _Bill Gosper_
%F 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
%F The table W(n,k) = A000012 * A007318(transform), where A000012 = (1; 1,1; 1,1,1; ...). - _Gary W. Adamson_, Nov 15 2007
%F E.g.f. for row n: (1 + x + x^2/2! + ... + x^n/n!)* exp(x). - _Geoffrey Critzer_, Mar 15 2010
%F 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
%F W(n, n) = 2^n. - _Michael Somos_, May 31 2016
%F From _Jianing Song_, May 30 2022: (Start)
%F 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.
%F T(n, k) = Sum_{m=0..n-k} binomial(k, m).
%F T(n,k) = 2^k for 0 <= k <= floor(n/2). (End)
%e Table W(n,k) begins:
%e 1 1 1 1 1 1 1 ...
%e 1 2 3 4 5 6 7 ...
%e 1 2 4 7 11 16 22 ...
%e 1 2 4 8 15 26 42 ... - _Michael Somos_, Apr 28 2000
%e 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
%e Table T(n, k) begins:
%e 1
%e 1 1
%e 1 2 1
%e 1 2 3 1
%e 1 2 4 4 1
%e 1 2 4 7 5 1
%e 1 2 4 8 11 6 1
%e ... - _Michael Somos_, May 31 2016
%t Transpose[ Table[Table[Sum[Binomial[n, k], {k, 0, m}], {m, 0, 15}], {n, 0, 15}]] // Grid (* _Geoffrey Critzer_, Mar 15 2010 *)
%t 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 *)
%o (PARI) /* array read by antidiagonals up coordinate index functions */
%o t1(n) = binomial(floor(3/2 + sqrt(2+2*n)), 2) - (n+1); /* A025581 */
%o t2(n) = n - binomial(floor(1/2 + sqrt(2+2*n)), 2); /* A002262 */
%o /* define the sequence array function for A004070 */
%o W(n, k) = sum(i=0, n, binomial(k, i));
%o /* visual check ( origin 0,0 ) */
%o printp(matrix(7, 7, n, k, W(n-1, k-1)));
%o /* print the sequence entries by antidiagonals going up ( origin 0,0 ) */
%o print1("S A004070 "); for(n=0, 32, print1(W(t1(n), t2(n))","));
%o print1("T A004070 "); for(n=33, 61, print1(W(t1(n), t2(n))","));
%o print1("U A004070 "); for(n=62, 86, print1(W(t1(n), t2(n))",")); /* _Michael Somos_, Apr 28 2000 */
%o (PARI) T(n, k)=sum(m=0, n-k, binomial(k, m)) \\ _Jianing Song_, May 30 2022
%Y Cf. A007799. As a triangle, mirror A052509.
%Y Rows converge to powers of two (A000079). Subdiagonals include A000225, A000295, A002662, A002663, A002664, A035038, A035039, A035040, A035041, A035042. Antidiagonal sums are A000071.
%Y Rows are: A000012, A000027, A000124, A000125, A000127, A006261, A008859, A008860, A008861, A008862, A008863. - _Geoffrey Critzer_, Mar 15 2010
%Y Cf. A178522, A178524. - _Emeric Deutsch_, Jun 15 2010
%K tabl,nonn,easy,nice
%O 0,5
%A _N. J. A. Sloane_
%E More terms from Larry Reeves (larryr(AT)acm.org), Mar 20 2000
|
