# An experience in automatically extracting CAPAs from code repositories

1st Yegor Bugayenko  Huawei
Moscow, Russia
<EMAIL_ADDRESS>2nd Imre Delgado  Innopolis University
Innopolis, Russia
<EMAIL_ADDRESS>3rd Firas Jolha  Innopolis University
Innopolis, Russia
<EMAIL_ADDRESS>4th Zamira Kholmatova  5th Artem Kruglov
Innopolis University
Innopolis, Russia
<EMAIL_ADDRESS>Innopolis University
Innopolis, Russia
<EMAIL_ADDRESS>6th Witold Pedrycz  University of Alberta
Edmonton, Canada
<EMAIL_ADDRESS>7th Giancarlo Succi  University of Bologna
Bologna, Italy
<EMAIL_ADDRESS>7th Xavier Vasquez  Innopolis University
Innopolis, Russia
<EMAIL_ADDRESS>
###### Abstract

TOM (stands for Theoretically Objective Measurements of Software Development
Projects) is a set of services that are in charge of helping developers or
teams in the process of identifying anomilies within their software
development process, and providing a list of preventive or corrective actions
(aka CAPAS) that positively impact the process. and in this way to improve the
quality of the final product and its development process.

In order to get help from TOM, it is as simple as adding our bot (@0capa) to
the list of collaborators in your repository, and with this our bot will
automatically take care of obtaining different metrics from your repository,
in order to suggest actions to take into account to that in your future
updates the identified anomalies are not repeated.

This paper presents the underlying research on this idea.

###### Index Terms:

Anomaly, Metrics, Commits, Prediction, Classification, Actions, Software
Quality, Management, Issues

##  I Introduction

We have been struggling with understanding the evolution of software projects
for several years, in particular it is difficult to understand reasons and
means of changes in code. We focus on this paper in how we can interpret
information present in code repositories to determine the intended corrective
and preventive maintenance actions performed by developers on the code.

The work is intended primarily to large organizations, featuring tens of
thousands of developers or more, like Huawei, Microsoft, etc., and, indeed the
overall world community of open source software development, which is actually
the empirical tested for this study.

Software engineering is difficult and that despite now several decades of
research, still most of the projects fail: according to The Standish Group
less than 30% of the projects can be considered successful, a percentage that
has remained practically constant in the previous five years. Moreover, for
the large projects the success rate is just above 10% [23]. All these
percentages should horrify project managers and key stakeholders of software
development enterprises.

The proposed solutions appears to be monotonic: better process, better
management, and more recently, more agility. To many it appears that it is
only a matter of intensity and of higher discipline in adhering to protocols,
and even reading more recent articles [15] we do not see a really change of
perspective. Even if a plethora of alternative development processes have
appeared, it appears that the intrinsic combinatorial complexity of all the
factors determining how approach the wicked problems during software
development process are completely ignored [19].

In a sense this is quite surprising, as from the ’70s there was a large
discussion of using expert systems in management [7] and the matter was
already discussed by [18], when they suggested to use AI, and, specifically,
expert systems to manage the complexity of software projects. This idea went
forward till the early 2000 with various favours and contributions [24], a
focus on effort estimation [9], and also using case based reasoning [10] and
neural networks [11]. Their idea suffered from the relative inability of
expert systems to be accepted by the general industry [5] and by the
difficulty to formalize the problems of software management in terms of
explicit knowledge.

The problem was then tackled from a different perspective by the work of [20]
and the one by [21]; in these cases instead of a predefined set of expert
rules, the idea was to provide an advice at runtime based on features that
were being emerged by developing the project. This approach was strongly
influenced by the emerging of the Agile approach, which centered the process
in the developer [1] with the acknowledgment that software is the result of
the creative act of the human mind.

The scientific background and justification provide a basis to perform a
significant move forward in the discipline, by elaborating mechanisms from
data mining [17] and machine learning [12] approaches that could retrieve the
artifacts being produced by teams throughout the software development process,
parse them, and compare them with previously developed ones, thereby
identifying areas for improvements and suggesting best practices. Thus, the
main research question to be answered in this research is: how measurable
properties (metrics) of project digital artifacts can be attributed to
suggestions of corrective and preventive actions (CAPAs), in order to have a
positive effect.

The contribution of this research is the software agent and the model which
provide specific recommendations in form of CAPAs based on the current state
of a software development project.

The paper is structured as following. In Section II we observe the researches
conducted in the area. Section III presents the idea of the research at a
high-level perspective, which further disclosed in Section IV, Section V and
Section VI. The description of the software that implements the developed
model is given in Section VII. The conclusions on the work done are given in
Section VIII.

##  II Related Work

A number of researchers in the software engineering community, intending to
prevent project failures, proposed a variety of solutions aimed at improving
both management [22] and process [16]. However, it is very difficult to choose
a suitable management style or process because of the existence of a variety
of factors that lead to software project failure, such as management style
[3], stakeholders involvement [4], team [13], etc. Based on the critical
analysis of 70 different recorded failed projects, [25] observed that for each
of them, there is a wide spectrum of circumstantial factors (such as
environmental and psychological ones) that could be considered the root causes
of failures [13]. It, therefore, seems that there is a strong need for
objective and universal assessments of software projects, which could be
achieved through the usage of metrics. The possibility of providing “genuinely
improved management decision support systems” based on the adoption of
specific software metrics has already been established [8, 6, 2].

Other researchers, such as [14], identified several management areas where
artificial intelligent technologies or techniques could be applied. These
include:  1. estimation of project success;  2. identification of critical
success factors;  3. relatedness to project budget;  4. connection to projects
schedule;  5. project planning;  6. relatedness to risk identification.

Yet, there is no item on this list that suggests actions that could be taken
to prevent failures. However, [26] attempted to specify the relationship
between software metrics and corrective and preventive actions.

The preliminary work we done in this subject area is related to the formation
of an objective list of possible CAPAs. For this purpose we performed the
analysis of the most popular project management frameworks, guides and
standards to the software engineering and IT project management:  1. Control
Objectives for Information and related Technology (COBIT),  2. Information
Technology Infrastructure Library (ITIL),  3. Capability Maturity Model
Integration (CMMI),  4. The Guide to the Software Engineering Body of
Knowledge (SWEBOK), and  5. The Open Group Architecture Framework (TOGAF).
Based on expert evaluation of the applicability of these information sources,
we chose CMMI for extraction of CAPAs relevant to the software development
process. The resulted set of 766 derived CAPAs is available to our readers in
the GitHub repository for further analysis.

##  III Research workflow

The development of the model for theoretically objective measurements (TOM) a
number of consecutive tasks must be solved. Thus, the general algorithm of the
model can be represented as the following steps:

  1. Step 1.

A repository can be uniquely described by a multidimensional time series of
specific metrics $T\in\mathbb{R}^{m\times n}$, where $n$ is the number of
commits in the repository (or days of project life) and $m$ is the number of
metrics. The task at the first step is to identify a minimum set
$X=\\{x_{1},x_{2},\dots,x_{m}\\}$ of $m$ metrics that can comprehensively
enough describe the status of the software project.

  2. Step 2.

Given a set of $m$ univariate time series of selected metrics
$T_{A}=\\{T^{(1)},T^{(2)},\dots,T^{(m)}\\}$, we are looking for set of
patterns $P=\\{T_{i,j}^{(1)},\dots,T_{i,j}^{(n)}\\}$ whereby by $T_{i,j}$ is
observed in $k$ time series belonging to $T_{A}$ and $i<j$. The pattern
$T_{i,j}$ should appear not less than $a$ times and also not more than $b$
times in each of the $m$ univariate series.

Once we identified such sets $\sum_{i=0}^{N}P_{i}$ for N repositories, we can
look for similar patterns across repositories using Z-Normalized Euclidean
Distance.

The outcome of this step is a catalogue of patterns
$\hat{P}=\\{\hat{p}_{1},\hat{p}_{2},\dots,\hat{p}_{l}\\},l\leq k$ repetitive
across a number of repositories.

  3. Step 3.

After detecting a pattern we need to find the corrective action associated
with it. In software repositories, any corrective action $c$ takes the form of
a pull request. By extracting and analyzing the $m$ metrics of these $\hat{p}$
pull requests following the time of the given anomaly we can assign to every
row $x_{i}\in X\in\mathbb{R}^{\hat{p}\times m}$ its respective corrective or
preventive action (CAPA) $c_{k}$, leading to groups of pull requests according
to their respective CAPAs. Moreover, we can use the data of the relevant issue
— its open and close times — to define more precisely the time range for the
search.

The outcome of this step should be the set of tuples
$PC=\\{\\{\hat{p}_{1},c_{1}\\},\\{\hat{p}_{2},c_{2}\\},\dots,\\{\hat{p}_{n},c_{n}\\}\\}$
for $n\leq l$ which represent pairs of pattern $\hat{p}$ and related CAPA $c$.

  4. Step 4.

To understand whether the obtained relation between pattern and CAPA is not
due to the randomness is the analysis of statistical distribution for each
pair pattern-CAPA.

The resulted outcome of the whole methodology is a set
$\sum_{i=0}^{N}\\{\hat{p}_{i},c_{i}\\}$ with statistically significant
pairwise relationship between elements.

##  IV Pattern Recognition

By analysing the GitHub API we identified three metrics which could be
collected for each commit and describe the “most” of the variance in the code:
1. total lines added,  2. total lines deleted, and  3. total lines changed.

We visually observed similarly shaped and repetitive figures in the diagrams
of these metrics. We called them “patterns” and developed a method for
automatically detecting them. The method has a few configuration parameters:
a) the minimum percentage of repositories where a pattern must be seen,  b)
the minimum and the maximum length of the pattern in data points,  c) the
minimum and the maximum amount of times a pattern must be seen in a
repository, and  d) the minimum required Z-Normalized Euclidean Distance as a
characteristic of similarity between all occurrences of a pattern.

The overall proposed algorithm for finding patterns of interest is presented
in Algorithm 1. The algorithm for pattern retrieval is available here.

Algorithm 1 Matrix Profile Approach

0: $\gamma$ \- set of time series , $p$ \- maximum number of repositories to
contain consensus pattern, $z$ \- minimum number of times a consensus pattern
is seen in each time series

0: R \- set of consensus subsequences

1: $\textbf{R}\leftarrow\emptyset$

2: for all $m\in[d,e]$ do

3: $k\leftarrow 0$

4: $T_{a,m}\leftarrow$ consensus subsequence of length $m$

5: for all $T\in\gamma$ do

6: $tmatches\leftarrow$number of pattern matches $T_{a,m}$ in $T$

7: if $tmatches>z$ then

8: $k\leftarrow k+1$

9: end if

10: end for

11: if $k<p$ then

12: add $T_{a,m}$ to $R$

13: end if

14: end for

We tested the proposed solution on the dataset of 1000 repositories and found
30 patterns of different types. The visualized example of a pattern is given
in Figure 1. The patterns found are available here.

Figure 1: Sample repository represented by time series of lines removed and
its corresponding patterns found using algorithm 1. The red color highlights
the patterns matching the consensus pattern

##  V CAPA Categorization

