A036258 Number of inequivalent strings of n digits, when 2 strings are equivalent if turning 1 upside down gives the other.

1, 9, 90, 945, 9700, 98475, 992250, 9961125, 99805000, 999024375, 9995118750, 99975590625, 999877937500, 9999389671875, 99996948281250, 999984741328125, 9999923706250000, 99999618530859375, 999998092652343750, 9999990463259765625, 99999952316289062500

Offset

0,2

References

Nick Baxter, The Burnside di-lemma: combinatorics and puzzle symmetry, in Tribute to a Mathemagician, Peters, 2005, pp. 199-210.

De Bruijn, Polya's theory of counting, in Beckenbach, ed., Applied Combinatorial Math., Wiley, 1964 (p. 182).

Links

Colin Barker, Table of n, a(n) for n = 0..950

Index entries for linear recurrences with constant coefficients, signature (15,-45,-75,250).

Formula

a(n+1) = (1/10)*{10^n - 5^n + (4-(-1)^n)*5^[n/2]} (De Bruijn)

From Colin Barker, Jul 03 2017: (Start)

G.f.: (1 - 6*x + 75*x^3) / ((1 - 5*x)*(1 - 10*x)*(1 - 5*x^2)).

a(n) = 5^((n-1)/2+1/2)/2 - 5^n/2 + 10^n for n even.

a(n) = 3*5^((n-1)/2)/2 - 5^n/2 + 10^n for n odd.

a(n) = 15*a(n-1) - 45*a(n-2) - 75*a(n-3) + 250*a(n-4) for n>3.

(End)

Maple

f:=n-> if n mod 2 = 0 then 10^n-(5^n-5^(n/2))/2 else 10^n-(5^n-3*5^((n-1)/2))/2; fi;

Mathematica

LinearRecurrence[{15, -45, -75, 250}, {1, 9, 90, 945}, 30] (* Harvey P. Dale, Jul 05 2023 *)

Prog

(PARI) Vec((1 - 6*x + 75*x^3) / ((1 - 5*x)*(1 - 10*x)*(1 - 5*x^2)) + O(x^30)) \\ Colin Barker, Jul 03 2017

Crossrefs

Cf. A036255, A036257.

Sequence in context: A052268 A155199 A147841 * A098399 A264914 A143079

Adjacent sequences: A036255 A036256 A036257 * A036259 A036260 A036261

Keyword

nonn,easy,base

Author

N. J. A. Sloane

Status

approved