Barry Cipra - cp's OEIS frontend

A357442 Consider a clock face with 2*n "hours" marked around the dial; a(n) = number of ways to match the even hours to the odd hours, modulo rotations and reflections.

1, 1, 3, 5, 17, 53, 260, 1466, 10915, 93196, 917898, 10015299, 119914982, 1557364352, 21797494987, 326930305166, 5230756117008, 88922108947567, 1600594738591550, 30411281088326498, 608225534389576956, 12772735698577492558

Offset: 1

N. J. A. Sloane, Nov 06 2022, based on an email from Barry Cipra, Oct 26 2022

nonn

Barry Cipra, Illustration for a(5) = 17
N. J. A. Sloane, Sketch illustrating a(1) = a(2) = 1, a(3) = 3
Philip Todd, Theorem Discovery Amongst Cyclic Polygons, arXiv:2401.13002 [cs.CG], 2024.

Cf. A000031, A000699, A007769, A059375.

{ a357442(n) = ( sumdiv(n,d,(n\d)!*d^(n\d)*eulerphi(d)) + n*sum(k=0,n\2,n!\k!\2^k\(n-2*k)!) + if(n%2, n*((n-1)\2)!*2^((n-1)\2) + sumdiv(n,d, eulerphi(d)*sum(k=0,n\d\2,(n\d)! \ (2*k+1)! \ ((n\d-1)\2-k)! * (d/2)^((n\d-1)\2-k) ))) )\n\4; } \\ Max Alekseyev, Nov 10 2022

See PARI code for the formula. - Max Alekseyev, Nov 10 2022

Terms a(7) onward from Max Alekseyev, Nov 10 2022

A333296 Largest number of non-congruent integer-sided bricks that can be assembled into an n X n X n cube.

Original entry on oeis.org

1, 1, 6, 10, 15, 21, 28, 35, 43, 52

Offset: 1

N. J. A. Sloane, Mar 25 2020, following a suggestion from Barry Cipra

The problem originated with Barry Cipra; the 10 values given here were found by Rob Pratt using integer programming.

Mathematics Stack Exchange, Different bricks making a cube, Mar 23 2020.

A170941 a(n+1) = a(n) + n*a(n-1) - a(n-2) + a(n-3).

Original entry on oeis.org

1, 1, 1, 2, 5, 13, 37, 112, 363, 1235, 4427, 16526, 64351, 259471, 1083935, 4668704, 20732609, 94607409, 443476993, 2130346450, 10482534517, 52740593933, 271186949333, 1423127827792, 7618169603035, 41554791114643, 230857090312059, 1305086617517534

Offset: 0

Barry Cipra, Feb 09 2010

The number of different RNA structures for sequences of length n.
a(n) = number of involutions on [n] that contain no adjacent transpositions. For example, a(3) = 2 counts (in cycle form) the identity and (1,3), but not (1,2) or (2,3) because they are adjacent transpositions. - David Callan, Nov 11 2012
Conjecture: a(n)/A000085(n) -> 1/e as n -> inf. In other words, the asymptotic proportion of involutions that contain no adjacent transpositions is conjecturally = 1/e. - David Callan, Nov 11 2012
Number of matchings (i.e. Hosoya index) in the complement of P_n where P_n is the n-path graph. - Andrew Howroyd, Mar 15 2016

M. Nebel, Combinatorial Properties of RNA secondary Structures, 2001.
M. Regnier, Generating Functions in Computational Biology, INRIA, March 3, 1997.

Alois P. Heinz, Table of n, a(n) for n = 0..500
Mohammad Ganjtabesh, Armin Morabbi and Jean-Marc Steyaert, Enumerating the number of RNA structures [See slide 8]
Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.
I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
P. Stadler and C. Haslinger, RNA structures with pseudo-knots: Graph theoretical and combinatorial properties, Bull. Math. Biol., Preprint 97-03-030, 1997. See Theorem 5, p. 36 for the titular recurrence.
M. S. Waterman, Secondary structure of single-stranded nucleic acids, Studies in Foundations and Combinatorics, Vol. 1, pp. 167-212, 1978.
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Path Complement Graph

Column k=0 of A217876.

Column k=1 of A239144.

