A215909 -id:A215909 - cp's OEIS frontend

A006171 Number of factorization patterns of polynomials of degree n over integers.

1, 1, 3, 5, 11, 17, 34, 52, 94, 145, 244, 370, 603, 899, 1410, 2087, 3186, 4650, 6959, 10040, 14750, 21077, 30479, 43120, 61574, 86308, 121785, 169336, 236475, 326201, 451402, 618135, 848209, 1153733, 1571063, 2123325, 2871419, 3857569, 5182999, 6924303

Offset: 0

N. J. A. Sloane

Number of partitions of n where there are unlimited distinguishable but unlabeled objects of each size. E.g., in splitting 2 into two parts of size 1, we distinguish whether the same object is used for each part. Also number of factorization patterns over rationals, or many other UFDs (but not over real or complex numbers). - Franklin T. Adams-Watters, Jun 19 2006
Equals the "aerate and convolve" convergent of A000041: (1, 1, 2, 3, 5, 7, 11, ...) * (1, 0, 1, 0, 2, 0, 3, 0, 5, ...) * (1, 0, 0, 1, 0, 0, 2, 0, 0, 3, ...). - Gary W. Adamson, Jun 16 2009
Also equals the number of distinct (up to unitary similarity) unital *-subalgebras of the n X n complex matrices. A unital *-subalgebra is a subspace that is closed under multiplication and the conjugate transpose, and which contains the identity matrix (see A215905 and A215925). - Nathaniel Johnston, Aug 27 2012
Also equals the number of partitions having parts consisting of runs of equal parts. - Gregory L. Simay, May 25 2017
Also equals the number of generalized partitions of n when there are d(a) different types of a, (a = 1,2,3,...), where d(n) is the number of divisors of n. a(3)=5 because there are 5 partitions of 3 with "d(a) copies of a", namely (3_1), (3_2), (2_1, 1_1), (2_2, 1_1), (1_1, 1_1, 1_1). - Augustine O. Munagi, Jun 13 2022

			For n=3 we have 3 = (3*1) = (1*3) = (2*1) + (1*1) = (1*2) + (1*1) = (1*1) + (1*1) + (1*1) so a(3)=5.
For n=4 we have the following 11 partitions, with the additive runs indicated by "[]": [4], [3]+[1], [2+2], [2]+[2], [2]+[1+1], [2]+[1]+[1], [1+1+1+1], [1+1+1]+[1], [1+1]+[1+1], [1+1]+[1]+[1], [1]+[1]+[1]+[1]. - _Gregory L. Simay_, May 25 2017

R. A. Hultquist, G. L. Mullen and H. Niederreiter, Association schemes and derived PBIB designs of prime power order, Ars. Combin., 25 (1988), 65-82.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
A. K. Agarwal and G. L. Mullen, Partitions with "d(a) copies of a", J. Combin. Theory Ser. A, 48(1)(1988), 120-135.
N. A. Brigham, A General Asymptotic Formula for Partition Functions, Proc. Amer. Math. Soc., vol. 1 (1950), pp. 182-191.
William Q. Erickson, The Demazure product extended to biwords, arXiv:2407.13165 [math.CO], 2024. See p. 16.
MathOverflow, Number of representations of an integer as an (arbitrary) sum of products, 2014.
N. J. A. Sloane, Transforms

Cf. A000005, A060640, A061255, A061256, A001970, A061257.
Cf. A006167-A006170, A006171 (log).
Cf. A000041, A115621, A215905, A215909, A215914, A215925, A288098.
Cf. A000219.

with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d,j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: a:=etr(tau): seq(a(n), n=0..40); # Alois P. Heinz, Sep 08 2008

