login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A011973 Triangle of numbers {C(n-k,k), n >= 0, 0<=k<=[ n/2 ]}; or, triangle of coefficients of (one version of) Fibonacci polynomials. 53
1, 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, 1, 13, 66, 165, 210, 126, 28, 1, 1, 14, 78, 220, 330, 252, 84, 8, 1, 15, 91, 286, 495, 462 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

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, 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, 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, Apr 16 2008

Row k gives the nonzero coefficients of U(k,x/2) where U is the Chebyshev 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, Jul 22 2008

T(n,k) is the number of nodes at level k in the Fibonacci tree f(k-1). The Fibonacci trees f(k) of order k are defined as follows: 1. f(-1) and f(0) each consist of a single node. 2. For k>=1, to the root of f(k-1), taken as the root of f(k), we attach with a rightmost edge the tree f(k-2). See the Iyer and Reddy references. These trees are not the same as the Fibonacci trees in A180566.Example: T(3,0)=1 and T(3,1)=2 because in f(2) = /\ we have 1 node at level 0 and 2 nodes at level 1. - Emeric Deutsch, Jume 21, 2011

Triangle, with zeros omitted, given by (1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2011

Riordan array (1/(1-x),x^2/(1-x). - Philippe Deléham, Dec 12 2011

This sequence is the elements on the rising diagonals of the Pascal triangle, where the sum of the elements in each rising diagonal represents a Fibonacci number. - Mohammad K. Azarian, Mar 08 2012

If we set F(0;x) = 0, F(1;x) = 1, F(n+1;x) = x*F(n;x) + F(n-1;x), then we obtain the sequence of Vieta-Fibonacci polynomials discussed by Gary W. Adamson above. We note that F(n;x) = (-i)^n * U(n;i*x/2), where U denotes the respective Chebyshev polynomial of the second kind (see David Callan's remark above). Let us fix a,b,f(0),f(1) in C, b is not the zero, and set f(n) = a*f(n-1) + b*f(n-2). Then we deduce the relation: f(n) = b^((n-1)/2) * F(n;a/sqrt(b))*f(1) + b^(n/2) * F(n-1;a/sqrt(b))*f(0), where for a given value of the complex root sqrt(b) we set b^(n/2) = (sqrt(b))^n. Moreover, if b=1 then we get f(n+k) + (-1)^k * f(n-k) = L(k;a)*f(n), for every k=0,1,...,n, and where L(0;a)=2, L(1;a)=a, L(n+1;a)=a*L(n;a) + L(n-1;a) are the Vieta-Lucas polynomials. Let us observe that L(n+2;a) = F(n+2;a) + F(n;a), L(m+n;a) = L(m;a)*F(n;a) + L(m-1;a)*F(n-1;a), which implies also L(n+1;a) = a*F(n;a) + 2*F(n-1;a). Further we have L(n;a) = 2*(-i)^n * T(n;i*x/2), where T(n;x) denotes the n-th Chebyshev polynomial of the first kind. For the proofs, other relations and facts - see Witula-Slota's papers. - Roman Witula, Oct 12 2012

The diagonal sums of this triangle are A000930. - John Molokach, Jul 04 2013

REFERENCES

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 - Roger L. Bagula, Feb 20 2009

K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of binomial trees and Fibonacci trees, Int'l. J. Math. Engin. with Comp., Accepted for publication, Sept. 2009.

R. Witula and D. Slota, Conjugate sequences in a Fibonacci-Lucas sense and some identities for sums of powers of their elements, Integers: Electronic Journal of Combinatorial Number Theory, 7 (2007), #A08.

R. Witula and D. Slota, On modified Chebyshev polynomials, J. Math. Anal. Appl., 324 (2006), 321-343.

LINKS

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

M. Barnabei, F. Bonetti, S. Elizalde, M. Silimbani, Descent sets on 321-avoiding involutions and hook decompositions of partitions, arXiv preprint arXiv:1401.3011, 2014

J. Bodeen, S. Butler, T. Kim, X. Sun, S. Wang, Tiling a strip with triangles, El. J. Combinat. 21 (1) (2014) P1.7

E. J. Farrell, An introduction to matching polynomials, J. Comb. Theory B 27 (1) (1979) 75-86, Table 1.

K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of binomial trees and Fibonacci trees, arXiv:0910.4432

Dennis Walsh, Notes on subsets of {1,2,...,n} that contain no consecutive integers.

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

FORMULA

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

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, Sep 22 2003

G.f. for k-th column: x^(2*k-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.

From Roger L. Bagula, 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)

T(n, k) = A102541(2*n+2, 2*k+1) + A102541(2*n+1, 2*k) - A102541(2*n+3, 2*k+1), n >= 0 and 0 <= k <= floor(n/2). - Johannes W. Meijer, Aug 26 2013

G.f.: 1/(1-x-y*x^2) = R(0)/2, where R(k) = 1 + 1/(1 - (2*k+1+ x*y)*x/((2*k+2+ x*y)*x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Nov 09 2013

EXAMPLE

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

From Roger L. Bagula, Feb 20 2009: (Start)

1;

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)

For n=9 and k=4, T(9,4)=C(5,4)=5 since there are exactly five size-4 subsets of {1,2,...,8} that contain no consecutive integers, namely, {1,3,5,7}, {1,3,5,8}, {1,3,6,8}, {1,4,6,8}, and {2,4,6,8}. - Dennis P. Walsh, Mar 31 2011

When the rows of the triangle are displayed as centered text, the falling diagonal sums are A005314. The first few terms are row1 = 1 = 1; row2 = 1+1 = 2; row3 = 2+1 = 3; row4 = 1+3+1 = 5; row5 = 1+3+4+1 = 9; row6 = 4+6+5+1 = 16; row7 = 1+10+10+6+1 = 28; row8 = 1+5+20+15+7+1 = 49; row9 = 6+15+35+21+8+1 = 86; row10 = 1+21+35+56+28+9+1 = 151. - John Molokach, Jul 08 2013

MAPLE

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

T := proc(n, k): if k<0 or k>floor(n/2) then return(0) fi: binomial(n-k, k) end: seq(seq(T(n, k), k=0..floor(n/2)), n=0..15); - Johannes W. Meijer, Aug 26 2013

MATHEMATICA

(* first: sum method *) Table[CoefficientList[Sum[Binomial[n - m + 1, m]*x^m, {m, 0, Floor[(n + 1)/2]}], x], {n, 0, 12}] (* Roger L. Bagula, Feb 20 2009 *)

(* 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[%] (* Roger L. Bagula, Feb 20 2009 *)

(* Center option shows falling diagonals are A224838 *) Column[Table[Binomial[n - m, m], {n, 0, 25}, {m, 0, Floor[n/2]}], Center] (* John Molokach, Jul 26 2013 *)

Table[ Select[ CoefficientList[ Fibonacci[n, x], x], Positive] // Reverse, {n, 1, 18} ] // Flatten (* Jean-François Alcover, Oct 21 2013 *)

PROG

(PARI) {T(n, k) = if( k<0 || 2*k>n, 0, binomial(n-k, k))}

(Sage) # Prints the table; cf. A145574.

for n in (2..20): [Compositions(n, length=m, min_part=2).cardinality() for m in (1..n//2)]  # Peter Luschny, Oct 18 2012

CROSSREFS

Row sums = A000045(n+1) (Fibonacci numbers). - Michael Somos, Apr 02 1999

Cf. A000129, A054123, A052553, A000930.

All of A011973, A092865, A098925, A102426, A169803 describe essentially the same triangle in different ways.

Sequence in context: A166556 A143318 A122610 * A115139 A198788 A112543

Adjacent sequences:  A011970 A011971 A011972 * A011974 A011975 A011976

KEYWORD

tabf,easy,nonn,nice

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 2 10:42 EDT 2014. Contains 246353 sequences.