login
T(n,k) = binomial(n-floor((k+1)/2), floor(k/2)). Triangle read by rows, for 0 <= k <= n.
74

%I #153 Aug 18 2024 19:05:30

%S 1,1,1,1,1,1,1,1,2,1,1,1,3,2,1,1,1,4,3,3,1,1,1,5,4,6,3,1,1,1,6,5,10,6,

%T 4,1,1,1,7,6,15,10,10,4,1,1,1,8,7,21,15,20,10,5,1,1,1,9,8,28,21,35,20,

%U 15,5,1,1,1,10,9,36,28,56,35,35,15,6,1,1,1,11,10,45,36,84,56,70,35,21,6,1

%N T(n,k) = binomial(n-floor((k+1)/2), floor(k/2)). Triangle read by rows, for 0 <= k <= n.

%C Also the q-Stirling2 numbers at q = -1. - _Peter Luschny_, Mar 09 2020

%C Row sums give the Fibonacci sequence. So do the alternating row sums.

%C Triangle of coefficients of polynomials defined by p(-1,x) = p(0,x) = 1, p(n, x) = x*p(n-1, x) + p(n-2, x), for n >= 1. - _Benoit Cloitre_, May 08 2005 [rewritten with correct offset. - _Wolfdieter Lang_, Feb 18 2020]

%C Another version of triangle in A103631. - _Philippe Deléham_, Jan 01 2009

%C The T(n,k) coefficients appear in appendix 2 of Parks's remarkable article "A new proof of the Routh-Hurwitz stability criterion using the second method of Liapunov" if we assume that the b(n) coefficients are all equal to 1 and ignore the first column. The complete version of this triangle including the first column is A103631. - _Johannes W. Meijer_, Aug 11 2011

%C Signed ++--++..., the roots are chaotic using f(x) --> x^2 - 2 with cycle lengths shown in A003558 by n-th rows. Example: given row 3, x^3 + x^2 - 2x - 1; the roots are (a = 1.24697, ...; b = -0.445041, ...; c = -1.802937, ...). Then (say using seed b with x^2 - 2) we obtain the trajectory -0.445041, ... -> -1.80193, ... -> 1.24697, ...; matching the entry "3" in A003558(3). - _Gary W. Adamson_, Sep 06 2011

%C From _Gary W. Adamson_, Aug 25 2019: (Start)

%C Roots to the polynomials and terms in A003558 can all be obtained from the numbers below using a doubling series mod N procedure as follows: (more than one row may result). Any row ends when the trajectory produces a term already used. Then try the next higher odd term not used as the leftmost term, then repeat.

%C For example, for N = 11, we get: (1, 2, 4, 3, 5), showing that when confronted with two choices after the 4: (8 and -3), pick the smaller (abs) term, = 3. Then for the next row pick 7 (not used) and repeat the algorithm; succeeding only if the trajectory produces new terms. But 7 is also (-4) mod 11 and 4 was used. Therefore what I call the "r-t table" (for roots trajectory) has only one row: (1, 2, 4, 3, 5). Conjecture: The numbers of terms in the first row is equal to A003558 corresponding to N, i.e., 5 in this case with period 2.

%C Now for the roots to the polynomials. Pick N = 7. The polynomial is x^3 - x^2 - 2x + 1 = 0, with roots 1.8019..., -1.2469... and 0.445... corresponding to 2*cos(j*Pi/N), N = 7, and j = (1, 2, and 3). The terms (1, 2, 3) are the r-t terms for N = 7. For 11, the r-t terms are (1, 2, 4, 3, 5). This implies that given any roots of the corresponding polynomial, they are cyclic using f(x) --> x^2 - 2 with cycle lengths shown in A003558. The terms thus generated are 2*cos(j*Pi), with j = (1, 2, 4, 3, 5). Check: Begin with 2*j*Pi/N, with j = 1 (1.9189...). The other trajectory terms are: --> 1.6825..., --> 0.83083..., -1.3097...; 545...; (a 5 period and cyclic since we can begin with any of the constants). The r-t table for odd N begins as follows:

%C 3...............1

%C 5...............1, 2

%C 7...............1, 2, 3

%C 9...............1, 2, 4

%C ...............3 (singleton terms reduce to "1") (9 has two rows)

%C 11...............1, 2, 4, 3, 5

%C 13...............1, 2, 4, 5, 3, 6

%C 15...............1, 2, 4, 7

