A169803 - OEIS

This site is supported by donations to The OEIS Foundation.

A169803

Triangle read by rows: T(n,k) = binomial(n+1-k,k) (n >= 0, 0 <= k <= n).

1, 1, 1, 1, 2, 0, 1, 3, 1, 0, 1, 4, 3, 0, 0, 1, 5, 6, 1, 0, 0, 1, 6, 10, 4, 0, 0, 0, 1, 7, 15, 10, 1, 0, 0, 0, 1, 8, 21, 20, 5, 0, 0, 0, 0, 1, 9, 28, 35, 15, 1, 0, 0, 0, 0, 1, 10, 36, 56, 35, 6, 0, 0, 0, 0, 0, 1, 11, 45, 84, 70, 21, 1, 0, 0, 0, 0, 0, 1, 12, 55, 120, 126, 56, 7, 0, 0, 0 (list; table; graph; refs; listen; history; text; internal format)

	OFFSET	`0,5`
	COMMENTS	`T(n,k) = 0 if k <0 or k > n+1-k.` `T(n,k) is the number of binary vectors of length n and weight k containing no pair of adjacent 1's.` `Take Pascal's triangle A007318 and push the k-th column downwards by 2k-1 places (k>=1).` `Row sums are A000045.` `From Emanuele Munarini, May 24 2011: (Start)` `Diagonal sums are A000930(n+1).` `A sparse subset (or scattered subset) of {1,2,...,n} is a subset never containg two consecutive elements. T(n,k) is the number of sparse subsets of {1,2,...,n} having size k. For instance, for n=4 and k=2 we have the 3 sparse 2-subsets of {1,2,3,4}: 13, 14, 24. (End)` `As a triangle, row 2n-1 consists of the coefficients of Morgan-Voyce polynomial B(n,x), A172431, and row 2n to the coefficients of Morgan-Voyce polynomial b(n,x), A054142.`
	REFERENCES	`E. Munarini, N. Zagaglia Salvi, Scattered Subsets, Discrete Mathematics 267 (2003), 213-228.` `E. Munarini, N. Zagaglia Salvi, On the Rank Polynomial of the Lattice of Order Ideals of Fences and Crowns, Discrete Mathematics 259 (2002), 163-177.` `E. Munarini, A combinatorial interpretation of the Chebyshev polynomials, SIAM Journal on Discrete Mathematics, Volume 20, Issue 3 (2006), 649-655.`
	LINKS	`Table of n, a(n) for n=0..87.`
	EXAMPLE	`Triangle begins:` `[1]` `[1, 1]` `[1, 2, 0]` `[1, 3, 1, 0]` `[1, 4, 3, 0, 0]` `[1, 5, 6, 1, 0, 0]` `[1, 6, 10, 4, 0, 0, 0]` `[1, 7, 15, 10, 1, 0, 0, 0]` `[1, 8, 21, 20, 5, 0, 0, 0, 0]` `[1, 9, 28, 35, 15, 1, 0, 0, 0, 0]` `[1, 10, 36, 56, 35, 6, 0, 0, 0, 0, 0]` `[1, 11, 45, 84, 70, 21, 1, 0, 0, 0, 0, 0]` `[1, 12, 55, 120, 126, 56, 7, 0, 0, 0, 0, 0, 0]` `[1, 13, 66, 165, 210, 126, 28, 1, 0, 0, 0, 0, 0, 0]` `[1, 14, 78, 220, 330, 252, 84, 8, 0, 0, 0, 0, 0, 0, 0]` `[1, 15, 91, 286, 495, 462, 210, 36, 1, 0, 0, 0, 0, 0, 0, 0]` `[1, 16, 105, 364, 715, 792, 462, 120, 9, 0, 0, 0, 0, 0, 0, 0, 0]` `[1, 17, 120, 455, 1001, 1287, 924, 330, 45, 1, 0, 0, 0, 0, 0, 0, 0, 0]` `[1, 18, 136, 560, 1365, 2002, 1716, 792, 165, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0]` `[1, 19, 153, 680, 1820, 3003, 3003, 1716, 495, 55, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]` `[1, 20, 171, 816, 2380, 4368, 5005, 3432, 1287, 220, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]` `...`
	PROG	`(Maxima) create_list(binomial(n-k+1, k), n, 0, 20, k, 0, n); [Emanuele Munarini, May 24 2011]` `(PARI) T(n, k)=binomial(n+1-k, k) \\ Charles R Greathouse IV, Oct 24 2012`
	CROSSREFS	`Cf. A007318, A011973 (another version), A000045.` `All of A011973, A092865, A098925, A102426, A169803 describe essentially the same triangle in different ways. - N. J. A. Sloane, May 29 2011.` `A172431 and A054142 describe the odd and even lines of the triangle.` `Sequence in context: A165317 A174067 A124943 * A099557 A214576 A079217` `Adjacent sequences: A169800 A169801 A169802 * A169804 A169805 A169806`
	KEYWORD	`nonn,tabl`
	AUTHOR	`Nadia Heninger and N. J. A. Sloane, May 21 2010`
	STATUS	`approved`

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

Last modified June 19 16:47 EDT 2013. Contains 226415 sequences.