A008288 / Delannoy-numbers
Gottfried Helms
Annette.Warlich at t-online.de
Sun Aug 28 14:13:22 CEST 2005
Seqfans -
Rereading a posting dated 02.10.2000 07:35 of Fred W. Helenius:
subject: Re: City-block volume in N dimensions
newsgroup: sci.math
where he also referenced the sequence A008288
Table of delannoy-numbers: Table(A008288 )
A:
| 1 1 1 1 1 |
| 1 3 5 7 9 |
| 1 5 13 25 41 |
| 1 7 25 63 129 |
| 1 9 41 129 321 |
The cholesky-decomposition B of matrix(A) has an interesting pattern:
B :
| 1 0 0 0 0 |
| 1 1.41421 0 0 0 |
| 1 2.82842 2 0 0 |
| 1 4.24264 6 2.82842 0 |
| 1 5.65685 12 11.3137 4 |
where the diagonal entries are powers of the square-root of 2.
If I divide B by that diagonal, then
C = B * inv(diag(B))
C:
| 1 0 0 0 0 |
| 1 1 0 0 0 |
| 1 2 1 0 0 |
| 1 3 3 1 0 |
| 1 4 6 4 1 |
which is the "binomial" or "pascal"-array.
nrows*(nrows-1)/2
This also means, that det(A) = 2
In turn, A could be computed from the binomial-array multiplied
by diag(powers-of-sqrt(2))
Gottfried Helms
--------------------------------
Appended:
* OEIS-Entry
* Posting of Fred W. Helenius
> ID Number: A008288
> URL: http://www.research.att.com/projects/OEIS?Anum=A008288
> Sequence: 1,1,1,1,3,1,1,5,5,1,1,7,13,7,1,1,9,25,25,9,1,1,11,41,63,41,
> 11,1,1,13,61,129,129,61,13,1,1,15,85,231,321,231,85,15,1,1,
> 17,113,377,681,681,377,113,17,1,1,19,145,575,1289,1683,1289,
> 575,145,19,1,1,21,181,833,2241,3653,3653
> Name: Square array of Delannoy numbers D(i,j) (i >= 0, j >= 0) read by
> antidiagonals.
> Comments: D(n, k) is the number of k-matchings of a comb-like graph with n+k teeth.
> Example: D(1, 3)=7 because the graph consisting of a horizontal path
> ABCD and the teeth Aa, Bb, Cc, Dd has seven 3-matchings: four triples of
> three teeth and the three triples {Aa, Bb, CD}, {Aa, Dd, BC}, {Cc, Dd,
> AB}. Also D(3, 1)=7, the 1-matchings of the same graph being the seven
> edges: {AB}, {BC}, {CD}, {Aa}, {Bb}, {Cc}, {Dd}. - Emeric Deutsch
> (deutsch(AT)duke.poly.edu), Jul 01 2002
> Sum of n-th row = A000129(n). - Reinhard Zumkeller
> (reinhard.zumkeller(AT)lhsystems.com), Dec 03 2004
(...)
> Formula: D(n,0) = 1 = D(0,n) for n >= 0; D(n,k) = D(n,k-1) + D(n-1,k-1) +
> D(n-1,k).
> Sum_{n >= 0, k >= 0} D(n,k)*x^n*y^k = 1/(1-x-y-x*y).
> D(n,k) = Sum_{d} binomial(k,d)*binomial(n+k-d,k) = Sum_{d}
> 2^d*binomial(n,d)*binomial(k,d).
> Seen as a triangle read by rows: T(n,0)=T(n,n)=1 for n>=0 and
> T(n,k)=T(n-1,k-1)+T(n-2,k-1)+T(n-1,k), 0<k<n and n>1. -
> Reinhard Zumkeller (reinhard.zumkeller(AT)lhsystems.com), Dec 03
> 2004
> Read as a number triangle, this is the Riordan array
> (1/(1-x),x(1+x)/(1-x)) with T(n,k)=sum{j=0..n-k,
> C(n-k,j)C(k,j)2^j}. - Paul Barry (pbarry(AT)wit.ie), Jul 18 2005
> Example: Square array D(i,j) begins:
> 1 1 1 1 1 1 1 1
> 1 3 5 7 9 11 13 ...
> 1 5 13 25 41 61 ...
> 1 7 25 63 129 231 ...
> 1 9 41 129 321 681 ...
> Maple: A008288 := proc(n,k) option remember; if n = 1 then 1; elif k = 1 then 1;
> else A008288(n-1,k-1)+A008288(n,k-1)+A008288(n-1,k); fi; end;
> read transforms; SERIES2(1/(1-x-y-x*y),x,y,12):
> SERIES2TOLIST(%,x,y,12);
> See also: Sums of antidiagonals = A000129 (Pell numbers), D(n, n) = A001850
> (Delannoy numbers), (T(n, 3)) = A001845, (T(n, 4)) = A001846, etc. See
> also A027618. Rows and diagonals give A001844-A001850. Cf. A059446.
> Has same main diagonal as A064861. Different from A100936.
> Cf. A101164, A101167.
> Adjacent sequences: A008285 A008286 A008287 this_sequence A008289
> A008290 A008291
> Sequence in context: A109128 A103450 A026714 this_sequence A106597
> A108359 A100936
(...)
> Extension: Expanded description from Clark Kimberling 6/97. Additional
> references from Sylviane R. Schwer
> (schwer(AT)lipn.univ-paris13.fr), Nov 28 2001.
> I have changed the notation to make the formulae more precise. - njas,
> Jul 01, 2002
--------------------------------------------------------------------------------
Am 02.10.00 07:35 schrieb Fred W. Helenius:
> Andrew Morse <morse4 at prodigy.net> wrote:
>
>
>>Define the "hypersphere of radius R" as the set of
>>hypercubes that can be reached in R steps or fewer making only
>>traversals between hypercubes which share an entire hyperedge(?).
>>Define the hypervolume of the hypershpere of radius R as the number
>>of hypercubes in the hypersphere of radius R, including the hypercube at the
>>origin.
>
>
>> Given these definitions,
>> In 1-dimension,
>> The hypershpere of radius 1 has a hypervolume of 3.
>> The hypersphere of radius 2 has a hypervolume of 5.
>> The hypersphere of radius 3 has a hypervolume of 7...
>> In 2-dimensions,
>> The hypershpere of radius 1 has a hypervolume of 5.
>> The hypersphere of radius 2 has a hypervolume of 13.
>> The hypersphere of radius 3 has a hypervolume of 25...
>> In 3-dimensions,
>> The hypershpere of radius 1 has a hypervolume of 7.
>> The hypersphere of radius 2 has a hypervolume of 25.
>> The hypersphere of radius 3 has a hypervolume of 62...
>
>
> That last should be 63.
>
>
>> What is the relationship between radius and city-block hypervolume
>>for N-dimensions?
>
>
> Including radius zero and dimension zero, these numbers form a nice
> symmetric table:
>
> 1 1 1 1 1 ...
> 1 3 5 7 9 ...
> 1 5 13 25 41 ...
> 1 7 25 63 129 ...
> 1 9 41 129 321 ...
> : : : : :
>
>>From the table or the definition, you can see that
> V(n,r) = V(n,r-1) + V(n-1,r-1) + V(n-1,r), with V(n,0) = V(0,r) = 1.
> Solving this recurrence one dimension at a time yields
>
> V(0,r) = 1,
> V(1,r) = 2r + 1,
> V(2,r) = 2r^2 - 2r + 1,
> V(3,r) = (4r^3 + 6r^2 + 8r + 3)/3, etc.
>
> For a fixed n, V(n,r) is an nth degree polynomial in r with leading
> coefficient 2^n/n! .
>
> Neil Sloane's On-Line Encyclopedia of Integer Sequences calls these
> numbers the Delannoy triangle, and lists them, with references, at
> http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=008288
>
> Each row of the table is also called the "crystal ball sequence for
> the n-dimensional cubic lattice". Some additional references appear
> in their entries for dimensions 3 through 10, see for example
> http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001848
> They turn out to have very simple generating functions.
>
>
(...)
----------------------------------------------------------------------
More information about the SeqFan
mailing list