Jerrold Grossman - cp's OEIS frontend

A381194 Number of equal-length matchings of 2n uniformly spaced points on a circle.

1, 3, 3, 9, 5, 17, 7, 33, 15, 49, 11, 113, 13, 153, 57, 321, 17, 617, 19, 1153, 165, 2089, 23, 4577, 85, 8241, 555, 16737, 29, 34049, 31, 66177, 2109, 131137, 377, 267521, 37, 524361, 8265, 1051393, 41, 2114081, 43, 4198561, 33945, 8388697, 47, 16851905, 427, 33556689

Offset: 1

Jerrold Grossman, Feb 16 2025

nonn

a(n) is the number of ways to draw n segments of equal length so that each vertex of a regular 2n-gon is an endpoint of one of the segments. It is not difficult to prove that the Maple program given below computes the correct value. Note that a(n) = n when n is an odd prime.

Finding the value when n = 12 was a problem in the 2025 American Invitational Mathematics Examination (AIME), a part of the American Mathematics Competitions run by the Mathematical Association of America. A solution is presented in the Art of Problem Solving website.

Yifan Xie, Table of n, a(n) for n = 1..5000
Art of Problem Solving, 2025 AIME II Problems/Problem 11.

a := 1;
for i from 1 to n - 1 do
    if (2*n/gcd(2*n, i)) mod 2 = 0 then a := a + 2^gcd(2*n, i); end if;
end do;

a[n_]:=1+Sum[Boole[Mod[2n/GCD[2n,i],2]==0]2^GCD[2n,i],{i,n-1}]; Array[a,50] (* Stefano Spezia, Feb 24 2025 *)

a(n)={my(s=1); for(i=1, n-1, my(d=gcd(2*n, i)); if((2*n/d)%2 == 0, s += 2^d)); s} \\ Yifan Xie, Apr 13 2025

a(n) = 1 + Sum_{i=1..n-1} [2*n/GCD(2*n,i) mod 2 == 0] * 2^GCD(2*n,i), where [ ] denotes the Iverson bracket.

A263292 Number of distinct values of |product(A) - product(B)| where A and B are a partition of {1,2,...,n}.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 13, 26, 44, 76, 119, 238, 324, 648, 1008, 1492, 2116, 4232, 5680, 11360, 15272, 21872, 33536, 67072, 83168, 121376, 185496, 249072, 328416, 656832, 790656, 1581312, 1980192, 2758624, 4193040, 5555616, 6532896, 13065792, 19845216

Offset: 0

Jerrold Grossman, Oct 13 2015

nonn

The problem of showing that no number k is equal to |product(A)-product(B)| for infinitely many different values of n appears in a Hungarian journal for high school students in math and physics (see KöMaL link).
Compare to A038667, which provided the smallest value of |product(A) - product(B)|.
Also the number of distinct values <= sqrt(n!) of element products of subsets of [n]. - Alois P. Heinz, Oct 17 2015

			For n = 4, the four possible values of |product(A) - product(B)| are 2, 5, 10, and 23.

KöMaL-Mathematical and Physical Journal for Secondary Schools, Problems in Mathematics, September 2015.

Cf. A038667.

b:= proc(n) option remember; local f, g, h;
      if n<2 then {1}
    else f, g, h:= n!, y-> `if`(y^2<=f, y, NULL), (n-1)!;
         map(x-> {x, g(x*n), g(h/x)}[], b(n-1))
      fi
    end:
a:= n-> nops(b(n)):
seq(a(n), n=0..25);  # Alois P. Heinz, Oct 17 2015

a[n_] := Block[{v = Times @@@ Subsets[ Range[2, n], Floor[n/2]]}, Length@ Union@ Abs[v - n!/v]]; Array[a, 20] (* Giovanni Resta, Oct 17 2015 *)