A170941 := proc(n) option remember; if n < 4 then [1$3,2][n+1] ; else procname(n-1)+(n-1)*procname(n-2)-procname(n-3)+procname(n-4) ; end if; end proc: seq(A170941(n), n=0..40) ; # R. J. Mathar, Feb 20 2010

a[0] = a[1] = a[2] = 1; a[3] = 2; a[n_] := a[n] = a[n-1] + (n-1) a[n-2] - a[n-3] + a[n-4];
Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Dec 30 2017 *)
RecurrenceTable[{a[n + 1] == a[n] + n a[n - 1] - a[n - 2] + a[n - 3], a[0] == a[1] == a[2] == 1, a[3] == 2}, a, {n, 20}] (* Eric W. Weisstein, Apr 12 2018 *)
nxt[{n_,a_,b_,c_,d_}]:={n+1,b,c,d,d+(n+1)c-b+a}; NestList[nxt,{2,1,1,1,2},30][[All,2]] (* Harvey P. Dale, Feb 16 2020 *)

a=vector(50); a[1]=a[2]=1;a[3]=2; a[4]=5; for(n=5, #a, a[n]=a[n-1]+(n-1)*a[n-2]-a[n-3]+a[n-4]); concat(1, a) \\ Altug Alkan, Apr 12 2018

a(n) ~ exp(sqrt(n) - n/2 - 5/4) * n^(n/2) / sqrt(2) * (1 + 31/(24*sqrt(n))). - Vaclav Kotesovec, Sep 10 2014

More terms from R. J. Mathar, Feb 20 2010

a(0)=1 inserted and program adapted by Alois P. Heinz, Mar 10 2014

A137200 Number of ways to tile an n X 1 strip with 1 X 1 squares and 2 X 1 dominoes with the restriction that no three consecutive tiles are of the same type.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 7, 9, 13, 18, 25, 34, 47, 65, 90, 124, 171, 236, 326, 450, 621, 857, 1183, 1633, 2254, 3111, 4294, 5927, 8181, 11292, 15586, 21513, 29694, 40986, 56572, 78085, 107779, 148765, 205337, 283422, 391201, 539966, 745303, 1028725, 1419926, 1959892

Offset: 0

Barry Cipra, Mar 03 2008

nonn

Without the restriction one gets the Fibonacci numbers, A000045.

Might be called the no-tri-bonacci numbers.

			For example (using 1's to denote squares and 2's to denote dominoes), a(6)=7 because you have the tilings 11211, 1122, 1212, 1221, 2112, 2121 and 2211 and no others.

Brian Rice, Proof of the recurrence
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

Cf. A000045.

Join[{1},LinearRecurrence[{1,0,0,1},{1,2,2,4},50]] (* Harvey P. Dale, Jul 26 2011 *)

a(n) = a(n-1) + a(n-4) for n>4; g.f.: (1+x^2+x^4)/(1-x-x^4). Also a(n) = a(n-2) + a(n-4) + a(n-5).

A133800 Triangle read by rows in which row n gives number of ways to partition n labeled elements into k pie slices allowing the pie to be turned over (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 6, 3, 1, 15, 25, 30, 12, 1, 31, 90, 195, 180, 60, 1, 63, 301, 1050, 1680, 1260, 360, 1, 127, 966, 5103, 12600, 15960, 10080, 2520, 1, 255, 3025, 23310, 83412, 158760, 166320, 90720, 20160, 1, 511, 9330, 102315, 510300, 1369620

Offset: 1

Barry Cipra and N. J. A. Sloane, Jan 17 2008

			Triangle begins:
1,
1,  1,
1,  3,   1,
1,  7,   6,    3,
1, 15,  25,   30,   12,
1, 31,  90,  195,  180,   60,
1, 63, 301, 1050, 1680, 1260, 360.
...
For row n = 4 we have the following "pies":
. 1
./ \
2 . 3 . 12 .. 12 . 123
.\ / .. / \ .(..)..(..)
. 4 .. 3--4 . 34 .. 4 .. (1234)
k=4 .. k=3 ..k=2 . k=2 . k=1
(3)....(6)...(3)..(4)... (1)

C. G. Bower, Transforms (2)

Row sums give A032262. Diagonals give A000225, A000392, A032263, A133799, A001710.

A001710 := proc(n) if n < 2 then 1; else n!/2 ; fi ; end: A008277 := proc(n,k) combinat[stirling2](n,k) ; end: A133800 := proc(n,k) A008277(n,k)*A001710(k-1) ; end: for n from 1 to 10 do for k from 1 to n do printf("%d, ",A133800(n,k)) ; od: od: # R. J. Mathar, Jan 18 2008

A001710[n_] := If[n<2, 1, n!/2]; A008277[n_, k_] := StirlingS2[n, k]; A133800[n_, k_] := A008277[n, k]*A001710[k-1]; Table[A133800[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 20 2014, after R. J. Mathar *)
(* A (n >= 0, k >= 0)-based version: *)
A133800[n_, k_] := k! StirlingS2[n+1, k+1] / If[k>1, 2, 1];
Table[A133800[n,k], {n,0,9}, {k,0,n}] // Flatten (* Peter Luschny, Oct 19 2017 *)

Take triangle of Stirling numbers of second kind (A008277) and multiply k-th column by A001710(k) (order of alternating group A_k).

More terms from R. J. Mathar, Jan 18 2008

A129860 Number of unrooted bifurcating tree shapes with n leaves.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 18, 37, 66, 135, 265, 552, 1132, 2410, 5098, 11020, 23846, 52233, 114796, 254371, 565734, 1265579, 2841632, 6408674, 14502229, 32935002, 75021750, 171404424, 392658842, 901842517, 2076217086, 4790669518, 11077270335

Offset: 2

Barry Cipra, May 23 2007

nonn

Alternatively, the number of unrooted, unlabeled binary tree topologies with n leaves. - Steven Kelk, Jul 22 2016

This sequence is identical to A000672 (3-valent trees, boron trees, or binary trees) except the offset is different. A000672 is the main entry for this sequence and has much more information (including a b-file with many more terms). Thanks to Steven Kelk for noticing the errors in the present sequence (which have now been corrected), and for discovering the connection with A000672. - N. J. A. Sloane, Jul 22 2016

Joseph Felsenstein, Inferring Phylogenies. Sinauer Associates, Inc., 2004, page 33. Note that at least the first two editions give an incorrect version of this sequence.

Jean-François Fortin, Wen-Jie Ma, Witold Skiba, Seven-Point Conformal Blocks in the Extended Snowflake Channel and Beyond, arXiv:2006.13964 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, Witold Skiba, All Global One- and Two-Dimensional Higher-Point Conformal Blocks, arXiv:2009.07674 [hep-th], 2020.

Essentially the same sequence as A000672.

Entry revised by N. J. A. Sloane, Jul 22 2016 at the suggestion of Steven Kelk

A094866 Number of truncated ST-pairs O(q^n).

Original entry on oeis.org

1, 2, 4, 6, 11, 15, 26, 41, 67, 96, 138, 197, 300, 431, 636, 893, 1258, 1723, 2447, 3425, 4962, 6839, 10000, 13989, 21383, 30781, 48292, 70456, 110214, 159686, 253265, 374385, 591648, 876405, 1354888

Offset: 3

Barry Cipra, Jun 15 2004

nonn

A truncated ST-pair O(q^n) consists of a subset S of {1, 2, ..., n-1} and a subset T of {1, 2, ..., n-2} such that (Product_{k in S} 1/(1-q^k)) - q (Product_{k in T} 1/(1-q^k)) = 1 + O(q^n). - Andrey Zabolotskiy, Feb 27 2024

F. G. Garvan, Shifted and Shiftless Partition Identities, in Number Theory for the Millennium II (M. A. Bennett et al., eds.), AK Peters, Ltd. 2002, pp. 75-92.

F. G. Garvan, Shifted and shiftless partition identities (2001).

st[n_] := Select[Flatten[Table[{s, t}, {s, Subsets@Range[n - 1]}, {t, Subsets@Range[n - 2]}], 1], Normal[Product[1/(1-q^k) + O[q]^n, {k, First@#}] - q Product[1/(1-q^k) + O[q]^n, {k, Last@#}] - 1] == 0 &];
Table[Length@st[n], {n, 3, 9}] (* Andrey Zabolotskiy, Feb 27 2024 *)

A094708 Size of the smallest set hitting all {x, 2x, 3x} contained in D(n) = the first n 3-smooth numbers {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27,...} (A003586).

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 13, 13, 13, 13, 13, 14, 14, 15, 15, 15, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 21

Offset: 1

Barry Cipra, Jun 15 2004

nonn

A057561(n) = n - a(n). [Steven Finch, Feb 25 2009]

F. Chung, P. Erdős and R. L. Graham, On Sparse Sets Hitting Linear Forms, in Number Theory for the Millennium I (M. A. Bennett et al., eds.), 2002, pp. 257-272.
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]

Cf. A003586, A057561.

More terms from Sean A. Irvine, Nov 19 2015

A079486 Number of different solutions to a variant of the 3-ball tennis ball problem.

Original entry on oeis.org

3, 15, 103, 879, 8787, 99061, 1227369, 16409937, 233588249, 3504149013, 54963273921, 895797910129, 15094359120933, 261882874511985, 4662472442136561, 84940003965749601, 1579633610378515989, 29927014639635474589, 576597813697577550447, 11280469732919709557493

Offset: 1

Barry Cipra, Jan 19 2003

You're given labeled balls three at time (labeled 1,2,3 then 4,5,6 etc.), choose two balls from those still on hand (including the three you've just been given) and throw the larger out the window onto the front lawn, the smaller onto the back lawn.

a(n) is the number of 2 X n matrices of positive integers, with the numbers in each row and column increasing, the numbers in column k less than or equal to 3k and no number used more than once.

Kevin Ryde, Table of n, a(n) for n = 1..325
Sean A. Irvine, Java program (github)
Kevin Ryde, PARI/GP Code and Notes

Cf. A000108, A001764, A002293, A049235.

PARI
```
\\ See links.
```

Larger terms through to a(12) computed by Matt Richey.

a(13) onwards from Sean A. Irvine, Aug 17 2025

A055518 a_{k+1} = 6a_k + 11a_{k-1} - 19a_{k-2} - 4a_{k-3} + a_{k-4}, a_1=1, a_2=2, a_3=19, a_4=118, a_5=875.

Original entry on oeis.org

1, 2, 19, 118, 875, 6180, 44389, 317236, 2270893, 16247718, 116267271, 831957002, 5953209015, 42598982984, 304823192665, 2181205436792, 15607926184313, 111684733527034, 799175992102923, 5718617425358462, 40920380028968819

Offset: 1

Barry Cipra, Jul 04 2000

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (6,11,-19,-4,1).

Cf. A054894, A055519.

LinearRecurrence[{6,11,-19,-4,1},{1,2,19,118,875},30] (* Harvey P. Dale, Nov 25 2018 *)

a(n) = Sum_{k=1..n} Fibonacci(k)^4*a(n-k), a(0)=1. - Vladeta Jovovic, Apr 23 2003

cp's OEIS Frontend

User: Barry Cipra

A357442 Consider a clock face with 2*n "hours" marked around the dial; a(n) = number of ways to match the even hours to the odd hours, modulo rotations and reflections.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A333296 Largest number of non-congruent integer-sided bricks that can be assembled into an n X n X n cube.

Views

Author

Keywords

Comments

Links

A170941 a(n+1) = a(n) + n*a(n-1) - a(n-2) + a(n-3).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A137200 Number of ways to tile an n X 1 strip with 1 X 1 squares and 2 X 1 dominoes with the restriction that no three consecutive tiles are of the same type.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A133800 Triangle read by rows in which row n gives number of ways to partition n labeled elements into k pie slices allowing the pie to be turned over (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A129860 Number of unrooted bifurcating tree shapes with n leaves.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A094866 Number of truncated ST-pairs O(q^n).

Views

Author

Keywords

Comments

References

Links

Programs

Mathematica

A094708 Size of the smallest set hitting all {x, 2x, 3x} contained in D(n) = the first n 3-smooth numbers {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27,...} (A003586).

Views

Author

Keywords

Comments

Links

Crossrefs

A055518 a_{k+1} = 6a_k + 11a_{k-1} - 19a_{k-2} - 4a_{k-3} + a_{k-4}, a_1=1, a_2=2, a_3=19, a_4=118, a_5=875.