|
| |
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