max = 50; gf[x_] := Product[(1 - x^k)^-DivisorSigma[0, k], {k, 1, max}]; CoefficientList[ Series[gf[x], {x, 0, max}], x] (* Jean-François Alcover, Nov 23 2011 *)
nmax = 50; s = 1 - x; Do[s *= Sum[Binomial[DivisorSigma[0, k], j]*(-1)^j*x^(j*k), {j, 0, nmax/k}]; s = Expand[s]; s = Take[s, Min[nmax + 1, Exponent[s, x] + 1, Length[s]]];, {k, 2, nmax}]; CoefficientList[Series[1/s, {x, 0, nmax}], x] (* Vaclav Kotesovec, Aug 28 2018, the fastest *)
nmax = 50; CoefficientList[Series[Product[Sum[PartitionsP[k]*x^(j*k), {k, 0, nmax/j}], {j, 1, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Dec 26 2020 *)

{a(n) = if(n<0, 0, polcoeff( 1 / prod(k=1, n, (1 - x^k + x * O(x^n))^numdiv(k)), n))}; /* Michael Somos, Apr 01 2003 */

N=66; x='x+O('x^N); gf=1/prod(j=1,N, eta(x^j)); Vec(gf) \\ Joerg Arndt, May 03 2008

{a(n)=if(n==0,1,polcoeff(exp(sum(m=1,n,sigma(m)*x^m/(1-x^m+x*O(x^n))/m)),n))} /* Paul D. Hanna, Mar 28 2009 */

{A060640(n)=sumdiv(n, d, d*sigma(n/d))}
{a(n)=polcoeff(exp(sum(m=1,n+1,A060640(m)*x^m/m)+x*O(x^n)),n)} /* Paul D. Hanna, Oct 19 2011 */

From Vladeta Jovovic, Apr 21 2001: (Start)
Euler transform of tau(n), tau(n) = the number of divisors of n, cf. A000005.
G.f.: Product_{k>=1} (1 - x^k)^(-tau(k)).
a(n) = 1/n*Sum_{k=1..n} a(n-k)*b(k), n>1, a(0)=1, b(k) = Sum_{d|k} d*tau(d), cf. A060640. (End)
a(n) = Sum_{ partition of n} product p(k(i)), where p(n) is the partition function A000041. E.g., for the partition [4,2^3,1^4], the product is p(1)*p(3)*p(4) = 1*3*5 = 15. - Franklin T. Adams-Watters, Jun 19 2006
G.f.: A(x) = exp( Sum_{n>=1} sigma(n)*x^n/(1-x^n)/n ). - Paul D. Hanna, Mar 28 2009
From Paul D. Hanna, Oct 19 2011: (Start)
Logarithmic derivative yields A060640.
G.f.: A(x) = exp( Sum_{n>=1} A060640(n)*x^n/n ), where A060640(n) = Sum_{d|n} d*sigma(n/d). (End)
G.f.: 1/Product_{n>=1} E(q^n) where E(q) = Product_{n>=1} (1-q^n). - Joerg Arndt, Feb 27 2014
log(a(n)) ~ Pi * sqrt(n*log(n)/3) [Brigham, 1950]. - Vaclav Kotesovec, Jan 04 2017
a(n) ~ exp(Pi*sqrt(n/(3*log(n))) * (log(n) - log(log(n))/2 + gamma + 6*Zeta'(2)/Pi^2 + log(2/Pi) + log(3)/2)) * Pi^(1/4) * (log(n))^(1/8) / (2^(3/4) * 3^(1/8) * n^(5/8)), where gamma is the Euler-Mascheroni constant (A001620) and Zeta'(2) = -0.9375482543158437537... (see A073002) [user Lucia, MathOverflow, 2014]. - Vaclav Kotesovec, Jan 05 2017

A215905 Triangle read by rows in which row n contains the possible dimensions of unital *-subalgebras of the n X n complex matrices.

Original entry on oeis.org

1, 1, 2, 4, 1, 2, 3, 5, 9, 1, 2, 3, 4, 5, 6, 8, 10, 16, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 17, 25, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 17, 18, 20, 26, 36, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 21, 25, 26, 27, 29, 37, 49

Offset: 1

Nathaniel Johnston, Aug 25 2012

A *-subalgebra is a subalgebra (i.e., a subspace closed under matrix multiplication) that is closed under the conjugate transpose operation. A unital subalgebra is one that contains the identity matrix.
Every *-subalgebra of the n X n complex matrices is unitarily similar to a direct sum of full matrix algebras of smaller dimension, where elements of those full matrix algebras of the same dimension may or may not be forced to be identical.
As a result of the previous characterization, the possible dimensions of unital *-subalgebras of the n X n matrices are obtained by finding all partitions of n and summing the squares of the parts, possibly omitting some or all duplicated parts.
The first n entries of row n are 1, 2, ..., n. The smallest positive integer not contained in the n-th row is A215914(n).
The last entry of row n is A000290(n).
The 2nd-to-last entry of row n is A002522(n-1).
Row lengths are given by A215909.

			When n = 3, there are five different (up to unitary similarity) unital *-subalgebras, which contain matrices of the following forms:
a 0 0 ... a 0 0 ... a 0 0 ... a b 0 ... a b c
0 a 0 ... 0 b 0 ... 0 b 0 ... c d 0 ... d e f
0 0 a ... 0 0 b ... 0 0 c ... 0 0 e ... g h i
The above *-subalgebras have dimensions 1, 2, 3, 5, and 9, which is the 3rd row of the triangle.
When n = 4, we can compute the possible dimension by finding all partitions of 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1. Then the possible dimensions are 4^2 = 16, 3^2 + 1^2 = 10, 2^2 + 2^2 = 8, 2^2 = 4, 2^2 + 1^2 + 1^2 = 6, 2^2 + 1^2 = 5, 1^2 + 1^2 + 1^2 + 1^2 = 4, 1^2 + 1^2 + 1^2 = 3, 1^2 + 1^2 = 2, and 1^2 = 1, which are the entries of the 4th row.
The triangle begins:
1
1, 2, 4
1, 2, 3, 5, 9
1, 2, 3, 4, 5, 6, 8, 10, 16
1, 2, 3, 4, 5, 6, 7, 9,  10, 11, 13, 17, 25
1, 2, 3, 4, 5, 6, 7, 8,  9,  10, 11, 12, 14, 17, 18, 20, 26, 36
...

William Q. Erickson, The Demazure product extended to biwords, arXiv:2407.13165 [math.CO], 2024. See p. 15.

Cf. A215909, A215914.

sum_sq:=proc(lst) return add(lst[i]^2,i=1..nops(lst)): end: tot_sum_sq:=proc(lst,tmp_res,strt) local j,new_lst,new_res: new_res:={op(tmp_res),sum_sq(lst)}: for j from strt to nops(lst) do if(lst[j-1]=lst[j] and not (j>2 and lst[j-2]=lst[j]))then new_res:={op(new_res),op(tot_sum_sq(subsop(j=NULL,lst),new_res,j))}: fi: od: return new_res: end: nth_row:=proc(n) local part,parts,res: parts:=combinat[partition](n): res:=[]: for part in parts do res:={op(res),op(tot_sum_sq(part,[],2))}: od: return res: end: seq(op(nth_row(n)),n=1..7);

A215914 Smallest positive integer k such that there is no k-dimensional unital *-subalgebra of the n X n complex matrices.

Original entry on oeis.org

2, 3, 4, 7, 8, 13, 16, 23, 24, 43, 44, 49, 64, 77, 80, 97, 116, 141, 144, 167, 168, 193, 248, 249, 280, 313, 348, 385, 424, 473, 484, 527, 528, 573, 620, 625, 720, 725, 828, 833, 890, 949, 1010, 1073, 1088, 1153, 1220, 1289, 1360, 1433

Offset: 1

Nathaniel Johnston, Aug 26 2012

nonn

a(n) is the smallest positive integer that is not contained in the n-th row of A215905.

a(n) >= n+1. In fact, for any m >= 1 there exists N >= 1 such that a(n) > mn for all n >= N. That is, this sequence grows super-linearly.

			In the n = 4 case, there are unital *-subalgebras of dimensions 1 though 6, as follows:
a 0 0 0 ... a 0 0 0 ... a 0 0 0 ... a 0 0 0 ... a 0 0 0 ... a 0 0 0
0 a 0 0 ... 0 b 0 0 ... 0 b 0 0 ... 0 b 0 0 ... 0 a 0 0 ... 0 b 0 0
0 0 a 0 ... 0 0 b 0 ... 0 0 c 0 ... 0 0 c 0 ... 0 0 b c ... 0 0 c d
0 0 0 a ... 0 0 0 b ... 0 0 0 c ... 0 0 0 d ... 0 0 d e ... 0 0 e f
However, there is no unital *-subalgebra of the 4-by-4 matrices of dimension 7, so a(4) = 7.

Cf. A215905, A215909.

A215925 The number of distinct (up to unitary similarity) *-subalgebras of the n X n complex matrices.

Original entry on oeis.org

1, 2, 5, 10, 21, 38, 72, 124, 218, 363, 607, 977, 1580, 2479, 3889, 5976, 9162, 13812, 20771, 30811, 45561, 66638, 97117, 140237, 201811, 288119, 409904, 579240, 815715, 1141916, 1593318, 2211453, 3059662, 4213395, 5784458, 7907783, 10779202, 14636771, 19819770

Offset: 0

Nathaniel Johnston, Aug 27 2012

nonn

A *-subalgebra is a subalgebra (i.e., a subspace closed under matrix multiplication) that is closed under the conjugate transpose operation.

Also the partial sums of A006171.

			There are 10 different (up to unitary similarity) *-subalgebras of the 3 X 3 complex matrices, which contain matrices of the following forms:
0 0 0 ... a 0 0 ... a 0 0 ... a 0 0 ... a b 0
0 0 0 ... 0 0 0 ... 0 a 0 ... 0 b 0 ... c d 0
0 0 0 ... 0 0 0 ... 0 0 0 ... 0 0 0 ... 0 0 0
. . . ... . . . ... . . . ... . . . ... . . .
a 0 0 ... a 0 0 ... a 0 0 ... a b 0 ... a b c
0 a 0 ... 0 b 0 ... 0 b 0 ... c d 0 ... d e f
0 0 a ... 0 0 b ... 0 0 c ... 0 0 e ... g h i
Thus a(3) = 10.

Nathaniel Johnston, Table of n, a(n) for n = 0..1000
William Q. Erickson, The Demazure product extended to biwords, arXiv:2407.13165 [math.CO], 2024. See p. 16.

Cf. A215905, A215909, A215914.

cp's OEIS Frontend

A006171 Number of factorization patterns of polynomials of degree n over integers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

A215905 Triangle read by rows in which row n contains the possible dimensions of unital *-subalgebras of the n X n complex matrices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A215914 Smallest positive integer k such that there is no k-dimensional unital *-subalgebra of the n X n complex matrices.

Views

Author

Keywords

Comments

Examples

Crossrefs

A215925 The number of distinct (up to unitary similarity) *-subalgebras of the n X n complex matrices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs