A098810 - OEIS

A098810

Array read by antidiagonals: Costs E[m,N] of m-ary Huffman trees of maximum height with N internal nodes (non-leaves) for minimizing absolutely ordered sequences of size n=2N+1; m > 1, N > 0.

2, 6, 3, 13, 10, 4, 25, 25, 14, 5, 45, 56, 39, 18, 6, 78, 119, 97, 55, 22, 7, 132, 246, 233, 148, 73, 26, 8, 220, 501, 546, 393, 209, 93, 30, 9, 363, 1012, 1270, 1014, 605, 280, 115, 34, 10, 595, 2035, 2936, 2619, 1686, 875, 361, 139, 38, 11, 971, 4082, 6777, 6712

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,1

LINKS

Table of n, a(n) for n=0..58.

Alex Vinokur, Fibonacci-Like Polynomials Produced by m-ary Huffman Codes for Absolutely Ordered Sequences, E-print

Alex Vinokur, Fibonacci connection between Huffman codes and Wythoff array, E-print, 2004, 10 pages

FORMULA

E[m, N] = (G[N+4, m-1] - 2)/(m-1) - (N+3) where N is number of internal nodes (non-leaves) of m-ary Huffman tree; m > 1, N > 0. G[i, j] are Fibonacci-like polynomials defined by the recurrence relation G[0, j] = 1, G[1, j] = 1, G[2, j] = 2; G[i, j] = G[i-1, j] + j*G[i-2, j] when i > 2; j > 0.

EXAMPLE

Top left corner of array:

2 6 13 25 45 78 132 220 363 595 971 1580 2566 4162 6745 10925 17689 28634 46344 75000 121367

3 10 25 56 119 246 501 1012 2035 4082 8177 16368 32751 65518 131053 262124 524267 1048554 2097129 4194280 8388583

4 14 39 97 233 546 1270 2936 6777 15619 35987 82884 190888 439586 1012299 2331109 5368061 12361446 28465690 65550092 150947229

5 18 55 148 393 1014 2619 6712 17229 44122 113087 289628 742033 1900606 4868803 12471296 31946581 81831842 209618247 536945700 1375418777

6 22 73 209 605 1686 4752 13228 37039 103235 288491 804732 2247258 6270994 17507365 48862421 136399337 380711538 1062708324 2966266120 8279807851

7 26 93 280 875 2598 7897 23540 70983 212290 638261 1912080 5741731 17214302 51664785 154950700 464939519 1394643834 4184281069 12552144200 37657830747

8 30 115 361 1209 3786 12306 38872 125085 397267 1272947 4053908 12964636 41342098 132094663 421489469 1346152237 4296578654 13719644454 43795695180 139833206513

9 34 139 452 1613 5286 18255 60616 206737 691754 2345747 7879884 26645973 89685166 302853079 1020334544 3443159321 11605835826 39151110555 131997797332 445206681949

10 38 165 553 2093 7134 26044 90332 324819 1137907 4061387 14302668 50855278 179579426 637277073 2253492061 7988985881 28270414602 100171287712 354605019320 1256146608927

11 42 193 664 2655 9366 35997 129748 489819 1787410 6685721 24559952 91417303 337016974 1251190165 4621360076 17133261907 63346862858 234679482129 868148110920 3214942932431

12 46 223 785 3305 12018 48462 180760 713953 2702435 10556051 40282980 156399696 599512642 2319909475 8914548725 34433553149 132493589334 511262674194 1968692157100 7592581573477

13 50 255 916 4049 15126 63811 245432 1011285 3956602 16092167 63571548 256677721 1019536478 4099669323 16334107264 65530139357 261539426754 1047901099279 4186374220580 16761187412193

14 54 289 1057 4893 18726 82440 325996 1397847 5635939 23808107 97075484 406581058 1668562546 6954116509 28645429829 119048944681 491439532706 2039075813820 8427789739272 34935775319219

15 58 325 1208 5843 22854 104769 424852 1891759 7839842 34324637 144082608 624627723 2641784446 11386572793 48371555276 207783574631 884985348762 3793955393877 16183750276840 69299125791427

16 62 363 1369 6905 27546 131242 544568 2513349 10682035 48382451 208613172 934350148 4063547954 18078800415 79032019981 350214026477 1535694326478 6788904723934 29824319621420 131657890480761

17 66 403 1540 8085 32838 162327 687880 3285273 14291530 66856091 295520780 1365218461 6093551182 27937046815 125433866000 572426615329 2579368471634 11738194317219 53008089863700 240819198939557

18 70 445 1721 9389 38766 198516 857692 4232635 18813587 90768587 410599788 1953666006 8933862658 42146185033 194021850509 910506996377 4208878455354 19687497394104 91238431135480 425925886835623

19 74 489 1912 10823 45366 240325 1057076 5383107 24410674 121306817 560699184 2744222143 12836807726 62232806589 293295345964 1413485864891 6692802092586 32135547660985 152605985327912 731045843226039

20 78 535 2113 12393 52674 288294 1289272 6767049 31263427 159837587 753842948 3790757368 18113773666 90138163963 434299863941 2146924979581 10398622394822 51190197007242 248764022509260 1221377765647277

21 82 583 2324 14105 60726 342987 1557688 8417629 39571610 207924431 999356892 5157845793 25144983934 128301900115 631201579136 3197239581797 15821271164898 79766062801239 396191486099620 1991512742124841

22 86 633 2545 15965 69558 404992 1865900 10370943 49555075 267345131 1308001980 6922250026 34390291922 179757542805 901953673525 4676862072809 23617889217234 121831992746644 617807666309000 3176279513988987

CROSSREFS

Sequence in context: A054618 A120859 A253258 * A360006 A081469 A331441

Adjacent sequences: A098807 A098808 A098809 * A098811 A098812 A098813

KEYWORD

easy,nonn,tabl

AUTHOR

Alex Vinokur (alexvn(AT)barak-online.net), Nov 02 2004

STATUS

approved