A000123 -id:A000123 - cp's OEIS frontend

A005705 Number of partitions of 4*n into powers of 4.

1, 2, 3, 4, 6, 8, 10, 12, 15, 18, 21, 24, 28, 32, 36, 40, 46, 52, 58, 64, 72, 80, 88, 96, 106, 116, 126, 136, 148, 160, 172, 184, 199, 214, 229, 244, 262, 280, 298, 316, 337, 358, 379, 400, 424, 448, 472, 496, 524, 552, 580, 608, 640, 672, 704, 736, 772, 808, 844

Offset: 0

N. J. A. Sloane

Also number of partitions of 4*n+k into powers of 4 where k=1,2,3. - Michael Somos, Mar 15 2020

R. K. Guy, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..1000
C. Banderier, H.-K. Hwang, V. Ravelomanana and V. Zacharovas, Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics, preprint 2012; SIAM J. Discrete Math., 28(1), 342-371, 2014. - _N. J. A. Sloane_, Dec 23 2012
R. K. Guy, Letters to N. J. A. Sloane and J. W. Moon, 1988
M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, Australasian J. Combin., 30 (2004), 193-196.
M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions
M. Latapy, Partitions of an integer into powers, DMTCS Proceedings AA (DM-CCG), 2001, 215-228.
M. Latapy, Partitions of an integer into powers, DMTCS Proceedings AA (DM-CCG), 2001, 215-228. [Cached copy, with permission]
O. J. Rodseth and J. A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.

Column k=4 of A292477.

Cf. A000041, A000123, A005704, A005706.