It is a common practice in GitHub to make changes to repositories through pull
requests (PR), which are reviewed by other contributors and then merged. We
assumed that PRs are not homogeneous: most often they fix bugs and implement
features, while sometimes they improve the entire code base. We assumed that
the latter may be classified as CAPAs and created an automated ML-based method
of such classification. Using GitHub Search API and special keywords for each
action, we found 10629 PRs (see Table I). Using GitHub API, for each PR we
collected 56 metrics and then, after a number of iterations, refined and
reduced the list down to 27 metrics (see Table II).

TABLE I: Size of train and test datasets for classification of pull requests into CAPAs and non-CAPAs. category | train | test
---|---|---
CAPAs | 4743 | 1184
non-CAPAs | 5886 | 1474
Total | 10629 | 2658
TABLE II: Data Type # |  metric | data type
---|---|---
1 |  number of comments | numeric
2 |  number of commits | numeric
3 |  number of files | numeric
4 |  number of issue comments | numeric
5 |  number of issue events | numeric
6 |  number of labels | numeric
7 |  number of review comments | numeric
8 |  number of review requests | numeric
9 |  number of reviewers | numeric
10 |  number of additions | numeric
11 |  closure date | timestamp
12 |  creation date | timestamp
13 |  number of deletions | numeric
14 |  locked state | boolean
15 |  merged state | boolean
16 |  merged date | timestamp
17 |  milestone status | boolean
18 |  milestone closure date | timestamp
19 |  number of milestone closed issues | numeric
20 |  milestone creation date | timestamp
21 |  milestone due on date | timestamp
22 |  milestone state | boolean
23 |  pull request number | numeric
24 |  pull request state | boolean
25 |  update date | timestamp
26 |  number of participants | numeric
27 |  number of file changes | numeric

We conducted series of experiments using three classification models. A Random
Forest Classifier (RFC) with 500 estimators, an XGBoost Classifier (XBC) also
500 estimators, and a CatBoost Classifier (CBC) with a learning rate of 0.1,
and 500 iteration steps. The experiments were performed on the dataset using a
ratio of 80% and 20% for the train and test sets, respectively.

First, we classified PRs into CAPAs and non-CAPAs (see Table III). Second, for
the selected PRs we classified them to one of the possible actions (see Table
IV).

TABLE III: Report of the first step of classification. Three models are compared: Random Forest Classifier (RFC), XGBoost Classifier (XBC), and CatBoost Classifier (CBC). Classes are labeled as: 1—CAPA category, 2—non-CAPA category. label |  model | TP | TN | FP | FN | PRE | REC | F1
---|---|---|---|---|---|---|---|---
1 |  RFC | 1174 | 1380 | 94 | 10 | 0.93 | 0.99 | 0.96
|  XBC | 1177 | 1378 | 96 | 7 | 0.92 | 0.99 | 0.96
|  CBC | 1169 | 1386 | 88 | 15 | 0.93 | 0.99 | 0.96
2 |  RFC | 1380 | 1174 | 10 | 94 | 0.99 | 0.94 | 0.96
|  XBC | 1378 | 1177 | 7 | 96 | 0.99 | 0.93 | 0.96
|  CBC | 1386 | 1169 | 15 | 88 | 0.99 | 0.94 | 0.96
TABLE IV: Report of the second step of classification. Each class is labeled as: 1—add linter, 2—coverage, 3—documentation, 4—functional requirements, 5—refactoring, 6—unstable build, 7—unused. label |  model | TP | TN | FP | FN | PRE | REC | F1
---|---|---|---|---|---|---|---|---
1 |  RFC | 182 | 1187 | 10 | 21 | 0.95 | 0.9 | 0.92
|  XBC | 176 | 1180 | 17 | 27 | 0.91 | 0.87 | 0.89
|  CBC | 169 | 1176 | 21 | 34 | 0.89 | 0.83 | 0.86
2 |  RFC | 184 | 1128 | 48 | 40 | 0.79 | 0.82 | 0.81
|  XBC | 152 | 1129 | 47 | 72 | 0.76 | 0.68 | 0.72
|  CBC | 160 | 1114 | 62 | 64 | 0.72 | 0.71 | 0.72
3 |  RFC | 150 | 1183 | 39 | 28 | 0.79 | 0.84 | 0.82
|  XBC | 125 | 1152 | 70 | 53 | 0.64 | 0.7 | 0.67
|  CBC | 117 | 1164 | 58 | 61 | 0.67 | 0.66 | 0.66
4 |  RFC | 200 | 1180 | 5 | 15 | 0.98 | 0.93 | 0.95
|  XBC | 202 | 1176 | 9 | 13 | 0.96 | 0.94 | 0.95
|  CBC | 194 | 1172 | 13 | 21 | 0.94 | 0.9 | 0.92
5 |  RFC | 169 | 1187 | 30 | 14 | 0.85 | 0.92 | 0.88
|  XBC | 160 | 1154 | 63 | 23 | 0.72 | 0.87 | 0.79
|  CBC | 160 | 1154 | 63 | 23 | 0.72 | 0.87 | 0.79
6 |  RFC | 197 | 1174 | 15 | 14 | 0.93 | 0.93 | 0.93
|  XBC | 180 | 1164 | 25 | 31 | 0.88 | 0.85 | 0.87
|  CBC | 178 | 1159 | 30 | 33 | 0.86 | 0.84 | 0.85
7 |  RFC | 160 | 1203 | 11 | 26 | 0.94 | 0.86 | 0.9
|  XBC | 148 | 1188 | 26 | 38 | 0.85 | 0.8 | 0.82
|  CBC | 147 | 1186 | 28 | 39 | 0.84 | 0.79 | 0.81

The average demonstrated accuracy is 83%. The model is available here. The
data used for training and testing is here.

##  VI Validation of the Results

For each instance of identified patterns, we scanned the corresponding
repository for a pull request during the time period when the pattern occurred
plus one month. This decision is dictated by the fact that the potential
corrective action is not performed immediately after the associated pattern
occurs, but after some time. At the end, we identified 217 pull requests which
then were categorized as specific CAPAs.

Our hypothesis is that there is a causality between some patterns and CAPAs.
To prove it we need to test the statistical significance of the dependency
between sets of detected patterns and CAPAs occurred nearby. All cases where
the PR identified as a particular CAPA was created between the beginning of a
particular pattern and one month after its end are shown in the Table V

TABLE V: Number of CAPAs that occurred in close proximity to the identified patterns Pattern type | CAPA
---|---
0 |  1 |  2 |  3 |  4 |  5 |  6 |  Total
Pattern 5 |  6 |  2 |  5 |  4 |  0 |  3 |  0 |  20
Pattern 6 |  2 |  2 |  1 |  1 |  0 |  0 |  0 |  6
Pattern 7 |  2 |  0 |  6 |  2 |  0 |  3 |  0 |  13
Pattern 8 |  4 |  3 |  4 |  0 |  0 |  0 |  1 |  12
Pattern 9 |  3 |  6 |  7 |  1 |  1 |  2 |  1 |  21
Pattern 10 |  3 |  6 |  5 |  0 |  3 |  2 |  1 |  20
Pattern 11 |  0 |  9 |  9 |  0 |  0 |  11 |  2 |  31
Pattern 12 |  8 |  7 |  19 |  0 |  0 |  6 |  3 |  43
Pattern 13 |  8 |  6 |  3 |  1 |  1 |  4 |  0 |  23
Pattern 14 |  1 |  8 |  10 |  1 |  1 |  4 |  3 |  28
Total |  37 |  49 |  69 |  10 |  6 |  35 |  11 |  217

We ran Chi-squared test of independence to check whether there is a
relationship between patterns and CAPAs. Our null hypothesis was that there is
no relationship between patterns and CAPA, With the obtained p-value 0.0085 we
can reject the null hypothesis with a level of significance alpha 0.05a one-
sample t-test to check the dependency between patterns and CAPAs. The result
of experiment showed the presence of dependence with p-value 0.0085.

For each type of pattern we empirically determined the rule for the CAPAs to
be considered as potentially relevant to it as at least five time of
occurrences. Then for the filtered tuples pattern-CAPA we performed a pairwise
comparison to understand whether the specific CAPA has a significantly higher
probability of belonging to the given pattern. Table VI shows the results of
this experimentinvestigation. For example, the first row represents the
investigation of the following null hypothesis: the mean value of probability
that CAPA 0 belongs to Pattern 5 is equal to the mean value of probability
that CAPA 2 belongs to Pattern 5. While testing the hypothesis, we got p-value
equal to 0.136. If we consider the level of significance 0.05, the null
hypotheses cannot be rejected.

TABLE VI: Pairwise comparison of the CAPAs with 2-sample t-test Pattern type |  (I) Spot |  (J) Spot |  Mean value I |  Mean value J |  p-value
---|---|---|---|---|---
Pattern 5 |  CAPA 0 |  CAPA 2 |  0.7 |  0.54 |  0.136
Pattern 9 |  CAPA 1 |  CAPA 2 |  0.48 |  0.46 |  0.806
Pattern 10 |  CAPA 1 |  CAPA 2 |  0.54 |  0.48 |  0.512
Pattern 11 |  CAPA 1 |  CAPA 2 |  0.63 |  0.43 |  0.003
CAPA 1 |  CAPA 5 |  0.63 |  0.45 |  0.006
CAPA 2 |  CAPA 5 |  0.43 |  0.45 |  0.71
Pattern 12 |  CAPA 0 |  CAPA 1 |  0.94 |  0.67 |  0.001
CAPA 0 |  CAPA 2 |  0.94 |  0.48 |  $2.6\cdot e^{-8}$
CAPA 0 |  CAPA 5 |  0.94 |  0.48 |  $3.5\cdot e^{-5}$
CAPA 1 |  CAPA 2 |  0.67 |  0.48 |  0.007
CAPA 1 |  CAPA 5 |  0.67 |  0.48 |  0.021
CAPA 2 |  CAPA 5 |  0.48 |  0.48 |  0.93
Pattern 13 |  CAPA 0 |  CAPA 1 |  0.73 |  0.55 |  0.112
Pattern 14 |  CAPA 1 |  CAPA 2 |  0.7 |  0.54 |  0.004

As a result of the analysis, we showed a statistically significant
relationship between certain patterns and CAPAs. By choosing a acceptable
level of significance, we can determine the final set of patterns-CAPA. Thus,
for the significance level 0.15, the output of the whole experiment is a
dictionary of the following tuples pattern-CAPA:

$\begin{gathered}(Pattern\ 5\rightarrow CAPA\ 0),\\\ (Pattern\ 11\rightarrow
CAPA\ 1),\\\ (Pattern\ 12\rightarrow CAPA\ 0),\\\ (Pattern\ 13\rightarrow
CAPA\ 0),\\\ (Pattern\ 14\rightarrow CAPA\ 1).\end{gathered}$

##  VII Implementation

In order to automate of the data collection and processing process, a system
was developed that is described below.

Given the needs of the system, a system was proposed that is composed of 3
modules mainly (see Figure 2), where the first of them is in charge of
integrating and monitoring the different sources of information, carrying out
an initial implementation to integrate GitHub, this particular component will
be called “TOM-Radar”.