from math import prod, factorial
from itertools import combinations
def A263292(n):
    m = factorial(n)
    return 1 if n == 0 else len(set(abs((p:=prod(d))-m//p) for l in range(n,n//2,-1) for d in combinations(range(1,n+1),l))) # Chai Wah Wu, Apr 07 2022

a(21)-a(27) from Giovanni Resta, Oct 17 2015

a(28)-a(38) from Alois P. Heinz, Oct 17 2015

A225177 Numerator of answer to sock-sorting problem with n socks.

Original entry on oeis.org

1, 5, 35, 311, 3377, 43373, 643475, 10831151, 203961377, 4248732053, 97006864835, 2409006894311, 64645920431057, 1864195055263613, 57489983163699635, 1888035573701458271, 65785247971229129537, 2423878578219411790373, 94161366504933859099235, 3846438440798147117812631

Offset: 1

N. J. A. Sloane, May 01 2013, based on an email from Jerrold Grossman, Apr 27 2013

Here is the problem as presented in Technology Review.
"... Fred Tydeman owns N pairs of socks, each pair a different color, which he washes when all of them are dirty. When the washing and drying are complete, he uses the following algorithm for sorting and storing the socks. Tydeman first brings the entire basket of clean socks up to the bedroom, removes one sock, and lays it on the bed. He then removes another sock at random. If the new sock matches any on the bed (initially there is only one there), he folds the pair and places it in a drawer. If there is no match, the new sock is placed on the bed and another sock is taken from the basket, again at random. Tydeman repeats the procedure until all the socks are matched and records the maximum number of unmatched socks on the bed. He would like to know the expected value of this maximum in terms of N...."
It appears that the expectation can be written as a(n)/b(n), where b(n) = A001147(n) is the product of the first n odd numbers. (This is certainly true for n <= 10.) The sequence gives the values of a(n).

			The expectations in lowest terms are 1, 5/3, 7/3, 311/105, 3377/945, 3943/945, 18385/3861, 10831151/2027025, 203961377/34459425, 4248732053/654729075, ...

Allan Gottlieb, editor, Problem M/J-2, MIT Technology Review, May-June 2013.

Paul Tek, Table of n, a(n) for n = 1..300
Milton Eisner, Problem 216, The Two-Year College Mathematics Journal, Vol. 13, No. 3, Jun., 1982, page 206.
Wenbo V. Li, Geoffrey Pritchard, A central limit theorem for the sock-sorting problem, In "High Dimensional Probability" (Oberwolfach, 1996), 245-248, Progr. Probab., 43, Birkhäuser, Basel, 1998.
David Steinsaltz, Random time changes for sock-sorting and other stochastic process limit theorems, Electron. J. Probab. 4 (1999), no. 14, 25 pp.
Paul Tek, PARI program for this sequence

Cf. A001147.

A102263 Denominators of probabilities in gift exchange problem with n people.

Original entry on oeis.org

1, 4, 36, 144, 1800, 43200, 705600, 705600, 2116800, 127008000, 23051952000, 6638962176000, 280496151936000, 31415569016832000, 471233535252480000, 471233535252480000, 54474596675186688000, 3268475800511201280000

Offset: 2

Jerrold Grossman, Feb 17 2005

n friends organize a gift exchange. The n names are put into a hat and the first person draws one. If she picks her own name, then she returns it to the bag and draws again, repeating until she has a name that is not her own. Then the second person draws, again returning his own name if it is drawn. This continues down the line. What is the probability p(n) that when the n-th person draws, only her own name will be left in the bag?

I heard about the problem from Gary Thompson at Grove City College in PA.

			p(2) through p(10) are 0, 1/4, 5/36, 19/144, 203/1800, 4343/43200, 63853/705600, 58129/705600, 160127/2116800.

Jon E. Schoenfield, Table of n, a(n) for n = 2..389
Math Forum at Drexel, A variant on the "Secret Santa"

Cf. A102262, A136300.

See A102262 for formula for p(n).

More terms from Jon E. Schoenfield, Sep 30 2006

A102262 Numerators of probabilities in gift exchange problem with n people.

Original entry on oeis.org

0, 1, 5, 19, 203, 4343, 63853, 58129, 160127, 8885501, 1500518539, 404156337271, 16040576541971, 1694200740145637, 24047240650458731, 22823917472900053, 2511014355032164231, 143734030512459889193, 49611557898193759558813, 950601970122346247310883

Offset: 2

Jerrold Grossman, Feb 17 2005

This is a version of the Secret Santa game.
n friends organize a gift exchange. The n names are put into a hat and the first person draws one. If she picks her own name, then she returns it to the bag and draws again, repeating until she has a name that is not her own. Then the second person draws, again returning his own name if it is drawn. This continues down the line. What is the probability p(n) that when the n-th person draws, only her own name will be left in the bag?
I heard about the problem from Gary Thompson at Grove City College in PA.

			p(2) through p(10) are 0, 1/4, 5/36, 19/144, 203/1800, 4343/43200, 63853/705600, 58129/705600, 160127/2116800.

Jon E. Schoenfield, Table of n, a(n) for n = 2..389
Math Forum at Drexel, A variant on the "Secret Santa"

Cf. A102263, A136300.

N:=21; a:=[]; row:=[]; T:=[]; for n in [2..N] do row[n-1]:=0; T[n]:=row; T[n][1]:=(-1)^(n-1)*Factorial(n-1) div 2; for i in [2..n-2] do T[n][i]:=(n-2)*i^2/(i-1)*T[n-1][i-1]-(n-i-2)*T[n-1][i]; end for; p:=0; for i in [1..n-2] do p+:=T[n][i]/Factorial(n-1)^2; end for; a[#a+1]:=Numerator(p); end for; a; // Jon E. Schoenfield, Dec 10 2021

From Jon E. Schoenfield, Sep 30 2006: (Start)
p(n) = Sum_{i=1..n-2} t(n,i)/(n-1)!^2
where
  t(n,i) = (n-2)*i^2/(i-1)*t(n-1,i-1) - (n-i-2)*t(n-1,i) for 1 < i < n-1;
  t(n,1) = (-1)^(n-1)*(n-1)!/2 for i = 1 and n > 2;
  t(n,i) = 0 otherwise.
(End)
Based on the values of p(n) for n <= 1000, it seems plausible that, as n increases, p(n) approaches 1/(n + log(n) + EulerGamma), where EulerGamma = 0.5772156649015... (the Euler-Mascheroni constant). - Jon E. Schoenfield, Dec 11 2021

More terms from Jon E. Schoenfield, Sep 30 2006

A098921 Let [n] = {1,2,...,n}. Let G_n be the union of all closed line segments joining any two elements of [n] X [n] along a vertical or horizontal line, or along a line with slope +-1. Then a(n) = combined total of the number of (nondegenerate) triangles and rectangles for which all edges are subsets of G_n.

Original entry on oeis.org

0, 9, 62, 211, 534, 1127, 2112, 3629, 5844, 8941, 13130, 18639, 25722, 34651, 45724, 59257, 75592, 95089, 118134, 145131, 176510, 212719, 254232, 301541, 355164, 415637, 483522, 559399, 643874, 737571, 841140, 955249, 1080592

Offset: 1

Jerrold Grossman, Oct 17 2004

The vertices of these figures need not be in [n] X [n].

Matthew Coppenbarger, Problem 11060, The American Mathematical Monthly, Vol. 111, No. 1 (2004), p. 65; Little Boxes Made of Ticky-Tacky, Solution to Problem 11060, ibid., Vol. 112, No. 8 (2005), pp. 753-754.
Index entries for linear recurrences with constant coefficients, signature (4,-5,0,5,-4,1).

F:= n -> trunc((11*n^4-2*n^3-5*n^2-22*n+18)/12);

F_n = (11n^4-2n^3-5n^2-22n+12)/12 for n even and F_n = (11n^4-2n^3-5n^2-22n+18)/12 for n odd. It can also be represented by the floor of the second expression for all n.

G.f.: -x^2*(x^4+8*x^2+26*x+9) / ((x-1)^5*(x+1)). [Colin Barker, Feb 18 2013]

A085119 a(n) = number at which the standard Ackermann function mod n stabilizes, or -1 if it does not stabilize.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 5, 2, 1, 1, 1, 9, 13, 13, 13, 13, 13, 2, 13, 13, 17, 13, 13, 5, 13, 13, 13, 22, 13, 5, 29, 1, 13, 13, 13, 29, 13, 13, 13, 7, 13, 1, 17, 13, 29, 1, 13, 1, 33, 49, 13, 20, 31, 11, 13, 11, 3, 19, 13, 19, 61, 13, 61, 13, 61, 27, 49, 10, 13, 40, 13, 34, 37

Offset: 2

Jerrold Grossman, Apr 25 2004

nonn

a(1969) = -1, but otherwise a(n) is positive for all n >= 2 and < 8000000.

[Needs program(s). - N. J. A. Sloane, May 25 2025]

J. Froemke and J. W. Grossman, A mod-n Ackermann function, or what's so special about 1969?, Amer. Math. Monthly, 100 (1993), 180-183.
Mark Rickert, The first 8 million terms a(n) [a gzipped file], March 2022.
Stan Wagon, Problem of the Week POW #1340: Modular Ackermann, March 2022.
Stan Wagon, Problem of the Week POW #1340: Solution, March 2022.

Cf. A352196, A383460.

Revised by N. J. A. Sloane, May 25 2025

cp's OEIS Frontend

User: Jerrold Grossman

A381194 Number of equal-length matchings of 2n uniformly spaced points on a circle.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

PARI

Formula

A263292 Number of distinct values of |product(A) - product(B)| where A and B are a partition of {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A225177 Numerator of answer to sock-sorting problem with n socks.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A102263 Denominators of probabilities in gift exchange problem with n people.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A102262 Numerators of probabilities in gift exchange problem with n people.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Formula

Extensions

Views

Author

Keywords

Comments

Links

Programs

Maple

Formula

A085119 a(n) = number at which the standard Ackermann function mod n stabilizes, or -1 if it does not stabilize.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions