0,6

T(n,k) is the number of subsets of {1,2,...,n-1} of size k and containing no consecutive integers. Example: T(6,2)=6 because the subsets of size 2 of {1,2,3,4,5} with no consecutive integers are {1,3},{1,4},{1,5},{2,4},{2,5} and {3,5}. Equivalently, T(n,k) is the number of k-matchings of the path graph P_n. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 10 2003

T(n,k)= number of compositions of n+2 into k+1 parts, all >=2. Example: T(6,2)=6 because we have (2,2,4),(2,4,2),(4,2,2),(2,3,3),(3,2,3) and (3,3,2). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Apr 09 2005

Given any recurrence sequence S(k) = x*a(k-1) + a(k-2), starting (1, x, x^2+1,...); the (k+1)-th term of the series = f(x) in the k-th degree polynomial: (1, (x), (x^2 + 1), (x^3 + 2x), (x^4 + 3x^2 + 1), (x^5 + 4x^3 + 3x), (x^6 + 5x^4 + 6x^2 + 1),...Example: let x = 2, then S(k) = 1, 2, 5, 12, 29, 70, 169,...such that A000129(7) = 169 = f(x), x^6 + 5x^4 + 6x^2 + 1 = (64 + 80 + 24 + 1). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 16 2008

Row k gives the nonzero coefficients of U(k,x/2) where U is the Chebychev polynomial of the second kind. For example, row 6 is 1,5,6,1 and U(6,x/2) = x^6 - 5x^4 + 6x^2 - 1. - David Callan (callan(AT)stat.wisc.edu), Jul 22 2008

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 141ff.

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 91, 145.

C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.

A. Holme, A combinatorial proof ..., Discrete Math., 241 (2001), 363-378; see p. 375.

C.-K. Lim and K. S. Lam, The characteristic polynomial of ladder graphs and an annihilating uniqueness theorem, Discr. Math., 151 (1996), 161-167.

D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, Vol. A 99 (2002), 307-344 (Table 3).

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 182-183 [From Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Feb 20 2009]

T. D. Noe, Rows n=0..100 of triangle, flattened

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 26, ex. 12.

Index entries for triangles and arrays related to Pascal's triangle

Let F(n, x) be the n-th Fibonacci polynomial in x; the g.f. for F(n, x) is sum_{n=0..inf} F(n, x)*y^n = (1 + x*y)/(1 - y - x*y^2). - Paul D. Hanna (pauldhanna(AT)juno.com)

T(m, n) = 0 for n /= 0 and m <= 1 T(0, 0) = T(1, 0) = 1 T(m, n) = T(m - 1, n) + T(m-2, n-1) for m >= 2 (i.e. like the recurrence for Pascal's triangle A007318, but going up one row as well as left one column for the second summand). E.g. T(7, 2) = 10 = T(6, 2) + T(5, 1) = 6 + 4 - Rob Arthan (rda(AT)lemma-one.com), Sep 22 2003

G.f. for k-th column: x^(2k-1)/(1-x)^(k+1).

Identities for the Fibonacci polynomials F(n, x):

F(m+n+1, x) = F(m+1, x)*F(n+1, x) + x*F(m, x)F(n, x).

F(n, x)^2-F(n-1, x)*F(n+1, x)=(-x)^(n-1).

The degree of F(n, x) is floor((n-1)/2) and F(2p, x) = F(p, x) times a polynomial of equal degree which is 1 mod p.

Contribution from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Feb 20 2009: (Start)

p(x,n)=Sum[Binomial[n - m + 1, m]*x^m, {m, 0, Floor[(n + 1)/2]}];

p(x,n)=p(x, n - 1) + x*p(x, n - 2) (End)

{1}; {1}; {1,1}; {1,2}; {1,3,1}; {1,4,3}; {1,5,6,1}; {1,6,10,4}, ...

The first few Fibonacci polynomials (defined here by F(0,x) = 0, F(1,x) = 1; F(n+1, x) = F(n, x) + x*F(n-1, x)) are:

0: 0

1: 1

2: 1

3: 1 + x

4: 1 + 2 x

5: 1 + 3 x + x^2

6: (1 + x) (1 + 3 x)

7: 1 + 5 x + 6 x^2 + x^3

8: (1 + 2 x) (1 + 4 x + 2 x^2 )

9: (1 + x) (1 + 6 x + 9 x^2 + x^3 )

10: (1 + 3 x + x^2 ) (1 + 5 x + 5 x^2 )

11: 1 + 9 x + 28 x^2 + 35 x^3 + 15 x^4 + x^5

Contribution from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Feb 20 2009: (Start)

{1},

{1, 1},

{1, 2},

{1, 3, 1},

{1, 4, 3},

{1, 5, 6, 1},

{1, 6, 10, 4},

{1, 7, 15, 10, 1},

{1, 8, 21, 20, 5},

{1, 9, 28, 35, 15, 1},

{1, 10, 36, 56, 35, 6},

{1, 11, 45, 84, 70, 21, 1},

{1, 12, 55, 120, 126, 56, 7} (End)

a := proc(n) local k; [ seq(binomial(n-k, k), k=0..floor(n/2)) ]; end;

Contribution from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Feb 20 2009: (Start)

(* first: sum method*);

Table[CoefficientList[Sum[Binomial[n - m + 1, m]*x^m, {m, 0, Floor[(n + 1)/2]}], x], {n, 0, 12}]

(*second: polynomial recursion method*)

Clear[L, p, x, n, m];

L[x, 0] = 1; L[x, 1] = 1 + x;

L[x_, n_] := L[x, n - 1] + x*L[x, n - 2];

Table[ExpandAll[L[x, n]], {n, 0, 10}];

Table[CoefficientList[ExpandAll[L[x, n]], x], {n, 0, 12}];

Flatten[%] (End)

(PARI) T(n, k)=if(k<0|k>n, 0, binomial(n-k, k))

Row sums = A000045(n+1) (Fibonacci numbers).

Cf. A054123.

Cf. A000129.

Sequence in context: A166556 A143318 A122610 this_sequence A115139 A124033 A112543

Adjacent sequences: A011970 A011971 A011972 this_sequence A011974 A011975 A011976

tabf,easy,nonn,nice

N. J. A. Sloane (njas(AT)research.att.com).