|
| |
|
|
A011973
|
|
Triangle of numbers {C(n-k,k), n >= 0, 0<=k<=[ n/2 ]}; or, triangle of coefficients of (one version of) Fibonacci polynomials.
|
|
39
| |
|
|
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; 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 (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
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. - DELEHAM Philippe, Dec 12 2011
Riordan array (1/(1-x),x^2/(1-x) .- DELEHAM Philippe, Dec 12 2011
|
|
|
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 [From Roger L. Bagula (rlbagulatftn(AT)yahoo.com), 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.
|
|
|
LINKS
| K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of binomial trees and Fibonacci trees, arXiv:0910.4432
T. D. Noe, Rows n=0..100 of triangle, flattened
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 (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)
|
|
|
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
Contribution from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), 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
|
|
|
MAPLE
| a := proc(n) local k; [ seq(binomial(n-k, k), k=0..floor(n/2)) ]; end;
|
|
|
MATHEMATICA
| 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)
|
|
|
PROG
| (PARI) T(n, k)=if(k<0|k>n, 0, binomial(n-k, k))
|
|
|
CROSSREFS
| Row sums = A000045(n+1) (Fibonacci numbers).
Cf. A000129, A054123. See A169803 for another version.
All of A011973, A092865, A098925, A102426, A169803 describe essentially the same triangle in different ways. - N. J. A. Sloane, May 29 2011.
Cf. A052553. - DELEHAM Philippe, Dec 12 2011
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 (njas(AT)research.att.com).
|
| |
|
|