The next of the developed components is the one in charge of processing the
collected data, relying on the model that was described in Section III, an ML
module was developed, which is capable of taking the different metrics
collected by the radar and produce a set anomalies.

Finally, to complete the system, a module was developed that is in charge of
notifying the teams about the different anomalies found, in a way that CAPAS
can propose to solve the incidents detected.

Figure 2: System Architecture - High level view

Now, diving deeper in the modules’ implementation, we can realize that both 3
modules (see Figure 3) have been designed following a similar pattern, since
for all of them we want to meet similar non-functional requirements. So that,
taking into consideration that one of the main drivers is the flexibility of
the system to be able to be integrated into multiple data sources, implement
different processing models and, in the same way, be able to integrate with
different ticket tracking systems.

Figure 3: System Architecture - components view

Regarding the implementation of the TOM-Radar module, in the picture Figure 4,
we can see that it is a quite simple but quite functional design, where given
the need to be able to generate different instances of the radars, an instance
factory has been implemented that depending on the load of the system can
dispatch them as needed, then looking at the details of the radar itself, we
see that we have defined the methods necessary to complete the data collection
cycle, which must be implemented in each type of radar that you want to
incorporate.

Where we find methods to initialize the radar, in which basically the radar
configurations are loaded and the state is updated to control the concurrence
of the different instances, in addition to this, we see another method that is
responsible for monitoring if the system has received permissions to monitor
new repositories or projects, to be able to add them to the processing queue
and a third method that takes care of data collection per se.

And as a control measure, two methods were added to be able to start and stop
the radar activity, in this way the steps described above are executed
periodically and unattended. Seeing this level of detail, it is worth
mentioning that both the ML advisor and the chat-bot have a similar design,
with an instance factory and a clearly defined template for integration with
new external systems.

The developed software is available here.

Figure 4: System Architecture - radar implementation

##  VIII Conclusion

In this research we have demonstrated the idea of managing the software
development process through theoretically objective measurement. We performed
the post-mortem analysis of more than 1000 repositories to identify the
typical characteristic situations in development process, which we called
patterns. Also, we analyzed more than 10000 pull requests to create a model
for their classification into specific corrective and preventive actions.
After it, we identified the tuples pattern-CAPA which have statistically
significant dependency.

This research could be considered as a spike solution to what we can call
automatic monitoring and management of software development projects. It
demonstrates the overall concept, however, to make the solution effective we
need to expand the CAPA set, add pattern retrieval from multivariate time
series, and increase the number of analyzed repositories to tens of thousands.

## References

  * [1] Kent Beck and Cynthia Andres  “Extreme Programming Explained: Embrace Change (2nd Edition)”  Boston: Addison-Wesley Professional, 2004  URL: http://portal.acm.org/citation.cfm?id=1076267
  * [2] Guru Prasad Bhandari and Ratneshwer Gupta  “Measuring the Fault Predictability of Software Using Deep Learning Techniques with Software Metrics”  In _Proceedings of the 2018 5th IEEE Uttar Pradesh Section International Conference on Electrical, Electronics and Computer Engineering (UPCON)_ , 2018, pp. 1–6  IEEE  DOI: 10.1109/UPCON.2018.8597154
  * [3] Narciso Cerpa and June M. Verner  “Why Did Your Project Fail?”  In _Communications of the ACM_ 52.12 New York, NY, USA: Association for Computing Machinery, 2009, pp. 130–134  DOI: 10.1145/1610252.1610286
  * [4] Robert N. Charette  “Why Software Fails [Software Failure]”  In _IEEE Spectrum_ 42.9 IEEE, 2005, pp. 42–49  DOI: 10.1109/MSPEC.2005.1502528
  * [5] Peter Duchessi and Robert M. O’Keefe  “Understanding expert systems success and failure”  In _Expert Systems with Applications_ 9.2 Elsevier BV, 1995, pp. 123–133  DOI: 10.1016/0957-4174(94)00056-2
  * [6] Khaled El Emam, Walcelio Melo and Javam C. Machado  “The Prediction of Faulty Classes Using Object-oriented Design Metrics”  In _Journal of Systems and Software_ 56.1 USA: Elsevier Science Inc., 2001, pp. 63–75  DOI: 10.1016/S0164-1212(00)00086-8
  * [7] Sean B. Eom, Sang M. Lee and Ahmed Ayaz  “Expert systems applications development research in business: A selected bibliography (1975–1989)”  In _European Journal of Operational Research_ 68.2 Elsevier BV, 1993, pp. 278–290  DOI: 10.1016/0377-2217(93)90309-b
  * [8] Norman E. Fenton and Martin Neil  “Software Metrics: Successes, Failures and New Directions”  In _Journal of Systems and Software_ 47.2-3 USA: Elsevier Science Inc., 1999, pp. 149–157  DOI: 10.1016/S0164-1212(99)00035-7
  * [9] G.R. Finnie and G.E. Wittig  “AI tools for software development effort estimation”  In _Proceedings 1996 International Conference Software Engineering: Education and Practice_ IEEE Comput. Soc. Press, 1996  DOI: 10.1109/seep.1996.534020
  * [10] K. Ganesan, Taghi M. Khoshgoftaar and Edward B. Allen  “Case-based Software Quality Prediction”  In _International Journal of Software Engineering and Knowledge Engineering_ 10.02 World Scientific Pub Co Pte Lt, 2000, pp. 139–152  DOI: 10.1142/s0218194000000092
  * [11] Eung Sup Jun and Jae Kyu Lee  “Quasi-optimal case-selective neural network model for software effort estimation”  In _Expert Systems with Applications_ 21.1 Elsevier BV, 2001, pp. 1–14  DOI: 10.1016/s0957-4174(01)00021-5
  * [12] Wolfgang Kratsch, Jonas Manderscheid, Maximilian Röglinger and Johannes Seyfried  “Machine Learning in Business Process Monitoring: A Comparison of Deep Learning and Classical Approaches Used for Outcome Prediction”  In _Business & Information Systems Engineering_ 63.3 Springer ScienceBusiness Media LLC, 2020, pp. 261–276  DOI: 10.1007/s12599-020-00645-0
  * [13] Timo O.A. Lehtinen et al.  “Perceived Causes of Software Project Failures–an Analysis of Their Relationships”  In _Information and Software Technology_ 56.6 Elsevier, 2014, pp. 623–643  DOI: https://doi.org/10.1016/j.infsof.2014.01.015
  * [14] Daniel Magaña Martínez and Juan Carlos Fernandez-Rodriguez  “Artificial Intelligence Applied to Project Success: A Literature Review”  In _International Journal of Interactive Multimedia and Artificial Intelligence_ 3.5, 2015, pp. 77–84
  * [15] Dana Miranda and Adam Hardy  “Core Project Management Methodologies—And How To Choose The One For You” https://www.forbes.com/advisor/business/project-management-methodologies/ – last visited $08^{th}$ of May, 2022, 2022
  * [16] Deependra Moitra  “Managing Organizational Change for Software Process Improvement”  In _Software Process Modeling_ Boston, MA: Springer US, 2005, pp. 163–185  DOI: 10.1007/0-387-24262-7˙7
  * [17] Gyunam Park and Wil M.. Aalst  “A General Framework for Action-Oriented Process Mining”  In _Business Process Management Workshops_ Springer International Publishing, 2020, pp. 206–218  DOI: 10.1007/978-3-030-66498-5˙16
  * [18] C.L. Ramsey and V.R. Basili  “An evaluation of expert systems for software engineering management”  In _IEEE Transactions on Software Engineering_ 15.6 Institute of ElectricalElectronics Engineers (IEEE), 1989, pp. 747–759  DOI: 10.1109/32.24728
  * [19] Horst W.. Rittel and Melvin M. Webber  “Dilemmas in a general theory of planning”  In _Policy Sciences_ 4.2 Springer ScienceBusiness Media LLC, 1973, pp. 155–169  DOI: 10.1007/bf01405730
  * [20] Jason E. Robbins, David M. Hilbert and David F. Redmiles  “Software architecture critics in Argo”  In _Proceedings of the 3rd international conference on Intelligent user interfaces - IUI ’98_ ACM Press, 1998  DOI: 10.1145/268389.268416
  * [21] Giancarlo Succi, Jason Yip, Eric Liu and Witold Pedrycz  “Holmes”  In _Proceedings of the 22nd international conference on Software engineering - ICSE ’00_ ACM Press, 2000  DOI: 10.1145/337180.337641
  * [22] Hamed Taherdoost  “How to Lead to Sustainable and Successful IT Project Management? Propose 5Ps Guideline”  In _Propose 5Ps Guideline (August 1, 2018)_ , 2018  eprint: https://dx.doi.org/10.2139/ssrn.3224225
  * [23] The Standish Group  “Chaos Report” https://www.standishgroup.com/sample_research_files/CHAOSReport2015-Final.pdf – last visited $08^{th}$ of May, 2022, 2015
  * [24] C. Vasudevan  “An experience-based approach to software project management”  In _Proceedings Sixth International Conference on Tools with Artificial Intelligence. TAI 94_ IEEE Comput. Soc. Press, 1994  DOI: 10.1109/tai.1994.346435
  * [25] June Verner, Jennifer Sampson and Narciso Cerpa  “What Factors Lead to Software Project Failure?”  In _Proceedings of the 2008 second international conference on research challenges in information science_ , 2008, pp. 71–80  IEEE  DOI: 10.1109/RCIS.2008.4632095
  * [26] Wayne M. Zage, Dolores M. Zage and Cathy Wilburn  “Avoiding Metric Monsters: A Design Metrics Approach”  In _Annals of Software Engineering_ 1.1 Springer, 1995, pp. 43–55  DOI: 10.1007/BF02249045


Sweet division problems: from chocolate bars to honeycomb strips and back

Tomislav Došlić

Faculty of Civil Engineering, University of Zagreb

Croatia, Zagreb 10000

Luka Podrug

Faculty of Civil Engineering, University of Zagreb

Croatia, Zagreb 10000

We consider two division problems on narrow strips of square and hexagonal
lattices. In both cases we compute the bivariate enumerating sequences and
the corresponding generating functions, which allowed us to determine
the asymptotic behavior of the total number of such subdivisions and the
expected number of parts. For the square lattice we extend results of two
recent references by establishing polynomiality of enumerating sequences
forming columns and diagonals of the triangular enumerating sequence.
In the hexagonal case, we find a number of new combinatorial interpretations
of the Fibonacci numbers and find combinatorial proofs of some Fibonacci
related identities. We also show how both cases could be treated via the
transfer matrix method and discuss some directions for future research.

§ INTRODUCTION

It has been a long standing problem of great practical importance to count the
ways of dividing a collection of entities into smaller sets according to a
given set of rules. If the entities are considered to be indivisible, and
we only care about their number, the natural framework for modeling such
situations is the theory of integer partitions and compositions, depending
on further properties of the considered entities. If, on the other hand,
we are interested in relationships between the entities, such as, e.g.,
their adjacency patterns or their relative positions, we must resort to
more complex models such as graphs and geometric figures.

