############################################################################## # # # The Table of Decomposable Structures # # # ############################################################################## # This table contains the specifications of some decomposable structures. # The syntax used is that of the combstruct package (formerly call gaia), # which is included in Maple V.4. # The specifications are ordered by their counting sequences, using the # same lexicographic order as in [SlPl95]. # The numbers Mxxxx refer to The Encyclopedia of Integer Sequences [SlPl95]. # You are welcome to submit new specifications to Paul Zimmermann # Contributors are: Philippe Flajolet (PF) References: [FlZiVa93] A Calculus for the Random Generation of Labelled Combinatorial Structures, Ph. Flajolet, P. Zimmermann, B. Van Cutsem, Theoretical Computer Science 132, 1994, 1-35. [SlPl95] The Encyclopedia of Integer Sequences, N. J. A. Sloane and S. Plouffe, Academic Press, 1995. [Zimmermann94] Gai"a: a package for the random generation of combinatorial structures, Paul Zimmermann, MapleTech 1:1, 1994, 38-46. # - all the examples here that do not use PowerSet and Predefined can be # run with combstruct version 2.06 or higher # - the examples with PowerSet can be run with version 2.1 or higher # - the examples with Predefined can be run with version 2.11 or higher with(combstruct): # M0012: number of ways of writing n as sum of 2 squares countS:=proc(n) if n>0 and type(sqrt(n),integer) then 1 else 0 fi end: M[12]:=[N,{N=Sequence(S,card<=2),S=Predefined(countS)},unlabelled]: seq(count(M[12],size=n),n=1..69); 1, 1, 0, 1, 2, 0, 0, 1, 1, 2, 0, 0, 2, 0, 0, 1, 2, 1, 0, 2, 0, 0, 0, 0, 3, 2, 0, 0, 2, 0, 0, 1, 0, 2, 0, 1, 2, 0, 0, 2, 2, 0, 0, 0, 2, 0, 0, 0, 1, 3, 0, 2, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 1, 4, 0, 0, 2, 0 draw(M[12],size=68); Sequence(4, 64) # M0022: partitions of n into distinct primes Primes:=proc(n) if isprime(n) then 1 else 0 fi end: M[22]:=[N,{N=PowerSet(P),P=Predefined(Primes)},unlabelled]: seq(count(M[22],size=n),n=0..57); 1, 0, 1, 1, 0, 2, 0, 2, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 4, 3, 4, 4, 4, 5, 5, 5, 6, 5, 6, 7, 6, 9, 7, 9, 9, 9, 11, 11, 11, 13, 12, 14, 15, 15, 17, 16, 18, 19, 20, 21, 23, 22, 25, 26, 27, 30, 29, 32 draw(M[22],size=57); PowerSet(2, 7, 17, 31) # M0045: representations of n as a sum of (distinct) Lucas numbers Lucas:=proc(n) option remember; Lucas(n-1)+Lucas(n-2) end: Lucas(0):=1: Lucas(1):=3: isLucas:=proc(n) local k; option remember; k:=round(log(n)/log((1+sqrt(5))/2)-1); if Lucas(k)=n then 1 else 0 fi end: isLucas(0):=0: isLucas(1):=1: M[45]:=[N,{N=PowerSet(L),L=Predefined(isLucas)},unlabelled]: seq(count(M[45],size=n),n=1..69); 1, 0, 1, 2, 1, 0, 2, 2, 0, 1, 3, 2, 0, 2, 3, 1, 0, 3, 3, 0, 2, 4, 2, 0, 3, 3, 0, 1, 4, 3, 0, 3, 5, 2, 0, 4, 4, 0, 2, 5, 3, 0, 3, 4, 1, 0, 4, 4, 0, 3, 6, 3, 0, 5, 5, 0, 2, 6, 4, 0, 4, 6, 2, 0, 5, 5, 0, 3, 6 draw(M[45],size=69); PowerSet(4, 18, 47) # M0050: partitions of n into not more than 5 pentagonal numbers isPentagonal:=proc(p) local n; n:=round(sqrt(2*p/3)); if p=n*(3*n-1)/2 then 1 else 0 fi end: isPentagonal(0):=0: M[50]:=[N,{N=Set(P,card<=5),P=Predefined(isPentagonal)},unlabelled]: seq(count(M[50],size=n),n=1..69); 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 2, 1, 2, 2, 3, 3, 2, 3, 2, 2, 2, 1, 2, 1, 3, 3, 3, 4, 3, 3, 2, 3, 3, 1, 2, 3, 4, 4, 3, 4, 3, 4, 3, 3, 3, 3, 3, 4, 5, 5, 3, 3, 4, 4, 3, 2, 4, 3, 4, 4 draw(M[50],size=69); Set(1, 5, 12, 51) # M0053: partitions of n into not more than 4 squares isSquare:=proc(n) if n>0 and type(sqrt(n),integer) then 1 else 0 fi end: M[53]:=[N,{N=Set(Predefined(isSquare),card<=4)},unlabelled]: > seq(count(M[53],size=n),n=1..69); 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 3, 3, 3, 3, 2, 2, 2, 1, 3, 4, 2, 4, 3, 3, 2, 2, 3, 4, 3, 2, 4, 2, 2, 2, 4, 5, 3, 5, 3, 5, 3, 1, 4, 5, 3, 3, 4, 3, 4, 2, 4, 6, 4, 4, 4 > draw(M[53],size=69); Set(4, 16, 49) # M0071: decompositions of 2n into sum of 2 lucky numbers # for a definition of lucky numbers, see # http://www.planetary.caltech.edu/~eww/math/node3453.html Lucky:=proc(n) local i,j,l; option remember; l:=[seq(2*i-1,i=1..iquo(n,2))]; i:=2; while l[i]<=nops(l) do l:=subsop(seq(l[i]*j=NULL,j=1..iquo(nops(l),l[i])),l); i:=i+1; od; l end: isLucky:=proc(n) local i,j,l; option remember; if n mod 2 = 0 then 0 else l:=[seq(2*i+1,i=0..iquo(n,2))]; i:=2; while i<=nops(l) and l[i]<=nops(l) do if nops(l) mod l[i]=0 then RETURN(0) fi; # unlucky ! l:=subsop(seq(l[i]*j=NULL,j=1..iquo(nops(l),l[i])),l); i:=i+1; od; 1 # lucky ! fi; end: M[71]:=[N,{N=Set(Predefined(isLucky),card=2)},unlabelled]: > seq(count(M[71],size=2*n),n=1..69); 1, 1, 1, 1, 2, 1, 2, 3, 2, 1, 3, 2, 2, 3, 2, 2, 4, 2, 3, 4, 2, 3, 5, 1, 4, 5, 2, 3, 5, 1, 3, 5, 3, 3, 5, 3, 5, 7, 3, 5, 7, 4, 4, 7, 3, 3, 7, 4, 3, 9, 5, 3, 7, 5, 3, 8, 5, 4, 8, 5, 3, 7, 5, 3, 9, 4, 3, 12, 6 > draw(M[71],size=2*69); Set(51, 87) # M0073: partitions of n into a prime and a square isSquare:=proc(n) if type(sqrt(n),integer) then 1 else 0 fi end: Primes:=proc(n) if isprime(n) then 1 else 0 fi end: M[73]:=[N,{N=Prod(Predefined(Primes),Predefined(isSquare))},unlabelled]: > seq(count(M[73],size=n),n=1..68); 0, 1, 2, 1, 1, 2, 2, 1, 1, 0, 3, 2, 1, 2, 1, 1, 2, 2, 2, 2, 2, 1, 3, 1, 0, 1, 3, 2, 2, 2, 1, 3, 2, 0, 2, 1, 1, 4, 2, 1, 3, 2, 2, 2, 2, 1, 4, 2, 1, 1, 2, 2, 3, 3, 1, 3, 2, 0, 3, 2, 1, 4, 2, 0, 2, 3, 3, 4 > draw(M[73],size=68); Prod(59, 9) # M0076: partitions of n into not more than 3 triangular numbers isTriangular:=proc(p) round(sqrt(2*p)); if p="*("+1)/2 then 1 else 0 fi end: isTriangular(0):=0: M[76]:=[N,{N=Set(Predefined(isTriangular),card<=3)},unlabelled]: seq(count(M[76],size=n),n=1..69); 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 3, 2, 1, 2, 3, 2, 2, 2, 1, 4, 3, 2, 2, 2, 2, 3, 3, 1, 4, 4, 2, 2, 3, 2, 3, 4, 2, 3, 3, 2, 4, 3, 2, 4, 4, 2, 4, 4, 1, 4, 5, 1, 2, 3, 4, 6, 4, 3, 2, 5, 2, 3, 3, 3, 6, 5, 2, 2 draw(M[76],size=69); Set(3, 21, 45) # M0101: sums of distinct Fibonacci numbers # use the fact that fib(n) ~ (1/2+sqrt(5)/2)^n/sqrt(5) isFib:=proc(n) if n=combinat[fibonacci](round(log[(1+sqrt(5))/2](n*sqrt(5)))) then 1 else 0 fi end: isFib(0):=0: M[101]:=[N,{N=PowerSet(Predefined(isFib))},unlabelled]: > seq(count(M[101],size=n),n=0..68); 1, 1, 1, 2, 1, 2, 2, 1, 3, 2, 2, 3, 1, 3, 3, 2, 4, 2, 3, 3, 1, 4, 3, 3, 5, 2, 4, 4, 2, 5, 3, 3, 4, 1, 4, 4, 3, 6, 3, 5, 5, 2, 6, 4, 4, 6, 2, 5, 5, 3, 6, 3, 4, 4, 1, 5, 4, 4, 7, 3, 6, 6, 3, 8, 5, 5, 7, 2, 6 > draw(M[101],size=68); PowerSet(13, 21, 34) # M104: decompositions of 2*n into sum of two odd primes isOddPrime:=proc(n) if isprime(n) then 1 else 0 fi end: isOddPrime(1):=0: isOddPrime(2):=0: M[104]:=[N,{N=Set(P,card=2),P=Predefined(isOddPrime)},unlabelled]: > seq(count(M[104],size=2*n),n=1..69); 0, 0, 1, 1, 2, 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 2, 4, 4, 2, 3, 4, 3, 4, 5, 4, 3, 5, 3, 4, 6, 3, 5, 6, 2, 5, 6, 5, 5, 7, 4, 5, 8, 5, 4, 9, 4, 5, 7, 3, 6, 8, 5, 6, 8, 6, 7, 10, 6, 6, 12, 4, 5, 10, 3, 7, 9, 6, 5, 8 > draw(M[104],size=2*69); Set(11, 127) # decompositions of n into sum of 2 primes isPrime:=proc(n) if isprime(n) then 1 else 0 fi end: isPrime(0):=1: M[202]:=[N,{N=Prod(P,P),P=Predefined(isPrime)},unlabelled]: > seq(count(M[202],size=n),n=0..66); 1, 0, 2, 2, 1, 4, 1, 4, 2, 2, 3, 2, 2, 4, 3, 2, 4, 2, 4, 4, 4, 2, 5, 2, 6, 2, 5, 0, 4, 2, 6, 4, 4, 2, 7, 0, 8, 2, 3, 2, 6, 2, 8, 4, 6, 2, 7, 2, 10, 2, 8, 0, 6, 2, 10, 2, 6, 0, 7, 2, 12, 4, 5, 2, 10, 0, 12 > draw(M[202],size=66); Prod(43, 23) # M0205: partitions of n into products of 2 primes isProductOfTwoPrimes:=proc(n) readlib(ifactors)(n)[2]; if nops(")=2 and op(2,"[1])=1 and op(2,"[2])=1 then 1 else 0 fi end: M[205]:=[N,{N=Set(Predefined(isProductOfTwoPrimes))},unlabelled]: > seq(count(M[205],size=n),n=1..61); 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 2, 2, 2, 0, 2, 1, 3, 2, 3, 1, 4, 2, 4, 3, 5, 4, 7, 3, 6, 5, 8, 6, 10, 6, 10, 9, 12, 9, 15, 11, 16, 14, 18, 14, 22, 19, 25, 22, 27, 23, 33, 29 > draw(M[205],size=61); Set(22, 39) # partitions of n into parts of the form 6n+1 or 6n-1 M[254]:=[N,{N=Set(P),P=Union(P1,P5),P1=Prod(Z,P0),P0=Set(Six), Six=Prod(Z$6),P5=Prod(Z$5,P0)},unlabelled]: > seq(count([N,sys],size=n),n=0..46); 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 23, 26, 30, 34, 38, 42, 47, 53, 60, 67, 74, 82, 91, 102, 114, 126, 139, 153, 169, 187, 207, 228, 250, 274, 301 # partitions of n into prime parts isPrime:=proc(n) if isprime(n) then 1 else 0 fi end: M[265]:=[N,{N=Set(Predefined(isPrime))},unlabelled]: > seq(count(M[265],size=n),n=1..45); 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 19, 23, 26, 30, 35, 40, 46, 52, 60, 67, 77, 87, 98, 111, 124, 140, 157, 175, 197, 219, 244, 272, 302, 336, 372, 413, 456, 504 > draw(M[265],size=45); Set(3, 19, 23) # partitions of n into distinct parts M[281]:=[N,{N=PowerSet(F),F=Sequence(Z,card>=1)},unlabelled]: seq(count(M[281],size=n),n=0..41); 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113, 1260 # Words with at least 8 consecutive b-letters (m=1 => Fibonacci seq.) [PF] ss:=proc(m) [L,{L=Prod(X,Sequence(Prod(a,X))),X=Sequence(b,card>=m), a=Atom,b=Atom},unlabelled]; end: M[479]:=ss(8): > seq(count(M[479],size=n),n=8..52); 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 19, 24, 30, 37, 45, 54, 64, 76, 91, 110, 134, 164, 201, 246, 300, 364, 440, 531, 641, 775, 939, 1140, 1386, 1686, 2050 # Words with at least 7 consecutive b-letters (m=1 => Fibonacci seq.) [PF] ss:=proc(m) [L,{L=Prod(X,Sequence(Prod(a,X))),X=Sequence(b,card>=m), a=Atom,b=Atom},unlabelled]; end: M[483]:=ss(7): > seq(count(M[483],size=n),n=7..49); 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 18, 23, 29, 36, 44, 53, 64, 78, 96, 119, 148, 184, 228, 281, 345, 423, 519, 638, 786, 970, 1198, 1479, 1824, 2247, 2766 # Words with at least 6 consecutive b-letters (m=1 => Fibonacci seq.) [PF] ss:=proc(m) [L,{L=Prod(X,Sequence(Prod(a,X))),X=Sequence(b,card>=m), a=Atom,b=Atom},unlabelled]; end: M[492]:=ss(6): > seq(count(M[492],size=n),n=6..47); 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 10, 13, 17, 22, 28, 35, 43, 53, 66, 83, 105, 133, 168, 211, 264, 330, 413, 518, 651, 819, 1030, 1294, 1624, 2037, 2555, 3206, 4025, 5055 # Words with at least 5 consecutive b-letters (m=1 => Fibonacci seq.) [PF] ss:=proc(m) [L,{L=Prod(X,Sequence(Prod(a,X))),X=Sequence(b,card>=m), a=Atom,b=Atom},unlabelled]; end: M[496]:=ss(5): > seq(count(M[496],size=n),n=5..44); 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 12, 16, 21, 27, 34, 43, 55, 71, 92, 119, 153, 196, 251, 322, 414, 533, 686, 882, 1133, 1455, 1869, 2402, 3088, 3970, 5103, 6558, 8427 # Words with at least 4 consecutive b-letters (m=1 => Fibonacci seq.) [PF] ss:=proc(m) [L,{L=Prod(X,Sequence(Prod(a,X))),X=Sequence(b,card>=m), a=Atom,b=Atom},unlabelled]; end: M[507]:=ss(4): > seq(count(M[507],size=n),n=4..41); 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 26, 34, 45, 60, 80, 106, 140, 185, 245, 325, 431, 571, 756, 1001, 1326, 1757, 2328, 3084, 4085, 5411, 7168, 9496, 12580, 16665 # Words with at least 3 consecutive b-letters (m=1 => Fibonacci seq.) [PF] ss:=proc(m) [L,{L=Prod(X,Sequence(Prod(a,X))),X=Sequence(b,card>=m), a=Atom,b=Atom},unlabelled]; end: M[526]:=ss(3): > seq(count(M[526],size=n),n=3..38); 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250, 345, 476, 657, 907, 1252, 1728, 2385, 3292, 4544, 6272, 8657, 11949, 16493, 22765, 31422, 43371 # necklaces with beads from 2 colors (thanks PF) M[564]:=[N,{N=Cycle(Union(Z$2))},unlabelled]: > seq(count(M[564],size=n),n=1..28); 2, 3, 4, 6, 8, 14, 20, 36, 60, 108, 188, 352, 632, 1182, 2192, 4116, 7712, 14602, 27596, 52488, 99880, 190746, 364724, 699252, 1342184, 2581428, 4971068, 9587580 # Words with at least 2 consecutive b-letters (m=1 => Fibonacci seq.) [PF] ss:=proc(m) [L,{L=Prod(X,Sequence(Prod(a,X))),X=Sequence(b,card>=m), a=Atom,b=Atom},unlabelled]; end: M[571]:=ss(2): > seq(count(M[571],size=n),n=2..34); 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491 # partitions of n [PZ] M[663]:=[N,{N=Set(Set(Z,card>=1))},unlabelled]: > seq(count(M[663],size=n),n=0..34); 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310 > draw(M[663],size=34); Set(Set(Z, Z, Z, Z, Z, Z), Set(Z, Z, Z, Z, Z, Z), Set(Z, Z, Z, Z), Set(Z, Z, Z, Z), Set(Z, Z, Z, Z, Z, Z, Z, Z, Z, Z, Z, Z, Z, Z)) # Fibonacci numbers (thanks PF) M[692]:=[F,{F=Sequence(Union(Z,Prod(Z,Z)))},unlabelled]: > seq(count(M[692],size=n),n=0..30); 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269 # hydrocarbons with n atoms (centered+bicentered) M[718]:=proc(n) centeredHC(n)+bicenteredHC(n) end: > seq(M[718](n),n=0..26); 1, 1, 1, 1, 2, 3, 5, 9, 18, 35, 75, 159, 355, 802, 1858, 4347, 10359, 24894, 60523, 148284, 366319, 910726, 2278658, 5731580, 14490245, 36797588, 93839412 # Non plane rooted binary trees (Wedderburn-Etherington numbers) [PF] M[790]:=[S,{S=Union(Z,Set(S,card=2))},unlabelled]: > seq(count(M[790],size=n),n=0..27); 0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, 127912, 293547, 676157, 1563372, 3626149, 8436379, 19680277, 46026618, 107890609 > draw(M[790],size=27): > lprint("); Set(Z,Set(Z,Set(Set(Set(Z,Set(Z,Z)),Set(Z,Z)),Set(Z,Set(Z,Set(Set(Z,Set(Set( Set(Set(Set(Z,Set(Z,Set(Set(Z,Z),Set(Z,Z)))),Z),Set(Z,Z)),Z),Set(Z,Set(Z,Set(Z, Set(Z,Z)))))),Set(Z,Z))))))) # Unrooted non plane trees [PZ] alias(Int=`combstruct/Int`,Delta=`combstruct/Delta`,Theta=`combstruct/Theta`): M[791]:=[t,{T=Prod(Z,Set(T)),t=Int(Union(T,Prod(T,Delta[Set(2)](Theta(T))), Delta[2](Theta(T))))},unlabelled]: > seq(count(M[791],size=n),n=1..25); 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 48629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890 > draw(M[791],size=25): > lprint("); Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Epsilon))))))), Prod(Z,Set(Prod(Z,Epsilon))))),Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod (Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Epsilon),Prod(Z,Epsilon))))))))))))),Prod(Z ,Set(Prod(Z,Epsilon),Prod(Z,Epsilon))))),Prod(Z,Epsilon),Prod(Z,Set(Prod(Z,Set( Prod(Z,Epsilon))),Prod(Z,Epsilon))))) # Unrooted plane trees [PZ] alias(Int=`combstruct/Int`,Delta=`combstruct/Delta`,Theta=`combstruct/Theta`): M[805]:=[p,{p=Int(Union(P,Prod(Z,Delta[Cycle(2)](Prod(Theta(P0), Sequence(P0)))),Delta[2](Theta(P0)))),P0=Prod(Z,Sequence(P0)), P=Union(Z,Prod(Z,Cycle(P0)))},unlabelled]: > seq(count(M[805],size=n),n=0..23); 0, 1, 1, 1, 2, 3, 6, 14, 34, 95, 280, 854, 2694, 8714, 28640, 95640, 323396, 1105335, 3813798, 13269146, 46509358, 164107650, 582538732, 2079165208 > draw(M[805],size=23): lprint("); Prod(Z,Cycle(Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Epsilon),Prod(Z,Sequence( Prod(Z,Epsilon),Prod(Z,Sequence(Prod(Z,Epsilon),Prod(Z,Sequence(Prod(Z,Epsilon) ,Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z,Epsilon ),Prod(Z,Epsilon),Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Epsilon))))),Prod(Z, Epsilon))))))))))),Prod(Z,Epsilon),Prod(Z,Sequence(Prod(Z,Epsilon))))))))) # Unlabelled trees of height 2 (or partitions of n - 1) [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[1012]:=n -> count(ht(2),size=n)-count(ht(1),size=n): > seq(M[1012](n),n=3..36); 1, 2, 4, 6, 10, 14, 21, 29, 41, 55, 76, 100, 134, 175, 230, 296, 384, 489, 626, 791, 1001, 1254, 1574, 1957, 2435, 3009, 3717, 4564, 5603, 6841, 8348, 10142, 12309, 14882 # Tribonacci numbers (thanks PF) M[1074]:=[L,{L=Prod(X,Sequence(Prod(Z,X))),X=Sequence(Z,card<=2)},unlabelled]: > seq(count(M[1074],size=n),n=0..25); 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770 # trees of height at most 3 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[1107]:=ht(3): > seq(count(M[1107],size=n),n=1..28); 1, 1, 2, 4, 8, 15, 29, 53, 98, 177, 319, 565, 1001, 1749, 3047, 5264, 9054, 15467, 26320, 44532, 75054, 125904, 210413, 350215, 580901, 960035, 1581534, 2596913 > draw(M[1107],size=28): > lprint("); Prod(Z,Set(Prod(Z,Set(Prod(Z,Epsilon))),Prod(Z,Set(Prod(Z,Set(Z)),Prod(Z, Epsilon))),Prod(Z,Set(Prod(Z,Set(Z)),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z, Epsilon),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z ,Epsilon))),Prod(Z,Set(Prod(Z,Epsilon),Prod(Z,Epsilon))),Prod(Z,Set(Prod(Z,Set( Z,Z)),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z,Epsilon))))) # Tetranacci numbers [PF] M[1108]:=[L,{L=Prod(X,Sequence(Prod(Z,X))),X=Sequence(Z,card<=3)},unlabelled]: > seq(count(M[1108],size=n),n=0..24); 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, 1055026, 2033628, 3919944, 7555935 # Pentanacci numbers [PF] M[1122]:=[L,{L=Prod(X,Sequence(Prod(Z,X))),X=Sequence(Z,card<=4)},unlabelled]: > seq(count(M[1122],size=n),n=0..24); 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513, 400096, 786568, 1546352, 3040048, 5976577, 11749641 # Hexanacci numbers [PF] M[1128]:=[L,{L=Prod(X,Sequence(Prod(Z,X))),X=Sequence(Z,card<=5)},unlabelled]: > seq(count(M[1128],size=n),n=0..24); 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536 # powers of two (or words with two letters) [PF] M[1129]:=[S,{S=Sequence(Union(Z,Z))},unlabelled]: > seq(count(M[1129],size=n),n=0..25); 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432 # quartic planted trees with n nodes M[1146]:=[T,{T=Union(Epsilon,U),U=Prod(Z,Set(U,card<=3))},unlabelled]: seq(count(M[1146],size=n),n=0..41); 1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241, 48865, 124906, 321198, 830219, 2156010, 5622109, 14715813, 38649152, 101821927, 269010485 # trees of height at most 4 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[1172]:=ht(4): > seq(count(M[1172],size=n),n=1..26); 1, 1, 2, 4, 9, 19, 42, 89, 191, 402, 847, 1763, 3667, 7564, 15564, 31851, 64987, 132031, 267471, 539949, 1087004, 2181796, 4367927, 8721533, 17372967, 34524291 > draw(M[1172],size=26): lprint("); Prod(Z,Set(Prod(Z,Set(Prod(Z,Epsilon))),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod( Z,Set(Prod(Z,Epsilon),Prod(Z,Set(Prod(Z,Set(Z)))))),Prod(Z,Set(Prod(Z,Epsilon), Prod(Z,Set(Prod(Z,Set(Z)))))),Prod(Z,Set(Prod(Z,Epsilon),Prod(Z,Set(Prod(Z,Set( Z,Z)),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z, Epsilon))))))) # trees of height at most 5 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[1177]:=ht(5): > seq(count(M[1177],size=n),n=1..24); 1, 1, 2, 4, 9, 20, 47, 108, 252, 582, 1345, 3086, 7072, 16121, 36667, 83099, 187885, 423610, 953033, 2139158, 4792126, 10714105, 23911794, 53273599 # Rooted, non plane, unlabelled trees [PF] M[1180]:=[T,{T=Prod(Z,Set(T))},unlabelled]: > seq(count(M[1180],size=n),n=1..24); 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847, 1721159, 4688676, 12826228, 35221832, 97055181, 268282855, 743724984 > draw(M[1180],size=24): lprint("); Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z, Epsilon))),Prod(Z,Epsilon))),Prod(Z,Epsilon))))),Prod(Z,Set(Prod(Z,Set(Prod(Z, Set(Prod(Z,Epsilon))),Prod(Z,Set(Prod(Z,Epsilon))),Prod(Z,Epsilon))))))),Prod(Z ,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Epsilon),Prod(Z,Epsilon))))),Prod( Z,Epsilon))))),Prod(Z,Epsilon))) # Connected mapping patterns (Connected graphs with one cycle) [PF] M[1182]:=[F,{F=Set(K,card=1), K=Cycle(T), T=Prod(Z,Set(T))},unlabelled]: > seq(count(M[1182],size=n),n=1..27); 1, 2, 4, 9, 20, 51, 125, 329, 862, 2311, 6217, 16949, 46350, 127714, 353272, 981753, 2737539, 7659789, 21492286, 60466130, 170510030, 481867683, 1364424829, 3870373826, 10996890237, 31293083540, 89173833915 > draw(M[1182],size=10); Set(Cycle(Prod(Z, Epsilon), Prod(Z, Set(Prod(Z, Set(Prod(Z, Set(Prod(Z, Set(Prod(Z, Epsilon))))))), Prod(Z, Epsilon), Prod(Z, Set(Prod(Z, Epsilon), Prod(Z, Epsilon)))) ))) # Motzkin numbers [PF] M[1184]:=[S,{S=Prod(Z,Sequence(S,card<=2))},unlabelled]: > seq(count(M[1184],size=n),n=1..24); 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415 > draw(M[1184],size=24): lprint("); Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z, Sequence(Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z ,Sequence(Prod(Z,Sequence(Prod(Z,Epsilon),Prod(Z,Sequence(Prod(Z,Epsilon),Prod( Z,Epsilon))))),Prod(Z,Sequence(Prod(Z,Epsilon),Prod(Z,Epsilon))))))),Prod(Z, Epsilon))),Prod(Z,Epsilon))))))))))))),Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z, Sequence(Prod(Z,Epsilon))))))))) # series-parallel networks M[1207]:=[N,{N=Union(Z,S,P),S=Set(Union(Z,P),card>=2),P=Set(Union(Z,S),card>=2)}]: > seq(count(M[1207],size=n),n=1..22); 1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624, 14136, 43930, 137908, 437502, 1399068, 4507352, 14611576, 47633486, 156047204, 513477502, 1696305728, 5623993944 # involutions [PF] # q describes partitions with all blocks of size<=m q:=proc(m) local j;[B,{B=Set(Union(seq(Set(Z,card=j),j=1..m)))},labelled] end: M[1221]:=q(2): > seq(count(M[1221],size=n),n=0..20); 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, 211799312, 997313824, 4809701440, 23758664096 # Non plane trees with degree >=2 (series-reduced planted trees) [PF] M[1421]:=[T,{T=Union(Z,Set(T,card>=2))},unlabelled]: > seq(count(M[1421],size=n),n=1..22); 1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, 218751, 699534, 2253676, 7305788, 23816743, 78023602, 256738751, 848152864, 2811996972 > draw(M[1421],size=22); Set(Set(Z, Z), Set(Z, Z), Set(Z, Z, Z, Z, Z, Z), Set(Set(Set(Z, Z), Set(Z, Z), Set(Z, Z, Set(Z, Set(Z, Z)))), Set(Z, Z, Z))) # Rooted triangular cacti [PZ] alias(Int=`combstruct/Int`,Delta=`combstruct/Delta`,Theta=`combstruct/Theta`): M[1448]:=[D0,{D0=Union(Epsilon,D1),D1=Set(Prod(Z,D2),card>=1), D2=Union(Prod(Epsilon,Epsilon), Int(Union(Prod(D0,Theta(D1)),Delta[2](Theta(D1)))))},unlabelled]: # completes the sequence in EIS > seq(count(M[1448],size=n),n=0..20); 1, 1, 2, 5, 13, 37, 111, 345, 1105, 3624, 12099, 41000, 140647, 487440, 1704115, 6002600, 21282235, 75890812, 272000538, 979310627, 3540297130 > draw(M[1448],size=20): lprint("); Set(Prod(Z,Prod(Set(Prod(Z,Prod(Epsilon,Set(Prod(Z,Prod(Epsilon,Set(Prod(Z, Prod(Epsilon,Set(Prod(Z,Prod(Epsilon,Epsilon)))))))),Prod(Z,Prod(Epsilon,Set( Prod(Z,Prod(Epsilon,Epsilon))))),Prod(Z,Prod(Epsilon,Set(Prod(Z,Prod(Epsilon, Epsilon))))),Prod(Z,Prod(Epsilon,Set(Prod(Z,Prod(Epsilon,Epsilon))))))))),Set( Prod(Z,Prod(Epsilon,Set(Prod(Z,Prod(Set(Prod(Z,Prod(Epsilon,Epsilon))),Set(Prod (Z,Prod(Epsilon,Set(Prod(Z,Prod(Epsilon,Epsilon)),Prod(Z,Prod(Epsilon,Epsilon)) ,Prod(Z,Prod(Epsilon,Epsilon))))))))))),Prod(Z,Prod(Epsilon,Epsilon))))),Prod(Z ,Prod(Epsilon,Epsilon))) # Catalan numbers [PF] M[1459]:=[S,{S=Prod(Z,Sequence(S))},unlabelled]: > seq(count(M[1459],size=n),n=1..22); 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020 > draw(M[1459],size=22): lprint("); Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z, Epsilon))),Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Epsilon),Prod(Z,Epsilon),Prod (Z,Epsilon),Prod(Z,Sequence(Prod(Z,Sequence(Prod(Z,Epsilon),Prod(Z,Epsilon))), Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z,Sequence(Prod(Z,Sequence (Prod(Z,Epsilon))))),Prod(Z,Epsilon))))),Prod(Z,Epsilon))))))))) # partitions with all blocks of size<=3 [PF] q:=proc(m) local j;[B,{B=Set(Union(seq(Set(Z,card=j),j=1..m)))},labelled] end: M[1465]:=q(3): > seq(count(M[1465],size=n),n=0..19); 1, 1, 2, 5, 14, 46, 166, 652, 2780, 12644, 61136, 312676, 1680592, 9467680, 55704104, 341185496, 2170853456, 14314313872, 97620050080, 687418278544 # N-free posets M[1476]:=[N,{N=Union(R,S,P), R=Atom, S=Sequence(Union(R,P), card>=2), P=Set(Union(R,S), card>=2)}]: > seq(count(M[1476],size=n),n=1..20); 1, 2, 5, 15, 48, 167, 602, 2256, 8660, 33958, 135292, 546422, 2231462, 9199869, 38237213, 160047496, 674034147, 2854137769, 12144094756, 51895919734 > draw(M[1476],size=20); Set(Sequence(Set(R, R), Set(Sequence(R, Set(Sequence(R, R), R)), Sequence(R, Set(R, R)), R, R), R) , Sequence(Set(Sequence(R, R), R), R), Sequence(R, R), Sequence(R, R)) # partitions with all blocks of size<=4 [PF] q:=proc(m) local j;[B,{B=Set(Union(seq(Set(Z,card=j),j=1..m)))},labelled] end: M[1481]:=q(4): > seq(count(M[1481],size=n),n=0..19); 1, 1, 2, 5, 15, 51, 196, 827, 3795, 18755, 99146, 556711, 3305017, 20655285, 135399720, 927973061, 6631556521, 49294051497, 380306658250, 3039453750685 # Bell numbers [PF] # p encodes set partitions with all blocks of size>=m p:=proc(m) [B,{B=Set(Set(Z,card>=m))},labelled] end: M[1484]:=p(1): > seq(count(M[1484],size=n),n=0..19); 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057 # Arrangements, partial permutations [PF] M[1497]:=[N,{N=Prod(Sequence(Z),Set(Z))},labelled]: > seq(count(M[1497],size=n),n=0..16); 1, 2, 5, 16, 65, 326, 1957, 13700, 109601, 986410, 9864101, 108505112, 1302061345, 16926797486, 236975164805, 3554627472076, 56874039553217 > draw(M[1497],size=16); Prod(Sequence(Z[15], Z[13], Z[8], Z[1], Z[16], Z[5], Z[7], Z[2], Z[11], Z[10], Z[3], Z[6], Z[14], Z[12]), Set(Z[9], Z[4])) # functional digraphs [PZ] M[1597]:=[FD,{T=Prod(Z,Set(T)),FD=Set(Cycle(T,card>=2))},unlabelled]: # completes the sequence in EIS > seq(count(M[1597],size=n),n=0..21); 1, 0, 1, 2, 6, 13, 40, 100, 291, 797, 2273, 6389, 18264, 51916, 148666, 425529, 1221900, 3511507, 10111043, 29142941, 84112009, 243000149 > draw(M[1597],size=21): > lprint("); Set(Cycle(Prod(Z,Epsilon),Prod(Z,Epsilon),Prod(Z,Set(Prod(Z,Set(Prod(Z,Set( Prod(Z,Epsilon),Prod(Z,Epsilon))))),Prod(Z,Set(Prod(Z,Epsilon)))))),Cycle(Prod( Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Epsilon),Prod(Z, Epsilon))))))))))),Prod(Z,Set(Prod(Z,Set(Prod(Z,Epsilon),Prod(Z,Set(Prod(Z, Epsilon))))))))) # royal paths in a lattice (or series-parallel graphs or bicolored trees) M[1659]:=[N,{N=Union(R,S,P), R=Atom, S=Sequence(Union(R,P), card>=2), P=Sequence(Union(R,S), card>=2)}]: > seq(count(M[1659],size=n),n=1..19); 1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446, 27297738, 142078746, 745387038, 3937603038, 20927156706, 111818026018, 600318853926 > draw(M[1659],size=19); Sequence(Sequence(R, Sequence(Sequence(Sequence(Sequence(Sequence(Sequence( Sequence(R, Sequence(R, R)), Sequence(R, Sequence(R, Sequence(R, R)))), R) , Sequence(Sequence(R, R), R)), R), R, R, R), R), R), R) # Increasing (nonstrict) injective partial maps (values of Bell polynomials) [PF] M[1662]:=[InPM2,{InPM2=Set(Union(Set(Z,card>=1),Set(Z,card>=1)))},labelled]: > seq(count(M[1662],size=n),n=0..17); 1, 2, 6, 22, 94, 454, 2430, 14214, 89918, 610182, 4412798, 33827974, 273646526, 2326980998, 20732504062, 192982729350, 1871953992254, 18880288847750 > draw(M[1662],size=17); Set(Set(Z[10]), Set(Z[6]), Set(Z[16]), Set(Z[1]), Set(Z[11], Z[5]), Set(Z[15]), Set(Z[4], Z[12]), Set(Z[14]), Set(Z[17], Z[7]), Set(Z[9], Z[2], Z[3], Z[13], Z[8])) # factorial numbers (or permutations) [PF] M[1675]:=[A,{A=Set(Cycle(Z))},labelled]: > seq(count(M[1675],size=n),n=0..17); 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000 # injective partial maps [PF] M[1795]:=[IPM,{IPM=Set(Union(Cycle(Z),Sequence(Z,card>=1)))},labelled]: > seq(count(M[1795],size=n),n=0..15); 1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, 3405357682, 53334454417, 896324308634, 16083557845279, 306827170866106 > draw(M[1795],size=15); Set(Cycle(Z[15]), Sequence(Z[2], Z[10], Z[9]), Sequence(Z[13], Z[6], Z[5], Z[1], Z[11], Z[4]), Cycle(Z[8]), Cycle(Z[14]), Cycle(Z[3], Z[12], Z[7])) # cycles of cycles [PF] M[1798]:=[A,{A=Cycle(Cycle(Z))},labelled]: M[1799]:=M[1798]: > seq(count(M[1798],size=n),n=1..16); 1, 2, 7, 35, 228, 1834, 17582, 195866, 2487832, 35499576, 562356672, 9794156448, 186025364016, 3826961710272, 84775065603888, 2011929826983504 > draw(M[1798],size=16); Cycle(Cycle(Z[1], Z[11]), Cycle(Z[4], Z[13], Z[6]), Cycle(Z[5]), Cycle(Z[3], Z[14], Z[9]), Cycle(Z[12]), Cycle(Z[8]), Cycle(Z[15]), Cycle(Z[7]), Cycle(Z[16]), Cycle(Z[2], Z[10])) # without combstruct: n x n matrices with no 2 adjacent 1's M[1816]:=proc(N) local i,j,p,q; option remember; p:=1+x11; for i from 2 to N do q:=p-select(has,p,x.(i-1).1); p:=p+expand(q*x.i.1) od; for j from 2 to N do q:=p-select(has,p,x1.(j-1)); p:=subs(x1.(j-1)=1,p)+expand(q*x1.j); for i from 2 to N do q:=p-select(has,p,{x.(i-1).j,x.i.(j-1)}); p:=subs(x.i.(j-1)=1,p)+expand(q*x.i.j); od od; map(icontent,p) end: > seq(M[1816](N),N=1..18); 2, 7, 63, 1234, 55447, 5598861, 1280128950, 660647962955, 770548397261707, 2030049051145980050, 12083401651433651945979, 162481813349792588536582997, 4935961285224791538367780371090, 338752110195939290445247645371206783, 52521741712869136440040654451875316861275, 18396766424410124752958806046933947217821482942, 14557601701834111295974187104248827765798599152358303, 26024585612650837861658126921792857026992497268285945167621 # derangements or rencontres numbers or subfactorials [PF] # a(m) describes permutations with all cycles of length >= m a:=proc(m) [A,{A=Set(Cycle(Z,card>=m))},labelled]; end: M[1937]:=a(2): > seq(count(M[1937],size=n),n=0..17); 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664 # Partial maps (n^(n-1)) [PF] M[1946]:=[PartialMap, {PartialMap=Set(Connected), Connected=Union(Cycle(Tree),Prod(Undefined,Tree)), Tree=Prod(Z,Set(Tree)), Undefined=Epsilon}, labelled]: > seq(count(M[1946],size=n),n=0..14); 1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000, 25937424601, 743008370688, 23298085122481, 793714773254144, 29192926025390625 # Bicolored functional graphs [Volker Strehl] M[2040]:=[G,{Ab = Union(b,Prod(b,A),Prod(b,Ab,Ar)), Ar = Union(r,Prod(r,A),Prod(r,Ab,Ar)), A = Union(Ab,Ar), A2 = Union(Prod(r,Ab),Prod(b,Ar)), C = Cycle(Union(A2,b,r)), G = Set(C), b = Atom, r = Atom},labelled]: > seq(count(M[2040],size=n),n=0..13); 1, 2, 12, 120, 1680, 30240, 665280, 17297280, 518918400, 17643225600, 670442572800, 28158588057600, 1295295050649600, 64764752532480000 # necklaces with beads from 3 colors [PF] M[2548]:=[N,{N=Cycle(Union(Z$3))},unlabelled]: > seq(count(M[2548],size=n),n=1..22); 3, 6, 11, 24, 51, 130, 315, 834, 2195, 5934, 16107, 44368, 122643, 341802, 956635, 2690844, 7596483, 21524542, 61171659, 174342216, 498112275, 1426419858 > draw(M[2040],size=13); Set(Cycle(r[1], b[7], Prod(r[9], Prod(b[3], b[6], Prod(r[5], r[8]))), b[12], Prod(r[2], Prod(b[10], b[4])), Prod(b[11], r[13]))) # mappings from n points to themselves [PF] M[2671]:=[F,{F=Set(K), K=Cycle(T), T=Prod(Z,Set(T))},unlabelled]: > seq(count(M[2671],size=n),n=1..21); 1, 3, 7, 19, 47, 130, 343, 951, 2615, 7318, 20491, 57903, 163898, 466199, 1328993, 3799624, 10884049, 31241170, 89814958, 258604642, 745568756 > draw(M[2671],size=15); Set(Cycle(Prod(Z, Set(Prod(Z, Set(Prod(Z, Epsilon), Prod(Z, Set(Prod(Z, Set( Prod(Z, Epsilon), Prod(Z, Epsilon), Prod(Z, Set(Prod(Z, Epsilon), Prod(Z, Epsilon), Prod(Z, Epsilon), Prod(Z, Set(Prod(Z, Epsilon), Prod(Z, Epsilon), Prod(Z, Epsilon))))))))))))))) # Unlabelled trees of height 3 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[2732]:= n -> count(ht(3),size=n)-count(ht(2),size=n): > seq(M[2732](n),n=4..29); 1, 3, 8, 18, 38, 76, 147, 277, 509, 924, 1648, 2912, 5088, 8823, 15170, 25935, 44042, 74427, 125112, 209411, 348960, 579326, 958077, 1579098, 2593903, 4247768 # Oriented trees [PZ] alias(Int=`combstruct/Int`,Delta=`combstruct/Delta`,Theta=`combstruct/Theta`): M[2756]:=[r,{R=Prod(Z,Set(R),Set(R)),r=Int(Union(R,r2,r2)), r2=Prod(R,Delta[Set(2)](Theta(R)))},unlabelled]: # there is a typo in the two terms before the last one in EIS > seq(count(M[2756],size=n),n=1..20); 1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, 2266502, 10598452, 50235931, 240872654, 1166732814, 5702001435, 28088787314, 139354922608 > draw(M[2756],size=20): > lprint("); Prod(Z,Set(Prod(Z,Epsilon,Epsilon)),Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Epsilon, Epsilon),Prod(Z,Epsilon,Set(Prod(Z,Set(Prod(Z,Set(Prod(Z,Epsilon,Epsilon)), Epsilon),Prod(Z,Set(Prod(Z,Epsilon,Epsilon)),Set(Prod(Z,Set(Prod(Z,Set(Prod(Z, Set(Prod(Z,Epsilon,Set(Prod(Z,Set(Prod(Z,Epsilon,Epsilon)),Set(Prod(Z,Set(Prod( Z,Epsilon,Epsilon)),Epsilon)))))),Set(Prod(Z,Epsilon,Epsilon)))),Epsilon)), Epsilon)))),Epsilon)))),Epsilon)),Epsilon))) # forests with trees of height at most 1 [PF] M[2857]:=[F,{F=Set(K), K=Cycle(T,card=1), T=Prod(Z,Set(Z))},labelled]: > seq(count(M[2857],size=n),n=0..17); 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, 293608, 2237921, 18210094, 157329097, 1436630092, 13810863809, 139305550066, 1469959371233, 16184586405328 > draw(M[2857],size=17); Set(Cycle(Prod(Z[7], Set(Z[8], Z[12]))), Cycle(Prod(Z[3], Epsilon)), Cycle(Prod(Z[13], Set(Z[11]))), Cycle(Prod(Z[15], Epsilon)), Cycle(Prod(Z[5], Set(Z[2], Z[16]))), Cycle(Prod(Z[6], Set(Z[14], Z[9]))), Cycle(Prod(Z[10], Set(Z[1], Z[4], Z[17])))) # Schroeder's second problem [PF] # (Dissections of a polygon or parenthesizing a product) M[2898]:=[S,{S=Union(Z,Sequence(S,card>=2))},unlabelled]: > seq(count(M[2898],size=n),n=1..19); 1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, 518859, 2646723, 13648869, 71039373, 372693519, 1968801519, 10463578353, 55909013009, 300159426963 > subs(Sequence=Seq,draw(M[2898],size=19)); Seq(Seq(Z, Z), Seq(Seq(Z, Z), Z, Z, Seq(Z, Z, Seq(Seq(Seq(Z, Seq(Z, Z)), Seq(Z, Z), Seq(Z, Z, Z)), Z, Z)), Z)) # permutations with exactly 2 cycles (Stirling numbers of first kind) [PF] a:=proc(m) [A,{A=Set(Cycle(Z),card=m)},labelled]; end: M[2902]:=a(2): > seq(count(M[2902],size=n),n=2..17); 1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576, 10628640, 120543840, 1486442880, 19802759040, 283465647360, 4339163001600, 70734282393600 # Sets of segments (Forest of greatest height) [PF] M[2950]:=[R,{R=Set(Sequence(Z,card>=1))},labelled]: > seq(count(M[2950],size=n),n=0..16); 1, 1, 3, 13, 73, 501, 4051, 37633, 394353, 4596553, 58941091, 824073141, 12470162233, 202976401213, 3535017524403, 65573803186921, 1290434218669921 > draw(M[2950],size=16); Set(Sequence(Z[10], Z[13], Z[16], Z[5], Z[14], Z[11], Z[1]), Sequence(Z[12], Z[3], Z[8], Z[9], Z[7], Z[2], Z[4], Z[15], Z[6])) # Ordered set partitions, surjections (Preferential arrangements) [PF] M[2952]:=[R,{R=Sequence(Set(Z,card>=1))},labelled]: > seq(count(M[2952],size=n),n=0..16); 1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, 1622632573, 28091567595, 526858348381, 10641342970443, 230283190977853, 5315654681981355 > draw(M[2952],size=16); Sequence(Set(Z[5], Z[14], Z[4]), Set(Z[6], Z[11]), Set(Z[1], Z[12]), Set(Z[8]), Set(Z[16]), Set(Z[3], Z[9]), Set(Z[13], Z[15]), Set(Z[7], Z[2]), Set(Z[10])) # connected functional graphs [PF] M[3040]:=[F,{F=Set(K,card=1), K=Cycle(T), T=Prod(Z,Set(T))},labelled]: > seq(count(M[3040],size=n),n=1..14); 1, 3, 17, 142, 1569, 21576, 355081, 6805296, 148869153, 3660215680, 99920609601, 2998836525312, 98139640241473, 3478081490967552 > draw(M[3040],size=14): > lprint("); Set(Cycle(Prod(Z[11],Set(Prod(Z[7],Set(Prod(Z[2],Set(Prod(Z[1],Set(Prod(Z[13] ,Set(Prod(Z[8],Set(Prod(Z[9],Set(Prod(Z[5],Epsilon))))),Prod(Z[6],Epsilon)))))) ))))),Prod(Z[3],Set(Prod(Z[4],Set(Prod(Z[12],Epsilon))))),Prod(Z[10],Epsilon), Prod(Z[14],Epsilon))) # necklaces with beads from 4 colors [PF] M[3390]:=[N,{N=Cycle(Union(Z$4))},unlabelled]: > seq(count(M[3390],size=n),n=1..19); 4, 10, 24, 70, 208, 700, 2344, 8230, 29144, 104968, 381304, 1398500, 5162224, 19175140, 71582944, 268439590, 1010580544, 3817763740, 14467258264 # partitions with blocks of size>=2 [PF] p:=proc(m) [B,{B=Set(Set(Z,card>=m))},labelled] end: M[3423]:=p(2): > seq(count(M[3423],size=n),n=0..20); 1, 0, 1, 1, 4, 11, 41, 162, 715, 3425, 17722, 98253, 580317, 3633280, 24011157, 166888165, 1216070380, 9264071767, 73600798037, 608476008122, 5224266196935 # Unlabelled trees of height 4 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[3461]:= n -> count(ht(4),size=n)-count(ht(3),size=n): > seq(M[3461](n),n=5..27); 1, 4, 13, 36, 93, 225, 528, 1198, 2666, 5815, 12517, 26587, 55933, 116564, 241151, 495417, 1011950, 2055892, 4157514, 8371318, 16792066, 33564256, 66875221 # permutations with at least 2 cycles [PF] a:=proc(m) [A,{A=Set(Cycle(Z),card>=m)},labelled]; end: M[3545]:=a(2): > seq(count(M[3545],size=n),n=2..17); 1, 4, 18, 96, 600, 4320, 35280, 322560, 3265920, 36288000, 439084800, 5748019200, 80951270400, 1220496076800, 19615115520000, 334764638208000 # Functional graphs or n^n [PF] M[3619]:=[F,{F=Set(K), K=Cycle(T), T=Prod(Z,Set(T))},labelled]: > seq(count(M[3619],size=n),n=1..14); 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, 285311670611, 8916100448256, 302875106592253, 11112006825558016 > draw(M[3619],size=14); Set(Cycle(Prod(Z[13], Set(Prod(Z[1], Epsilon), Prod(Z[6], Epsilon))), Prod(Z[4], Epsilon), Prod(Z[7], Set(Prod(Z[12], Epsilon), Prod(Z[2], Epsilon))), Prod(Z[5], Set(Prod(Z[9], Epsilon))), Prod(Z[11], Epsilon), Prod(Z[10], Set(Prod(Z[8], Epsilon))), Prod(Z[14], Epsilon), Prod(Z[3], Epsilon))) # necklaces with beads from 5 colors [PF] M[3860]:=[N,{N=Cycle(Union(Z$5))},unlabelled]: > seq(count(M[3860],size=n),n=1..18); 5, 15, 45, 165, 629, 2635, 11165, 48915, 217045, 976887, 4438925, 20346485, 93900245, 435970995, 2034505661, 9536767665, 44878791365, 211927736135 # Unlabelled trees of height 5 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[3884] := n -> count(ht(5),size=n)-count(ht(4),size=n): > seq(M[3884](n),n=6..26); 1, 5, 19, 61, 180, 498, 1323, 3405, 8557, 21103, 51248, 122898, 291579, 685562, 1599209, 3705122, 8532309, 19543867, 44552066, 101124867, 228640542 # Unlabelled trees of height 6 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[4170] := n -> count(ht(6),size=n)-count(ht(5),size=n): > seq(M[4170](n),n=7..26); 1, 6, 26, 94, 308, 941, 2744, 7722, 21166, 56809, 149971, 390517, 1005491, 2564164, 6485901, 16289602, 40659669, 100934017, 249343899, 613286048 # permutations with exactly 3 cycles (Stirling numbers of first kind) [PF] a:=proc(m) [A,{A=Set(Cycle(Z),card=m)},labelled]; end: M[4218]:=a(3): > seq(count(M[4218],size=n),n=3..17); 1, 6, 35, 225, 1624, 13132, 118124, 1172700, 12753576, 150917976, 1931559552, 26596717056, 392156797824, 6165817614720, 102992244837120 # Labelled trees of height=2 # ht(m) counts trees of height<=m ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},labelled] end: M[4220]:=n->count(ht(2),size=n)-count(ht(1),size=n): > seq(M[4220](n),n=3..17); 6, 36, 200, 1170, 7392, 50568, 372528, 2936070, 24617120, 218521116, 2045278248, 20112821274, 207162957120, 2228888801040, 24989309310944 # Unlabelled trees of height 7 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[4408]:= n -> count(ht(7),size=n)-count(ht(6),size=n): > seq(M[4408](n),n=8..27); 1, 7, 34, 136, 487, 1615, 5079, 15349, 45009, 128899, 362266, 1002681, 2740448, 7411408, 19865445, 52840977, 139624510, 366803313, 958696860, 2494322662 # Unlabelled trees of height 8 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},unlabelled]; end: M[4525]:= n -> count(ht(8),size=n)-count(ht(7),size=n): > seq(M[4525](n),n=9..27); 1, 8, 43, 188, 728, 2593, 8706, 27961, 86802, 262348, 776126, 2256418, 6466614, 18311915, 51334232, 142673720, 393611872, 1078955836, 2941029334 # permutations with exactly 4 cycles (Stirling numbers of first kind) [PF] a:=proc(m) [A,{A=Set(Cycle(Z),card=m)},labelled]; end: M[4730]:=a(4): > seq(count(M[4730],size=n),n=4..18); 1, 10, 85, 735, 6769, 67284, 723680, 8409500, 105258076, 1414014888, 20313753096, 310989260400, 5056995703824, 87077748875904, 1583313975727488 # partitions with blocks of size>=3 [PF] p:=proc(m) [B,{B=Set(Set(Z,card>=m))},labelled] end: M[4789]:=p(3): > seq(count(M[4789],size=n),n=0..21); 1, 0, 0, 1, 1, 1, 11, 36, 92, 491, 2557, 11353, 60105, 362506, 2169246, 13580815, 91927435, 650078097, 4762023647, 36508923530, 292117087090, 2424048335917 # permutations with exactly 5 cycles (Stirling numbers of first kind) [PF] a:=proc(m) [A,{A=Set(Cycle(Z),card=m)},labelled]; end: M[4983]:=a(5): > seq(count(M[4983],size=n),n=5..18); 1, 15, 175, 1960, 22449, 269325, 3416930, 45995730, 657206836, 9957703756, 159721605680, 2706813345600, 48366009233424, 909299905844112 # permutations with exactly 6 cycles (Stirling numbers of first kind) [PF] a:=proc(m) [A,{A=Set(Cycle(Z),card=m)},labelled]; end: M[5114]:=a(6): > seq(count(M[5114],size=n),n=6..18); 1, 21, 322, 4536, 63273, 902055, 13339535, 206070150, 3336118786, 56663366760, 1009672107080, 18861567058880, 369012649234384 # Labelled trees of height=3 [PF] # ht(m) describes trees of height <= m ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},labelled] end: M[5159]:=n -> count(ht(3),size=n)-count(ht(2),size=n): > seq(M[5159](n),n=4..19); 24, 300, 3360, 38850, 475776, 6231960, 87530400, 1316954430, 21173760960, 362670636900, 6596214691248, 126980000240730, 2579214238608000, 55118036257959600, 1235935135837111104, 29009023670878484598 # permutations with exactly 7 cycles (Stirling numbers of first kind) [PF] a:=proc(m) [A,{A=Set(Cycle(Z),card=m)},labelled]; end: M[5202]:=a(7): > seq(count(M[5202],size=n),n=7..19); 1, 28, 546, 9450, 157773, 2637558, 44990231, 790943153, 14409322928, 272803210680, 5374523477960, 110228466184200, 2353125040549984 # Labelled trees of height=4 [PF] ht:=proc(m) local i; [T0,{seq(T.i=Prod(Z,Set(T.(i+1))),i=0..m-1),T.m=Z},labelled] end: M[5378]:=n -> count(ht(4),size=n)-count(ht(3),size=n): > seq(M[5378](n),n=5..19); 120, 2520, 43680, 757680, 13747104, 264181680, 5395040640, 117080049240, 2696387899920, 65774992411128, 1695845836077120, 46110625382246880, 1319345179723609920, 39640903618873667040, 1248193457738661143808 ####################### other nice sequences not in EIS ####################### # centered hydrocarbons with n atoms Alkyl:=proc(k) subs('K'=k,proc(n) if n0 then 0 else # a bicentered hydrocarbons if of the form CkH2k+1-CkH2k+1 binomial(count(M[1146],size=n/2)+1,2) fi end: