%I A011973
%S A011973 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,
%T A011973 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,
%U A011973 13,66,165,210,126,28,1,1,14,78,220,330,252,84,8,1,15,91,286,495,462
%N A011973 Triangle of numbers {C(n-k,k), n >= 0, 0<=k<=[ n/2 ]}; or, triangle of 
               coefficients of (one version of) Fibonacci polynomials.
%C A011973 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
%C A011973 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
%C A011973 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
%C A011973 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
%D A011973 A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of 
               combinatorial proof, M.A.A. 2003, p. 141ff.
%D A011973 A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci 
               Association, San Jose, CA, 1972, p. 91, 145.
%D A011973 C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
%D A011973 A. Holme, A combinatorial proof ..., Discrete Math., 241 (2001), 363-378; 
               see p. 375.
%D A011973 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 A011973 D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. 
               Combin. Theory, Vol. A 99 (2002), 307-344 (Table 3).
%D A011973 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 
               182-183 [From Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Feb 20 
               2009]
%H A011973 T. D. Noe, <a href="b011973.txt">Rows n=0..100 of triangle, flattened</
               a>
%H A011973 H. S. Wilf, <a href="http://www.math.upenn.edu/~wilf/DownldGF.html">Generatingfunctionology</
               a>, 2nd edn., Academic Press, NY, 1994, p. 26, ex. 12.
%H A011973 <a href="Sindx_Pas.html#Pascal">Index entries for triangles and arrays 
               related to Pascal's triangle</a>
%F A011973 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)
%F A011973 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
%F A011973 G.f. for k-th column: x^(2k-1)/(1-x)^(k+1).
%F A011973 Identities for the Fibonacci polynomials F(n, x):
%F A011973 F(m+n+1, x) = F(m+1, x)*F(n+1, x) + x*F(m, x)F(n, x).
%F A011973 F(n, x)^2-F(n-1, x)*F(n+1, x)=(-x)^(n-1).
%F A011973 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.
%F A011973 Contribution from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Feb 20 
               2009: (Start)
%F A011973 p(x,n)=Sum[Binomial[n - m + 1, m]*x^m, {m, 0, Floor[(n + 1)/2]}];
%F A011973 p(x,n)=p(x, n - 1) + x*p(x, n - 2) (End)
%e A011973 {1}; {1}; {1,1}; {1,2}; {1,3,1}; {1,4,3}; {1,5,6,1}; {1,6,10,4}, ...
%e A011973 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:
%e A011973 0: 0
%e A011973 1: 1
%e A011973 2: 1
%e A011973 3: 1 + x
%e A011973 4: 1 + 2 x
%e A011973 5: 1 + 3 x + x^2
%e A011973 6: (1 + x) (1 + 3 x)
%e A011973 7: 1 + 5 x + 6 x^2 + x^3
%e A011973 8: (1 + 2 x) (1 + 4 x + 2 x^2 )
%e A011973 9: (1 + x) (1 + 6 x + 9 x^2 + x^3 )
%e A011973 10: (1 + 3 x + x^2 ) (1 + 5 x + 5 x^2 )
%e A011973 11: 1 + 9 x + 28 x^2 + 35 x^3 + 15 x^4 + x^5
%e A011973 Contribution from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Feb 20 
               2009: (Start)
%e A011973 {1},
%e A011973 {1, 1},
%e A011973 {1, 2},
%e A011973 {1, 3, 1},
%e A011973 {1, 4, 3},
%e A011973 {1, 5, 6, 1},
%e A011973 {1, 6, 10, 4},
%e A011973 {1, 7, 15, 10, 1},
%e A011973 {1, 8, 21, 20, 5},
%e A011973 {1, 9, 28, 35, 15, 1},
%e A011973 {1, 10, 36, 56, 35, 6},
%e A011973 {1, 11, 45, 84, 70, 21, 1},
%e A011973 {1, 12, 55, 120, 126, 56, 7} (End)
%p A011973 a := proc(n) local k; [ seq(binomial(n-k,k),k=0..floor(n/2)) ]; end;
%t A011973 Contribution from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Feb 20 
               2009: (Start)
%t A011973 (* first: sum method*);
%t A011973 Table[CoefficientList[Sum[Binomial[n - m + 1, m]*x^m, {m, 0, Floor[(n 
               + 1)/2]}], x], {n, 0, 12}]
%t A011973 (*second: polynomial recursion method*)
%t A011973 Clear[L, p, x, n, m];
%t A011973 L[x, 0] = 1; L[x, 1] = 1 + x;
%t A011973 L[x_, n_] := L[x, n - 1] + x*L[x, n - 2];
%t A011973 Table[ExpandAll[L[x, n]], {n, 0, 10}];
%t A011973 Table[CoefficientList[ExpandAll[L[x, n]], x], {n, 0, 12}];
%t A011973 Flatten[%] (End)
%o A011973 (PARI) T(n,k)=if(k<0|k>n,0,binomial(n-k,k))
%Y A011973 Row sums = A000045(n+1) (Fibonacci numbers).
%Y A011973 Cf. A054123.
%Y A011973 Cf. A000129.
%Y A011973 Sequence in context: A166556 A143318 A122610 this_sequence A115139 A124033 
               A112543
%Y A011973 Adjacent sequences: A011970 A011971 A011972 this_sequence A011974 A011975 
               A011976
%K A011973 tabf,easy,nonn,nice
%O A011973 0,6
%A A011973 N. J. A. Sloane (njas(AT)research.att.com).