cp's OEIS Frontend

A233288 Number of (3/2,2)-tight graphs with 2n vertices, or kinematic chains with 2n links.

%I A233288 #18 Jun 02 2025 15:56:37
%S A233288 1,1,2,16,230,6856,318162,19819281,1535380884
%N A233288 Number of (3/2,2)-tight graphs with 2n vertices, or kinematic chains with 2n links.
%C A233288 A 2n-vertex graph is (3/2,2)-sparse if every subgraph with k vertices has at most (3/2)k-2 edges, and (3/2,2)-tight if in addition it has exactly 3n-2 edges; see Lee and Streinu (2008). These graphs represent two-dimensional mechanical systems formed by 2n rigid bodies (links), connected at joints where exactly two links are pinned together and can rotate relative to each other, with the entire system having one degree of freedom and having no rigid subsystems. The vertices of the graph represent links and the edges represent joints.
%H A233288 Eric A. Butcher and Chris Hartman, <a href="http://dx.doi.org/10.1016/j.mechmachtheory.2004.12.015">Efficient enumeration and hierarchical classification of planar simple-jointed kinematic chains: Application to 12- and 14-bar single degree-of-freedom chains</a>, Mechanism and Machine Theory 30 (2005), 1030-1050.
%H A233288 Martin Larsson, <a href="https://github.com/martinkjlarsson/nauty-laman-plugin">Nauty Laman plugin</a>
%H A233288 Audrey Lee and Ileana Streinu, <a href="http://dx.doi.org/10.1016/j.disc.2007.07.104">Pebble game algorithms and sparse graphs</a>, Discrete Math. 308 (2008), 1425-1437.
%H A233288 E. E. Peisakh, <a href="http://dx.doi.org/10.3103/S1052618808030011">Structural analysis of planar jointed mechanisms: Current state and problems</a>, J. Machinery Manufacture and Reliability 37 (2008), 207-212.
%H A233288 Rajesh P. Sunkari and Linda C. Schmidt, <a href="http://dx.doi.org/10.1016/j.mechmachtheory.2005.11.007">Structural synthesis of planar kinematic chains by adapting a Mckay-type algorithm</a>, Mechanism and Machine Theory 41 (2006), 1021-1030. This paper sources the 19819281 value for n=8 but contains a typo for n=7.
%e A233288 For n=1 the single example (a graph with two vertices and one edge) is represented by familiar mechanical systems including door hinges and pairs of scissors. For n=3 the a(3)=2 solutions are the 6-vertex 7-edge graphs Theta(1,3,3) and Theta(2,2,3), each of which has two degree-three vertices connected by three paths of the given lengths. These correspond respectively to the Watt linkage (two four-bar linkages sharing a pair of adjacent links) and the Stephenson linkage.
%o A233288 (nauty) gensparseg 2*$n -K3/2L2 -u # With Laman plugin; see Larsson link.
%Y A233288 Cf. A227117, A273468, A306420, A328060, A328061, A371901.
%K A233288 nonn,more
%O A233288 1,3
%A A233288 _David Eppstein_, Dec 06 2013
%E A233288 a(9) from _Martin Larsson_ added by _Max Alekseyev_, Jan 14 2025