ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P3.03
https://doi.org/10.26493/1855-3974.2701.b7d
(Also available at http://amc-journal.eu)
An online bin-packing problem with an
underlying ternary structure
Helmut Prodinger
Mathematics Department, Stellenbosch University, 7602 Stellenbosch, South Africa and
NITheCS (National Institute for Theoretical and Computational Sciences), South Africa
Received 19 September 2021, accepted 30 June 2023, published online 12 June 2024
Abstract
Following an orginal idea by Knödel, an online bin-packing problem is considered
where the large items arrive in double-packs. The dual problem where the small items
arrive in double-packs is also considered. The enumerations have a ternary random walk
flavour, and for the enumeration, the kernel method is employed.
Keywords: Knödel walks, third-order recursion, kernel method, coefficient extraction, state diagram.
Math. Subj. Class. (2020): 05A15, 68R05
1 Introduction
Walter Knödel introduced the following online bin-packing problem [3]: There are bins of
size 1, and random items of size 23 (large items) and of size
1
3 (small items) appear and are
put into the boxes. A typical scenario is that a number j of partially filled boxes exist, and
the number j becomes j + 1 resp. j − 1, depending on whether a the new item is of large
resp. small type. “At random” means that both types appear with the same probability 12 .
In my collection of examples [4], I showed how to deal with the Knödel problem us-
ing the kernel method. I was, however, not the only author who was intrigued by such
questions; a notable paper is by Michael Drmota [1], which is of a more probabilistic type,
whereas I tried to emphasize the combinatorial point of view.
The present paper has a certain ‘ternary’ flavour: the next section deals with the instance
of large items appearing in double-packs. The handler breaks off the double-packs, and
then treats the items as Knödel would have done. Typically, the number of partially filled
boxes increases by 2 or decreases by 1. In order to keep the system balanced, we assume
that the small items appear twice as often as the double-packs.
E-mail address: hproding@sun.ac.za (Helmut Prodinger)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P3.03
The last section deals with the dual problem, where the small items appear in double-
packs and the large items as single units.
The kernel method is used to obtain all the relevant enumerations. The recent paper [5]
served as an inspiration, but deals with a different issue. It must be said that, when [4] was
prepared, such ternary questions would have been outside of my reach. Luckily, now, they
are not.
We confine ourselves here just to enumerations, deriving explicit generating functions
in one or two variables. Questions of a more probabilistic nature are not treated.
2 The first model
The following items arrive at random: a double-pack of items, each of size 23 , and an item
of size 13 . We could equip the set-up with general probabilities p and q = 1 − p, but we
restrict ourselves to the ‘balanced’ case where the single items are twice as likely as the
double-packs, so we set p = 13 and q =
2
3 .
The following state diagram (we show only a finite part of it) describes the situation.
There are states representing ‘i boxes filled to 23 ’; a double-pack pushes the i to i+ 2, and
a single item reduces it to i − 1. There is an exceptional state, called β, standing for one
box, filled to 13 . The red edges represent an arrival of a double-pack, and will be labelled
by pz; the black edges represent an arrival of a single item, and will be labelled by qz.
0 1 2 3 4 5 6 7 8
β
From the state diagram, we set off an infinite set of generating functions in the variable
z, where the coefficient of zn is the probability that n random steps lead to state i, for i ≥ 0
or i = β. Mostly, we just write fi instead of fi(z). The following system of recursions can
be read off immediately:
f0 = 1 + qzf1, fβ = qzf0,
f1 = zfβ + qzf2 = qz
2f0 + qzf2,
fi = pzfi−2 + qzfi+1, i ≥ 2.
Our method to solve this system is the kernel method. For that, we introduce a bivariate
H. Prodinger: An online bin-packing problem with an underlying ternary structure 3
generating function F (u, z), but we mostly write just F (u):
F (u) =
∑
i≥0
uifi(z)
= 1 + qzf1 + qz
2uf0 + qzuf2 +
∑
i≥2
ui
[
pzfi−2 + qzfi+1
]
= 1 + qzf1 + qz
2uf0 + pzu
2F (u) +
∑
i≥1
uiqzfi+1
= 1 + qzf1 + qz
2uf0 + pzu
2F (u) +
qz
u
(
F (u)− f0 − uf1
)
= 1 + qz2uf0 + pzu
2F (u) +
qz
u
(
F (u)− f0
)
Note that f0 = F (0). It is beneficial to introduce the new variable u = zU ; doing this,
powers of z that appear are multiples of 3. Later, it will be convenient to set x = z3. As can
be seen, the numbers of steps leading to a state i belong to just one residue class modulo 3.
We compute
F (u) =
−3U − 2z3U2f0 + 2f0
z3U3 − 3U + 2
=
−3U − 2xU2f0 + 2f0
xU3 − 3U + 2
.
As it is common using the kernel method, setting U = 0 leads to a void equation. How-
ever, factorizing the denominator is the method of choice. There is ‘bad’ factor in the
denominator, which must also appear in the numerator, which allows us to compute f0
and consequently the whole bivariate generating function. In order to deal with the ternary
equation successfully, we further set x = z3 = 274 t(1− t)
2 and we find the 3 roots
U1 =
2
3(1− t)
, U2 =
1
σ
, U3 =
1
τ
,
with
σ =
3
4
(t−
√
4t− 3t2 ), τ = 3
4
(t+
√
4t− 3t2).
A motivation for this substitution is the Lagrange inversion formula and/or the enumeration
of ternary trees; see also [6]. Plugging U = 23(1−t) into the numerator (this is the bad factor,
as explained a little bit later), leads to
f0 =
1
(1− t)(1− 3t)
and furthermore to the simplified numerator
−3U − 2xU2f0 + 2f0
U − 23(1−t)
=
1
1− 3t
(
− 3 + 27
2
t(t− 1)U
)
.
4 Ars Math. Contemp. 24 (2024) #P3.03
The variable x is given in terms of t. The inverse relation is of interest. It can be obtained
by the Lagrange inversion formula or, as here, by contour integration:
[xk]t =
1
2πi
∮
dx
xk+1
t =
1
2πi
27
4
( 4
27
)k+1 ∮ dt(1− t)(1− 3t)
tk+1(1− t)2k+2
t
=
1
2πi
( 4
27
)k ∮ dt(1− 3t)
tk(1− t)2k+1
=
( 4
27
)k
[tk−1]
1− 3t
(1− t)2k+1
=
( 4
27
)k[(3k − 1
k − 1
)
− 3
(
3k − 2
k − 2
)]
,
which, after simplification, gives us
t =
∑
k≥1
1
k
(
3k − 2
k − 1
)
22k
33k
xk.
A similar computation leads to
1
1− t
=
∑
k≥0
1
2k + 1
(
3k
k
)
22k+1
33k+1
xk.
From this we infer that for z ∼ 0, U ∼ 23 , or u ∼
2
3z, explaining why we are talking about
the bad factor. We continue the computation:
F (u) =
1
1− 3t
(
− 3 + 27
2
t(t− 1)U
) 1
x(U − 1σ )(U −
1
τ )
=
1
1− 3t
(
− 3 + 27
2
t(t− 1)U
) 9
4 t(t− 1)
x(1− σU)(1− τU)
=
1
(1− 3t)(1− t)
(
1− 9
2
t(t− 1)U
) 1
(1− σU)(1− τU)
.
Partial fraction decomposition leads to (we use the abbreviation W =
√
4t− 3t2 )
1
(1− σU)(1− τU)
=
1
2
(
1− t
W
) 1
1− σU
+
1
2
(
1 +
t
W
) 1
1− τU
=
1
2
[ 1
1− σU
+
1
1− τU
]
+
t
2W
[ 1
1− τU
− 1
1− σU
]
=
1
2
[ 1
1− σU
+
1
1− τU
]
+
3t
4(τ − σ)
[ 1
1− τU
− 1
1− σU
]
.
For the further simplification we will resort to two identities going by the name of Girard-
Waring formula, see e. g. [2]:
Xm + Y m =
∑
0≤k≤m/2
(−1)k
(
m− k
k
)
m
m− k
(XY )k(X + Y )m−2k;
Xm − Y m
X − Y
=
∑
0≤k≤(m−1)/2
(−1)k
(
m− 1− k
k
)
(XY )k(X + Y )m−1−2k.
H. Prodinger: An online bin-packing problem with an underlying ternary structure 5
Of course, we will apply them with X = τ and Y = σ. Then
[Um]
1
2
[ 1
1− σU
+
1
1− τU
]
=
1
2
∑
0≤k≤m/2
(−1)k
(
m− k
k
)
m
m− k
(9
4
t(t− 1)
)k(3
2
t
)m−2k
=
1
2
(3
2
)m ∑
0≤k≤m/2
(−1)k
(
m− k
k
)
m
m− k
tk(t− 1)ktm−2k
=
1
2
(3
2
)m ∑
0≤k≤m/2
(−1)k
(
m− k
k
)
m
m− k
(t− 1)ktm−k
and
[Um]
3t
4(τ − σ)
[ 1
1− τU
− 1
1− σU
]
=
3t
4
∑
0≤k≤(m−1)/2
(−1)k
(
m− 1− k
k
)(9
4
t(t− 1)
)k(3
2
t
)m−1−2k
=
(3
2
)m−1 3t
4
∑
0≤k≤(m−1)/2
(−1)k
(
m− 1− k
k
)
(t− 1)ktm−1−k
=
1
2
(3
2
)m ∑
0≤k≤(m−1)/2
(−1)k
(
m− 1− k
k
)
(t− 1)ktm−k.
Combining the two leads to a pleasant simplification:
[Um]
1
2
[ 1
1− σU
+
1
1− τU
]
+ [Um]
3t
4(τ − σ)
[ 1
1− τU
− 1
1− σU
]
=
(3
2
)m ∑
0≤k≤m/2
(−1)k
(
m− k
k
)
(t− 1)ktm−k,
or simpler
[Um]
1
(1− σU)(1− τU)
=
(3
2
)m ∑
0≤k≤m/2
(−1)k
(
m− k
k
)
(t− 1)ktm−k.
We need a second similar term:
[Um]
(
− 9
2
t(t− 1)U
) 1
(1− σU)(1− τU)
= −9
2
t(t− 1)[Um−1] 1
(1− σU)(1− τU)
= −9
2
t(t− 1)
(3
2
)m−1 ∑
0≤k≤m/2
(−1)k
(
m− 1− k
k
)
(t− 1)ktm−1−k
= −3
(3
2
)m ∑
0≤k≤m/2
(−1)k
(
m− 1− k
k
)
(t− 1)k+1tm−k.
6 Ars Math. Contemp. 24 (2024) #P3.03
Putting everything together we found
F (u) =
1
(1− 3t)(1− t)
∑
m≥0
um
zm
(3
2
)m ∑
0≤k≤m/2
(−1)k
(
m− k
k
)
(t− 1)ktm−k
− 3
(1− 3t)(1− t)
∑
m≥0
um
zm
(3
2
)m ∑
0≤k≤m/2
(−1)k
(
m− 1− k
k
)
(t− 1)k+1tm−k.
Reading off the coefficients of zj for j ≥ 1 as well is now done with Cauchy’s integral for-
mula; the contours are always small circles (or equivalent) around the origin. The starting
point is
[znuj ]F (u) =
(3
2
)j
[zn+j ]
1
(1− 3t)(1− t)
∑
0≤k≤j/2
(−1)k
(
j − k
k
)
(t− 1)ktj−k
−
(3
2
)j
[zn+j ]
3
(1− 3t)(1− t)
∑
0≤k≤j/2
(−1)k
(
j − 1− k
k
)
(t− 1)k+1tj−k
and we will treat the two sums separately. There is only a contribution if n+ j ≡ 0 mod 3.
(This is also clear from the combinatorial context.) Assume this and set N := n+j3 .
Step 1:
[xN ]
1
(1− 3t)(1− t)
∑
0≤k≤j/2
(−1)k
(
j − k
k
)
(t− 1)ktj−k
=
1
2πi
∮
dx
xN+1
1
(1− 3t)(1− t)
∑
0≤k≤j/2
(−1)k
(
j − k
k
)
(t− 1)ktj−k
=
1
2πi
∮
27
4
dt(
27
4 t(1− t)2
)N+1 ∑
0≤k≤j/2
(−1)k
(
j − k
k
)
(t− 1)ktj−k
=
1
2πi
∮ ( 4
27
)N
dt
∑
0≤k≤j/2
(−1)k
(
j − k
k
)
(t− 1)k−2N−2tj−k−N−1
=
( 4
27
)N
[tN−j+k]
∑
0≤k≤j/2
(−1)k
(
j − k
k
)
(t− 1)k−2N−2
=
( 4
27
)N
(−1)N−j
∑
0≤k≤j/2
(
j − k
k
)(
k − 2N − 2
N − j + k
)
.
Step 2:
[xN ]
3
(1− 3t)(1− t)
∑
0≤k≤j/2
(−1)k
(
j − 1− k
k
)
(t− 1)k+1tj−k
= 3
( 4
27
)N
[tN−j+k]
∑
0≤k≤j/2
(−1)k
(
j − 1− k
k
)
(t− 1)k−2N−1
= 3
( 4
27
)N
(−1)N−j
∑
0≤k≤j/2
(
j − 1− k
k
)(
k − 2N − 1
N − j + k
)
.
H. Prodinger: An online bin-packing problem with an underlying ternary structure 7
We put all the results of this section together in a theorem.
Theorem 2.1. The generating function F (u) = F (u, z) has the following explicit form:
F (u) =
1
(1− 3t)(1− t)
(
1− 9
2
t(t− 1)U
) 1
(1− σU)(1− τU)
Here, u = zU , z3 = x = 274 t(1− t)
2, and
σ =
3
4
(t−
√
4t− 3t2 ), τ = 3
4
(t+
√
4t− 3t2 ).
Note that (1 − σU)(1 − τU) = 1 − 32 tU +
9
4 t(t − 1)U
2. Written in the new variable U ,
only powers of z that are multiples of 3 appear. Further, we get the representation sorted
by powers of u:
F (u, z) =
1
(1− 3t)(1− t)
∑
m≥0
um
zm
(3
2
)m ∑
0≤k≤m/2
(−1)k
(
m− k
k
)
(t− 1)ktm−k
− 3
(1− 3t)(1− t)
∑
m≥0
um
zm
(3
2
)m ∑
0≤k≤(m−1)/2
(−1)k
(
m− 1− k
k
)
(t− 1)k+1tm−k.
Reading off coefficients of zNuj , where N = n+j3 leads to
[zNuj ]F (u, z) =
( 4
27
)N
(−1)N−j
∑
0≤k≤j/2
(
j − k
k
)(
k − 2N − 2
N − j + k
)
− 3
( 4
27
)N
(−1)N−j
∑
0≤k≤(j−1)/2
(
j − 1− k
k
)(
k − 2N − 1
N − j + k
)
.
For the special state β, the following series representation holds:
fβ(z) =
∑
n≥0
22n+1
33n+1
(
3n+ 1
n
)
z3n+1.
The computation for the special state was not shown yet:
[z3n+1]fβ =
2
3
[xn]
1
(1− t)(1− 3t)
=
2
3
1
2πi
∮
dx
xn+1
1
(1− t)(1− 3t)
=
2
3
27
4
1
2πi
∮
dt
( 274 )
n+1tn+1(1− t)2n+2
=
2
3
( 4
27
)n 1
2πi
∮
dt
tn+1(1− t)2n+2
=
2
3
( 4
27
)n
[tn]
1
(1− t)2n+2
=
22n+1
33n+1
(
3n+ 1
n
)
.
3 The dual model
Now, the red edges mean the arrival of the large objects (size 23 ) and the black edges mean a
double-pack of the small edges (size 13 each). To keep the system balanced, the large objects
should arrive twice as often as the double-packs of small edges. Again, the generating
8 Ars Math. Contemp. 24 (2024) #P3.03
function gi refers to paths of length n leading eventually into state i. After n steps, only
a state i can be reached with n ≡ i mod 3. The state diagram and the recursions are
immediate:
0 1 2 3 4 5 6 7 8
β
We work only with p = 23 , q =
1
3 . Directly from the state diagram,
g0 = 1 + zgβ + qzg2 = 1 + qz
2g1 + qzg2,
gβ = qzg1, g1 = zg0 + qzg3,
gi = pzgi−1 + qzgi+2, i ≥ 2.
Summing the recursions,
G(u) =
∑
i≥0
uigi(z) = g0 + ug1 +
∑
i≥2
ui
(
pzgi−1 + qzgi+2
)
= g0 + uzg0 + qzug3 + pzu
∑
i≥1
uigi +
qz
u2
∑
i≥4
uigi
= g0 + uzg0 + pzuG(u)− pzug0 +
qz
u2
∑
i≥3
uigi
= g0 + uzg0 + pzuG(u)− pzug0 +
qz
u2
(G(u)− g0 − ug1 − u2g2)
= g0 + quzg0 + pzuG(u) +
qz
u2
G(u)− qz
u2
g0 −
qz
u
g1 − qzg2
= g0 + quzg0 + pzuG(u) +
qz
u2
G(u)− qz
u2
g0 −
qz
u
g1 + 1 + qz
2g1 − g0.
Solving, we find with V = uz:
G(u) =
−V 3g0 − 3V 2 − g1V 2z2 + z3g0 + g1V z2
2V 3 − 3V 2 + x
.
Now we factorize the denominator, using the same substitutions x = z3 and x = 274 t(1 −
t)2:
2(V − 32 (1− t))(V − σ)(V − τ) = 2V
3 − 3V 2 + x.
This time, both, (V −σ) and (V − τ) are bad factors. Plugging into the numerator, we find
two equations, and the solutions:
g0 =
4
(1− 3t)(4− 3t)
, g1 =
27t(1− t)
z2(1− 3t)(4− 3t)
.
It can be noted that Ṽ := V −1, with the denominator of the previous section; thus, the
three roots carry over. Dividing out the bad factors, we find
−V 3g0 − 3V 2 − g1V 2z2 + z3g0 + g1V z2
(V − σ)(V − τ)
=
12(t− 1)− 4V
(1− 3t)(4− 3t)
.
H. Prodinger: An online bin-packing problem with an underlying ternary structure 9
Altogether:
G(u) =
6(t− 1)− 2V
(1− 3t)(4− 3t)
1
V − 32 (1− t)
=
6(1− t) + 2V
(1− 3t)(4− 3t) 32 (1− t)
1
1− 23(1−t)V
= 2
2 + 23(1−t)V
(1− 3t)(4− 3t)
1
1− 23(1−t)V
.
Furthermore
[V j ]G(u) =
2
(1− 3t)(4− 3t)
[
2
(2
3
1
1− t
)j
+
(2
3
1
1− t
)j]
=
6
(1− 3t)(4− 3t)
(2
3
1
1− t
)j
, j ≥ 1,
and
[uj ]G(u) = zj
6
(1− 3t)(4− 3t)
(2
3
1
1− t
)j
.
Now let us consider j + 3N steps to reach state j, and then
[zj+3Nuj ]G(u) = [xN ]
6
(1− 3t)(4− 3t)
(2
3
1
1− t
)j
=
1
2πi
∮
dx
xN+1
6
(1− 3t)(4− 3t)
(2
3
1
1− t
)j
=
27
4
( 4
27
)N+1 1
2πi
∮
dt(1− t)(1− 3t)
tN+1(1− t)2N+2
6
(1− 3t)(4− 3t)
(2
3
1
1− t
)j
=
( 4
27
)N(2
3
)j 1
2πi
∮
dt
tN+1(1− t)2N+j+1
6
(4− 3t)
=
( 4
27
)N(2
3
)j−1
[tN ]
1
(1− t)2N+j+1
1
(1− 34 t)
=
( 4
27
)N(2
3
)j−1 N∑
i=0
(3
4
)N−i(2N + j + i
i
)
=
N∑
i=0
22i+j−1
32N+i+j−1
(
2N + j + i
i
)
.
The coefficients of g0 are different:
[z3N ]g0 =
N∑
i=0
22i
32N+i
(
2N + i
i
)
.
Furthermore,
[z3N+1]gβ =
1
3
[z3N ]g1 =
N∑
i=0
22i
32N+i+1
(
2N + 1 + i
i
)
.
Here are the main results of this section:
10 Ars Math. Contemp. 24 (2024) #P3.03
Theorem 3.1. The generating function G(u) = G(u, z) has the following explicit form:
G(u) = 2
2 + 23(1−t)V
(1− 3t)(4− 3t)
1
1− 23(1−t)V
.
Here, u = Vz , z
3 = x = 274 t(1− t)
2. Written in the new variable V , only powers of z that
are multiples of 3 appear. Further, we get the representation sorted by powers of u:
[V j ]G(u) =
6
(1− 3t)(4− 3t)
(2
3
1
1− t
)j
, j ≥ 1,
and
[uj ]G(u) = zj
6
(1− 3t)(4− 3t)
(2
3
1
1− t
)j
.
Reading off coefficients of zj+3Nuj leads to
[zj+3Nuj ]G(u, z) =
N∑
i=0
22i+j−1
32N+i+j−1
(
2N + j + i
i
)
.
For the special cases, the following series representation holds:
[z3N ]g0 =
N∑
i=0
22i
32N+i
(
2N + i
i
)
,
[z3N+1]gβ =
1
3
[z3N ]g1 =
N∑
i=0
22i
32N+i+1
(
2N + 1 + i
i
)
.
ORCID iDs
Helmut Prodinger https://orcid.org/0000-0002-0009-8015
References
[1] M. Drmota, Discrete random walks on one-sided “periodic” graphs, in: Discrete Random
Walks, DRW’03. Proceedings of the conference, Paris, France, September 1–5, 2003, Maison
de l’Informatique et des Mathématiques Discrètes (MIMD), Paris, pp. 83–94, 2003.
[2] H. W. Gould, The Girard-Waring power sum formulas for symmetric functions and Fibonacci
sequences, Fibonacci Q. 37 (1999), 135–140, https://www.fq.math.ca/37-2.html.
[3] W. Knödel, Über das mittlere verhalten von online-packungsalgorithmen, Elektron. Informa-
tionsverarb. Kybernetik 19 (1983), 427–433.
[4] H. Prodinger, The kernel method: a collection of examples, Sémin. Lothar. Comb. 50 (2003),
b50f, 19 pp.
[5] H. Prodinger, Enumeration of S-Motzkin paths from left to right and from right to left: a kernel
method approach, PU.M.A., Pure Math. Appl. 29 (2020), 28–38, doi:10.1515/puma-2015-0039,
https://doi.org/10.1515/puma-2015-0039.
H. Prodinger: An online bin-packing problem with an underlying ternary structure 11
[6] H. Prodinger, S. J. Selkirk and S. Wagner, On two subclasses of Motzkin paths and their relation
to ternary trees, in: Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions
and Computer Algebra, Springer, Cham, pp. 297–316, 2020, doi:10.1007/978-3-030-44559-1
15, https://doi.org/10.1007/978-3-030-44559-1_15.