%C ................3, 6 (dividing through by the gcd gives (1, 2))

%C ................5. (singleton terms reduce to "1")

%C The result is that 15 has 3 factors (since 3 rows), and the values of those factors are the previous terms "N", corresponding to the r-t terms in each row. Thus, the first row is new, the second (1, 2), corresponds to N = 5, and the "1" in row 3 corresponds to N = 3. The factors are those values apart from 15 and 1. Note that all of the unreduced r-t terms in all rows for N form a complete set of the terms 1 through (N-1)/2 without duplication. (End)

%C From _Gary W. Adamson_, Sep 30 2019: (Start)

%C The 3 factors of the 7th degree polynomial for 15: (x^7 - x^6 - 6x^5 + 5x^4 + 10x^3 - 6x^2 - 4x + 1) can be determined by getting the roots for 2*cos(j*Pi/1), j = (1, 2, 4, 7) and finding the corresponding polynomial, which is x^4 + x^3 - 4x^2 - 4x + 1. This is the minimal polynomial for N = 15 as shown in Table 2, p. 46 of (Lang). The degree of this polynomial is 4, corresponding to the entry in A003558 for 15, = 4. The trajectories (3, 6) and (5) are j values for 2*cos(j*Pi/15) which are roots to x^2 - x - 1 (relating to the pentagon), and (x - 1), relating to the triangle. (End)

%C From _Gary W. Adamson_, Aug 21 2019: (Start)

%C Matrices M of the form: (1's in the main diagonal, -1's in the subdiagonal, and the rest zeros) are chaotic if we replace (f(x) --> x^2 - 2) with f(x) --> M^2 - 2I, where I is the Identity matrix [1, 0, 0; 0, 1, 0; 0, 0, 1]. For example, with the 3 X 3 matrix M: [0, 0, 1; 0, 1, -1; 1, -1, 0]; the f(x) trajectory is:

%C ....M^2 - 2I: [-1, -1, 0; -1, 0, -1; 0, -1, 0], then for the latter,

%C ....M^2 - 2I: [0, 1, 1; 1, 0, 0; 1, 0, -1]. The cycle ends with period 3 since the next matrix is (-1) * the seed matrix. As in the case with f(x) --> x^2 - 2, the eigenvalues of the 3 chaotic matrices are (abs) 1.24697, 0.44504... and 1.80193, ... Also, the characteristic equations of the 3 matrices are the same as or variants of row 4 of the triangle below: (x^3 + x - 2x - 1) with different signs. (End)

%C Received from _Herb Conn_, Jan 2004: (Start)

%C Let x = 2*cos(2A) (A = Angle); then

%C sin(A)/sin A = 1

%C sin(3A)/sin A = x + 1

%C sin(5A)/sin A = x^2 + x - 1

%C sin(7A)/sin A = x^3 + x - 2x - 1

%C sin(9A)/sin A = x^4 + x^3 - 3x^2 - 2x + 1

%C ... (signed ++--++...). (End)

%C Or Pascal's triangle (A007318) with duplicated diagonals. Also triangle of coefficients of polynomials defined by P_0(x) = 1 and for n>=1, P_n(x) = F_n(x) + F_(n+1)(x), where F_n(x) is Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} C(n-i-1,i)*x^(n-2*i-1). - _Vladimir Shevelev_, Apr 12 2012

%C The matrix inverse is given by

%C 1;

%C 1, 1;

%C 0, -1, 1;

%C 0, 1, -2, 1;

%C 0, 0, 1, -2, 1;

%C 0, 0, -1, 3, -3, 1;

%C 0, 0, 0, -1, 3, -3, 1;

%C 0, 0, 0, 1, -4, 6, -4, 1;

%C 0, 0, 0, 0, 1, -4, 6, -4, 1;

%C ... apart from signs the same as A124645. - _R. J. Mathar_, Mar 12 2013

%H Nathaniel Johnston, <a href="/A065941/b065941.txt">Rows 0..100, flattened</a>

%H Leonard E. Dickson, <a href="https://doi.org/10.2307/2967797">The Inscription of Regular Polygons</a>, The American Mathematical Monthly, Vol. 1, No. 9 (Sep., 1894), pp. 299-301.

