词条 | Wedderburn–Etherington number |
释义 |
The Wedderburn–Etherington numbers are an integer sequence named for Ivor Malcolm Haddon Etherington[1][2] and Joseph Wedderburn[3] that can be used to count certain kinds of binary trees. The first few numbers in the sequence are 0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, ... ({{OEIS2C|A001190}}) Combinatorial interpretationThese numbers can be used to solve several problems in combinatorial enumeration. The nth number in the sequence (starting with the number 0 for n = 0) counts
FormulaThe Wedderburn–Etherington numbers may be calculated using the recurrence relation beginning with the base case .[4] In terms of the interpretation of these numbers as counting rooted binary trees with n leaves, the summation in the recurrence counts the different ways of partitioning these leaves into two subsets, and of forming a subtree having each subset as its leaves. The formula for even values of n is slightly more complicated than the formula for odd values in order to avoid double counting trees with the same number of leaves in both subtrees.[7] Growth rateThe Wedderburn–Etherington numbers grow asymptotically as where B is the generating function of the numbers and ρ is its radius of convergence, approximately 0.4027 {{OEIS|A240943}}, and where the constant given by the part of the expression in the square root is approximately 0.3188 {{OEIS|A245651}}.[11] Applications{{harvtxt|Young|Yung|2003}} use the Wedderburn–Etherington numbers as part of a design for an encryption system containing a hidden backdoor. When an input to be encrypted by their system can be sufficiently compressed by Huffman coding, it is replaced by the compressed form together with additional information that leaks key data to the attacker. In this system, the shape of the Huffman coding tree is described as an Otter tree and encoded as a binary number in the interval from 0 to the Wedderburn–Etherington number for the number of symbols in the code. In this way, the encoding uses a very small number of bits, the base-2 logarithm of the Wedderburn–Etherington number.[12]{{harvtxt|Farzan|Munro|2008}} describe a similar encoding technique for rooted unordered binary trees, based on partitioning the trees into small subtrees and encoding each subtree as a number bounded by the Wedderburn–Etherington number for its size. Their scheme allows these trees to be encoded in a number of bits that is close to the information-theoretic lower bound (the base-2 logarithm of the Wedderburn–Etherington number) while still allowing constant-time navigation operations within the tree.[13]{{harvtxt|Iserles|Nørsett|1999}} use unordered binary trees, and the fact that the Wedderburn–Etherington numbers are significantly smaller than the numbers that count ordered binary trees, to significantly reduce the number of terms in a series representation of the solution to certain differential equations.[14]See also
References1. ^1 {{citation | last = Etherington | first = I. M. H. | author-link = Ivor Malcolm Haddon Etherington | doi = 10.2307/3605743 | issue = 242 | journal = Mathematical Gazette | pages = 36–39, 153 | title = Non-associate powers and a functional equation | volume = 21 | year = 1937}}. 2. ^1 {{citation | last = Etherington | first = I. M. H. | author-link = Ivor Malcolm Haddon Etherington | issue = 2 | journal = Proc. Royal Soc. Edinburgh | pages = 153–162 | title = On non-associative combinations | volume = 59 | year = 1939}}. 3. ^1 {{citation | last = Wedderburn | first = J. H. M. | author-link = Joseph Wedderburn | doi = 10.2307/1967710 | issue = 2 | journal = Annals of Mathematics | pages = 121–140 | title = The functional equation | volume = 24 | year = 1923}}. 4. ^1 2 3 {{Cite OEIS|A001190}}. 5. ^{{citation | last1 = Bóna | first1 = Miklós | author1-link = Miklós Bóna | last2 = Flajolet | first2 = Philippe | author2-link = Philippe Flajolet | arxiv = 0901.0696 | doi = 10.1239/jap/1261670685 | issue = 4 | journal = Journal of Applied Probability | mr = 2582703 | pages = 1005–1019 | title = Isomorphism and symmetries in random phylogenetic trees | volume = 46 | year = 2009}}. 6. ^{{citation | last = Otter | first = Richard | doi = 10.2307/1969046 | journal = Annals of Mathematics | mr = 0025715 | pages = 583–599 | series = Second Series | title = The number of trees | volume = 49 | year = 1948}}. 7. ^1 {{citation | last = Murtagh | first = Fionn | doi = 10.1016/0166-218X(84)90066-0 | issue = 2 | journal = Discrete Applied Mathematics | mr = 727923 | pages = 191–199 | title = Counting dendrograms: a survey | volume = 7 | year = 1984}}. 8. ^{{citation | last1 = Cyvin | first1 = S. J. | last2 = Brunvoll | first2 = J. | last3 = Cyvin | first3 = B.N. | doi = 10.1016/0166-1280(95)04329-6 | issue = 3 | journal = Journal of Molecular Structure: THEOCHEM | pages = 255–261 | title = Enumeration of constitutional isomers of polyenes | volume = 357 | year = 1995}}. 9. ^{{citation | last = Maurer | first = Willi | journal = The Annals of Statistics | jstor = 2958441 | mr = 0371712 | pages = 717–727 | title = On most effective tournament plans with fewer games than competitors | volume = 3 | year = 1975 | doi = 10.1214/aos/1176343135}}. 10. ^This equivalence between trees and elements of the free commutative magma on one generator is stated to be "well known and easy to see" by {{citation | last = Rosenberg | first = I. G. | doi = 10.1016/0166-218X(86)90068-5 | issue = 1 | journal = Discrete Applied Mathematics | mr = 829338 | pages = 41–59 | title = Structural rigidity. II. Almost infinitesimally rigid bar frameworks | volume = 13 | year = 1986}}. 11. ^{{citation | last = Landau | first = B. V. | issue = 2 | journal = Mathematika | mr = 0498168 | pages = 262–265 | title = An asymptotic expansion for the Wedderburn-Etherington sequence | volume = 24 | year = 1977 | doi=10.1112/s0025579300009177}}. 12. ^{{citation | last1 = Young | first1 = Adam | last2 = Yung | first2 = Moti | author2-link = Moti Yung | contribution = Backdoor attacks on black-box ciphers exploiting low-entropy plaintexts | doi = 10.1007/3-540-45067-X_26 | isbn = 3-540-40515-1 | pages = 297–311 | publisher = Springer | series = Lecture Notes in Computer Science | title = Proceedings of the 8th Australasian Conference on Information Security and Privacy (ACISP'03) | volume = 2727 | year = 2003}}. 13. ^{{citation | last1 = Farzan | first1 = Arash | last2 = Munro | first2 = J. Ian | author2-link = Ian Munro (computer scientist) | contribution = A uniform approach towards succinct representation of trees | doi = 10.1007/978-3-540-69903-3_17 | mr = 2497008 | pages = 173–184 | publisher = Springer | series = Lecture Notes in Computer Science | title = Algorithm theory—SWAT 2008 | volume = 5124 | year = 2008}}. 14. ^{{citation | last1 = Iserles | first1 = A. | last2 = Nørsett | first2 = S. P. | doi = 10.1098/rsta.1999.0362 | issue = 1754 | journal = The Royal Society of London | mr = 1694700 | pages = 983–1019 | title = On the solution of linear differential equations in Lie groups | volume = 357 | year = 1999| bibcode = 1999RSPTA.357..983I }}. Further reading
| last = Finch | first = Steven R. | doi = 10.1017/CBO9780511550447 | isbn = 0-521-81805-2 | location = Cambridge | mr = 2003519 | pages = 295–316 | publisher = Cambridge University Press | series = Encyclopedia of Mathematics and its Applications | title = Mathematical constants | volume = 94 | year = 2003}}.{{DEFAULTSORT:Wedderburn-Etherington number}} 3 : Integer sequences|Trees (graph theory)|Graph enumeration |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。