|
| |
|
|
A055248
|
|
Triangle of partial row sums of triangle A007318(n,m) (Pascal's triangle). Triangle A008949 read backwards. Riordan (1/(1-2x), x/(1-x)).
|
|
30
|
|
|
|
1, 2, 1, 4, 3, 1, 8, 7, 4, 1, 16, 15, 11, 5, 1, 32, 31, 26, 16, 6, 1, 64, 63, 57, 42, 22, 7, 1, 128, 127, 120, 99, 64, 29, 8, 1, 256, 255, 247, 219, 163, 93, 37, 9, 1, 512, 511, 502, 466, 382, 256, 130, 46, 10, 1, 1024, 1023, 1013, 968, 848, 638, 386, 176, 56, 11, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
In the language of the Shapiro et al. reference (also given in A053121) such a lower triangular (ordinary) convolution array, considered as matrix, belongs to the Riordan-group. The g.f. for the row polynomials p(n,x) (increasing powers of x) is 1/((1-2*z)*(1-x*z/(1-z))).
Binomial transform of the all 1's triangle: as a Riordan array, it factors to give (1/(1-x),x/(1-x))(1/(1-x),x). Viewed as a number square read by antidiagonals, it has T(n,k) = Sum_{j=0..n} binomial(n+k,n-j) and is then the binomial transform of the Whitney square A004070. - Paul Barry, Feb 03 2005
Read as a square array, this is the generalized Riordan array ( 1/(1 - 2*x), 1/(1 - x) ) as defined in the Bala link (p. 5), which factorizes as ( 1/(1 - x), x/(1 - x) )*( 1/(1 - x), x )*( 1, 1 + x ) = P*U*transpose(P), where P denotes Pascal's triangle, A007318, and U is the lower unit triangular array with 1's on or below the main diagonal. - Peter Bala, Jan 13 2016
|
|
|
LINKS
|
Norman Lindquist and Gerard Sierksma, Extensions of set partitions, Journal of Combinatorial Theory, Series A 31.2 (1981): 190-198. See Table I.
L. W. Shapiro, S. Getu, Wen-Jin Woan and L. C. Woodson, The Riordan Group, Discrete Appl. Maths. 34 (1991) 229-239.
|
|
|
FORMULA
|
a(n, m) = A008949(n, n-m), if n > m >= 0.
a(n, m) = Sum_{k=m..n} A007318(n, k) (partial row sums in columns m).
Column m recursion: a(n, m) = Sum_{j=m..n-1} a(j, m) + A007318(n, m) if n >= m >= 0, a(n, m) := 0 if n<m.
G.f. for column m: (1/(1-2*x))*(x/(1-x))^m, m >= 0.
a(n, m) = Sum_{j=0..n} binomial(n, m+j). - Paul Barry, Feb 03 2005
Exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(8 + 7*x + 4*x^2/2! + x^3/3!) = 8 + 15*x + 26*x^2/2! + 42*x^3/3! + 64*x^4/4! + .... The same property holds more generally for Riordan arrays of the form ( f(x), x/(1 - x) ).
Let M denote the present triangle. For k = 0,1,2,... define M(k) to be the lower unit triangular block array
/I_k 0\
\ 0 M/ having the k X k identity matrix I_k as the upper left block; in particular, M(0) = M. The infinite product M(0)*M(1)*M(2)*..., which is clearly well-defined, is equal to A143494 (but with a different offset). See the Example section. Cf. A106516. (End)
a(n,m) = Sum_{p=m..n} 2^(n-p)*binomial(p-1,m-1), n >= m >= 0, else 0. - Wolfdieter Lang, Jan 09 2015
T(n, k) = 2^n - (1/2)*binomial(n, k-1)*hypergeom([1, n+1], [n-k+2], 1/2). - Peter Luschny, Oct 10 2019
T(n, k) = binomial(n, k)*hypergeom([1, k - n], [k + 1], -1). - Peter Luschny, Oct 06 2023
|
|
|
EXAMPLE
|
The triangle a(n,m) begins:
n\m 0 1 2 3 4 5 6 7 8 9 10 ...
0: 1
1: 2 1
2: 4 3 1
3: 8 7 4 1
4: 16 15 11 5 1
5: 32 31 26 16 6 1
6: 64 63 57 42 22 7 1
7: 128 127 120 99 64 29 8 1
8: 256 255 247 219 163 93 37 9 1
9: 512 511 502 466 382 256 130 46 10 1
10: 1024 1023 1013 968 848 638 386 176 56 11 1
Fourth row polynomial (n=3): p(3,x)= 8 + 7*x + 4*x^2 + x^3.
The matrix inverse starts
1;
-2, 1;
2, -3, 1;
-2, 5, -4, 1;
2, -7, 9, -5, 1;
-2, 9, -16, 14, -6, 1;
2, -11, 25,- 30, 20, -7, 1;
-2, 13, -36, 55, -50, 27, -8, 1;
2, -15, 49, -91, 105, -77, 35, -9, 1;
-2, 17, -64, 140, -196, 182, -112, 44, -10, 1;
2, -19, 81, -204, 336, -378, 294, -156, 54, -11, 1;
...
With the array M(k) as defined in the Formula section, the infinite product M(0)*M(1)*M(2)*... begins
/1 \ /1 \ /1 \ /1 \
|2 1 ||0 1 ||0 1 | |2 1 |
|4 3 1 ||0 2 1 ||0 0 1 |... = |4 5 1 |
|8 7 4 1 ||0 4 3 1 ||0 0 2 1 | |8 19 9 1 |
|... ||0 8 7 4 1 ||0 0 4 3 1| |... |
|... ||... ||... | | |
Matrix factorization of square array as P*U*transpose(P):
/1 \ /1 \ /1 1 1 1 ...\ /1 1 1 1 ...\
|1 1 ||1 1 ||0 1 2 3 ... | |2 3 4 5 ... |
|1 2 1 ||1 1 1 ||0 0 1 3 ... | = |4 7 11 16 ... |
|1 3 3 1 ||1 1 1 1 ||0 0 0 1 ... | |8 15 26 42 ... |
|... ||... ||... | |... |
|
|
|
MAPLE
|
T := (n, k) -> 2^n - (1/2)*binomial(n, k-1)*hypergeom([1, n + 1], [n-k + 2], 1/2).
seq(seq(simplify(T(n, k)), k=0..n), n=0..10); # Peter Luschny, Oct 10 2019
|
|
|
MATHEMATICA
|
a[n_, m_] := Sum[ Binomial[n, m + j], {j, 0, n}]; Table[a[n, m], {n, 0, 10}, {m, 0, n}] // Flatten (* Jean-François Alcover, Jul 05 2013, after Paul Barry *)
T[n_, k_] := Binomial[n, k] * Hypergeometric2F1[1, k - n, k + 1, -1];
Flatten[Table[T[n, k], {n, 0, 7}, {k, 0, n}]] (* Peter Luschny, Oct 06 2023 *)
|
|
|
PROG
|
(Haskell)
a055248 n k = a055248_tabl !! n !! k
a055248_row n = a055248_tabl !! n
a055248_tabl = map reverse a008949_tabl
|
|
|
CROSSREFS
|
Column sequences: A000079 (powers of 2, m=0), A000225 (m=1), A000295 (m=2), A002662 (m=3), A002663 (m=4), A002664 (m=5), A035038 (m=6), A035039 (m=7), A035040 (m=8), A035041 (m=9), A035042 (m=10).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