In this paper we look at finite portions of the square and hexagonal
regular lattices, and count ways of dividing narrow strips in such lattices
into a given number of pieces while preserving integrity of individual
squares or hexagons. The considered portions of square and hexagonal lattices
remind us on chocolate bars and honeycomb slabs, respectively, hence the title.
We start by revisiting some partial results for narrow
strips in the square lattice available in the literature and present complete
solution to the problem. In particular, we derive the recurrences satisfied
by the sequences enumerating the divisions of a $2 \times n$ strip into
$k$ pieces. From them, we compute the bivariate generating function whose
univariate specialization yields the recurrence for the overall number of
divisions. In that way we recover the results of Knopfmacher obtained in
the context of compositions of ladder graphs [4]. We refine those
results by investigating behavior of columns in the enumerating triangle.
We establish
convolution-type recurrences for all columns, going thus beyond partial
results of references [2, 3, 6]. Then we apply the same approach
to narrow strips of hexagons, again deriving the recurrences and computing
the bivariate generating function. Along the way we find a new combinatorial
representation of odd-indexed Fibonacci numbers and provide a new combinatorial proof for one well-known identity for Fibonacci numbers. Then we show how the results for
honeycomb strips can be obtained by using transfer matrices. Finally, we also
derive transfer matrices for the chocolate bars we started from.

The paper is concluded by some remarks on the strong and weak points of
employed methods and with some indications of possible further directions.

§ DEFINITIONS AND PRELIMINARY RESULTS

Let $n$ be a non-negative integer. We consider a $2 \times n$ rectangular
strip consisting of $2n$ squares arranged in 2 rows and $n$ columns such as the one shown in Fig. <ref>. In the rest of the paper we will
often refer to such strips as to chocolate bars of length $n$. We consider
divisions of such structures into a given number of pieces obtained by
cutting along the edges of basic squares. More precisely, we would like to
find the number of all possible divisions of such a bar of a given length,
and also the number of such divisions into a given number of parts $k$.
Clearly, $1 \leq k \leq 2n$ are the only meaningful values of $k$. Let $r_k(n)$
denote the number of divisions of $2\times n$ rectangular strip into exactly
$k$ pieces and $r(n)$ the total number of divisions. From definition we have
that $r_k(n)=0$ for $ k < 0$ and for $k>2n$. The initial values are
$r_1(1)=r_2(1)=1$, and $r_1(2)=1$, $r_2(2)=6$, $r_3(2)=4$ and $r_1(4)=1$.

(M1) at (0,2);
(M2) at (2,2);
(M3) at (4,2);
(M4) at (6,2);
(M5) at (8,2);
(M6) at (10,2);

(N1) at (0,0);
(N2) at (2,0);
(N3) at (4,0);
(N4) at (6,0);
(N5) at (8,0);
(N6) at (10,0);

(P1) at (0,-2);
(P2) at (2,-2);
(P3) at (4,-2);
(P4) at (6,-2);
(P5) at (8,-2);
(P6) at (10,-2);

(A) at (sqrt(3),1);
(B) at (sqrt(3)/2,0.5);
(C) at (sqrt(3)/2,-0.5);
(D) at (sqrt(3),-1);
(E) at (3*sqrt(3)/2,-0.5);
(F) at (3*sqrt(3)/2,0.5);

(A1) at (2*sqrt(3),1);
(B1) at (3*sqrt(3)/2,0.5);
(C1) at (3*sqrt(3)/2,-0.5);
(D1) at (2*sqrt(3),-1);
(E1) at (5*sqrt(3)/2,-0.5);
(F1) at (5*sqrt(3)/2,0.5);

(A2) at (3*sqrt(3),1);
(B2) at (5*sqrt(3)/2,0.5);
(C2) at (5*sqrt(3)/2,-0.5);
(D2) at (3*sqrt(3),-1);
(E2) at (7*sqrt(3)/2,-0.5);
(F2) at (7*sqrt(3)/2,0.5);

(A3) at (4*sqrt(3),1);
(B3) at (7*sqrt(3)/2,0.5);
(C3) at (7*sqrt(3)/2,-0.5);
(D3) at (4*sqrt(3),-1);
(E3) at (9*sqrt(3)/2,-0.5);4
(F3) at (9*sqrt(3)/2,0.5);

(A4) at (5*sqrt(3),1);
(B4) at (9*sqrt(3)/2,0.5);
(C4) at (9*sqrt(3)/2,-0.5);
(D4) at (5*sqrt(3),-1);
(E4) at (11*sqrt(3)/2,-0.5);4
(F4) at (11*sqrt(3)/2,0.5);

(A5) at (6*sqrt(3),1);
(B5) at (11*sqrt(3)/2,0.5);
(C5) at (11*sqrt(3)/2,-0.5);
(D5) at (6*sqrt(3),-1);
(E5) at (13*sqrt(3)/2,-0.5);4
(F5) at (13*sqrt(3)/2,0.5);

(G) at (sqrt(3)/2,-0.5);
(H) at (0,-1);
(I) at (0,-2);
(J) at (sqrt(3)/2,-2.5);
(K) at (sqrt(3),-2);
(L) at (sqrt(3),-1);

(G1) at (3*sqrt(3)/2,-0.5);
(H1) at (sqrt(3),-1);
(I1) at (sqrt(3),-2);
(J1) at (3*sqrt(3)/2,-2.5);
(K1) at (2*sqrt(3),-2);
(L1) at (2*sqrt(3),-1);

(G2) at (5*sqrt(3)/2,-0.5);
(H2) at (2*sqrt(3),-1);
(I2) at (2*sqrt(3),-2);
(J2) at (5*sqrt(3)/2,-2.5);
(K2) at (3*sqrt(3),-2);
(L2) at (3*sqrt(3),-1);

(G3) at (7*sqrt(3)/2,-0.5);
(H3) at (3*sqrt(3),-1);
(I3) at (3*sqrt(3),-2);
(J3) at (7*sqrt(3)/2,-2.5);
(K3) at (4*sqrt(3),-2);
(L3) at (4*sqrt(3),-1);

(G4) at (9*sqrt(3)/2,-0.5);
(H4) at (4*sqrt(3),-1);
(I4) at (4*sqrt(3),-2);
(J4) at (9*sqrt(3)/2,-2.5);
(K4) at (5*sqrt(3),-2);
(L4) at (5*sqrt(3),-1);

(G5) at (11*sqrt(3)/2,-0.5);
(H5) at (5*sqrt(3),-1);
(I5) at (5*sqrt(3),-2);
(J5) at (11*sqrt(3)/2,-2.5);
(K5) at (6*sqrt(3),-2);
(L5) at (6*sqrt(3),-1);

[line width=0.25mm] (M1)–(M3)–(P3)–(P1)–(M1);
[line width=0.25mm] (M2)–(P2);
[line width=0.25mm] (N1)–(N3);
[line width=0.25mm] (M5)–(M6)–(P6)–(P5)–(M5);
[line width=0.25mm] (N5)–(N6);

[] (p) at (6,0) $\cdots$;
[] (p) at (1,-1) $1$;
[] (p) at (1,1) $2$;
[] (p) at (3,-1) $3$;
[] (p) at (3,1) $4$;
[] (p) at (9,1) $2n$;
[] (p) at (9,-1) $2n-1$;

Rectangular strip containing $2n$ squares.

In a recent paper, Brown [2] studied such divisions and obtained a
system of recursive relations that we include below as Theorem <ref>.
In order to state the Brown's results, we need one auxiliary term, more
specifically, the number of divisions of a $2\times n$ rectangular strip
into $k$ parts such that the squares in the last column belong to different
parts. We denote that number by $q_k(n)$ and show one such division in Figure <ref> as an example.

[line width=0.25mm, fill=green] (M2)–(M1)–(P1)–(P4)–(M4)–(M3)–(N3)–(N2)–(M2);
[line width=0.25mm,fill=yellow] (M2)–(M3)–(N3)–(N2)–(M2);
[line width=0.25mm,fill=orange] (M4)–(M6)–(N6)–(N5)–(P5)–(P4)–(M4);
[line width=0.25mm, fill=blue] (N5)–(N6)–(P6)–(P5)–(N5);
[dashed,opacity=0.4] (N1)–(N2) (N3)–(N5)  (N2)–(P2) (N3)–(P3) (M5)–(N5);

One division of $2\times 5$ rectangular strip into $4$ parts with squares in the last column being in different parts. Total number of such divisions is denoted by $q_4(5)$.

The number of divisions of $2\times n$ strip into $k$ parts satisfies following system of equations:

\begin{align*}
\end{align*}

It is an easy exercise to eliminate $q_k(n)$ from the system of equations in
Theorem  <ref> and to obtain recursive relations for $r_{k}(n)$,

\begin{equation} \label{eq:r_k(n)}

and for the overall number of such divisions,

\begin{equation} \label{eq:r(n)} r(n+1)=6r(n)+r(n-1).
\end{equation}

These recurrences will serve as the starting point of our Section 3, where
the Brown's results will be extended and refined by establishing recurrences
in $n$ for a fixed $k$ and by computing the expected values of $k$ in a
random division of a $2 \times n$ chocolate bar.

Next we consider a hexagonal strip composed of $n$ regular hexagons as shown
in Figure <ref>. Throughout the paper, such  hexagonal strips
will be also referred to as honeycomb strips. As in the rectangular case,
we are interested in counting the number of all possible divisions of this
strip that contains exactly $k$ pieces. Note that here $n$ does not denote
the number of columns but the total number of hexagons in the strip. Hence
we consider $k$ to be any integer between (and including) $1$ and $n$.
Again, only divisions along the edges of hexagons are considered. The
hexagons are added in the order as it is shown in Figure <ref>.

[line width=0.25mm, fill=yellow] (A1) – (B1) – (C1) – (H1) – (I1) – (J1) –(K1)–(J2)–(K2)–(J3)–(K3)–(L3)–(E3)–(D4)–(E4)–(F4)–(A4)–(B4)–(A3)–(B3)–(G3)–(H3)–(G2)–(F1)–(A1);

[line width=0.25mm, fill=orange] (A5)–(B5)–(C5)–(H5)–(G4)–(H4)–(I4)–(J4)–(K4)–(J5)–(K5)–(L5)–(E5)–(F5)–(A5);
[line width=0.25mm, fill=cyan] (A2) – (B2) – (C2) – (D2) – (E2) – (F2) –(A2);

[line width=0.25mm, fill=green] (A) – (B) – (C) – (H) – (I) – (J) –(K)–(L)–(E)–(F)–(A);

[dashed,opacity=0.4] (D) – (C) (C1) – (D1)–(E1) (D1)–(K1) (D2)–(K2) (C3)–(D3) (E3)–(F3) (K4)–(L4) (C5)–(D5);

