cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A052551 Expansion of 1/((1 - x)*(1 - 2*x^2)).

Original entry on oeis.org

1, 1, 3, 3, 7, 7, 15, 15, 31, 31, 63, 63, 127, 127, 255, 255, 511, 511, 1023, 1023, 2047, 2047, 4095, 4095, 8191, 8191, 16383, 16383, 32767, 32767, 65535, 65535, 131071, 131071, 262143, 262143, 524287, 524287, 1048575, 1048575, 2097151, 2097151
Offset: 0

Views

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

Comments

Equals row sums of triangle A137865. - Gary W. Adamson, Feb 18 2008
Also, the decimal representation of the diagonal from the corner to the origin of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 566", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - Robert Price, Jul 05 2017
Number of nonempty subsets of {1,2,...,n+1} that contain only odd numbers. a(0) = a(1) = 1: {1}; a(6) = a(7) = 15: {1}, {3}, {5}, {7}, {1,3}, {1,5}, {1,7}, {3,5}, {3,7}, {5,7}, {1,3,5}, {1,3,7}, {1,5,7}, {3,5,7}, {1,3,5,7}. - Enrique Navarrete, Mar 16 2018
Number of nonempty subsets of {1,2,...,n+2} that contain only even numbers. a(0) = a(1) = 1: {2}; a(4) = a(5) = 7: {2}, {4}, {6}, {2,4}, {2,6}, {4,6}, {2,4,6}. - Enrique Navarrete, Mar 26 2018
Doubling of A000225(n+1), n >= 0 entries. First differences give A077957. - Wolfdieter Lang, Apr 08 2018
a(n-2) is the number of achiral rows or cycles of length n partitioned into two sets or the number of color patterns using exactly 2 colors. An achiral row or cycle is equivalent to its reverse. Two color patterns are equivalent if the colors are permuted. For n = 4, the a(n-2) = 3 row patterns are AABB, ABAB, and ABBA; the cycle patterns are AAAB, AABB, and ABAB. For n = 5, the a(n-2) = 3 patterns for both rows and cycles are AABAA, ABABA, and ABBBA. For n = 6, the a(n-2) = 7 patterns for rows are AAABBB, AABABB, AABBAA, ABAABA, ABABAB, ABBAAB, and ABBBBA; the cycle patterns are AAAAAB, AAAABB, AAABAB, AAABBB, AABAAB, AABABB, and ABABAB. - Robert A. Russell, Oct 15 2018
For integers m > 1, the expansion of 1/((1 - x)*(1 - m*x^2)) generates a(n) = (sqrt(m)^(n + 1)*((-1)^n*(sqrt(m) - 1) + sqrt(m) + 1) - 2)/(2*(m - 1)). It appears, for integer values of n >= 0 and m > 1, that it could be simplified in the integral domain a(n) = (m^(1 + floor(n/2)) - 1)/(m - 1). - Federico Provvedi, Nov 23 2018
From Werner Schulte, Mar 04 2019: (Start)
More generally: For some fixed integers q and r > 0 the expansion of A(q,r; x) = 1/((1-x)*(1-q*x^r)) generates coefficients a(q,r; n) = (q^(1+floor(n/r))-1)/(q-1) for n >= 0; the special case q = 1 leads to a(1,r; n) = 1 + floor(n/r).
The a(q,r; n) satisfy for n > r a linear recurrence equation with constant coefficients. The signature vector is given by the sum of two vectors v and w where v has terms 1 followed by r zeros, i.e., (1,0,0,...,0), and w has r-1 leading zeros followed by q and -q, i.e., (0,0,...,0,q,-q).
Let a_i(q,r; n) be the convolution inverse of a(q,r; n). The terms are given by the sum a_i(q,r; n) = b(n) + c(n) for n >= 0 where b(n) has terms 1 and -1 followed by infinitely zeros, i.e., (1,-1,0,0,0,...), and c(n) has r leading zeros followed by -q, q and infinitely zeros, i.e., (0,0,...,0,-q,q,0,0,0,...).
Here is an example for q = 3 and r = 5: The expansion of A(3,5; x) = 1/((1-x)*(1-3*x^5)) = Sum_{n>=0} a(3,5; n)*x^n generates the sequence of coefficients (a(3,5; n)) = (1,1,1,1,1,4,4,4,4,4,13,13,13,13,13,40,...) where r = 5 controls the repetition and q = 3 the different values.
The a(3,5; n) satisfy for n > 5 the linear recurrence equation with constant coefficients and signature (1,0,0,0,0,0) + (0,0,0,0,3,-3) = (1,0,0,0,3,-3).
The convolution inverse a_i(3,5; n) has terms (1,-1,0,0,0,0,0,0,0,...) + (0,0,0,0,0,-3,3,0,0,...) = (1,-1,0,0,0,-3,3,0,0,...).
For further examples and informations see A014983 (q,r = -3,1), A077925 (q,r = -2,1), A000035 (q,r = -1,1), A000012 (q,r = 0,1), A000027 (q,r = 1,1), A000225 (q,r = 2,1), A003462 (q,r = 3,1), A077953 (q,r = -2,2), A133872 (q,r = -1,2), A004526 (q,r = 1,2), A052551 (this sequence with q,r = 2,2), A077886 (q,r = -2,3), A088911 (q,r = -1,3), A002264 (q,r = 1,3) and A077885 (q,r = 2,3). The offsets might be different.
(End)
a(n) is the number of palindromes of length n over the alphabet {1,2} containing the letter 1. More generally, the number of palindromes of length n over the alphabet {1,2,...,k} containing the letter 1 is given by k^ceiling(n/2)-(k-1)^ceiling(n/2). - Sela Fried, Dec 10 2024

