Victor S. Miller - cp's OEIS frontend

A383447 Number of "peerless" trees on n nodes.

1, 0, 1, 1, 2, 3, 6, 9, 19, 33, 67, 130, 270, 547, 1165, 2456, 5314, 11521, 25357, 56022, 125067, 280471, 633490, 1437340, 3278912, 7510503, 17277697, 39890262, 92427559, 214835923, 500879602, 1171013350, 2744946654, 6450077870

Offset: 1

N. J. A. Sloane, May 01 2025, based on postings to the SeqFan Mailing List in April and May 2025 by Victor S. Miller, Allan C. Wechsler, Brendan McKay, and others

A "peerless" tree is an unlabeled, unrooted tree (as in A000055) with the property that if two nodes are joined by an edge then these nodes have different degrees.
Victor S. Miller reports that this sequence was first proposed on Project Euler.
Comment from Brendan McKay, May 01 2025 (Start)
The enumeration could be extended by the following argument.
If the tree has a unique centroid (not center!) then removing the centroid gives rooted subtrees of size less than n/2. If there are two centroids, they are adjacent and removing that edge gives two rooted subtrees with exactly n/2 vertices.
Start by making all rooted trees up to n/2 vertices which have no adjacent vertices of the same degree, not counting adjacencies of the root. Then classify them according to which degrees the root can be increased to without violating this condition for edges adjacent to the root.
With this information the counts for n vertices can be reconstructed. In this way getting up past 60 vertices should be possible. (End)
This sequence forms the left-most column of A383448.

Victor Miller and others, Peerless trees, Seqfan, 2025.
Project Euler, Problem 936: Peerless Trees.

Cf. A000055, A383448.

a(1)-a(8) were computed by Allan C. Wechsler, Apr 30 2025, and a(9)-a(34) by Brendan McKay, May 02 2025.

A339479 Number of partitions consisting of n parts, each of which is a power of 2, where one part is 1 and no part is more than twice the sum of all smaller parts.

Original entry on oeis.org

1, 2, 5, 13, 35, 95, 259, 708, 1938, 5308, 14543, 39852, 109216, 299326, 820378, 2248484, 6162671, 16890790, 46294769, 126886206, 347774063, 953191416, 2612541157, 7160547089, 19625887013, 53791344195, 147433273080, 404090482159, 1107545909953, 3035602173663

Offset: 1

Victor S. Miller, Apr 24 2021

nonn

a(n) is the number of n-tuples of nondecreasing integers, which are the exponents of 2 in the partition, the first of which is 0 and which are "reduced". The 1-tuple (0) is reduced. If the tuple is (x(1), ..., x(n)), then it is reduced if (x(1), ..., x(n-1)) is reduced and x(n) <= ceiling(log_2(1 + Sum_{i=1..n-1} 2^x(i))). This sequence arose in analyzing the types of partitions of a positive integer into parts which are powers of 2.

			The a(2) = 2 partitions are {1,1} and {1,2}.
The a(3) = 5 partitions are {1,1,1}, {1,1,2}, {1,1,4}, {1,2,2}, {1,2,4}.
The a(4) = 13 partitions are {1,1,1,1}, {1,1,1,2}, {1,1,1,4}, {1,1,2,2}, {1,1,2,4}, {1,1,2,8}, {1,1,4,4}, {1,1,4,8}, {1,2,2,2}, {1,2,2,4}, {1,2,2,8}, {1,2,4,4}, {1,2,4,8}.

Alois P. Heinz, Table of n, a(n) for n = 1..2285

Cf. A002572, A018819, A086449, A174980, A343801.

b:= proc(n, t) option remember; `if`(n=0, 1,
     `if`(t=0, 0, b(n, iquo(t, 2))+b(n-1, t+2)))
    end:
a:= n-> b(n, 1):
seq(a(n), n=1..30);  # Alois P. Heinz, Apr 27 2021

b[n_, t_] := b[n, t] = If[n == 0, 1, If[t == 0, 0, b[n, Quotient[t, 2]] + b[n - 1, t + 2]]];
a[n_] := b[n, 1];
Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jul 07 2021, after Alois P. Heinz *)

seq(n)={my(v=vector(n), a=vector(n)); a[1]=v[1]=1; for(n=2, n, for(j=1, n-1, v[n-(n-j)\2] += v[j]); a[n]=vecsum(v)); a} \\ Andrew Howroyd, Apr 25 2021

from functools import cache
@cache
def r339479(n, k):
    if n == 0:
        return 1
    elif k == 0:
        return r339479(n - 1, 1)
    else:
        return r339479(n - 1, k + 1) + r339479(n, k // 2)
def a339479(n): return r339479(n,0)
print([a339479(n) for n in range(1, 100)])

G.f.: x/(1 - x - B(x)) where B(x) is the g.f. of A002572.

a(n) = F(n,0) where F(0,k) = 1, F(n,0) = F(n-1,1) for n > 0 and F(n,k) = F(n-1,k+1) + F(n, floor(k/2)) for n,k > 0. In this recursion, F(n,k) gives the number of partitions with n parts where the sum of all parts smaller than the current part size being considered is between k and k+1 multiples of the part size. This function is independent of the current part size. In the case that k is zero, the only choice is to add a part of the current part size, otherwise parts of double the size are also a possibility. - Andrew Howroyd, Apr 24 2021

Terms a(19) and beyond from Andrew Howroyd, Apr 24 2021

A267132 Unipotent n X n matrices over GF(2) that are squares of other such matrices.

Original entry on oeis.org

1, 1, 22, 316, 85096, 23105944, 87537588832

Offset: 1

Victor S. Miller, Jan 13 2016

			a(2) = 1, the matrix is [[1,0],[0,1]].

Victor S. Miller, Counting Matrices that are Squares, arXiv:1606.09299 [math.GR], 2016.

Cf. A006950 which counts the partitions involved.

a(n)/A002884(n) = sum(lambda,1/C(lambda,2)), where the sum is over all partitions lambda whose conjugate has odd parts with multiplicity <=1 (see A006950), and C(lambda,2) = prod(i>=1,prod(k=0 to m_i(lambda),1-2^(-k))), and m_i(lambda) is the multiplicity of i in the partition lambda (proved).

A266462 The number of conjugacy classes of invertible n X n matrices over GF(2) which are squares of other such matrices.

Original entry on oeis.org

1, 1, 2, 5, 10, 20, 41, 82, 166, 334, 667, 1336, 2682, 5360, 10724, 21467, 42936, 85876, 171786, 343574, 687184, 1374427, 2748852, 5497766, 10995706, 21991402, 43982908, 87966150, 175932383, 351864964, 703730584, 1407461288, 2814923196, 5629847656, 11259695532

Offset: 0

Victor S. Miller, Dec 29 2015

nonn

It follows from the form of the generating function that a(n) is asymptotic to alpha*2^n where alpha = Product_{m>=1} (1-(1/16)^m)*(1-2*(1/4)^m)/((1-2*(1/16)^m)*(1-(1/4)^m)). [corrected by Jason Yuen, May 19 2025]

N. J. A. Sloane, Table of n, a(n) for n = 0..60 [Based on the table in Miller (2016)]
Victor S. Miller, Counting Matrices that are Squares, arXiv:1606.09299 [math.GR], 2016.
Index entries for matrices, binary, which are squares

Cf. A006950.

terms = 35; CoefficientList[Product[(1-2x^(2n))(1-x^(2n))/((1-2x^n) (1-2x^(4n))(1+x^(2n-1))), {n, 1, terms}] + O[x]^terms, x] (* Jean-François Alcover, Aug 06 2018 *)

G.f.: Product_{n>=1} (1-2*x^(2*n))*(1-x^(2*n))/((1-2*x^n)*(1-2*x^(4*n))*(1+x^(2*n-1))).

More terms from Alois P. Heinz, Dec 29 2015

A235459 Number of facets of the correlation polytope of degree n.

Original entry on oeis.org

2, 4, 16, 56, 368, 116764, 217093472

Offset: 1

Victor S. Miller, Jan 10 2014

The correlation polytope of degree n is the set of symmetric n X n matrices, P such that P[i,j] = Prob(X[i] = 1 and X[j] = 1) where (X[1],...,X[n]) is a sequence of 0/1 valued random variables (not necessarily independent). It is the convex hull of all n X n symmetric 0/1 matrices of rank 1.
The correlation polytope COR(n) is affinely equivalent to CUT(n+1), where CUT(n) is the cut polytope of complete graph on n vertices -- the convex hull of indicator vectors of a cut delta(S) -- where S is a subset of the vertices. The cut delta(S) is the set of edges with one end point in S and one endpoint not in S.
According to the SMAPO database it is conjectured that a(8) = 12246651158320. This database also says that the above value of a(7) is conjectural, but Ziegler lists it as known.

			a(2) corresponds to 0 <= p[1,2] <= p[1,1],p[2,2] and p[1,1] + p[2,2] - p[1,2] <= 1.

M. M. Deza and M. Laurent, Geometry of Cuts and Metrics, Springer, 1997, pp. 52-54.
G. Kalai and G. Ziegler, ed. "Polytopes: Combinatorics and Computation", Springer, 2000, Chapter 1, pp 1-41.

T. Christof, The SMAPO database about the CUT polytope
Michel Deza and Mathieu Dutour Sikirić, Enumeration of the facets of cut polytopes over some highly symmetric graphs, Intl. Trans. in Op. Res., 23 (2016), 853-860; arXiv:1501.05407 [math.CO], 2015. [Confirms the value of a(7).]
Stefan Forcey, Encyclopedia of Combinatorial Polytope Sequences: Cut Polytope.
G. Ziegler, Lectures on 0/1 Polytopes, arXiv:math/9909177 [math.CO], 1999, p 22-28.

Cf. A053043, A246427.

def Correlation(n):
   if n == 0:
      yield (tuple([]),tuple([]))
      return
   for x,y in Correlation(n-1):
      yield (x + (0,),y + (n-1)*(0,))
      yield (x + (1,),y + x)
def CorrelationPolytope(n):
   return Polyhedron(vertices=[x + y for x,y in Correlation(n)])
def a(n):
   return len(CorrelationPolytope(n).Hrepresentation())

A226236 Number of semisimple invertible n X n matrices over GF(2).

Original entry on oeis.org

1, 3, 105, 11025, 5439105, 11193473025, 89273960290305, 2926331900465537025, 380704455834655419367425, 200503685263248842050957082625, 418936006416927720918846481798529025, 3516831926000321799217446305276779638554625

Offset: 1

Victor S. Miller, Jun 04 2013

Fulman shows that the ratio a(n)/A002884(n) converges to Product_{r>=1, r == 0,2,3 mod 5} (1-2^(-(r-1)))/(1-2^(-r)).

			a(2) = 3, the matrices are [[1,0],[0,1]], [[0,1],[1,1]], [[1,1],[1,0]].

Jason Fulman, Cycle Indices for the Finite Classical Groups, J. Group Thy., v. 2, 1999, 251-289.

Cf. A225371 (every semisimple matrix over GF(2) is a square of another matrix).

A182211 The number of integers k < 10^n such that both k and k^3 mod 10^n have all odd decimal digits.

Original entry on oeis.org

5, 25, 62, 151, 381, 833, 2163, 5291, 13317, 33519, 85179, 213083, 539212, 1344272, 3358571

Offset: 1

Victor S. Miller, Apr 18 2012

Inspired by a discussion on the math-fun list on April 18, 2012 by James R. Buddenhagen.

Cf. A085597 (n such that both n and n^3 have all odd digits).

oddDigits 0 = True
oddDigits n = let (q,r) = quotRem n 10
              in (odd r) && oddDigits q
oddSet 0 = []
oddSet 1 = [1,3..9]
oddSet k = [n | i <- [1,3..9], x <- oddSet (k-1), let n = i*10^(k-1) + x,
               oddDigits((n^3) `mod` 10^k)]
main = putStrLn $ map (length . oddSet) [1..]

A197704 Integers divisible by their generalized weight.

Original entry on oeis.org

13, 18, 42, 60, 100, 115, 120, 145, 272, 279, 310, 319, 341, 372, 403, 434, 465, 480, 493, 496, 518, 540, 592, 595, 612, 665, 720, 748, 792, 805, 864, 884, 900, 918, 952, 1053, 1080, 1147, 1200, 1254, 1287, 1312, 1320, 1360, 1440, 1482, 1520, 1560, 1591, 1596

Offset: 1

Victor S. Miller, Oct 17 2011

The generalized weight of a binary number is obtained by assigning 1->3, 0->4, and summing up the weights of the digits (no leading zeros), for example 13 is in the sequence because it's 1101 in binary.

Cf. A177869 (same sort of sequence in which each digit gets weight 1).

base_weight b g n | n == 0 = 0 | otherwise = (base_weight b g (n `div` b)) + (g $ n `mod` b)
interesting b g = filter f [1..] where f n = n `mod` (base_weight b g n) == 0
bin_interesting g = interesting 2 g
weights l n | (n >=0) && ((length l) > fromInteger n) = l !! fromInteger n | otherwise = 0
original = weights [4,3]
let a = bin_interesting original

Select[Range[2000], IntegerQ[#/Plus@@(IntegerDigits[#, 2]/.{1 -> 3, 0 -> 4})] &] (* Alonso del Arte, Oct 17 2011 *)

is(n)=my(v=binary(n));n%(#v<<2-sum(i=1,#v,v[i]))==0 \\ Charles R Greathouse IV, Oct 19 2011

A133357 Number of 2-colorings of a 3 X n rectangle for which no subsquare has monochromatic corners.

Original entry on oeis.org

1, 8, 50, 276, 1498, 8352, 46730, 260204, 1447890, 8062968, 44907298, 250082756, 1392637914, 7755351712, 43188407610, 240509081468, 1339353796226, 7458635202952, 41535888495186, 231306378487028, 1288106280145770, 7173247100732400, 39946606186601514

Offset: 0

Victor S. Miller, Dec 21 2007

Figures obtained via clever exhaustion, using Gray Codes.

			a(1) = 8, because there are no conditions.
a(2) = 50 because if the middle row is not monochromatic, the top and bottom rows are unconstrained, contributing 2*4*4.  If the middle row is monochromatic, the top and bottom rows can each take on only 3 values contributing 2*3*3.

J. Solymosi, "A Note on a Question of Erdos and Graham", Combinatorics, Probability and Computing, Volume 13, Issue 2 (March 2004) 263 - 267.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Sci.math, Discussion of a related problems

Cf. A133129, A255255.

Column k=3 of A255256.

gf:= -(x+1)*(8*x^7-12*x^6-2*x^5-16*x^4-30*x^3-15*x^2-4*x-1)/
     (24*x^8-4*x^7-46*x^6-66*x^5-74*x^4-25*x^3-7*x^2-3*x+1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 18 2015

G.f.: -(x+1)*(8*x^7-12*x^6-2*x^5-16*x^4-30*x^3-15*x^2-4*x-1) / (24*x^8-4*x^7-46*x^6-66*x^5-74*x^4-25*x^3-7*x^2-3*x+1). - Alois P. Heinz, Feb 18 2015

a(0), a(8)-a(22) from Alois P. Heinz, Feb 18 2015

A133130 Number of 0/1 colorings of an n X n square for which no 2 by 2 subsquare is monochromatic.

Original entry on oeis.org

1, 2, 14, 322, 23858, 5735478, 4468252414, 11282914491066, 92343922085798834, 2449629600675855540670, 210618917058297166847778158, 58694743562963266347581955456602, 53015873227026172656988353687982082782, 155209215810704933798454506348361943868443334

Offset: 0

Victor S. Miller, Sep 19 2007

nonn

For each n we define an undirected labeled graph (with self loops), where the vertices are labeled with strings from {0,1}^n and there is an edge between two vertices exactly when we can form a 2 X n rectangle whose rows are the two labels and the 2 X n rectangle has no monochromatic 2 X 2 subsquares. a(n) is the number of walks of length n in this graph. Thus it is the sum of all of the entries of A^n, where A is the adjacency matrix of the graph.

			a(2) = 14 because 2 of the 16 unrestricted colorings are monochromatic.

Alois P. Heinz, Table of n, a(n) for n = 0..15

Cf. A055099.

Main diagonal of A181245.

a(0)-a(1), a(11)-a(13) from Alois P. Heinz, Feb 18 2015

cp's OEIS Frontend

User: Victor S. Miller

A383447 Number of "peerless" trees on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A339479 Number of partitions consisting of n parts, each of which is a power of 2, where one part is 1 and no part is more than twice the sum of all smaller parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A267132 Unipotent n X n matrices over GF(2) that are squares of other such matrices.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A266462 The number of conjugacy classes of invertible n X n matrices over GF(2) which are squares of other such matrices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A235459 Number of facets of the correlation polytope of degree n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Sage

A226236 Number of semisimple invertible n X n matrices over GF(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A182211 The number of integers k < 10^n such that both k and k^3 mod 10^n have all odd decimal digits.

Views

Author

Keywords

Comments

Crossrefs

Programs

Haskell

A197704 Integers divisible by their generalized weight.

Views

Author

Keywords

Comments

Crossrefs

Programs

Haskell

Mathematica