login
Consider the 2^(n-1) monic polynomials f(x) with coefficients 0 or 1, degree n and f(0)=1. Sequence gives triangle read by rows, in which T(n,k) (n>=1) is the number of such polynomials of thickness k (2 <= k <= n+1).
15

%I #22 Feb 10 2023 17:12:19

%S 1,1,1,3,0,1,3,3,1,1,5,4,6,0,1,7,7,10,6,1,1,13,8,27,6,9,0,1,15,21,41,

%T 23,17,9,1,1,27,20,98,34,56,8,12,0,1,25,53,148,96,104,50,22,12,1,1,45,

%U 56,325,116,294,66,96,10,15,0,1,59,89,487,319,518,262,184,86

%N Consider the 2^(n-1) monic polynomials f(x) with coefficients 0 or 1, degree n and f(0)=1. Sequence gives triangle read by rows, in which T(n,k) (n>=1) is the number of such polynomials of thickness k (2 <= k <= n+1).

%C The thickness of a polynomial f(x) is the magnitude of the largest coefficient in the expansion of f(x)^2.

%H <a href="/index/Ca#CARRYLESS">Index entries for sequences related to carryless arithmetic</a>

%F Wanted: a recurrence. Are any of A169940-A169954 related to any other entries in the OEIS?

%F From _M. F. Hasler_, Nov 12 2010: (Start)

%F T(n,n+1) = 1 = T(2m,2m), T(2m+1,2m+1) = 0,

%F T(n+1,n) = (3, 3, 6, 6, 9, 9, ...) = 3*[n/2-1] = A168237(n) (n>2),

%F T(2m+2,2m) = (3, 10, 17, 22, 27, 32, 37, ...) = 5m+2 for m>2,

%F T(2m+3,2m+1) = (4, 6, 8, 10, ...) = 2m+2 for m>0,

%F T(2m+3,2m) = (5, 27, 56, 96, 143, 199, 264, ...) = m(9m+13)/2-2 for m>3,

%F T(2m+4,2m+1) = (7, 23, 50, 86, 131, 185, 248, ...) = 9m(m+1)/2-4 for m>1,

%F ... (End)

%e Triangle begins:

%e [1]

%e [1, 1]

%e [3, 0, 1]

%e [3, 3, 1, 1]

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

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

%e [13, 8, 27, 6, 9, 0, 1]

%e [15, 21, 41, 23, 17, 9, 1, 1]

%e [27, 20, 98, 34, 56, 8, 12, 0, 1]

%e [25, 53, 148, 96, 104, 50, 22, 12, 1, 1]

%e [45, 56, 325, 116, 294, 66, 96, 10, 15, 0, 1]

%e [59, 89, 487, 319, 518, 262, 184, 86, 27, 15, 1, 1]

%e [89, 112, 942, 434, 1279, 346, 608, 112, 143, 12, 18, 0, 1]

%e [103, 197, 1348, 1042, 2181, 1153, 1166, 528, 291, 131, 32, 18, 1, 1]

%e [163, 220, 2613, 1320, 4981, 1568, 3313, 720, 1083, 168, 199, 14, 21, 0, 1]

%e ...

%e For n=3 there are four polynomials x^3+1, x^3+x+1, x^3+x^2+1, x^3+x^2+x+1. Their squares are x^6+2*x^3+1, x^6+2*x^4+2*x^3+x^2+2*x+1, x^6+2*x^5+2*x^3+x^4+2*x^2+1 and x^6+2*x^5+3*x^4+4*x^3+3*x^2+2*x+1. Their thicknesses are 2,2,2,4. So T(3,2)=3, T(3,3)=0, T(3,4)=1.

%e The next 15 rows of the triangle are:

%e [187, 397, 3693, 2849, 8393, 4499, 6123, 2873, 2157, 939, 413, 185, 37, 21, 1, 1]

%e [281, 456, 6672, 3854, 17730, 6404, 15634, 4056, 6864, 1316, 1730, 234, 264, 16, 24, 0, 1]

%e [313, 711, 9458, 7940, 28938, 16432, 28534, 13398, 13488, 5906, 3568, 1514, 556, 248, 42, 24, 1, 1]

