{"entities":{"Q1252855":{"pageid":1263605,"ns":120,"title":"Item:Q1252855","lastrevid":67349361,"modified":"2026-04-12T17:01:41Z","type":"item","id":"Q1252855","labels":{"en":{"language":"en","value":"On a class of linked diagrams. I: Enumeration"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3613043"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1252855$543D7176-B2DF-4C65-A3A0-9F6EC4D6B665","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8626835bff7d6d64922a51a9bc1f4b53613e83eb","datavalue":{"value":{"text":"On a class of linked diagrams. I: Enumeration","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1252855$06CAC63A-B201-4981-AE18-8EA5F4451158","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8dcb1c9bded30a1ffd0ba3700c6d6fa84f14f18a","datavalue":{"value":"0395.05002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1252855$819C6337-A2C7-43AC-895A-58F1FB764C73","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dcb3c7afd4cc75801a17597d70e992e991ded8e6","datavalue":{"value":"10.1016/0097-3165(78)90065-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1252855$B48EB6DB-1B9D-4365-8D4A-8DF3522A7560","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1252855$5A499D7B-E5F9-4EAE-835F-916F14F622C4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"23512e79b17ec0dbe00d89a570006ab4e1ecd403","datavalue":{"value":{"time":"+1978-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1252855$0061A54C-218B-41EA-AAFB-A0AE79E9D293","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"82f292d15ddd4c8cd2d1cc35e859085d1c962d2c","datavalue":{"value":"This article is concerned with the enumeration of a class of combinatorial structures first encountered by \\textit{J. Touchard} [Can. J. Math. 4, 2--25 (1952; Zbl 0047.01801)] and later considered briefly by \\textit{D. J. Kleitman} [Stud. Appl. Math. 49, 297--299 (1970; Zbl 0198.03802)]. The structures are defined as follows:   Take \\(2n\\) points on a line, and construct a complete pairing of these points, the paired points being connected by arcs. Each of the \\(n\\) arcs connects two distinct points, and no point is incident on more than one arc. The points are taken as labelled in the natural order. Clearly, the total number of distinct arrangements is \\((2n - 1)!!\\equiv (2n-1)(2n-3)\\ldots 3.1\\). If a complete pairing on \\(2n\\) points contains a complete subpairing on \\(2j <2n\\) consecutive points, the original complete pairing is called reducible; in the contrary case, it is irreducible. Let \\(S_n\\) be the number of irreducible complete pairings on \\(2n\\) points. By direct combinatorial arguments, it is shown that  \\[ S_{n+1} = \\sum \\frac{\\alpha!}{\\alpha_1!\\cdots \\alpha_n!} \\prod_{j=1}^n [(2j-1)S_j]^\\alpha j \\tag{1} \\]  \\[ \\text{with}\\quad \\sum_{i=1}^n i\\alpha_i=n,\\quad \\sum_{i=1}^n \\alpha_i=\\alpha \\text{  for nonnegative }\\alpha_i. \\tag{2} \\]   J. Riordan (private communication) pointed out to the author that (1) can be written in the simpler form:   \\[ S_n = (n-1) \\sum_{j=1}^{n-1} S_j S_{n-j}, \\quad S_1=1; \\tag{3} \\]   recently, a direct combinatorial proof of (3) has been given by \\textit{N. Nijenhuis} and \\textit{H. S. Wilf} [The enumeration of connected graphs and linked diagrams, Univ. Pennsylvania preprint (1978); J. Comb. Theory, Ser. A 27, 356--359 (1979; Zbl 0421.05038)].   The second part of the paper under review deals with the ``symmetry-reduced'' case in which complete pairings which are mirror images of each other are identified. Again, a direct combinatorial construction is employed. The results, equations 5.3 and 5.5, contain a common misprint; in both cases, the terms \\(\\frac{S_{n-n}}{2}\\) should be \\(\\frac{S_{n-m}}{2}\\). A table of values for both the labeled and unlabeled cases through \\(n=20\\) is included. The limit theorem \\(\\lim_{n\\to\\infty}\\frac{S_n}{(2n-1)!!} = e^{-1}\\) was first given in [2]; a detailed proof by \\textit{C. J. Everett} and the author may be found in the paper reviewed below [Zbl 0395.05003]. Further asymptotic results on generalizations of equations (3) are given in the paper of the author and \\textit{C. J. Everett} in [J. Comb. Inf. Syst. Sci. 3, 1--10 (1978; Zbl 0393.65050).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1252855$50ACBC6E-B607-45D6-AFE3-58A5079C3E7A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1252855$8FE1CEF7-5084-4E74-983A-43DBF00D6C01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1252855$4494232C-A1A2-4B4F-9D95-D615B901A324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a46d831259493f05707be1b8dc8ce3db73fd0637","datavalue":{"value":"41A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1252855$BED12F15-2120-4FEA-90AB-991E773A3226","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eb24a15eaabb76f3cb5cdd3f436ac4ab6cc16d18","datavalue":{"value":"3613043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1252855$B3BBBA60-95E6-44D4-8C5E-F6868426801C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3f984e01d1e12366b52ba2bfa1c3f05a1dd5ef6","datavalue":{"value":"class of linked diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q1252855$E8073301-128E-444A-8B91-7F7041F9BC46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"159c518265271d1934334ee78b34d87ffa4b93ce","datavalue":{"value":"combinatorial structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1252855$0BFF2F27-15A2-4D5B-8AE1-D827F9329200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"816681eea21269f3ad56375e4f8d7d873b144eb6","datavalue":{"value":"enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1252855$FF95E21E-8DF6-45B2-BC60-FD1BB8ED4CDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76d2374d8794c6d48c3cc9d1f1ddc49c00c94880","datavalue":{"value":"total number of distinct arrangements","type":"string"},"datatype":"string"},"type":"statement","id":"Q1252855$D5443DF4-FF87-4AE1-AE5B-75D7FA76454B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88a9b2756b3993e41d239151520cfc0f49396c5e","datavalue":{"value":"complete pairing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1252855$674708C7-327B-42FB-B7B5-9C5C2E26231A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c45e0fa09935fa4863427909039bca0629fcd1f","datavalue":{"value":{"entity-type":"item","numeric-id":759148,"id":"Q759148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1252855$4892C4A3-3FA7-4BC6-89F3-9F8C0FEBD8BC","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1252855$5D610DE5-A115-4E98-A0C3-B6D84B9B7CB9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1009d1e015176b9a84708f294f697dea6e56d087","datavalue":{"value":"https://doi.org/10.1016/0097-3165(78)90065-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1252855$30D0B4FC-7FEF-4B61-AC7B-302601BEC718","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2687a95df4af18faf37f7c9602adbdb57d7f34c5","datavalue":{"value":"W2042966012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1252855$C1F03555-4241-4CAA-A87F-885E95370A40","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea3c8fc14a745170bca600bb735de5d34d0173d1","datavalue":{"value":{"entity-type":"item","numeric-id":5812204,"id":"Q5812204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1252855$6E01DB6B-7DCD-4798-92E0-2C0CB24AD24B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6abaca99af3d3bf5f44b53acaeba01877fc4bdd9","datavalue":{"value":{"entity-type":"item","numeric-id":4081259,"id":"Q4081259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1252855$23865E3E-476A-42DD-AF1D-11C56F8EE67D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44ccdb2ef35aa96ce770e975d06d3e6b3a1ae8e6","datavalue":{"value":{"entity-type":"item","numeric-id":5596259,"id":"Q5596259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1252855$880F4EA5-4215-4EF7-8B2D-251AAD0950F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6056280fc429c2451a79417a924cc72383a5677c","datavalue":{"value":{"entity-type":"item","numeric-id":1252856,"id":"Q1252856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1252855$7F22DD0D-6872-4D53-994D-D190063AF247","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d94fa34a4fa9c42456fde011444da92b06baa875","datavalue":{"value":{"entity-type":"item","numeric-id":1252856,"id":"Q1252856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08d38854b0b74447455796ce8a47b46456a6f5bb","datavalue":{"value":{"amount":"+0.8911197","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$C36F8A27-AF31-4CB3-B846-B67C5D23423E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c85d9d58ef5a5587c8e561bdaa9cbf5bbeeacc1a","datavalue":{"value":{"entity-type":"item","numeric-id":5753990,"id":"Q5753990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f6659deffcea32776762bea2a8c7b2c48d1a51a","datavalue":{"value":{"amount":"+0.8813424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$4123770D-2FCB-4182-A1FA-4FC741B6BABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66b05fbcb31ef7dc5bdec7c4efbf06f9783fa215","datavalue":{"value":{"entity-type":"item","numeric-id":4211458,"id":"Q4211458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d662916efedf7b00c3397d9ff4776826f48bf07","datavalue":{"value":{"amount":"+0.87337554","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$03D921E3-77F8-4753-92B2-46D99B35E6A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50e5310f1d37f23f8824a2848f790b0414974e7d","datavalue":{"value":{"entity-type":"item","numeric-id":1406560,"id":"Q1406560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b56bfdbc3df74acd4018543f22aa17f7b32d051","datavalue":{"value":{"amount":"+0.86285996","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$77B91A24-BCBC-43E2-A1FE-14F8ED9FB921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de38601603976aba69d77cb1dd14716a766cdb3d","datavalue":{"value":{"entity-type":"item","numeric-id":2441661,"id":"Q2441661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcaa012ed33bd07596d041a50c9d19129e921746","datavalue":{"value":{"amount":"+0.8607892","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$03EF9681-8B73-484B-9D0D-5CCCB17D6FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"857b0edcd1138eca9a7d9ef069ab6c7e9f792208","datavalue":{"value":{"entity-type":"item","numeric-id":3770567,"id":"Q3770567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e13b591304611779978e1b9f284600b387a4944","datavalue":{"value":{"amount":"+0.8602919","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$923E693A-7E21-4E1E-A68E-A43B4D0D9EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"959538c7bafebc29fc1ae225aa29a55ef6bea7b4","datavalue":{"value":{"entity-type":"item","numeric-id":5902721,"id":"Q5902721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8491e52e239398ab011ab56758eaca32d3df0aea","datavalue":{"value":{"amount":"+0.860193","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$D5B2A5BF-A51F-4218-8C2A-32410E874110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"281bddc79129e621838bbfc37e7c4ca69499a35e","datavalue":{"value":{"entity-type":"item","numeric-id":5035074,"id":"Q5035074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a11dd8a42edd56ec9c6efa0d02f7e812468f780b","datavalue":{"value":{"amount":"+0.85832465","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$A65264F9-33C7-46BF-B23C-E9450D5E6BF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82616bd051cf2fa67a87316a3e0e0ca3104dac46","datavalue":{"value":{"entity-type":"item","numeric-id":4272167,"id":"Q4272167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"505d9f1f5bb044eef3f8450c7bdb6148187ca641","datavalue":{"value":{"amount":"+0.85451335","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$6AF05292-5E64-48F9-BC07-03260F75DBE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9aa7a0e30bf4cdd02c26521320efb3a9a330c7f4","datavalue":{"value":{"entity-type":"item","numeric-id":3797195,"id":"Q3797195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63749d8f8c09a7ca45c944ce5aa93c00743c115f","datavalue":{"value":{"amount":"+0.8540622","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1252855$CDE04C3F-F585-4E57-9D0A-0864DBE0EE58","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On a class of linked diagrams. I: Enumeration","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_a_class_of_linked_diagrams._I:_Enumeration"}}}}}