%H Henry W. Gould, <a href="http://www.fq.math.ca/Scanned/3-4/gould.pdf"> A Variant of Pascal's Triangle </a>, The Fibonacci Quarterly, Vol. 3, Nr. 4, Dec. 1965, p. 257-271, with <a href="http://www.fq.math.ca/Scanned/4-1/corrections2.pdf">corrections</a>.

%H A. F. Horadam, R. P. Loh and A. G. Shannon, <a href="https://doi.org/10.1007/BFb0102684">Divisibility properties of some Fibonacci-type sequences</a>, pp. 55-64 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979. See Table 4.

%H A. F. Horadam, R. P. Loh and A. G. Shannon, <a href="/A005013/a005013.pdf">Divisibility properties of some Fibonacci-type sequences</a>, pp. 55-64 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979. [Annotated scanned copy]

%H Jay Kappraff, <a href="https://doi.org/10.1142/4767">Beyond Measure, A Guided Tour Through Nature, Myth and Number</a>, World Scientific, 2002; p. 490.

%H Jay Kappraff, S. Jablan, G. W. Adamson, and R. Sazdanovich, <a href="https://www.researchgate.net/publication/228848220">Golden Fields, Generalized Fibonacci Sequences, and Chaotic Matrices</a>, FORMA, Vol. 19, No. 4, 2005.

%H Jay Kappraff and Gary W. Adamson, Polygons and Chaos, <a href="http://www.tarupublications.com/journals/jdsgt/contents-of-published-issues.htm">Journal of Dynamical Systems and Geometric Theories</a>, Vol 2 (2004), p 65.

%H Thomas Koshy, <a href="https://doi.org/10.1002/9781118033067">Fibonacci and Lucas Numbers with Applications</a>, John Wiley and Sons, 2001 (Chapter 14)

%H E. Munarini and N. Z. Salvi, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s49zagaglia.html">Binary strings without zigzags</a>, Séminaire Lotharingien de Combinatoire, B49h (2004), 15 pp.

%H Wolfdieter Lang, <a href="http://arxiv.org/abs/1210.1018">The field Q(2cos(pi/n)), its Galois group and length ratios in the regular n-gon</a>, arXiv:1210.1018 [math.GR], 2012-2017.

%H P.C. Parks, <a href="http://dx.doi.org/10.1017/S030500410004072X"> A new proof of the Routh-Hurwitz stability criterion using the second method of Liapunov </a>, Math. Proc. of the Cambridge Philosophical Society, Vol. 58, Issue 04 (1962) p. 694-702.

%H P. Steinbach, <a href="http://www.jstor.org/stable/2691048">Golden fields: a case for the heptagon</a>, Math. Mag. 70 (1997), no. 1, 22-31.

%H <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>

%F T(n, k) = binomial(n-floor((k+1)/2), floor(k/2)).

%F As a square array read by antidiagonals, this is given by T1(n, k) = binomial(floor(n/2) + k, k). - _Paul Barry_, Mar 11 2003

%F Triangle is a reflection of that in A066170 (absolute values). - _Gary W. Adamson_, Feb 16 2004

%F Recurrences: T(k, 0) = 1, T(k, n) = T(k-1, n) + T(k-2, n-2), or T(k, n) = T(k-1, n) + T(k-1, n-1) if n even, T(k-1, n-1) if n odd. - _Ralf Stephan_, May 17 2004

%F G.f.: sum[n, sum[k, T(k, n)x^ky^n]] = (1+xy)/(1-y-x^2y^2). sum[n>=0, T(k, n)y^n] = y^k/(1-y)^[k/2]. - _Ralf Stephan_, May 17 2004

%F T(n, k) = A108299(n, k)*A087960(k) = abs(A108299(n, k)). - _Reinhard Zumkeller_, Jun 01 2005

%F From _Johannes W. Meijer_, Aug 11 2011: (Start)

%F T(n,k) = A046854(n, n-k) = abs(A066170(n, n-k)).

%F T(n+k, n-k) = A109223(n,k).

%F T(n, k) = sum(T(j, k-2), j=k-2..n-2), 2 <= k <= n, n>=2;

%F T(n, 0) =1, T(n+1, 1) = 1, n >= 0. (End)

%F For n > 1: T(n, k) = T(n-2, k) + T(n-1, k), 1 < k < n. - _Reinhard Zumkeller_, Apr 24 2013

%e Triangle T(n, k) begins:

%e n\k 0 1 2 3 4 5 6 7 8 9 ...

%e ---------------------------------------

%e [0] 1,

