A004250 -id:A004250 - cp's OEIS frontend

A035300 Expansion of Sum_{n>=0} (q^n / Product_{k=1..n+4} (1 - q^k)).

1, 2, 4, 7, 12, 18, 28, 40, 58, 80, 111, 149, 201, 264, 348, 450, 583, 744, 950, 1199, 1514, 1893, 2366, 2935, 3638, 4480, 5513, 6746, 8247, 10035, 12196, 14763, 17850, 21504, 25875, 31038, 37184, 44422

Offset: 0

N. J. A. Sloane

nonn

Cf. A004250, A035301.

ZL :=[S, {S = Set(Cycle(Z),3 < card)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=4..41); # Zerinvary Lajos, Mar 25 2008
B:=[S,{S = Set(Sequence(Z,1 <= card),card >=4)},unlabelled]: seq(combstruct[count](B, size=n), n=4..41); # Zerinvary Lajos, Mar 21 2009

a(n) = A000041(n+4) - round((n+7)^2/12). - Vladeta Jovovic, Jun 18 2003

A331488 Number of unlabeled lone-child-avoiding rooted trees with n vertices and more than two branches (of the root).

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 3, 6, 10, 20, 36, 70, 134, 263, 513, 1022, 2030, 4076, 8203, 16614, 33738, 68833, 140796, 288989, 594621, 1226781, 2536532, 5256303, 10913196, 22700682, 47299699, 98714362, 206323140, 431847121, 905074333, 1899247187, 3990145833, 8392281473

Offset: 1

Gus Wiseman, Jan 20 2020

nonn

Also the number of lone-child-avoiding rooted trees with n vertices and more than two branches.

			The a(4) = 1 through a(9) = 10 trees:
  (ooo)  (oooo)  (ooooo)   (oooooo)   (ooooooo)    (oooooooo)
                 (oo(oo))  (oo(ooo))  (oo(oooo))   (oo(ooooo))
                           (ooo(oo))  (ooo(ooo))   (ooo(oooo))
                                      (oooo(oo))   (oooo(ooo))
                                      (o(oo)(oo))  (ooooo(oo))
                                      (oo(o(oo)))  (o(oo)(ooo))
                                                   (oo(o(ooo)))
                                                   (oo(oo)(oo))
                                                   (oo(oo(oo)))
                                                   (ooo(o(oo)))

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014)
Eric Weisstein's World of Mathematics, Series-reduced tree.
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

The not necessarily lone-child-avoiding version is A331233.
The Matula-Goebel numbers of these trees are listed by A331490.
A000081 counts unlabeled rooted trees.
A001678 counts lone-child-avoiding rooted trees.
A001679 counts topologically series-reduced rooted trees.
A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.
A331489 lists Matula-Goebel numbers of series-reduced rooted trees.
Cf. A000014, A000669, A004250, A007097, A007821, A033942, A060313, A060356, A061775, A109082, A109129, A196050, A276625, A330943.

urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[urt[n],Length[#]>2&&FreeQ[#,{_}]&]],{n,10}]

For n > 1, a(n) = A001679(n) - A001678(n).

a(37)-a(38) from Jinyuan Wang, Jun 26 2020

Terminology corrected (lone-child-avoiding, not series-reduced) by Gus Wiseman, May 10 2021

A029895 Number of partitions of floor(n^2/2) with at most n parts and maximal height n.

Original entry on oeis.org

1, 1, 2, 3, 8, 20, 58, 169, 526, 1667, 5448, 18084, 61108, 208960, 723354, 2527074, 8908546, 31630390, 113093022, 406680465, 1470597342, 5342750699, 19499227828, 71442850111, 262754984020, 969548468960, 3589093760726, 13323571588607, 49596793134484

Offset: 0

torsten.sillke(AT)lhsystems.com

nonn

This is the maximum value for the distribution of partitions of (0 .. n^2) that fit in an n X n box; assuming the peak of a normal distribution 1/sqrt(variance*2*Pi) approximates to these partitions and using A068606 suggests C(2n,n)*sqrt(6/(Pi*n^2*(2n+1))) could be an approximation [within 0.3% for a(100)=88064925963069745337300842293630181021718294488842002448]; using Stirling's approximation gives the simpler (sqrt(3)/Pi)*4^n/n^2 [about 0.6% away for a(100)] though experimentation suggests that something like (sqrt(3)/Pi)*4^n/(n^2+3n/5+1/5) is closer [about 0.0001% away for a(100)]. - Henry Bottomley, Mar 13 2002

Bisection of A277218 with even indexes. - Vladimir Reshetnikov, Oct 09 2016

			a(4)=8 because the partitions of Floor[4^2 /2] that fit inside a 4 X 4 box are {4, 4}, {4, 3, 1}, {4, 2, 2}, {4, 2, 1, 1}, {3, 3, 2}, {3, 3, 1, 1}, {3, 2, 2, 1}, {2, 2, 2, 2}.

R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.

Vladimir Reshetnikov, Table of n, a(n) for n = 0..190
Eric W. Weisstein, q-Binomial Coefficient
Wikipedia, q-binomial

Cf. A000569, A004250, A004251, A029889, A047993, diagonal of A067059, A068607, A277218.

Table[Coefficient[Expand[FunctionExpand[QBinomial[2 n, n, q]]], q, Floor[n^2/2]], {n, 0, 30}] (* Vladimir Reshetnikov, Oct 09 2016 *)

{a(n)=if(n==0,1,polcoeff(prod(i=1,n,(1-q^(n+i))/(1-q^i)),n^2\2,q))} \\ Paul D. Hanna, Feb 15 2007

Calculated using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser. Table[T[Floor[n^2/2], n, n], {n, 0, 36}] with T[ ] defined as in A047993. a(n)=A067059(n, n).

a(n) equals the central coefficient of q in the central q-binomial coefficients for n>0: a(n) = [q^([n^2/2])] Product_{i=1..n} (1-q^(n+i))/(1-q^i), with a(0)=1. - Paul D. Hanna, Feb 15 2007

More terms and comments from Wouter Meeussen, Aug 14 2001
Edited by Henry Bottomley, Feb 17 2002
a(27)-a(28) from Alois P. Heinz, Oct 31 2018

A331490 Matula-Goebel numbers of series-reduced rooted trees with more than two branches (of the root).

Original entry on oeis.org

8, 16, 28, 32, 56, 64, 76, 98, 112, 128, 152, 172, 196, 212, 224, 256, 266, 304, 343, 344, 392, 424, 428, 448, 512, 524, 532, 602, 608, 652, 686, 688, 722, 742, 784, 848, 856, 896, 908, 931, 1024, 1048, 1052, 1064, 1204, 1216, 1244, 1304, 1372, 1376, 1444

Offset: 1

Gus Wiseman, Jan 20 2020

nonn

We say that a rooted tree is (topologically) series-reduced if no vertex has degree 2.
The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of its branches. This gives a bijective correspondence between positive integers and unlabeled rooted trees.
Also Matula-Goebel numbers of lone-child-avoiding rooted trees with more than two branches.

			The sequence of all series-reduced rooted trees with more than two branches together with their Matula-Goebel numbers begins:
    8: (ooo)
   16: (oooo)
   28: (oo(oo))
   32: (ooooo)
   56: (ooo(oo))
   64: (oooooo)
   76: (oo(ooo))
   98: (o(oo)(oo))
  112: (oooo(oo))
  128: (ooooooo)
  152: (ooo(ooo))
  172: (oo(o(oo)))
  196: (oo(oo)(oo))
  212: (oo(oooo))
  224: (ooooo(oo))
  256: (oooooooo)
  266: (o(oo)(ooo))
  304: (oooo(ooo))
  343: ((oo)(oo)(oo))
  344: (ooo(o(oo)))

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014)
Eric Weisstein's World of Mathematics, Series-reduced tree.
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

These trees are counted by A331488.
Unlabeled rooted trees are counted by A000081.
Lone-child-avoiding rooted trees are counted by A001678.
Topologically series-reduced rooted trees are counted by A001679.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Matula-Goebel numbers of series-reduced rooted trees are A331489.
Cf. A000014, A000669, A004250, A007097, A007821, A033942, A060313, A060356, A061775, A109082, A109129, A196050, A276625, A330943.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
srQ[n_]:=Or[n==1,With[{m=primeMS[n]},And[Length[m]>1,And@@srQ/@m]]];
Select[Range[1000],PrimeOmega[#]>2&&srQ[#]&]

A353502 Numbers with all prime indices and exponents > 2.

Original entry on oeis.org

1, 125, 343, 625, 1331, 2197, 2401, 3125, 4913, 6859, 12167, 14641, 15625, 16807, 24389, 28561, 29791, 42875, 50653, 68921, 78125, 79507, 83521, 103823, 117649, 130321, 148877, 161051, 166375, 205379, 214375, 226981, 274625, 279841, 300125, 300763, 357911

Offset: 1

Gus Wiseman, May 16 2022

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The initial terms together with their prime indices:
       1: {}
     125: {3,3,3}
     343: {4,4,4}
     625: {3,3,3,3}
    1331: {5,5,5}
    2197: {6,6,6}
    2401: {4,4,4,4}
    3125: {3,3,3,3,3}
    4913: {7,7,7}
    6859: {8,8,8}
   12167: {9,9,9}
   14641: {5,5,5,5}
   15625: {3,3,3,3,3,3}
   16807: {4,4,4,4,4}
   24389: {10,10,10}
   28561: {6,6,6,6}
   29791: {11,11,11}
   42875: {3,3,3,4,4,4}

David A. Corneth, Table of n, a(n) for n = 1..10000 (first 3000 terms from Amiram Eldar)

The version for only parts is A007310, counted by A008483.
The version for <= 2 instead of > 2 is A018256, # of compositions A137200.
The version for only multiplicities is A036966, counted by A100405.
The version for indices and exponents prime (instead of > 2) is:
- listed by A346068
- counted by A351982
- only exponents: A056166, counted by A055923
- only parts: A076610, counted by A000607
The version for > 1 instead of > 2 is A062739, counted by A339222.
The version for compositions is counted by A353428, see A078012, A353400.
The partitions with these Heinz numbers are counted by A353501.
A000726 counts partitions with multiplicities <= 2, compositions A128695.
A001222 counts prime factors with multiplicity, distinct A001221.
A004250 counts partitions with some part > 2, compositions A008466.
A056239 adds up prime indices, row sums of A112798 and A296150.
A124010 gives prime signature, sorted A118914.
A295341 counts partitions with some multiplicity > 2, compositions A335464.
Cf. A000720, A003963, A065483, A114901, A181819, A353503, A353508.

Select[Range[10000],#==1||!MemberQ[FactorInteger[#],{?(#<5&),}|{,?(#<3&)}]&]

Sum_{n>=1} 1/a(n) = Product_{p prime > 3} (1 + 1/(p^2*(p-1))) = (72/95)*A065483 = 1.0154153584... . - Amiram Eldar, May 28 2022

A380363 Triangle read by rows: T(n,k) is the number of linear trees with n vertices and k vertices of degree >= 3, 0 <= k <= max(0, floor(n/2)-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 3, 1, 11, 10, 1, 1, 17, 24, 5, 1, 25, 56, 22, 1, 1, 36, 114, 74, 6, 1, 50, 224, 219, 37, 1, 1, 70, 411, 576, 158, 8, 1, 94, 733, 1394, 591, 58, 1, 1, 127, 1252, 3150, 1896, 304, 9, 1, 168, 2091, 6733, 5537, 1342, 82, 1

Offset: 0

Andrew Howroyd, Jan 26 2025

A linear tree is a tree with all vertices of degree > 2 belonging to a single path. These are equinumerous with lobster graphs. All trees having at most 3 vertices of degree > 2 are linear trees.

			Triangle begins:
  1;
  1;
  1;
  1;
  1,   1;
  1,   2;
  1,   4,    1;
  1,   7,    3;
  1,  11,   10,    1;
  1,  17,   24,    5;
  1,  25,   56,   22,    1;
  1,  36,  114,   74,    6;
  1,  50,  224,  219,   37,   1;
  1,  70,  411,  576,  158,   8;
  1,  94,  733, 1394,  591,  58, 1;
  1, 127, 1252, 3150, 1896, 304, 9;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..2501 (rows 0..100)
Tanay Wakhare, Eric Wityk, and Charles R. Johnson, The proportion of trees that are linear, Discrete Mathematics 343.10 (2020): 112008. Also Corrigendum and preprint arXiv:1901.08502. See Table 1.
Eric Weisstein's World of Mathematics, Lobster Graph.

Columns 0..4 are A000012, A004250(n-1), A338706, A338707, A338708.
Row sums are A130131.
Cf. A238415 (initial columns same up to k=3).

G(n,y)={my(p=1/eta(x + O(x^n)), p2=1/eta(x^2 + O(x^n)),
  g1=(p - 1/(1-x))^2/((1 - x)*(1 - x*y*(p-1)/(1-x))),
  g2=(p2 - 1/(1-x^2))*(1 + x + x*y*(p-1))/((1 - x^2)*(1 - x^2*y^2*(p2-1)/(1-x^2))) );
  x^2*y^2*(g1 + g2)/2 + x*y*(p - 1/((1 + x)*(1 - x)^2)) + 1/(1-x)
}
T(n)=[Vecrev(p) | p<-Vec(G(n,y))]
{my(A=T(15)); for(i=1, #A, print(A[i]))}

A007721 Number of distinct degree sequences among all connected graphs with n nodes.

Original entry on oeis.org

1, 1, 2, 6, 19, 68, 236, 863, 3137, 11636, 43306, 162728, 614142, 2330454, 8875656, 33924699, 130038017, 499753560, 1924912505, 7429159770, 28723877046, 111236422377, 431403469046, 1675316533812, 6513837677642, 25354842098354, 98794053266471, 385312558567775

Offset: 1

Frank Ruskey

Sometimes called "graphical partitions", although this term is deprecated.

Wang Kai, Table of n, a(n) for n = 1..118
N. Durand, G. Granger, A traffic complexity approach through cluster analysis, in proceedings of the 5th ATM R&D Seminar, Budapest, Hungary (2003)
T. Hoppe, A. Petrone,Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
F. Ruskey, Alley CATs in search of good homes, Congress. Numerant., 102 (1994) 97-110.
Kai Wang, Efficient Counting of Degree Sequences, arXiv preprint arXiv:1604.04148 [math.CO], 2017.
Index entries for sequences related to graphical partitions

Cf. A000569, A004250, A004251, A007722, A029889; A095268 (analog for all graphs).

a(9) corrected by Gordon Royle, Aug 30 2006
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 19 2007
Prepended missing term a(1), Travis Hoppe, Aug 04 2014
a(22)-a(28) added by Wang Kai, Feb 15 2017

A169890 Carryless sum 1+2+3+...+n.

Original entry on oeis.org

0, 1, 3, 6, 0, 5, 1, 8, 6, 5, 15, 26, 38, 41, 55, 60, 76, 83, 91, 0, 20, 41, 63, 86, 0, 25, 41, 68, 86, 5, 35, 66, 98, 21, 55, 80, 16, 43, 71, 0, 40, 81, 23, 66, 0, 45, 81, 28, 66, 5, 55, 6, 58, 1, 55, 0, 56, 3, 51, 0, 60, 21, 83, 46, 0, 65, 21, 88, 46, 5, 75, 46, 18, 81, 55, 20, 96, 63, 31

Offset: 0

David Applegate, Marc LeBrun and N. J. A. Sloane, Jul 06 2010

Carryless analog of triangular numbers.

Rémy Sigrist, Table of n, a(n) for n = 0..9999
David Applegate, Marc LeBrun and N. J. A. Sloane, Carryless Arithmetic (I): The Mod 10 Version.
Index entries for sequences related to carryless arithmetic

Cf. A004250, A059729.

A238415 Triangle read by rows: T(n,k) is the number of trees with n vertices having k branching vertices (n>=2, 0<=k<=floor(n/2) - 1).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 3, 1, 11, 10, 1, 1, 17, 24, 5, 1, 25, 56, 22, 2, 1, 36, 114, 74, 10, 1, 50, 224, 219, 55, 2, 1, 70, 411, 576, 224, 19, 1, 94, 733, 1394, 807, 126, 4, 1, 127, 1252, 3150, 2536, 637, 38, 1, 168, 2091, 6733, 7305, 2711, 305, 6

Offset: 2

Emeric Deutsch, Mar 05 2014

A branching node of a tree is a vertex of degree at least 3.
Sum of entries in row n is A000055(n) (number of trees with n vertices).
Row n has floor(n/2) entries.
T(n,1) = A004250(n-1).

			Row n=4 is T(4,0)=1,T(4,1)=1; indeed, the path P[4] has no branching vertex and the star S[4] has 1 branching vertex.
Triangle starts:
1;
1;
1, 1;
1, 2;
1, 4, 1;
1, 7, 3;
1, 11, 10, 1;
1, 17, 24, 5;

Andrew Howroyd, Table of n, a(n) for n = 2..1226

Cf. A000055, A235111, A196049, A004250.

MI := [25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64]: with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 0 elif bigomega(n) = 1 and bigomega(pi(n)) <> 2 then a(pi(n)) elif bigomega(n) = 1 then a(pi(n))+1 elif bigomega(s(n)) <> 2 then a(r(n))+a(s(n)) else a(r(n))+a(s(n))+1 end if end proc: g := add(x^a(MI[j]), j = 1 .. nops(MI)): seq(coeff(g, x, q), q = 0 .. 2);

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
R(n)={my(v=[1]); for(i=2, n, v=concat([1], y*EulerMT(v) + (1-y)*v)); v}
seq(n)={my(p=x*Ser(R(n))); Vec(p + (((1-y)*x-1)*p^2 + ((1-y)*x+1)*substvec(p,[x,y],[x^2,y^2]))/2)}
{ my(A=Vec(seq(20))); for(n=2, #A, print(Vecrev(A[n]))) } \\ Andrew Howroyd, May 21 2018

The author knows of no formula for T(n,k). The entries have been obtained in the following manner, explained for row n = 7. In A235111 we find that the 11 (= A000055(7)) trees with 7 vertices have M-indices 25, 27, 30, 35, 36, 40, 42, 48, 49, 56, and 64 (the M-index of a tree t is the smallest of the Matula numbers of the rooted trees isomorphic, as a tree, to t). Making use of the formula in A196049, from these Matula numbers one obtains that these trees have 0, 1, 1, 1, 1, 1, 2, 1, 2, 2, and 1 branching vertices, respectively; the frequencies of 0, 1, and 2 are 1, 7, and 3, respectively. See the Maple program.

Terms a(51) and beyond from Andrew Howroyd, May 21 2018

A347542 Number of partitions of n into 6 or more parts.

Original entry on oeis.org

1, 2, 4, 7, 12, 19, 30, 44, 65, 92, 130, 178, 244, 326, 435, 571, 747, 964, 1242, 1581, 2009, 2530, 3178, 3962, 4930, 6094, 7518, 9225, 11296, 13768, 16751, 20295, 24546, 29583, 35591, 42685, 51112, 61028, 72757, 86523, 102740, 121720, 144007, 170018, 200461, 235910, 277270

Offset: 6

Ilya Gutkovskiy, Sep 06 2021

nonn

Cf. A000065, A001402, A004250, A035300, A035301, A347543, A347544, A347545, A347547.

nmax = 52; CoefficientList[Series[Sum[x^k/Product[(1 - x^j), {j, 1, k}], {k, 6, nmax}], {x, 0, nmax}], x] // Drop[#, 6] &

G.f.: Sum_{k>=6} x^k / Product_{j=1..k} (1 - x^j).

cp's OEIS Frontend

A035300 Expansion of Sum_{n>=0} (q^n / Product_{k=1..n+4} (1 - q^k)).

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

A331488 Number of unlabeled lone-child-avoiding rooted trees with n vertices and more than two branches (of the root).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A029895 Number of partitions of floor(n^2/2) with at most n parts and maximal height n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A331490 Matula-Goebel numbers of series-reduced rooted trees with more than two branches (of the root).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A353502 Numbers with all prime indices and exponents > 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A380363 Triangle read by rows: T(n,k) is the number of linear trees with n vertices and k vertices of degree >= 3, 0 <= k <= max(0, floor(n/2)-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A007721 Number of distinct degree sequences among all connected graphs with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A169890 Carryless sum 1+2+3+...+n.

Views

Author

Keywords

Comments

Links