%e [469, 850, 16483, 10670, 58520, 23610, 67290, 19842, 37934, 8502, 12540, 2158, 2582, 310, 338, 18, 27, 0, 1]

%e [533, 1347, 22903, 20511, 94574, 55510, 120550, 57880, 73288, 32006, 25552, 10754, 5484, 2284, 716, 320, 47, 27, 1, 1]

%e [835, 1428, 39252, 27560, 183225, 80676, 267894, 86894, 189156, 48572, 78530, 15786, 20948, 3292, 3660, 396, 421, 20, 30, 0, 1]

%e [873, 2303, 53874, 51088, 290401, 179485, 469928, 232610, 359532, 158100, 158248, 66158, 43924, 18026, 7948, 3274, 895, 401, 52, 30, 1, 1]

%e [1319, 2642, 89947, 68614, 545421, 260616, 998433, 353278, 868696, 244418, 442240, 101860, 146260, 26948, 32804, 4750, 4997, 492, 513, 22, 33, 0, 1]

%e [1551, 3777, 123653, 121487, 853975, 549189, 1725367, 876575, 1621096, 725016, 877388, 365898, 304048, 123536, 70436, 28400, 11029, 4511, 1093, 491, 57, 33, 1, 1]

%e [2093, 4636, 200706, 164644, 1558400, 798552, 3526978, 1340828, 3719207, 1137278, 2280612, 580200, 912118, 192574, 251928, 43126, 48875, 6572, 6616, 598, 614, 24, 36, 0, 1]

%e [2347, 6693, 271092, 285484, 2403986, 1616482, 5997220, 3147524, 6830683, 3108825, 4457858, 1874174, 1873798, 754630, 537286, 213744, 107163, 42619, 14802, 6022, 1310, 590, 62, 36, 1, 1]

%e [3477, 7550, 438403, 379800, 4292926, 2346592, 11882630, 4821002, 15021379, 4920018, 10948081, 3008372, 5200638, 1217690, 1719966, 336912, 408989, 65534, 70061, 8794, 8546, 714, 724, 26, 39, 0, 1]

%e [3881, 11109, 585071, 644971, 6538688, 4594134, 19912060, 10801102, 27155069, 12640031, 21054795, 8950909, 10529720, 4248966, 3632012, 1428638, 890393, 348839, 156301, 61531, 19322, 7834, 1546, 698, 67, 39, 1, 1]

%e [5363, 12876, 927332, 860898, 11437031, 6656592, 38401950, 16551444, 57664535, 20086508, 49373458, 14542512, 27487209, 6959998, 10699424, 2334678, 3027695, 555714, 633348, 95568, 97301, 11454, 10814, 840, 843, 28, 42, 0, 1]

%e [5871, 17965, 1239392, 1419768, 17273147, 12579603, 63611068, 35500374, 102865259, 48877549, 93622166, 40321020, 54860417, 22275601, 22298854, 8743268, 6540369, 2528691, 1403386, 543422, 220305, 86061, 24650, 9974, 1801, 815, 72, 42, 1, 1]

%t row[n_] := Module[{dd, xx, mm}, dd = Join[{1}, PadLeft[IntegerDigits[#, 2], n-1], {1}]& /@ Range[0, 2^(n-1) - 1]; xx = (((x^Range[n, 0, -1]).#)& /@ dd)^2 // Expand; mm = Max[CoefficientList[#, x]]& /@ xx; Table[Count[mm, k], {k, 2, n+1}]]; Table[row[n], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Oct 10 2017 *)

%o (PARI)

%o T(n)={ my(c=vector(n)); forstep(j=1<<n+1,2<<n,2, c[vecmax(Vec(Pol(binary(j))^2))-1]++);c} /* yields the n-th row of the triangle */

%o T(n,k)={ sum( j=1<<(n-1),1<<n-1, vecmax(Vec(Pol(binary(j*2+1))^2))==k )}

%o \\ _M. F. Hasler_, Nov 12 2010

%Y Related to thickness: A169940-A169954, A061909.

%K nonn,tabl

%O 1,4

%A _N. J. A. Sloane_, Aug 01 2010

%E Rows 16-30 from _Nathaniel Johnston_, Nov 12 2010