References

  • S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Crossrefs

Column 2 (offset by two) of A304972.
Cf. A000225 (oriented), A056326 (unoriented), and A122746(n-2) (chiral) for rows.
Cf. A056295 (oriented), A056357 (unoriented), and A059053 (chiral) for cycles.

Programs

  • GAP
    Flat(List([1..21],n->[2^n-1,2^n-1])); # Muniru A Asiru, Oct 16 2018
    
  • Magma
    [2^Floor(n/2)-1: n in [2..50]]; // Vincenzo Librandi, Aug 16 2011
    
  • Maple
    spec := [S,{S=Prod(Sequence(Prod(Z,Union(Z,Z))),Sequence(Z))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
  • Mathematica
    Table[StirlingS2[Floor[n/2] + 2, 2], {n, 0, 50}] (* Robert A. Russell, Dec 20 2017 *)
    Drop[LinearRecurrence[{1, 2, -2}, {0, 1, 1}, 50], 1] (* Robert A. Russell, Oct 14 2018 *)
    CoefficientList[Series[1/((1-x)*(1-2*x^2)), {x, 0, 50}], x] (* Stefano Spezia, Oct 16 2018 *)
    2^(1+Floor[(Range[0,50])/2])-1 (* Federico Provvedi, Nov 22 2018 *)
    ((-1)^#(Sqrt[2]-1)+Sqrt[2]+1)2^((#-1)/2)-1&@Range[0, 50] (* Federico Provvedi, Nov 23 2018 *)
  • PARI
    x='x+O('x^50); Vec(1/((1-x)*(1-2*x^2))) \\ Altug Alkan, Mar 19 2018
    
  • Sage
    [2^(floor(n/2)) -1 for n in (2..50)] # G. C. Greubel, Mar 04 2019

Formula

G.f.: 1/((1 - x)*(1 - 2*x^2)).
Recurrence: a(1) = 1, a(0) = 1, -2*a(n) - 1 + a(n+2) = 0.
a(n) = -1 + Sum((1/2)*(1 + 2*alpha)*alpha^(-1 - n)) where the sum is over alpha = the two roots of -1 + 2*x^2.
a(n) = A016116(n+2) - 1. - R. J. Mathar, Jun 15 2009
a(n) = A060546(n+1) - 1. - Filip Zaludek, Dec 10 2016
From Robert A. Russell, Oct 15 2018: (Start)
a(n-2) = S2(floor(n/2)+1,2), where S2 is the Stirling subset number A008277.
a(n-2) = 2*A056326(n) - A000225(n) = A000225(n) - 2*A122746(n-2) = A056326(n) - A122746(n-2).
a(n-2) = 2*A056357(n) - A056295(n) = A056295(n) - 2*A059053(n) = A056357(n) - A059053(n). (End)
From Federico Provvedi, Nov 22 2018: (Start)
a(n) = 2^( 1 + floor(n/2) ) - 1.
a(n) = ( (-1)^n*(sqrt(2)-1) + sqrt(2) + 1 ) * 2^( (n - 1)/2 ) - 1. (End)
E.g.f.: 2*cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x) - cosh(x) - sinh(x). - Franck Maminirina Ramaharo, Nov 23 2018

Extensions

More terms from James Sellers, Jun 06 2000

A152176 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations and reflections.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 14, 11, 3, 1, 1, 8, 31, 33, 16, 3, 1, 1, 17, 82, 137, 85, 27, 4, 1, 1, 22, 202, 478, 434, 171, 37, 4, 1, 1, 43, 538, 1851, 2271, 1249, 338, 54, 5, 1, 1, 62, 1401, 6845, 11530, 8389, 3056, 590, 70, 5, 1, 1, 121, 3838, 26148
Offset: 1

Views

Author

Vladeta Jovovic, Nov 27 2008

Keywords

Comments

Number of bracelet structures of length n using exactly k different colored beads. Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure. - Andrew Howroyd, Apr 06 2017
The number of achiral structures (A) is given in A140735 (odd n) and A293181 (even n). The number of achiral structures plus twice the number of chiral pairs (A+2C) is given in A152175. These can be used to determine A+C by taking half their average, as is done in the Mathematica program. - Robert A. Russell, Feb 24 2018
T(n,k)=pi_k(C_n) which is the number of non-equivalent partitions of the cycle on n vertices, with exactly k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Mohammad Hadi Shekarriz, Aug 21 2019

Examples

			Triangle begins:
  1;
  1,  1;
  1,  1,   1;
  1,  3,   2,    1;
  1,  3,   5,    2,    1;
  1,  7,  14,   11,    3,    1;
  1,  8,  31,   33,   16,    3,   1;
  1, 17,  82,  137,   85,   27,   4,  1;
  1, 22, 202,  478,  434,  171,  37,  4, 1;
  1, 43, 538, 1851, 2271, 1249, 338, 54, 5, 1;
  ...
		

References

  • M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Crossrefs

Columns 2-6 are A056357, A056358, A056359, A056360, A056361.
Row sums are A084708.
Partial row sums include A000011, A056353, A056354, A056355, A056356.
Cf. A081720, A273891, A008277 (set partitions), A284949 (up to reflection), A152175 (up to rotation).

Programs

  • Mathematica
    Adn[d_, n_] := Adn[d, n] = Which[0==n, 1, 1==n, DivisorSum[d, x^# &],
      1==d, Sum[StirlingS2[n, k] x^k, {k, 0, n}],
      True, Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n - 1], x] x]];
    Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[0==n, 1, 0], 1, If[n>0, 1, 0],
      (* else *) _, If[OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1],
      {i, 0, (n-1)/2}], Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]
      + 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]] (* achiral loops of length n, k colors *)
    Table[(CoefficientList[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/(x n), x]
    + Table[Ach[n, k],{k,1,n}])/2, {n, 1, 20}] // Flatten (* Robert A. Russell, Feb 24 2018 *)
  • PARI
    \\ see A056391 for Polya enumeration functions
    T(n,k) = NonequivalentStructsExactly(DihedralPerms(n), k); \\ Andrew Howroyd, Oct 14 2017
    
  • PARI
    \\ Ach is A304972 and R is A152175 as square matrices.
    Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
    R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
    T(n)={(R(n) + Ach(n))/2}
    { my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

A059053 Number of chiral pairs of necklaces with n beads and two colors (color complements being equivalent); i.e., turning the necklace over neither leaves it unchanged nor simply swaps the colors.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 2, 7, 12, 31, 58, 126, 234, 484, 906, 1800, 3402, 6643, 12624, 24458, 46686, 90157, 172810, 333498, 641340, 1238671, 2388852, 4620006, 8932032, 17302033, 33522698, 65042526, 126258960, 245361172, 477091232
Offset: 0

Views

Author

Henry Bottomley, Dec 21 2000

Keywords

Comments

Number of chiral pairs of set partitions of a cycle of n elements using exactly two different elements. - Robert A. Russell, Oct 02 2018

Examples

			For a(7) = 1, the chiral pair is AAABABB-AAABBAB.
For a(8) = 2, the chiral pairs are AAAABABB-AAAABBAB and AAABAABB-AAABBAAB.
		

Crossrefs

Column 2 of A320647 and A320742.
Cf. A056295 (oriented), A056357 (unoriented), A052551(n-2) (achiral).

Programs

  • Mathematica
    Prepend[Table[DivisorSum[n, EulerPhi[#] StirlingS2[n/# + If[Divisible[#,2],1,0], 2] &] / (2n) - StirlingS2[1+Floor[n/2],2] / 2, {n, 1, 40}],0] (* Robert A. Russell, Oct 02 2018 *)
  • PARI
    a(n) = {if(n<1, 0, (sumdiv(n, k, eulerphi(2*k) * 2^(n/k)) / (2*n) - 2^(n\2))/2)}; \\ Andrew Howroyd, Nov 03 2019

Formula

a(n) = A000013(n) - A000011(n) = A000011(n) - A016116(n) = (A000013(n) - A016116(n))/2.
From Robert A. Russell, Oct 02 2018: (Start)
a(n) = (A056295(n)-A052551(n-2)) / 2 = A056295(n) - A056357(n) = A056357(n) - A052551(n-2).
a(n) = -S2(1+floor(n/2),2) + (1/2n) * Sum_{d|n} phi(d) * S2(n/d+[2|d],2), where S2 is a Stirling subset number A008277.
G.f.: -x(1+2x)/(2-4x^2) - Sum_{d>0} phi(d) * log(1-2x^d) / (2d*(2-[2|d])).
(End)

Extensions

Name clarified by Robert A. Russell, Oct 02 2018

A084708 Number of set partitions up to rotations and reflections.

Original entry on oeis.org

1, 2, 3, 7, 12, 37, 93, 354, 1350, 6351, 31950, 179307, 1071265, 6845581, 46162583, 327731950, 2437753740, 18948599220, 153498350745, 1293123243928, 11306475314467, 102425554299516, 959826755336242, 9290811905391501
Offset: 1

Views

Author

Wouter Meeussen, Jul 02 2003

Keywords

Comments

Combines the symmetry operations of A080107 and A084423.
Equivalently, number of n-bead bracelets using any number of unlabeled (interchangable) colors. - Andrew Howroyd, Sep 25 2017

Examples

			SetPartitions[6] is the first to decompose differently from A084423: 4 cycles of length 1, 2 of 2, 9 of 3, 16 of 6, 6 of 12.
a(7) = 1 + A056357(7) + A056358(7) + A056359(7) + A056360(7) + A056361(7) + 1 = 1 + 8 + 31 + 33 + 16 + 3 + 1 = 93.
		

Crossrefs

Programs

  • Mathematica
    <A080107 *); Table[{Length[ # ], First[ # ]}&/@ Split[Sort[Length/@Split[Sort[First[Sort[Flatten[ {#, Map[Sort, (#/. i_Integer:>w+1-i), 2]}& @(NestList[Sort[Sort/@(#/. i_Integer :> Mod[i+1, w, 1])]&, #, w]), 1]]]&/@SetPartitions[w]]]]], {w, 1, 10}]
    u[0,j_]:=1;u[k_,j_]:=u[k,j]=Sum[Binomial[k-1,i-1]Plus@@(u[k-i,j]#^(i-1)&/@Divisors[j]),{i,k}]; a[n_]:=1/n*Plus@@(EulerPhi[ # ]u[Quotient[n,# ],# ]&/@Divisors[n]); Table[a[n]/2+If[EvenQ[n],u[n/2,2],Sum[Binomial[n/2-1/2,k] u[k,2], {k,0,n/2-1/2}]]/2,{n,40}] (* Wouter Meeussen, Dec 06 2008 *)

Formula

a(n) = (A080107(n)+A084423(n))/2. - Wouter Meeussen and Vladeta Jovovic, Nov 28 2008

Extensions

a(12) from Vladeta Jovovic, Jul 15 2007
More terms from Vladeta Jovovic's formula given in Mathematica line. - Wouter Meeussen, Dec 06 2008

A213942 a(n) is the number of representative two-color bracelets (necklaces with turnover allowed) with n beads for n >= 2.

Original entry on oeis.org

1, 1, 3, 3, 7, 8, 18, 22, 46, 62, 136, 189, 409, 611, 1344, 2055, 4535, 7154, 15881, 25481, 56533, 92204, 204759, 337593, 748665, 1246862, 2762111, 4636389, 10253938, 17334800, 38278784, 65108061, 143534770, 245492243, 540353057, 928772649, 2041154125
Offset: 2

Views

Author

Wolfdieter Lang, Jul 31 2012

Keywords

Comments

This is the second column (m=2) of triangle A213940.
The relevant floor(n/2) representative color multinomials are c[1]^(n-1)*c[2], c[1]^(n-2)*c[2]^2, ..., c[1]^(n-floor(n/2))* c[2]^(floor(n/2)). For such representative bracelets the color c[1] is therefore preferred. Only for even n can c[2] appear as often as c[1], namely, n/2 times.
Note that beads with different colors are always present. This is in contrast to, e.g., A000029, where not only representatives but also one-color bracelets are counted. This sequences gives the number of binary bracelets with at least as many 0's as 1's and at least one 1 (bracelet analog of A226881). The number of two-color bracelets up to permutations of colors is given by A056357. For odd n these two sequences are equal. For a(8), the bracelets 00011011 and 11100100 are equivalent in A056357 but distinct in this sequence. - Andrew Howroyd and Wolfdieter Lang, Sep 25 2017

Examples

			a(5) = A213939(5,2) + A213939(5,3) = 1 + 2 = 3 from the representative bracelets (with colors j for c[j], j=1,2) cyclic(11112), cyclic(11122) and cyclic(11212). The first one has color signature (exponents) [4,1] and the two others have signature [3,2]. For the number of all two-color 5-bracelets with beads of five colors available see A214308(5) = 60.
a(8) = 18 =  1 + 4 + 5 + 8 for the partitions of 8 with 2 parts (7,1), (6, 2), (5,3), (4,4), respectively. see A213939(5, k), k = 2..5). The 8 representative bracelets for the exponents (signature) from partition (4,4) are B1 = (11112222), B2 = (11121222), B3 = (11212122), B4 = (11212212), B5 = (11221122), B6 = (12121212), B7 = (11122122) and B8 = (11211222). B1 to B6 are color exchange (1 <-> 2) invariant (modulo D_8 symmetry, i.e., cyclic or anti-cyclic operations). B7 is equivalent to B8 under color exchange.
This explains why A056357(8) = 17. The difference between the present sequence and A056357 is that there, besides D_n symmetry, also color exchange is allowed. Here only color exchange compatible with D_n symmetry is allowed. - _Wolfdieter Lang_, Sep 28 2017
		

Crossrefs

Cf. A213939, A213940, A214307 (m=3), A214308 (m=2, all bracelets).

Programs

  • Mathematica
    a29[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#)&]/(2*n);
    a5648[n_] := 1/2*(Binomial[2*Quotient[n, 2], Quotient[n, 2]] + DivisorSum[n, EulerPhi[#]*Binomial[2*n/#, n/#]&]/(2*n));
    a[n_] := a29[n]/2 - 1 + If[EvenQ[n], a5648[n/2]/2, 0];
    Array[a, 37, 2] (* Jean-François Alcover, Nov 05 2017, after Andrew Howroyd *)

Formula

a(n) = A213940(n,2), n >= 2.
a(n) = Sum_{k=2..A008284(n,2)+1} A213939(n,k), n >= 2, with A008284(n,2) = floor(n/2).
a(2n) = (A000029(2n) + A005648(n)) / 2 - 1, a(2n+1) = A000029(2n+1) / 2 - 1. - Andrew Howroyd, Sep 25 2017

Extensions

Terms a(26) and beyond from Andrew Howroyd, Sep 25 2017

A327734 Number of n-bead bracelet structures using exactly two different colored beads that are not self-equivalent under either a nonzero rotation or reversal (turning over bracelet).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 2, 7, 12, 31, 57, 126, 232, 484, 900, 1800, 3388, 6643, 12594, 24457, 46624, 90157, 172680, 333498, 641088, 1238664, 2388357, 4620006, 8931052
Offset: 1

Views

Author

Andrew Howroyd, Sep 23 2019

Keywords

Examples

			Case n=7: There are 7 necklace structures using exactly two colors. See example in A056295. Of these, 5 are achiral and the other two a chiral pair: AAABABB/AAABBAB. a(7) = 1, since this sequence considers chiral pairs as the same bracelet structure.
		

Crossrefs

Column k=2 of A324802.
Showing 1-6 of 6 results.