login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055167 Number of optimal binary prefix-free codes with n words all ending in 1. 0
1, 1, 1, 1, 2, 3, 4, 5, 7, 9, 13, 17, 23, 30, 39, 50, 65, 83, 107, 136, 174, 219, 278, 348, 437, 544, 678, 839, 1039, 1279, 1574, 1929, 2362, 2881, 3511, 4264, 5174, 6258, 7560, 9107, 10959, 13152, 15766, 18855, 22522, 26844, 31960, 37973, 45066, 53386, 63167, 74615, 88038 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

REFERENCES

Z. Kukorelly, Optimal binary one-ended codes. IEEE Trans. Inform. Theory, Vol. 48 (2002), no. 7, 2125-2132.

LINKS

Table of n, a(n) for n=1..53.

FORMULA

a(n)=sum_{0 <= a < n/3} sum_{0 <= b < n/3} g(n, a, b) with for 1 <= n <= 4, g(n, a, b)=1 if a=b=1 and g(n, a, b)=0 otherwise; for n >= 5: g(n, b, 1)=sum_{a = 0..b, b-a even } g(n-1, a, b), (b >= 1); g(n, a, b)=g(n-1, a, b-1), (2 <= b <= a); g(n, a, b)=g(n-1, a, b-1), (b-a >= 2 text{even}, a >= 0); g(n, a, b)=g(n-1, a+1, b), (b-a >= 1 text{odd}, a >= 0); g(n, a, b)=0 (otherwise).

MATHEMATICA

g[n_, a_, b_] := 0; g[n_, 1, 1] := 1/; (n >= 1 && n<=4); g[n_, a_, b_] := 0/; (n >= 1 && n<=4 && (a!=1 || b!=1)); g[n_, b_, 1] := (g[n, b, 1] = Sum[g[n-1, 2 a, b], {a, 0, b/2}])/; (b>=1 && EvenQ[b]); g[n_, b_, 1] := (g[n, b, 1] = Sum[g[n-1, 2 a + 1, b], {a, 0, (b-1)/2}])/; (b>=1 && OddQ[b]); g[n_, a_, b_] := (g[n, a, b] = g[n-1, a, b-1]_/; (b>=2 && a>=b); g[n_, a_, b_] := (g[n, a, b] = g[n-1, a, b-1])/; (a>=0 && b>=a+2 && EvenQ[b-a]); g[n_, a_, b_] := (g[n, a, b] = g[n-1, a+1, b])/; (a>=0 && b>=a+1 && OddQ[b-a]);

a[n_] := Sum[g[n, a, b], {a, 0, Floor[n/3]}, {b, 0, Floor[n/3]}]

CROSSREFS

Sequence in context: A039863 A036802 A333265 * A064628 A188674 A320316

Adjacent sequences:  A055164 A055165 A055166 * A055168 A055169 A055170

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Jul 04 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 22 06:53 EDT 2020. Contains 337289 sequences. (Running on oeis4.)