Fold[Append[#1, Total[Take[Flatten[Transpose[Table[#1, {4}]]], #2]]] &, {1},  Range[2, 20]] (* Birkas Gyorgy, Apr 18 2011 *)

a(n) = a(n-1) + a(floor(n/4)).

G.f.: T(x)=(1-x)^(-1)/(Product_{k>=0} 1-x^(4^k)), it satisfies T(x)=(1-x^4)/(1-x)^2*T(x^4). - Joerg Arndt, May 12 2010

Formula and more terms from Henry Bottomley, Apr 30 2001

A072720 Number of partitions of n into parts which are each powers of a single number (which may vary between partitions).

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 10, 11, 15, 17, 23, 24, 34, 35, 43, 47, 57, 58, 73, 74, 91, 96, 112, 113, 139, 141, 163, 168, 197, 198, 235, 236, 272, 279, 317, 321, 378, 379, 427, 436, 501, 502, 575, 576, 653, 666, 742, 743, 851, 853, 952, 963, 1080, 1081, 1211, 1216, 1361

Offset: 0

Henry Bottomley, Jul 05 2002

nonn

First differs from A322912 at a(12) = 34, A322912(12) = 33.

			a(6)=10 since 6 can be written as 6 (powers of 6), 5+1 (5), 4+1+1 (4 or 2), 3+3 (3), 3+1+1+1 (3), 4+2 (2), 2+2+2 (2), 2+2+1+1 (2), 2+1+1+1+1 (2) and 1+1+1+1+1+1 (powers of anything).
From _Gus Wiseman_, Jan 01 2019: (Start)
The a(1) = 1 through a(8) = 15 integer partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (41)     (33)      (61)       (44)
             (111)  (31)    (221)    (42)      (331)      (71)
                    (211)   (311)    (51)      (421)      (422)
                    (1111)  (2111)   (222)     (511)      (611)
                            (11111)  (411)     (2221)     (2222)
                                     (2211)    (4111)     (3311)
                                     (3111)    (22111)    (4211)
                                     (21111)   (31111)    (5111)
                                     (111111)  (211111)   (22211)
                                               (1111111)  (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)
(End)

Cf. A000123, A005704, A005705, A005706, A072721.

Cf. A018819, A023893, A052410, A102430, A322900, A322901, A322902, A322903, A322912.

radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
Table[Length[Select[IntegerPartitions[n],SameQ@@radbase/@DeleteCases[#,1]&]],{n,30}] (* Gus Wiseman, Jan 01 2019 *)

a(n) = a(n-1) + A072721(n). a(p) = a(p-1)+1 for p prime.

A161809 G.f.: A(x) = exp( Sum_{n>=1} 3A038500(n) x^n/n ), where A038500 is the highest power of 3 dividing n.

Original entry on oeis.org

1, 3, 6, 12, 21, 33, 51, 75, 105, 147, 201, 267, 354, 462, 591, 753, 948, 1176, 1455, 1785, 2166, 2622, 3153, 3759, 4470, 5286, 6207, 7275, 8490, 9852, 11415, 13179, 15144, 17376, 19875, 22641, 25761, 29235, 33063, 37353, 42105, 47319, 53124

Offset: 0

Paul D. Hanna, Jul 20 2009

nonn

			G.f.: A(x) = 1 + 3*x + 6*x^2 + 12*x^3 + 21*x^4 + 33*x^5 + 51*x^6 + ...
log(A(x)) = 3*x + 3*x^2/2 + 9*x^3/3 + 3*x^4/4 + 3*x^5/5 + 9*x^6/6 + ...
From _Paul D. Hanna_, Jul 27 2009: (Start)
TRISECTIONS begin:
T_0(x) = 1 + 12*x + 51*x^2 + 147*x^3 + 354*x^4 + 753*x^5 + ...
T_1(x) = 3 + 21*x + 75*x^2 + 201*x^3 + 462*x^4 + 948*x^5 + ...
T_2(x) = 6 + 33*x + 105*x^2 + 267*x^3 + 591*x^4 + 1176*x^5 + ...
(End)

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000

Cf. A038500, A182000, A182185, A000123.

Partial sums of A309677.

nmax = 50; CoefficientList[Series[Exp[Sum[3^(IntegerExponent[k, 3] + 1)*x^k/k, {k, 1, nmax}]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Nov 01 2024 *)

{a(n)=local(L=sum(m=1, n,3*3^valuation(m,3)*x^m/m)+x*O(x^n)); polcoeff(exp(L), n)}

{a(n)=local(A=1+x);for(i=0,n\3,A=subst(A,x,x^3+x*O(x^n))*(1+x+x^2)/(1-x+x*O(x^n))^2);polcoeff(A,n)} \\ Paul D. Hanna, Jul 27 2009

From Paul D. Hanna, Jul 27 2009: (Start)
G.f. satisfies: A(x) = A(x^3)*(1+x+x^2)/(1-x)^2.
Define TRISECTIONS: A(x) = T_0(x^3) + x*T_1(x^3) + x^2*T_2(x^3), then:
T_1(x)/T_0(x) = 3*(1 + 2*x)/(1 + 7*x + x^2) and
T_2(x)/T_0(x) = 3*(2 + x)/(1 + 7*x + x^2).
(End)

A258487 Number of tangled chains of length k=4.

Original entry on oeis.org

1, 1, 14, 2140, 1017219, 1110178602, 2320017306125, 8278981347401059, 46556715158334549170, 388779284837787599307987, 4605471565794120802036550000, 74633554055057890778698344509705, 1606481673354648219373898238155693682, 44821655543075499856527523557216582931002

Offset: 1

Sara Billey, Matjaz Konvalinka, and Frederick A. Matsen IV, May 31 2015

nonn

Tangled chains are ordered lists of k rooted binary trees with n leaves and a matching between each leaf from the i-th tree with a unique leaf from the (i+1)-st tree up to isomorphism on the binary trees. This sequence fixes k=4, and n = 1,2,3,...

R. Page, Tangled trees: phylogeny, cospeciation, and coevolution, The University of Chicago Press, 2002.

S. Billey, Table of n, a(n) for n = 1..20
Sara Billey, Matjaž Konvalinka, and Frederick A. Matsen IV, On the enumeration of tanglegrams and tangled chains, arXiv:1507.04976 [math.CO], 2015.

Cf. A000123 (binary partitions), A258620 (tanglegrams), A258485, A258486, A258487, A258488, A258489 (tangled chains), A259114 (unordered tanglegrams).

t(n) = Sum_{b=(b(1),...,b(t))} Product_{i=2..t} (2(b(i)+...+b(t))-1)^4)/z(b) where the sum is over all binary partitions of n and z(b) is the size of the stabilizer of a permutation of cycle type b under conjugation.

A258488 Number of tangled chains of length k=5.

Original entry on oeis.org

1, 1, 41, 31732, 106420469, 1046976648840, 24085106680575625, 1117767454807330938472, 94308987414050519542935029, 13390317159105772877158700776107, 3014130596940522685213135526859317500, 1025828273466214412416440210115479183065903, 507888918625036626314714587415852381698509422634

Offset: 1

Sara Billey, Matjaz Konvalinka, and Frederick A. Matsen IV, May 31 2015

nonn

Tangled chains are ordered lists of k rooted binary trees with n leaves and a matching between each leaf from the i-th tree with a unique leaf from the (i+1)-st tree up to isomorphism on the binary trees. This sequence fixes k=5, and n = 1,2,3,...

R. Page, Tangled trees: phylogeny, cospeciation, and coevolution, The University of Chicago Press, 2002.

Sara Billey, Matjaž Konvalinka, and Frederick A. Matsen IV, On the enumeration of tanglegrams and tangled chains, arXiv:1507.04976 [math.CO], 2015.

Cf. A000123 (binary partitions), A258620 (tanglegrams), A258485, A258486, A258487, A258488, A258489 (tangled chains), A259114 (unordered tanglegrams).

t(n) = Sum_{b=(b(1),...,b(t))} Product_{i=2..t} (2(b(i)+...+b(t))-1)^5)/z(b) where the sum is over all binary partitions of n and z(b) is the size of the stabilizer of a permutation of cycle type b under conjugation.

A258489 Number of tangled chains of length k=6.

Original entry on oeis.org

1, 1, 122, 474883, 11168414844, 989169269347359, 250335000079534559375, 151038989624520433840089358, 191158216491241179675824199407135, 461408865973380293005829125668717407727, 1973397409908124305318632313047269426852165625, 14104214451439837037643144221899175649593123932192274

Offset: 1

Sara Billey, Matjaz Konvalinka, and Frederick A. Matsen IV, May 31 2015

nonn

Tangled chains are ordered lists of k rooted binary trees with n leaves and a matching between each leaf from the i-th tree with a unique leaf from the (i+1)-st tree up to isomorphism on the binary trees. This sequence fixes k=6, and n = 1,2,3,...

R. Page, Tangled trees: phylogeny, cospeciation, and coevolution, The University of Chicago Press, 2002.

Sara Billey, Matjaž Konvalinka, and Frederick A. Matsen IV, On the enumeration of tanglegrams and tangled chains, arXiv:1507.04976 [math.CO], 2015.

Cf. A000123 (binary partitions), A258620 (tanglegrams), A258485, A258486, A258487, A258488, A258489 (tangled chains), A259114 (unordered tanglegrams).

t(n) = Sum_{b=(b(1),...,b(t))} Product_{i=2..t} (2(b(i)+...+b(t))-1)^6)/z(b) where the sum is over all binary partitions of n and z(b) is the size of the stabilizer of a permutation of cycle type b under conjugation.

A089054 Solution to the non-squashing boxes problem (version 1).

Original entry on oeis.org

1, 2, 4, 8, 14, 23, 36, 54, 78, 109, 149, 199, 262, 339, 434, 548, 686, 849, 1043, 1269, 1535, 1842, 2199, 2607, 3078, 3613, 4225, 4915, 5700, 6581, 7576, 8686, 9934, 11321, 12871, 14585, 16493, 18596, 20925, 23481, 26303, 29392, 32788, 36492, 40553, 44972, 49799

Offset: 0

N. J. A. Sloane, Dec 04 2003

nonn

Given n boxes labeled 1..n, such that box i weighs i grams and can support a total weight of i grams; a(n) = number of stacks of boxes that can be formed such that no box is squashed.

Amanda Folsom, Youkow Homma, Jun Hwan Ryu, and Benjamin Tong, On a general class of non-squashing partitions, Discrete Mathematics 339 (2016) 1482-1506.
Oystein J. Rodseth, Sloane's box stacking problem, Discrete Math. 306 (2006), no. 16, 2005-2009.
Øystein J. Rødseth and James A. Sellers, Congruences modulo high powers of 2 for Sloane's box stacking function, Australasian Journal of Combinatorics, Volume 44 (2009), Pages 255-263.
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003; Discrete Math., 294 (2005), 259-274.

Cf. A000123, A088567, A089055, A090631, A090632. Row sums of A090641.

max = 50; B[x_] = 1+x/(1-x) + Sum[x^(3 2^(k-1))/Product[(1-x^(2^j)), {j, 0, k}], {k, 1, Log[2, max]}] + O[x]^max;
A[x_] = (B[x]-x)/(1-x)^2;
CoefficientList[A[x], x] (* Jean-François Alcover, Sep 01 2018 *)

G.f.: (B(x)-x)/(1-x)^2, where B(x) = g.f. for A088567.

A258486 Number of tangled chains of length k=3.

Original entry on oeis.org

1, 1, 5, 151, 9944, 1196991, 226435150, 61992679960, 23198439767669, 11380100883484302, 7087878538028540725, 5465174495550911165171, 5111311778783673593594175, 5701234859347275019419890715, 7477492710871626347942014991975, 11393306956061559325223329489826611, 19958666934810234750929365717573438949, 39835206091758734935374720734513530255512, 89867076346063005007676287874769844881101800, 227547795689116560408812799327387232156371842150

Offset: 1

Sara Billey, May 31 2015

nonn

Tangled chains are ordered lists of k rooted binary trees with n leaves and a matching between each leaf from the i-th tree with a unique leaf from the (i+1)st tree up to isomorphism on the binary trees. This sequence fixes k=3, and n = 1,2,3,...

R. Page, Tangled trees: phylogeny, cospeciation, and coevolution, The University of Chicago Press, 2002.

Sara Billey, Matjaž Konvalinka, and Frederick A. Matsen IV, On the enumeration of tanglegrams and tangled chains, (2015).

Cf. A000123 (binary partitions), A258485 (tanglegrams), A258487, A258488, A258489.

t(n) = Sum_{b=(b(1),...,b(t))} Product_{i=2..t} (2(b(i)+...+b(t))-1)^3)/z(b) where the sum is over all binary partitions of n and z(b) is the size of the stabilizer of a permutation of cycle type b under conjugation.

A022907 The sequence m(n) in A022905.

Original entry on oeis.org

0, 2, 5, 8, 14, 20, 29, 38, 53, 68, 89, 110, 140, 170, 209, 248, 302, 356, 425, 494, 584, 674, 785, 896, 1037, 1178, 1349, 1520, 1730, 1940, 2189, 2438, 2741, 3044, 3401, 3758, 4184, 4610, 5105, 5600, 6185, 6770, 7445, 8120, 8906, 9692, 10589

Offset: 1

Clark Kimberling

nonn

T. D. Noe, Table of n, a(n) for n=1..1000
J. M. Dover, On two OEIS conjectures, arXiv:1606.08033 [math.CO], 2016.

a123[n_] := a123[n] = If[n == 0, 1, a123[Floor[n/2]] + a123[n-1]];
a[n_] := If[n == 1, 0, (3/2) a123[n-1] - 1]; Array[a, 50] (* Jean-François Alcover, Dec 04 2018 *)

from itertools import islice
from collections import deque
def A022907_gen(): # generator of terms
    aqueue, f, b, a = deque([2]), True, 1, 2
    yield from (0, 2, 5)
    while True:
        a += b
        yield 3*a-1
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A022907_list = list(islice(A022907_gen(),40)) # Chai Wah Wu, Jun 08 2022

a(n) = 3 * A033485(n-1) - 1 = (3/2) * A000123(n-1) - 1, n>1. Proved by Jeremy Dover. - Ralf Stephan, Dec 08 2004

A088932 G.f.: 1/((1-x)^2(1-x^2)(1-x^4)*(1-x^8)).

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166, 201, 236, 280, 324, 380, 436, 504, 572, 656, 740, 840, 940, 1060, 1180, 1320, 1460, 1625, 1790, 1980, 2170, 2390, 2610, 2860, 3110, 3396, 3682, 4004, 4326, 4690, 5054, 5460, 5866, 6321, 6776, 7280, 7784

Offset: 0

N. J. A. Sloane, Dec 02 2003

a(n) is the number of partitions of 2*n into powers of 2 less than or equal to 2^4. First differs from A000123 at n=16. - Alois P. Heinz, Apr 02 2012

Alois P. Heinz, Table of n, a(n) for n = 0..2000
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,2,-2,0,2,0,-2,0,2,-2,2,0,-2,1).

See A000027, A002620, A008804, A088954, A000123 for similar sequences.
Column k=4 of A181322.
Cf. A010873.

f := proc(n,k) option remember; if k > n then RETURN(0); fi; if k= 0 then if n=0 then RETURN(1) else RETURN(0); fi; fi; if k = 1 then RETURN(1); fi; if n mod 2 = 1 then RETURN(f(n-1,k)); fi; f(n-1,k)+f(n/2,k-1); end; # present sequence is f(2m,5)
GFF := k->x^(2^(k-2))/((1-x)*mul((1-x^(2^j)),j=0..k-2)); # present g.f. is GFF(5)/x^8
a:= proc(n) local m, r; m := iquo(n, 8, 'r'); r:= r+1; [1, 2, 4, 6, 10, 14, 20, 26][r]+ (((8/3*m +(4*r +28)/3)*m +[0, 4, 9, 14, 20, 26, 33, 40][r] +43/3)*m +[22, 33, 50, 67, 93, 119, 154, 189][r]/3)*m end: seq(a(n), n=0..60); # Alois P. Heinz, Apr 17 2009

CoefficientList[Series[1/((1-x)^2(1-x^2)(1-x^4)(1-x^8)), {x,0,60}], x]  (* Harvey P. Dale, Apr 22 2011 *)
Table[1 + 1237*n/1536 + 17*n^2/96 + 13*n^3/768 + n^4/1536 + (5/32 + n/32) * Floor[n/4] + (81/256 + 3*n/32 + n^2/128) * Floor[n/2] - Floor[(n+1)/8]/4 - (n+3) * Floor[(n+1)/4]/32 - Floor[(n+2)/8]/4, {n, 0, 100}] (* Vaclav Kotesovec, May 02 2018 *)
Table[Simplify[1023/1024 + 85*n/96 + 341*n^2/1536 + n^3/48 + n^4/1536 + (-1)^n*(113/1024 + n/32 + n^2/512) - (1 + Sqrt[2])*Cos[Pi*n/4]/16 + Cos[Pi*n/2]/64 + (Sqrt[2] - 1) * Cos[3*Pi*n/4]/16 + (1/8 + n/64)*Sin[Pi*n/2]], {n, 0, 100}] (* Vaclav Kotesovec, May 02 2018 *)

Vec(1/((1-x)^2*(1-x^2)*(1-x^4)*(1-x^8))+O(x^99)) \\ Charles R Greathouse IV, Sep 03 2011

a(n) = (8*floor(n/4)^4 + 8*(m+8)*floor(n/4)^3 - 2*(m^3 - 6*m^2 - 19*m - 86)*floor(n/4)^2 -8*(m^3 - 6*m^2 - 6*m - 22)*floor(n/4) - 7*m^3 + 42*m^2 + 13*m + 54 - (m^3 - 6*m^2 + 5*m + 6)*(-1)^floor(n/4))/48 where m = n mod 4. - Luce ETIENNE, Apr 07 2018

cp's OEIS Frontend

A005705 Number of partitions of 4*n into powers of 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A072720 Number of partitions of n into parts which are each powers of a single number (which may vary between partitions).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A161809 G.f.: A(x) = exp( Sum_{n>=1} 3*A038500(n) * x^n/n ), where A038500 is the highest power of 3 dividing n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A258487 Number of tangled chains of length k=4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A258488 Number of tangled chains of length k=5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A258489 Number of tangled chains of length k=6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A089054 Solution to the non-squashing boxes problem (version 1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A258486 Number of tangled chains of length k=3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A161809 G.f.: A(x) = exp( Sum_{n>=1} 3A038500(n) x^n/n ), where A038500 is the highest power of 3 dividing n.

A088932 G.f.: 1/((1-x)^2(1-x^2)(1-x^4)*(1-x^8)).