[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (3*sqrt(3),0) 6;
[] (p) at (4*sqrt(3),0) 8;
[] (p) at (5*sqrt(3),0) 10;
[] (p) at (6*sqrt(3),0) 12;

[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;
[] (p) at (5*sqrt(3)/2,-1.5) 5;
[] (p) at (7*sqrt(3)/2,-1.5) 7;
[] (p) at (9*sqrt(3)/2,-1.5) 9;
[] (p) at (11*sqrt(3)/2,-1.5) 11;

Honeycomb strip with 12 hexagons divided into 4 pieces.

Let $D_k(n)$ denote the set of all possible divisions of the honeycomb strip
with $n$ hexagons into $k$ pieces and $d_k(n)=|D_k(n)|$ the number of elements
of the set $D_k(n)$. Now we can state some simple cases: $d_1(n)=1$, for every
non-negative integer $n$, since there is only one way to obtain one part,
and $d_n(n)=1$, since there is only one way to obtain $n$ parts, that is to
let each hexagon form its own part. Furthermore, $d_k(n)=0$ for $k < 1$ and
for $k>n$. It is convenient to set $d_1(0)=1$. As an example, we list all
possible divisions of the strip containing $4$ hexagons as the first
non-trivial case.

\begin{align*}
d_1(4)=1 \phantom{-}& \left\lbrace 1234\right\rbrace\\
d_2(4)=6 \phantom{-}& \left\lbrace 1,  234\right\rbrace,\left\lbrace 2,  134\right\rbrace,\left\lbrace 3, 124\right\rbrace,\left\lbrace 4,  123\right\rbrace,\left\lbrace 12,  34\right\rbrace,\left\lbrace 13, 24\right\rbrace\\
d_3(4)=5 \phantom{-}& \left\lbrace 12,3,4\right\rbrace,\left\lbrace 13,2,4\right\rbrace,\left\lbrace 23,1,4\right\rbrace,\left\lbrace 24,1,3\right\rbrace,\left\lbrace 34,1,2\right\rbrace\\
d_4(4)=1 \phantom{-}& \left\lbrace 1,2,3,4\right\rbrace
\end{align*}

Note that the division $\left\lbrace 14,23\right\rbrace$ is not included,
since hexagons $1$ and $4$ are not adjacent, as shown in
Figure <ref>, thus cannot form a part.

[line width=0.25mm,fill=green] (A)–(B)–(C)–(H)–(I)–(J)–(K)–(J1)–(K1)–(L1)–(E1)–(F1)–(A1)–(B1)–(A);
[dashed,opacity=0.4] (F)–(E)–(D)–(C);
[dashed,opacity=0.4] (C1) – (D1);
[dashed,opacity=0.4] (D1) – (E1);
[dashed,opacity=0.4] (K) – (L);
[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=yellow] (G)–(H)–(I)–(J)–(K)–(L)–(G) ;

[line width=0.25mm,fill=green] (A)–(B)–(C)–(D)–(I1)–(J1)–(K1)–(L1)–(E1)–(F1)–(A1)–(B1)–(A);

[dashed,opacity=0.4] (D)–(E) – (F) (C1)–(D1);
[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;
[line width=0.25mm,fill=yellow] (A)–(B)–(C)–(D)–(E)–(F)–(A);

[line width=0.25mm,fill=green] (G)–(H)–(I)–(J)–(K)–(J1)–(K1)–(L1)–(E1)–(F1)–(A1)–(B1)–(C1)–(H1)–(G);

[dashed,opacity=0.4] (C1) – (D1);
[dashed,opacity=0.4] (K) – (L);
[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=yellow] (G1)–(H1)–(I1)–(J1)–(K1)–(L1)–(G1) ;

[line width=0.25mm,line width=0.25mm,fill=green] (A)–(B)–(C)–(H)–(I)–(J)–(K)–(L)–(G1)–(L1)–(E1)–(F1)–(A1)–(B1)–(A);

[dashed,opacity=0.4] (D) – (E);
[dashed,opacity=0.4] (E) – (F);
[dashed,opacity=0.4] (L) – (G);

[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;
[line width=0.25mm,fill=yellow] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);
[line width=0.25mm,fill=green] (A)–(B)–(C)–(H)–(I)–(J)–(K)–(J1)–(K1)–(L1)–(G1)–(G1)–(F)–(A);
[dashed,opacity=0.4] (C)–(D) – (E);
[dashed,opacity=0.4] (K) – (L);
[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=green] (A)–(B)–(C)–(H)–(I)–(J)–(K)–(L)–(E)–(F)–(A);
[line width=0.25mm,fill=yellow] (A1)–(B1)–(C1)–(H1)–(I1)–(J1)–(K1)–(L1)–(E1)–(F1)–(A1);

[dashed,opacity=0.4] (C) – (D);
[dashed,opacity=0.4] (C1) – (D1);

[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=green] (A)–(B)–(C)–(D)–(E)–(D1)–(E1)–(F1)–(A1)–(B1)–(A);
[line width=0.25mm,fill=yellow] (G)–(H)–(I)–(J)–(K)–(J1)–(K1)–(L1)–(G1)–(H1)–(G);

[dashed,opacity=0.4] (F) – (E);
[dashed,opacity=0.4] (K) – (L);

[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=yellow] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);
[line width=0.25mm,fill=orange] (G1)–(H1)–(I1)–(J1)–(K1)–(L1)–(G1) ;
[line width=0.25mm,fill=green] (A)–(B)–(C)–(H)–(I)–(J)–(K)–(L)–(E)–(F)–(A);
[dashed,opacity=0.4] (D) – (C);
[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=yellow] (A) – (B) – (C) – (D) – (E) – (F) –(A);
[line width=0.25mm,fill=orange] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);

[line width=0.25mm,fill=green] (G)–(H)–(I)–(J)–(K)–(J1)–(K1)–(L1)–(G1)–(H1)–(G);

[dashed,opacity=0.4] (K) – (L);

[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=green] (A) – (B) – (C) – (D) – (I1) – (J1) –(K1)–(L1)–(E)–(F)–(A);
[line width=0.25mm,fill=orange] (G)–(H)–(I)–(J)–(K)–(L)–(G) ;

[line width=0.25mm,fill=yellow] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);

[dashed,opacity=0.4] (D) – (E);

[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=yellow] (G)–(H)–(I)–(J)–(K)–(L)–(G) ;
[line width=0.25mm,fill=orange] (G1)–(H1)–(I1)–(J1)–(K1)–(L1)–(G1) ;

[line width=0.25mm,fill=green] (A)–(B)–(C)–(D)–(C1)–(D1)–(E1)–(F1)–(A1)–(B1)–(A);

[dashed,opacity=0.4] (F) – (E);

[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=yellow] (A) – (B) – (C) – (D) – (E) – (F) –(A);
[line width=0.25mm,fill=orange] (G)–(H)–(I)–(J)–(K)–(L)–(G) ;

[line width=0.25mm,fill=green] (A1)–(B1)–(C1)–(H1)–(I1)–(J1)–(K1)–(L1)–(E1)–(F1)–(A1);

[dashed,opacity=0.4] (C1) – (D1);

[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

[line width=0.25mm,fill=green] (A) – (B) – (C) – (D) – (E) – (F) –(A);
[line width=0.25mm,fill=yellow] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);
[line width=0.25mm,fill=orange] (G)–(H)–(I)–(J)–(K)–(L)–(G) ;
[line width=0.25mm,fill=cyan] (G1)–(H1)–(I1)–(J1)–(K1)–(L1)–(G1) ;

[] (p) at (sqrt(3),0) 2;
[] (p) at (2*sqrt(3),0) 4;
[] (p) at (sqrt(3)/2,-1.5) 1;
[] (p) at (3*sqrt(3)/2,-1.5) 3;

All possible divisions of the strip with $4$ hexagons.

Since the inner dual of $2\times n$ rectangular strip is a subgraph of the
inner dual of hexagonal strip of length $2n$, all divisions of a $2\times n$
rectangular strip are also valid divisions of a hexagonal strip with $n$
hexagons, but not vice versa. Figure <ref>
shows the division $\left\lbrace 1,23,4\right\rbrace$ which is legal in the
hexagonal strip but illegal in the rectangular strip.

[line width=0.25mm,fill=green] (A) – (B) – (C) – (D) – (I1) – (J1) –(K1)–(L1)–(E)–(F)–(A);
[line width=0.25mm,fill=orange] (G)–(H)–(I)–(J)–(K)–(L)–(G) ;

[line width=0.25mm,fill=yellow] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);

[dashed,opacity=0.4] (D) – (E);

[] (p) at (sqrt(3),0) $2$;
[] (p) at (2*sqrt(3),0) $4$;
[] (p) at (sqrt(3)/2,-1.5) $1$;
[] (p) at (3*sqrt(3)/2,-1.5) $3$;

[line width=0.25mm,fill=green] (M1)–(M2)–(N2)–(N1)–(M1);
[line width=0.25mm,fill=orange] (N1)–(N2)–(P2)–(P1)–(N1);
[line width=0.25mm,fill=green] (N2)–(N3)–(P3)–(P2)–(N2);
[line width=0.25mm,fill=yellow] (M2)–(M3)–(N3)–(N2)–(M2);

[] (p) at (1,-1) $1$;
[] (p) at (1,1) $2$;
[] (p) at (3,-1) $3$;
[] (p) at (3,1) $4$;

On the left is a valid division of a honeycomb strip, and on the right corresponding division of rectangular grid that is not allowed.

§ DIVIDING A CHOCOLATE BAR INTO A GIVEN NUMBER OF PARTS

Numbers $r_k(n)$ of (<ref>) form a triangular array; its first few
lines are shown in Table <ref>.
In this section we investigate behavior of its columns, i.e., we turn our
attention to recursive relation for $r_k(n)$ where $k$ is fixed.

$\begin{array}[valign=c]{c| *{12}{@{}C{\mycolwd}@{}}}
n \backslash k& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10    \\[1.5ex]
\hline
1 &1 & 1\\
2 &1 & 6 & 4 & 1\\
3 &1 & 15 & 29 & 21 & 7 &1\\
4 &1 & 28 & 107 & 153 & 111 & 45 & 10 & 1\\
5 &1 & 45 & 286 & 678 & 831 & 603 & 274 & 78 & 13 & 1\\
\end{array}$
First few rows of of $r_k(n)$.

As mentioned before, $r_0(n) = 0$ and $r_{1}(n)=1$, so we look at the first
non-trivial case, $k=2$. From relation (<ref>) we obtain
By plugging in $r_{0}(n)=0$ and $r_{1}(n)=1$, we obtain

\begin{align*}
\end{align*}

and by subtracting these two equations we arrive at

\begin{equation}
r_{2}(n)=3r_{2}(n-1)-3r_{2}(n-2)+r_{2}(n-3). \label{eq:r_2(n)}
\end{equation}

Rewriting the trivial case

\begin{equation}
\end{equation}

\begin{equation}
\binom{1}{0}r_{1}(n)=\binom{1}{1}r_{2}(n-1),
\end{equation}

and case $k = 2$ as

\begin{equation}
\binom{3}{0}r_{2}(n)=\binom{3}{1}r_{2}(n)-\binom{3}{2}r_{2}(n-1)+\binom{3}{3}r_{2}(n-2)
\end{equation}

suggests that there is a pattern valid also for higher values of $k$. The
conjectured pattern is readily verified by induction, thus yielding the
following theorem.

For integers $n,k\geq 1$ we have

\begin{equation}
\sum\limits_{j=0}^{2k-1}(-1)^{j}\binom{2k-1}{j}r_{k}(n-j)=0.
\end{equation}

