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

1, 1, 1, 1, 3, 1, 1, 5, 7, 1, 1, 7, 17, 15, 1, 1, 9, 31, 49, 31, 1, 1, 11, 49, 111, 129, 63, 1, 1, 13, 71, 209, 351, 321, 127, 1, 1, 15, 97, 351, 769, 1023, 769, 255, 1, 1, 17, 127, 545, 1471, 2561, 2815, 1793, 511, 1, 1, 19, 161, 799, 2561, 5503, 7937, 7423, 4097, 1023, 1

Offset: 0

Author

Reinhard Zumkeller, May 11 2006

Keywords

• nonn
• tabl
• easy

Comments

From Richard M. Green, Jul 26 2011: (Start)

T(n,n-k) is the (k-1)-st Betti number of the subcomplex of the n-dimensional half cube obtained by deleting the interiors of all half-cube shaped faces of dimension at least k.

T(n,n-k) is the (k-2)-nd Betti number of the complement of the k-equal real hyperplane arrangement in R^n.

T(n,n-k) gives a lower bound for the complexity of the problem of determining, given n real numbers, whether some k of them are equal.

T(n,n-k) is the number of nodes used by the Kronrod-Patterson-Smolyak cubature formula in numerical analysis. (End)

Examples

			Triangle begins as:
  1;
  1, 1;
  1, 3,  1;
  1, 5,  7,  1;
  1, 7, 17, 15,  1;
  1, 9, 31, 49, 31, 1;
		

Links

• Reinhard Zumkeller, Rows n=0..120 of triangle, flattened
• A. Björner and V. Welker, The homology of "k-equal" manifolds and related partition lattices, Adv. Math., 110 (1995), 277-313.
• Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO], 2023.
• R. M. Green, Homology representations arising from the half cube, Adv. Math., 222 (2009), 216-239.
• R. M. Green, Homology representations arising from the half cube, II, J. Combin. Theory Ser. A, 117 (2010), 1037-1048.
• R. M. Green, Homology representations arising from the half cube, II, arXiv:0812.1208 [math.RT], 2008.
• R. M. Green and Jacob T. Harper, Morse matchings on polytopes, arXiv preprint arXiv:1107.4993 [math.GT], 2011.
• OEIS Wiki, Sequence of the Day for November 3.
• K. Petras, On the Smolyak cubature error for analytic functions, Adv. Comput. Math., 12 (2000), 71-93.
• M. Shattuck and T. Waldhauser, Proofs of some binomial identities using the method of last squares, Fib. Q., 48 (2010), 290-297.
• M. Shattuck and T. Waldhauser, Proofs of some binomial identities using the method of last squares, arXiv:1107.1063 [math.CO], 2010.
• Index entries for triangles and arrays related to Pascal's triangle

Crossrefs

Cf. A119259, A007318, A007051, A005408, A056220, A027608, A055580, A000337, A000225, A112857 (row reverse).

A145661, A119258 and A118801 are all essentially the same (see the Shattuck and Waldhauser paper). - Tamas Waldhauser, Jul 25 2011

Programs

Haskell

a119258 n k = a119258_tabl !! n !! k
a119258_row n = a119258_tabl !! n
a119258_list = concat a119258_tabl
a119258_tabl = iterate (\row -> zipWith (+)
   ([0] ++ init row ++ [0]) $ zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Nov 15 2011

Magma

function T(n,k)
  if k eq 0 or k eq n then return 1;
  else return 2*T(n-1,k-1) + T(n-1,k);
  end if;
  return T;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Nov 18 2019

Maple

# Case m = 2 of the more general:
A119258 := (n,k,m) -> (1-m)^(-n+k)-m^(k+1)*pochhammer(n-k, k+1) *hypergeom([1,n+1],[k+2],m)/(k+1)!;
seq(seq(round(evalf(A119258(n,k,2))),k=0..n), n=0..10); # Peter Luschny, Jul 25 2014

Mathematica

T[n_, k_] := Binomial[n, k] Hypergeometric2F1[-k, n-k, n-k+1, -1];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 10 2017 *)

PARI

T(n,k) = if(k==0 || k==n, 1, 2*T(n-1, k-1) + T(n-1,k) ); \\ G. C. Greubel, Nov 18 2019

Sage

@CachedFunction
def T(n, k):
    if (k==0 or k==n): return 1
    else: return 2*T(n-1, k-1) + T(n-1, k)
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Nov 18 2019

Formula

T(2*n,n-1) = T(2*n-1,n) for n > 0;

central terms give A119259; row sums give A007051;

T(n,0) = T(n,n) = 1;

T(n,1) = A005408(n-1) for n > 0;

T(n,2) = A056220(n-1) for n > 1;

T(n,n-4) = A027608(n-4) for n > 3;

T(n,n-3) = A055580(n-3) for n > 2;

T(n,n-2) = A000337(n-1) for n > 1;

T(n,n-1) = A000225(n) for n > 0.

T(n,k) = [k<=n]*(-1)^k*Sum_{i=0..k} (-1)^i*C(k-n,k-i)*C(n,i). - Paul Barry, Sep 28 2007

From Richard M. Green, Jul 26 2011: (Start)

T(n,k) = [k<=n] Sum_{i=n-k..n} (-1)^(n-k-i)*2^(n-i)*C(n,i).

T(n,k) = [k<=n] Sum_{i=n-k..n} C(n,i)*C(i-1,n-k-1).

G.f. for T(n,n-k): x^k/(((1-2x)^k)*(1-x)). (End)

T(n,k) = R(n,k,2) where R(n, k, m) = (1-m)^(-n+k)-m^(k+1)*Pochhammer(n-k,k+1)* hyper2F1([1,n+1], [k+2], m)/(k+1)!. - Peter Luschny, Jul 25 2014

From Peter Bala, Mar 05 2018: (Start)

The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 + 2*x)^n/(1 + x) about 0. For example, for n = 4 we have (1 + 2*x)^4/(1 + x) = 1 + 7*x + 17*x^2 + 15*x^3 + x^4 + O(x^5).

Row reverse of A112857. (End)