%e [1] 1, 1,

%e [2] 1, 1, 1,

%e [3] 1, 1, 2, 1,

%e [4] 1, 1, 3, 2, 1,

%e [5] 1, 1, 4, 3, 3, 1,

%e [6] 1, 1, 5, 4, 6, 3, 1,

%e [7] 1, 1, 6, 5, 10, 6, 4, 1,

%e [8] 1, 1, 7, 6, 15, 10, 10, 4, 1,

%e [9] 1, 1, 8, 7, 21, 15, 20, 10, 5, 1,

%e ---------------------------------------

%e From _Gary W. Adamson_, Oct 23 2019: (Start)

%e Consider the roots of the polynomials corresponding to odd N such that for N=7 the polynomial is (x^3 + x^2 - 2x - 1) and the roots (a, b, c) are (-1.8019377..., 1.247697..., and -0.445041...). The discriminant of a polynomial derived from the roots is the square of the product of successive differences: ((a-b), (b-c), (c-a))^2 in this case, resulting in 49, matching the method derived from the coefficients of a cubic. For our purposes we use the product of the differences, not the square, resulting in (3.048...) * (1.69202...) * (1.35689...) = 7.0. Conjecture: for all polynomials in the set, the product of the differences of the roots = the corresponding N. For N = 7, we get x^3 - 7x + 7. It appears that for all prime N's, these resulting companion polynomials are monic (left coefficient is 1), and all other coefficients are N or multiples thereof, with the rightmost term = N. The companion polynomials for the first few primes are:

%e N = 5: x^2 - 5;

%e N = 7: x^3 - 7x + 7;

%e N = 11: x^5 - 11x^3 + 11x^2 + 11x - 11;

%e N = 13: x^6 - 13x^4 + 13x^3 + 26x^2 - 39x + 13;

%e N = 17: x^8 - 17x^6 + 17x^5 + 68x^4 - 119x^3 + 17x^2 + 51x - 17;

%e N = 19: x^9 - 19x^7 + 19x^6 + 95x^5 - 171x^4 - 19x^3 + 190x^2 - 114x + 19. (End)

%p A065941 := proc(n,k): binomial(n-floor((k+1)/2),floor(k/2)) end: seq(seq(A065941(n,k), k=0..n), n=0..15); # _Johannes W. Meijer_, Aug 11 2011

%p A065941 := proc(n,k) option remember: local j: if k=0 then 1 elif k=1 then 1: elif k>=2 then add(procname(j,k-2), j=k-2..n-2) fi: end: seq(seq(A065941(n,k), k=0..n), n=0..15); # _Johannes W. Meijer_, Aug 11 2011

%p # The function qStirling2 is defined in A333143.

%p seq(print(seq(qStirling2(n, k, -1), k=0..n)), n=0..9);

%p # _Peter Luschny_, Mar 09 2020

%t Flatten[Table[Binomial[n-Floor[(k+1)/2],Floor[k/2]],{n,0,15},{k,0,n}]] (* _Harvey P. Dale_, Dec 11 2011 *)

%o (Haskell)

%o a065941 n k = a065941_tabl !! n !! k

%o a065941_row n = a065941_tabl !! n

%o a065941_tabl = iterate (\row ->

%o zipWith (+) ([0] ++ row) (zipWith (*) (row ++ [0]) a059841_list)) [1]

%o -- _Reinhard Zumkeller_, May 07 2012

%o (PARI) T065941(n, k) = binomial(n-(k+1)\2, k\2); \\ _Michel Marcus_, Apr 28 2014

%o (Magma) [Binomial(n - Floor((k+1)/2), Floor(k/2)): k in [0..n], n in [0..15]]; // _G. C. Greubel_, Jul 10 2019

%o (Sage) [[binomial(n - floor((k+1)/2), floor(k/2)) for k in (0..n)] for n in (0..15)] # _G. C. Greubel_, Jul 10 2019

%Y Cf. A065942 (central stalk sequence), A000045 (row sums), A108299.

%Y Reflected version of A046854.

%Y Some triangle sums (see A180662): A000045 (Fi1), A016116 (Kn21), A000295 (Kn23), A094967 (Fi2), A000931 (Ca2), A001519 (Gi3), A000930 (Ze3).

%Y Cf. A003558, A182579, A059841, A333143.

%K nonn,tabl,easy

%O 0,9

%A _Len Smiley_, Nov 29 2001