The proof is by induction. For $k=1,2$, the base of induction is true, as
stated above. To verify the step of induction, we use recursion
(<ref>) to obtain a system of $2k-2$ equations as follows:

\begin{align*}
r_{k}(n)=\, &r_{k-2}(n-1)+3r_{k-1}(n-1)+2r_{k}(n-1)+\\&+r_{k-2}(n-2)+r_{k-1}(n-2)-r_{k}(n-2)\\
r_{k}(n-1)=\, &r_{k-2}(n-2)+3r_{k-1}(n-2)+2r_{k}(n-2)+\\&+r_{k-2}(n-3)+r_{k-1}(n-3)-r_{k}(n-3)\\
r_{k}(n-2)=\, &r_{k-2}(n-3)+3r_{k-1}(n-3)+2r_{k}(n-3)+\\&+r_{k-2}(n-4)+r_{k-1}(n-4)-r_{k}(n-4)\\
\vdots&\\
r_{k}(n-2k+3)=\, &r_{k-2}(n-2k+2)+3r_{k-1}(n-2k+2)+2r_{k}(n-2k+2)+\\&+r_{k-2}(n-2k+1)+r_{k-1}(n-2k+1)-r_{k}(n-2k+1)
\end{align*}

The term $r_{k}(n-j)$ appears in at most three equations, namely in
the $(j-1)^{\textup{st}}$, $j^{\textup{th}}$ and $(j+1)^{\textup{st}}$ equation.
To proceed forward, we multiply $j$-th equation by $(-1)^{j}\binom{2k-3}{j-1}$
and we add up all equations. For even $j$, the term $r_{k}(n-j)$ appears with
the coefficient

and for odd $j$ with the same coefficient, but with the opposite sign. We
conclude that

\begin{equation}
\end{equation}

where $A_{k-1}(n)$ and $A_{k-2}(n)$ are some expressions involving
$r_{k-1}(n-j)$ and $r_{k-2}(n-j)$, respectively. The claim of the Theorem
will be established if we show that both $A_{k-1}(n)$ and $A_{k-2}(n)$ are
equal to zero. We first look at $A_{k-1}(n)$.
For $j\geq 1$, the term $r_{k-1}(n-j)$ appears twice in our system of
equations, in the $(j-1)^{\textup{st}}$ and in the $j^{\textup{th}}$ equation,
hence, the coefficient by $r_{k-1}(n-j)$ is
$\binom{2k-3}{j-2}-3\binom{2k-3}{j-1}$ for an odd $j$, and
$3\binom{2k-3}{j-1}-\binom{2k-3}{j-2}$ for an even $j$. So,

For $k-1$ we can use the induction hypothesis, hence

After adding the equations we have

\begin{align*}
&=\sum\limits_{j=1}^{2k-1}(-1)^{j}\left(\binom{2k-3}{j-2}-3\binom{2k-3}{j-1}\right) r_{k}(n-j),
\end{align*}

hence, $A_{k-1}(n)=0$.

Similarly, $A_{k-2}(n)$ can be expressed as

and, again, by using the induction hypothesis for $k-2$ we obtain
$A_{k-2}(n)=0$. The proof follows along the same lines as for $A_{k-1}(n)=0$
and we omit the details.

This completes our proof.

Theorem <ref> implies that all columns of the
array $r_k(n)$ are polynomials in $n$. Moreover, $r_k(n)$ is a polynomial
in $n$ of degree $2k-2$. The exact expressions can be easily
obtained by fitting to the initial values, but we omit the details. Our
Theorem <ref> reestablishes the polynomiality
results of references [2] and [3] in a more compact
and self-contained form.

A similar reasoning could be also employed near the upper end of the range
of $k$ and used to establish polynomiality of diagonals $r_{2n-k}(n)$,
going thus beyond the results of references [2, 3].
Indeed, $r_{2n}(n) = 1$ for all non-negative integers $n$.
Furthermore, $r_{2n-1}(n) = 3n-2$, since among the $2n-1$ pieces there must
be exactly one dimer. That dimer is an edge in the inner dual of our bar,
hence an edge in a ladder graph with $n$ rungs, and there are exactly
$3n-2$ such edges. In a similar way one can see that $r_{2n-2}(n)$ must be
a quadratic polynomial in $n$: A division into $2n-2$ parts can either
contain one trimer and $2n-3$ monomers, or two dimer and $2n-4$ monomers.
As the number of trimers is linear in $n$ and the number of pairs of dimers
is quadratic in $3n$, by fitting on the first few values for small $n$ one
obtains $r_{2n-2}(n) = \frac{9}{2}(n-1)(n-\frac{2}{3})$. By continuing
with the same reasoning, one obtains a general result.

$r_{2n-k}(n)$ is a polynomial of degree $k$ in $n$ with the leading coefficient

We leave the details to the interested reader.

We now move towards computing the bivariate generating function for $r_k(n)$.
$$F(x,y)=\sum\limits_{n\geq 1} \sum\limits_{k\geq 1}r_k(n)x^ny^k$$

denote the desired generating function. By starting from recurrence
(<ref>) we readily obtain

By substituting $y=1$ we obtain

the univariate generating function for the sequence $r_n$.

Now we can determine the expected number of pieces in a random division. We
rely on the following version of the Darboux's theorem [1].

If the generating function
$f(x)=\sum_{n\geq 0}a_x^n$ of a sequence $(a_n)$ can we written in the form
$f(x)=\left(1-\frac{x}{\omega}\right)^{\alpha}h(x)$, where $\omega$ is the
smallest modulus singularity of $f$ and $h$ is analytic in $\omega$,
then $a_n\sim\frac{h(\omega)n^{-\alpha-1}}{\Gamma(-\alpha)\omega^n}$,
where $\Gamma$ denotes the gamma function.

Since $\omega=\sqrt{10}-3$ we can write

Hence, we have
$h(x)=\dfrac{2x}{x\left(\sqrt{10}-3\right)+1}$ and

$$\left.\frac{\partial F(x,y)}{\partial y}\right\rvert_{y=1}=\frac{-x(x^3+3x^2+7x-3)}{\left(x\left(\sqrt{10}-3\right)x+1\right)^2}\left(1-\dfrac{x}{\left(\sqrt{10}-3\right)}\right)^{-2}$$

and $g(\omega)=\frac{3\sqrt{10}-4}{20}$.
By Theorem <ref>, the expected number of parts is

$$\dfrac{\dfrac{g(\omega)n}{\Gamma(2)\omega^n}}{\dfrac{h(\omega)}{\Gamma(1)\omega^n}}=\left(\dfrac{3}{2}-\sqrt{\frac{2}{5}}\right) n.$$

Hence, we have established the following result for the expected number of
parts in a random division of a chocolate bar of length $n$.

The expected number of parts in a random division of a chocolate bar of
length $n$ is given by
$$\left(\dfrac{3}{2}-\sqrt{\frac{2}{5}}\right) n
\approx 0.867544 \,n.$$

The above result is derived under the so-called equilibrium assumption, where
all divisions are equally likely.

The triangle of Table <ref> is not (yet) in the OEIS [5].
its row sums appear as A078469, the number of compositions of ladder graphs
in the sense of reference [4]. Hence our results could be also
interpreted as a refinement of the number of compositions of ladder graphs.
Sequence $r_3(n)$ appears as A345897, with the same interpretation as we
give here. Curiously, such an interpretation seems to be missing among
many combinatorial interpretations of A000384, the hexagonal numbers, which
appear as the second column of our triangle. Similarly, $r_{2n-2}(n)$
appears as A081266, but without the interpretation given here.

§ DIVISIONS OF HONEYCOMB STRIPS

§.§ Recurrences, explicit formulas and generating functions

Recall that $D_k(n)$ denotes the set of all possible divisions of the
honeycomb strip with $n$ hexagons into $k$ pieces and $d_k(n)=|D_k(n)|$
the number of elements of the set $D_k(n)$. In order to count the divisions
correctly, special attention must be paid to the rightmost two cells, since
the new $(n+1)^{\textup{st}}$ cell can interact only with them. Whether these
hexagons are in the same pieces or not plays crucial role in how the  new
hexagon can be added. We denote by $S_k(n)$ the set of all possible divisions
of the honeycomb strip with $n$ hexagons into $k$ pieces with two last
hexagons in the different parts. Similarly, let $T_k(n)$ denote the set of
all possible divisions of the strip into $k$ pieces with two two rightmost
hexagons belonging to the same piece. Let $s_k(n)=|S_k(n)|$ and
$t_k(n)=|T_k(n)|$.  Since the last two hexagons can either be together or
separated, we have divided the set $D_k(n)$ into two disjoint sets,
$D_k(n)=S_k(n)\cup T_k(n)$, hence $d_k(n)=t_k(n)+s_k(n)$.

[line width=0.25mm] (F)–(A) (K)–(J);
[line width=0.25mm, dotted] (A)–(B) (J)–(I);

[line width=0.25mm,fill=green] (A1)–(B1)–(C1)–(H1)–(I1)–(J1)–(K1)–(L1)–(E1)–(F1)–(A1);

[dashed,opacity=0.4] (C1)–(D1);

A honeycomb strip with two rightmost hexagons in the same piece.

[line width=0.25mm,fill=green] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);
[line width=0.25mm,fill=yellow] (G1)–(H1)–(I1)–(J1)–(K1)–(L1)–(G1) ;

[line width=0.25mm] (F)–(A) (K)–(J);
[line width=0.25mm, dotted] (A)–(B) (J)–(I);

[dashed,opacity=0.4] (G1) – (H1);

A honeycomb strip with two rightmost hexagons in different pieces.

We first establish an auxiliary result.

For $n\geq 1$, the number of all
possible divisions $s_k(n)$ of the honeycomb strip with $n$ hexagons into
$k$ pieces, with hexagons in the last column being in the different pieces,
satisfies the following relation:

\begin{align}\label{eq:s(n,k) recursive} s_k(n+1)&=s_{k-1}(n)+2s_k(n)-s_{k}(n-1).\end{align}

We start with a strip containing $n$ hexagons and add one new
hexagon to obtain a strip with $n+1$ hexagons. The new  hexagon can either
increase the number of parts in division by $1$ or not increase this number.
To obtain a division with $k$ pieces, we can only start with the
division with $k-1$ or $k$ pieces. These are two disjoint sets, so the
number of all divisions will be the sum of these cases.

When starting with division consisting of $k-1$ pieces, we can obtain $k$
pieces by adding the new hexagons as individual pieces. Since there is only
one way to do that, the number of divisions that can be obtained this way is
$d_{k-1}(n)$. Note that the condition that rightmost two hexagons belong to
different pieces is satisfied, as shown in
Figure <ref>.

[line width=0.25mm,fill=green] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);

[line width=0.25mm,fill=yellow] (G1)–(H1)–(I1)–(J1)–(K1)–(L1)–(G1) ;

[line width=0.25mm] (F)–(A) (K)–(J);
[line width=0.25mm, dotted] (A)–(B) (J)–(I);

[dashed,opacity=0.4] (G1) – (H1);

[font=] (p) at (2*sqrt(3),0) $n+1$;

[font=] (p) at (3*sqrt(3)/2,-1.5) $n$;

The element of $S_{k}(n+1)$ obtained from the element of
$D_{k-1}(n)$ by adding the new hexagon as separated piece.

It remains to consider one last case. We start with a strip divided into $k$
pieces and we add $(n+1)^{\textup{st}}$ hexagon. If the last two hexagons
in the division are together, we cannot add new hexagons so that
number of parts remains the same and that new hexagons are in different

Now we move to the case where the last two hexagons in the division
are separated. There is only one way to add new hexagons to the existing
strip, to put the $(n+1)^{\textup{st}}$ hexagon together with
$(n-1)^{\textup{st}}$ (see Figure <ref>). Every
other layout would be in contradiction with either number of pieces or the
fact that two last hexagons should be separated, since putting
$(n+1)^{\textup{st}}$ hexagon together with $n^{\textup{th}}$ hexagon would
produce the element of $T_k(n)$. So in this case we have $s_k(n)$ ways to
obtain the desired division.

[line width=0.25mm,fill=green] (A1)–(B1)–(C1)–(D1)–(E1)–(D2)–(E2)–(F2)–(A2)–(B2)–(A1);
[line width=0.25mm,fill=yellow] (G2)–(H2)–(I2)–(J2)–(K2)–(L2)–(G2) ;

[line width=0.25mm] (F)–(A) (K1)–(J1);
[line width=0.25mm, dotted] (A)–(B) (J1)–(I1);

[dashed,opacity=0.4] (E1) – (F1);

[font=] (p) at (2*sqrt(3),0) $n-1$;
[font=] (p) at (3*sqrt(3),0) $n-1$;
[font=] (p) at (5*sqrt(3)/2,-1.5) $n$;

The element of $S_k(n+1)$ obtained from the element of $S_k(n)$ by
joining the new hexagon with $(n-1)^{\textup{st}}$ hexagon

By summing these two cases, we obtain the recursive relation

\begin{equation} \label{eq:s(n,k) aux}
\end{equation}

To eliminate $d_{k-1}(n)$ from relation (<ref>), we use the
fact that $d_{k-1}(n)=t_{k-1}(n)+s_{k-1}(n)$. By removing the last hexagon
from the strip, we establish a 1-to-1 correspondence between all division of a
strip with $n-1$ hexagons and divisions of a strip with $n$ hexagons where
two last hexagons are in the same part. Hence, $t_k(n)=d_k(n-1)$. Then we

\begin{align*}
\end{align*}

hence $d_{k-1}(n-1)=s_k(n+1)-s_{k-1}(n)-s_k(n)$, which combined with
relation (<ref>) yields

\begin{align*}
\end{align*}

and we proved the theorem.

By disregarding values of $k$ in recursive relation <ref>
we obtain
where $s(n)$ represents the number of
all divisions of a honeycomb strip of length $n$ with two last hexagons in
different parts. Since we obtained the same recursive relation as for bisection
of Fibonacci sequence with $s(1)=0$ and $s(2)=1$ we have

Our main result of this section now follows by much the same reasoning, as
$d_k(n)$ satisfy the same recurrence as $s_k(n)$. We state it without
For $n\geq 1$, the number of
all possible divisions $d_k(n)$ of $n$  honeycomb strip into $k$ pieces
satisfies the following relation:

\begin{align}\label{eq:d(n,k) recursive}
d_k(n+1)= d_{k-1}(n)+2d_k(n)-d_k(n-1).
\end{align}

Again, by grouping together terms of recurrence <ref>
with respect to $n$, we obtain the recurrence satisfied by the sequence
$d(n)$ counting the total number of subdivisions of a honeycomb strip of
length $n$ as

$$ d(n+1) = 3d(n) - d(n-1).$$

Taking into account the initial conditions $d(1) = 1$ and $d(2) = 2$ yields
a very simple answer.

The total number of divisions of a honeycomb strip of length $n$ is given
by $d(n) = F_{2n-1}$, where $F_n$ denotes the $n^{\rm th}$ Fibonacci

The above theorem yields a nice combinatorial interpretation of the
odd-indexed Fibonacci numbers which seems to be absent from the entry
A001519 in the OEIS. It would be interesting to obtain our Theorem
<ref> by establishing a bijection between our divisions and
some of the objects listed there.

With the above result at hand, it is not too difficult to guess the
explicit formulas for $d_k(n)$ and $s_k(n)$. The following theorem is
easily proved by simply verifying that the proposed expressions satisfy
the respective recurrences and initial conditions, and we omit the
details. Again, it would be more interesting to verify the formulas
in a combinatorial way.
The number of all divisions
$d_k(n)$ of the honeycomb strip with $n$ hexagons into exactly $k$ pieces is

The number $s_k(n)$ of all divisions of the honeycomb strip with $n$
hexagons into $k$ pieces such that two rightmost hexagons belong to
different pieces is equal to zero if $n=1$ and for $n \geq 2$ it is given as

Even though sequences $r_k(n)$ and $d_k(n)$ satisfy
different recursive relations and describe different problems, it turns
out that their columns satisfy the same recurrences.
Our next theorem is analogue of Theorem <ref>,
but for the sequence $d_k(n)$. We state it without proof.

For $n,k\geq 1$ we have

\begin{equation}
\sum\limits_{j=0}^{2k-1}(-1)^{j}\binom{2k-1}{j}d_{k}(n-j)=0.
\end{equation}

As with a rectangular strip, we are now interested in generating function of
sequence $d_k(n)$. Let

$$G(x,y)=\sum\limits_{n\geq 1}\sum\limits_{k\geq 1}d_k(n)x^ny^k.$$

By recursive relation $\ref{eq:d(n,k) recursive}$ we have

\begin{align*}
G(x,y)&=xy+x^2y\left(1+y\right)+ \sum\limits_{n\geq 3}\sum\limits_{k\geq 1}\left(d_{k-1}(n-1)+2d_k(n-1)-d_k(n-2)\right)x^ny^k \\
&=xy+x^2y\left(1+y\right)+xy\left(G(x,y)-xy\right) +2x \left(G(x,y)-xy\right)-x^2G(x,y),
\end{align*}

so we have

By putting $y=1$ we obtain the univariate generating function for the sequence
$d(n)$ as

Its smallest-modulus singularity is $\omega=\frac{1}{2}\left(3-\sqrt{5}\right)$
and this gives us the asymptotics of the expected number of pieces in random
divisions of honeycomb strips of a given length.

The expected number of pieces in a random division of a honeycomb strip of
length $n$ asymptotically behaves as

$$\frac{\sqrt{5}}{5}n \approx 0.447214 n.$$

The proof follows by a straightforward application of Darboux theorem and
we omit the details.

§.§ Some consequences

Our results make possible to give new combinatorial interpretation for
some famous identities. We present two such cases.

First, by double counting the set $D(n)$, we gave
new meaning to the well-known identity

Another identity will be proven in the next theorem.

For $n,m\geq 1$ we have

We start with two honeycomb strips of lengths $n$ and $m$. To prove the
statement of a theorem we glue strips together as in
Figure <ref> and double count the number of divisions.
On one hand, we have a strip of length $n+m$ whose number of divisions is
$d(n+m)$. On the other hand, we consider what can happen when strips are
glued together. In the first case parts of each division do not interact,
hence we have $d(n)d(m)$ such divisions. In the other cases, at least two
parts, one from each strip, must merge. But to correctly count the number
of divisions in those cases, it is important to know whether division is
with two last hexagons together or separated. If both strips have the last
two hexagons hexagons together, the total number of such divisions is
$t(n)t(m)$. If both strips have last two hexagons hexagons separated,
the total number of such divisions is $4s(n)s(m)$, since there are four
different ways to merge parts. Finally, if one strip has two last hexagons
separated and the other one together, we can merge parts in two ways.
Since either one of strips can be in both situations, the total number of
divisions in this case is $2s(n)t(m)+2s(n)t(m)$.

[line width=0.25mm] (A)–(B)–(C)–(D)–(E)–(F)–(A);
[line width=0.25mm] (G)–(H)–(I)–(J)–(K)–(L)–(G);

[line width=0.25mm] (A2)–(B2)–(C2)–(D2)–(E2)–(F2)–(A2);
[line width=0.25mm] (A3)–(B3)–(C3)–(D3)–(E3)–(F3)–(A3);
[line width=0.25mm] (G2)–(H2)–(I2)–(J2)–(K2)–(L2)–(G2);
[line width=0.25mm] (G3)–(H3)–(I3)–(J3)–(K3)–(L3)–(G3);

[line width=0.25mm] (A5)–(B5)–(C5)–(D5)–(E5)–(F5)–(A5);
[line width=0.25mm] (G5)–(H5)–(I5)–(J5)–(K5)–(L5)–(G5);

[] (p) at (sqrt(3),0) $2$;
[] (p) at (3*sqrt(3),0) $n$;
[] (p) at (4*sqrt(3),0) $m-1$;
[] (p) at (6*sqrt(3),0) $1$;

[] (p) at (sqrt(3)/2,-1.5) $1$;
[] (p) at (3.55*sqrt(3)/2,-0.75) $\cdots$;
[] (p) at (5*sqrt(3)/2,-1.5) $n-1$;
[] (p) at (7*sqrt(3)/2,-1.5) $m$;
[] (p) at (9.55*sqrt(3)/2,-0.75) $\cdots$;
[] (p) at (11*sqrt(3)/2,-1.5) $2$;

Two honeycomb strips glued together.

\begin{align*}
\end{align*}

The claim now follows by substituting $d(n)=F_{2n-1}$, $s(n)=F_{2n-2}$ and
$t(n)=F_{2n-3}$ and rearranging the resulting expressions.

The results of this section can be also formulated in terms of graph
compositions, this time of the graph $P_n^2$ obtained by adding edges
between all pairs of vertices at distance $2$ in $P_n$, the path on $n$
vertices. The following results is a direct consequence of the fact that
$P_n^2$ is the inner dual of a honeycomb strip of length $n$.

The number of compositions of $P_n^2$ with $k$ components is equal to
$\binom{n+k-2}{n-2}$. The total number of compositions of $P_n^2$ is equal
to $F_{2n-1}$.

§ TRANSFER MATRIX METHOD

§.§ Honeycomb strips

In this section we present another approach to obtain overall number
of divisions, the one based on transfer matrices. It might seem less
natural than recurrence relations, but it often turns out to be suitable
when recurrence relations are complicated or unknown.

We again consider a honeycomb strip such as the one shown in the
Figure <ref>, and look at its rightmost column, i.e., at the
hexagons labeled by $n-1$ and $n$. There are two possible situations
regarding these hexagons: they can be in the same piece of a subdivision,
or they can belong to two different pieces. We denote a strip with last
two hexagons together as a type $T$ strip and a strip with last two
hexagons separated as a type $S$ strip. Adding the $(n+1)-$st hexagon might
result again in a type $S$ strip or in a type $T$ strip. There are
altogether four possibilities, each of them producing certain effects
on the number of pieces in the resulting strip. For example, if we start
with a strip of type $S$ and we want to end with a strip of type $S$,
we can either add the new hexagon to the part which contains the $(n-1)^{\textup{st}}$
hexagon, or we can let the $(n+1)^{\textup{st}}$ hexagon to form its own part. In the
first case, the number of parts will remain the same, in the second case
it will increase by one.
Figure <ref> shows this case.

[line width=0.25mm,fill=green] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);
[line width=0.25mm,fill=yellow] (G1)–(H1)–(I1)–(J1)–(K1)–(L1)–(G1);
[line width=0.25mm,fill=orange] (G2)–(H2)–(I2)–(J2)–(K2)–(L2)–(G2);
[font=] (p) at (2*sqrt(3),0) $n$;
[font=] (p) at (5*sqrt(3)/2,-1.5) $n+1$;
[font=] (p) at (3*sqrt(3)/2,-1.5) $n-1$;
[line width=0.25mm,fill=green] (A1)–(B1)–(C1)–(D1)–(E1)–(F1)–(A1);
[line width=0.25mm,fill=yellow] (G1)–(H1)–(I1)–(J1)–(K1)–(J2)–(K2)–(L2)–(G2)–(H2)–(G1);

[font=] (p) at (2*sqrt(3),0) $n$;
[font=] (p) at (5*sqrt(3)/2,-1.5) $n+1$;
[font=] (p) at (3*sqrt(3)/2,-1.5) $n-1$;
[dashed,opacity=0.4] (H2)–(I2);

Both cases resulting with a strip of type $S$.

The main idea of the transfer matrix method is to
arrange the effects of adding a single hexagon into a $2 \times 2$ matrix
whose entries will keep track of the number of pieces via a formal
variable, say, $y$. The rows and columns of such a matrix are indexed by
possible states, in our case $T$ and $S$, and the element at the position
$S,S$ in our example will be $1+y$. That clearly captures the fact that
transfer from $S$ to $S$ results either in the same number of pieces, or
the number of pieces increases by one. The other three possible transitions,
$T \to T$, $S \to T$ and $T \to S$ are described by matrix elements
$1, 1$, and $y$, respectively. Indeed, it is clear that adding a hexagon
so to obtain the rightmost column together cannot increase the number of
pieces, hence the two ones, and that starting from $T$ and arriving at $S$
is possible only by the last hexagon forming a new piece, hence increasing
the number of pieces by one, hence $y$. If we denote our matrix by $H$,
we can write it as

\begin{equation*}
1 & 1 \\ y & 1+y
\end{bmatrix}.
\end{equation*}

By construction, it is clear that adding a new hexagon will be well
described by multiplying some vector of states by our matrix $H(y)$, and that
repeated addition of hexagons will correspond to multiplication by powers
of $H(y)$. It remains to account for the initial conditions.

For the initial value $n=1$ we
have trivial case, one hexagon forms one part. For $n=2$ we have two
possibilities, hexagons are in the same part or separated. Hence his case
is represented by a vector

\begin{equation*}
\overrightarrow{h_2}=x\begin{bmatrix} y \\ y^2 \end{bmatrix}.
\end{equation*}

By introducing another formal variable, say $x$, to keep track of the length,
the above procedure will produce a sequence of bivariate polynomials whose
coefficients are our numbers $d_k(n)$. A first few polynomials are shown
in Table <ref> after the theorem which summarizes the described

The number of divisions of a honeycomb strip of a length $n$ into $k$ parts is the coefficient by $x^ny^k$ in the expression

\begin{equation}\label{expression}
\begin{bmatrix} 1& 1 \end{bmatrix} \begin{bmatrix}
1 & 1 \\ y & 1+y \end{bmatrix}^{n-2} \begin{bmatrix}
y \\ y^2 \end{bmatrix} x^n.
\end{equation}

$1$     $xy$

$2$     $x^2(y+y^2)$

$3$     $x^3(y+3y^2+y^3)$

$4$     $x^4(y+6y^2+5y^3+y^4)$

$5$     $x^5(y+10y^2+15y^3+7y^4+y^5)$

$6$     $x^6(y+15y^2+35y^3+28y^4+9y^5+y^6)$

First few bivariate polynomials from the transfer
matrix method.

The coefficients by $x^ny^k$ in expression (<ref>) could be now
determined by studying powers of the transfer matrix. By looking at the
first few cases,

1+y & 2+y \\ 2y+y^2 & 1+3y+y^2\end{bmatrix} \quad {\rm and}\quad  H(y)^3=\begin{bmatrix}
1+3y+y^2 & 3+4y+y^2 \\ 3y+4y^2+y^3 & 1+6y+5y^2+y^3\end{bmatrix},$$

we could guess the entries in the general case and then verify them by
induction. We state the result omitting the details of the proof.

p(n) & s(n) \\ ys(n) & p(n+1)
\end{bmatrix}$$
with $p(n)=\displaystyle\sum\limits_{k=1}^{n}\binom{n+k-2}{n-k}y^{k-1}$ and $s(n)=\displaystyle\sum\limits_{k=1}^{n}\binom{n+k-1}{n-k}y^{k-1}$.

Lemma <ref> allows us to simplify the expression (<ref>) to have

\begin{align*}
\begin{bmatrix} 1& 1 \end{bmatrix} \begin{bmatrix}
1 & 1 \\ y & 1+y \end{bmatrix}^{n-2} \begin{bmatrix}
y \\ y^2 \end{bmatrix} x^n &= \begin{bmatrix} 1& 1 \end{bmatrix} \begin{bmatrix}
p(n-2) & s(n-2) \\ ys(n-2) & p(n-1) \end{bmatrix} \begin{bmatrix}
y \\ y^2 \end{bmatrix} x^n \\
&= \left(yp(n-2) + ys(n-2) + y^2s(n-2) + y^2p(n-1)\right)  x^n \\
&= \left(yp(n-1) + y\left(s(n-2) + yp(n-1)\right)\right)  x^n \\
&= p(n)x^ny \\
&=\displaystyle\sum\limits_{k=1}^{n}\binom{n+k-2}{n-k}y^{k} x^n
\end{align*}

By Theorem <ref> we have

Now we turn our attention to the number of all possible divisions, i.e.
we wish to determine the number $d(n)$. To to that, we again use matrix
$H(y)$ and Theorem <ref>. By setting $y=1$ we have
1 & 1 \\ 1 & 2 \end{bmatrix}=\begin{bmatrix}
F_1 & F_2 \\ F_2 & F_3 \end{bmatrix}$. Again, the following claim is easily
guessed and verified by induction.
F_{2n-1} & F_{2n} \\ F_{2n} & F_{2n+1}
\end{bmatrix}$.

Finally, by Lemma <ref> we can simplify expression
(<ref>) to have

\begin{align*}  \begin{bmatrix} 1& 1 \end{bmatrix} \begin{bmatrix} F_{2n-5} & F_{2n-4} \\ F_{2n-4} & F_{2n-3} \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} &= \begin{bmatrix} F_{2n-5}+F_{2n-4}& F_{2n-4}+F_{2n-3} \end{bmatrix}\begin{bmatrix} 1 \\ 1 \end{bmatrix} \\
&=\begin{bmatrix} F_{2n-3}& F_{2n-2}\end{bmatrix}\begin{bmatrix} 1 \\ 1 \end{bmatrix} \\
&= F_{2n-1}. \end{align*}

By Theorem <ref> we have $d(n)=F_{2n-1}$.

§.§ Chocolate bars

Transfer matrices can be also used to obtain the sequence $r_{k}(n)$
denoting the number of ways to divide rectangular strip $2\times n$ into
$k$ parts. In this case we do not add square by square, but column by column.
So, let $T$ denote a division of a strip where squares in the last column
are in the same part and $S$ a division where squares in the last column are
in different parts.

For $n=1$ we have the same case as $n=2$ in a honeycomb strip, so this case
is represented by a vector

\begin{equation*}
\overrightarrow{q_1}=x\begin{bmatrix} y \\ y^2 \end{bmatrix}.
\end{equation*}

Similar as in the honeycomb case, if we start with a division of type $T$
and we wish to obtain another division of type $T$, we can do that either by
appending two new squares to the same part with the squares of the last
column or we can let two new squares form a new part. Hence, the
corresponding entry in the transfer matrix is $1+y$. By doing similar
analysis for other cases, we obtain the transfer matrix

\begin{equation*}
1+y & 2+y \\ y(2+y) & (1+y)^2
\end{bmatrix}.
\end{equation*}

Again, $y$ is a formal variable keeping track of the number of pieces.
So, for a strip $2\times n$, the coefficient by $x^ny^k$ in the expression

1 & 1
\end{bmatrix}\begin{bmatrix}
1+y & 2+y \\ y(2+y) & (1+y)^2
\end{bmatrix}^{n-1}\begin{bmatrix}
y \\ y^2
\end{bmatrix}x^n$$

represents the number of ways to divide rectangular strip $2\times n$ into
exactly $k$ parts.

We conclude this section by mentioning that in both cases we could have
obtained the asymptotic behavior of numbers $d(n)$ and $r(n)$ by computing
the leading eigenvalue of the corresponding transfer matrix.

§ CONCLUDING REMARKS

In this paper we have employed two different methods to count
divisions of narrow strips of squares and hexagons, respectively, into a
given number of pieces, when cutting is allowed only along the edges of
basic polygons. We have obtained several triangular integer arrays and
determined formulas for their entries. Despite similar settings, the two
problems behave in different ways: for honeycomb strips the entries of the
enumerating triangles are given as binomial coefficients with parameters
dependent on the strip length and the number of pieces, while for chocolate
bars no closed-form expression has been obtained. We were able to show, though,
that the entries in columns satisfy
convolution-type recurrences with coefficients forming alternating rows of
Pascal triangle.

Both problems were then addressed by using the transfer-matrix formalism.
The original results for the total number of divisions were re-derived
in a more compact way, demonstrating thus the power of transfer-matrix method.
However, we found the approach unsuitable for refining the aggregate results,
for establishing the polynomial nature of columns and for obtaining
closed-form solutions in the rectangular case. Nevertheless, we believe that
the transfer matrices would prove useful in treating a number of similar
problems, as indicated by our experiments with wider strips in both square
and hexagonal lattices and with narrow strips in the triangular lattice.

§ ACKNOWLEDGEMENT

Partial support of Slovenian ARRS (Grant no. J1-3002)
is gratefully acknowledged by T. Došlić.

[99]

[1]
E. A. Bender, S. G. Williamson,
Foundation of Combinatorics with Applications,
Dover (2006).

[2]
J. Brown,
Counting Divisions of a $2\times n$ Rectangular Grid,
Arxiv (2014).

[3]
S. Durham, J. Richmond,
Connected subsets of an $n \times 2$ rectangle,
College Math. J. 51 (2020) 32–42.

[4]
A. Knopfmacher, M. E. Mays,
Graph compositions I: Basic enumeration,
Integers 1 (2001) #A04.

[5]
OEIS Foundation Inc. (2023),
The On-Line Encyclopedia of Integer Sequences,
Published electronically at https://oeis.org.

[6]
S. Wagon,
Counting connected sets of squares,
College Math. J. 51 (2020) 173.