Rafa L Kozik
email: rafal.kozik@utp.edu.pl

Robert M Lodzikowski

Micha L Choraś

Netflow-based Malware Detection and Data Visualisation System

Keywords: cyber security, anomaly detection, botnet, NetFlow, visualisation

This paper presents a system for network traffic visualisation and anomalies detection by means of data mining and machine learning techniques. First, this work describes and analyses existing solutions in the field of network anomalies detection in order to identify adapted techniques in that area. Afterwards, the system architecture and the adapted tools and libraries are presented. Particularly, two different anomalies detection methods are proposed.

The key experiments and analysis focus on performance evaluation of the proposed algorithms. In particular, different setups are considered in order to evaluate such aspects as detection effectiveness and computational complexity. The obtained results are promising and show that the proposed system can be considered as a useful tool for the network administrator.

Introduction

Nowadays, one of the cybersecurity challenges is to counter the malicious software [START_REF] Michal | A Practical Framework and Guidelines to Enhance Cyber Security and Privacy[END_REF]. Usually, malware samples are carefully crafted pieces of computer programs that aim at staying dormant while performing detailed surveillance of infected infrastructures and assets. Infected computers commonly connect together over the telecommunication network and form so-called botnet that can be easily centrally controlled by the cybercriminals for different malicious purposes such as DDoS attacks, SPAM distribution, sensitive data thefts, extortion attacks, etc.

In order to combat such cyber threat, one may use different solutions. However, commonly used anti-virus software may not be efficient enough to protect the network. An example is the case of the polish financial sector problem that happened in 2017 [START_REF]Polish Banks Hacked using Malware Planted on their own Government Site[END_REF]. During that attack, the largest system hack in the country's history took place and several banks in Poland have been infected with malware. This particular malware was a new strain of malicious software which has never been seen before in live attacks and it had a zero detection rate on VirusTotal.

The advancements in machine learning and data mining techniques in the area of Big Data introduces new tools supporting the fight against the malware. Therefore, in this research, we analyse existing techniques for botnet detection. Moreover, we propose the system that adapts different pattern extraction techniques, classification and visualisation methods.

The main contribution of this work is a proposal of a tool enhancing the cyber security of local area network. The tool intends to support network administrator in network traffic analysis by providing visualisation, data mining and feature extraction capabilities. In the current version of the system we have provided (i) two different pattern extraction algorithms, (iii) a variety of data mining algorithms available via Weka [START_REF]WEKA Data Mining Software[END_REF] library, (iv) a visualisation module.

The paper is structured as follows. First, we provide an overview of existing solutions and methods for botnets detection. Next, we propose system architecture and different pattern extraction and classification methods for NetFlow analysis. The experiment section presents evaluation methodology and obtained results. This paper is concluded with final remarks and plans for the future work.

Related Work

Commonly the signatures (in form of reactive rules) of an attack for a software like Snort [START_REF] Snort | Project homepage[END_REF] are provided by experts from a cyber community. Typically, for deterministic attacks, it is fairly easy to develop patterns that will clearly identify the particular attack. It often happens when given malicious software (e.g. worm) uses the same protocol and algorithm to communicate trough network with command and control centre or other instance of such software. However, the task of developing new signatures becomes more complicated when it comes to polymorphic worms or viruses. Such software commonly modifies and obfuscates its code (without changing the internal algorithms) in order to be less predictive and hard to detect.

The development of an efficient and scalable method for malware detection is currently challenging also due to the general unavailability of raw network data. Therefore, this aspect while being related to users privacy and administrative and legal reasons causes additional difficulties for research and development [START_REF] Andrysiak | Network Traffic Prediction and Anomaly Detection Based on ARFIMA Model[END_REF][START_REF] Michal | Correlation Approach for SQL Injection Attacks Detection[END_REF].

Currently, the common alternative is so-called NetFlow [START_REF] Claise | Cisco Systems NetFlow Services Export Version 9[END_REF] data that is often captured by ISPs for auditing and performance monitoring purposes. Since NetFlow samples do not contain any sensitive data they are widely available. However, the fact that this kind of samples is lacking raw content of network packets is the disadvantage.

In the literature, there are different approaches focusing on the analysis of NetFlow data. In [START_REF] Francis | Bottrack: Tracking botnets using netflow and pagerank[END_REF][START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF] authors focused on computational paradigms (e.g. MapReduce) for NetFlow data analysis and malware detection. On the other hand, in [START_REF] Lakhina | Diagnosing network-wide traffic anomalies[END_REF] [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF] author proposed statistical techniques for feature extraction from groups of network flows.

The BClus [START_REF] Garcia | An Empirical Comparison of Botnet Detection Methods[END_REF] method uses behavioural approach for botnet detection. It aggregates NetFlows for specific IP addresses and clusters them according to statistical characteristics. The properties of the clusters are described and used for further botnet detection. Another approach is used in BotHunter [START_REF]BotHunter homepage[END_REF] tool. It monitors the two-way communication flows between hosts within internal network and the Internet. BotHunter employs Snort intrusion detection system. It models an infection sequence as a composition of participants and a loosely ordered sequence of network information exchanges. In the Fig. 1 the general overview of the system design is presented. The collected raw data is processed in order to extract the NetFlows. The NetFlow is a standardised format for describing bidirectional communication and contains such information as IP source and destination address, destination port, amount of bytes exchanged, etc. The extracted NetFlows are stored in the database for further processing, so that the data mining and feature extraction methods currently work in the batch processing mode. However, in the future, we plan to allow the system to analyse directly the streams of data containing the raw NetFlows.

The single NetFlow usually does not provide enough evidence to decide whenever the particular machine is infected or if the particular request has malicious symptoms. Therefore, it is quite common [START_REF] Garcia | An Empirical Comparison of Botnet Detection Methods[END_REF] that NetFlows are aggregated in so-called time windows so that more contextual data can be extracted and malicious behaviour recorded (e.g. port scanning, packet flooding effects, etc.). In order to do that different statistics can be extracted for each time window. In the current version of the proposed system, we have implemented two different methods for pattern extraction (the Feature Extraction block on the diagram). These methods have been described in the consecutive subsections. In general, these methods produce the feature vectors that are further used to learn different ML algorithms (the Data Mining and Machine Learning block on the diagram). The machine learning algorithms are available via the Weka[3] library.

The system is also facilitated with graphical user interface (indicated as GUI on the diagram) which allows the network administrator to visualise different statistical properties of the analysed traffic (e.g. amount of data generated by specific IP addresses or the most active ones) as well as classification results. Some aspects of the visualisation process have also been described in separate section.

In order to evaluate the effectiveness of different algorithms, we have used CTU-13 dataset. It contains different scenarios representing different infections and malware communication schemes with command and control. Therefore, in this paper, we do not consider the problem of the realistic testbed construction.

Method 1

The first feature extraction method aggregates NetFlows in a time window (in this approach we use 1-minute long time windows). One of the reasons behind the aggregation process is the context identification in order to capture relevant behaviours of different hosts. For each time window the following statistics are calculated:

number of NetFlows total sum of transferred bytes average sum of transferred bytes per NetFlow number of unique destination IP addresses One of the advantages of this approach is the fact that the number of features vectors is equal to the number of time windows. Therefore, for the short scenarios the size of the resulting dataset will be small and thus the machine learning process will be faster.

However, one of the obvious drawbacks is the fact that for this approach it is impossible to identify the IP address of the infected machine because the system will only signal that particular time window should be considered anomalous.

Method 2

The second feature extraction method, similar to the previous one, aggregates NetFlows in the time windows. However, for each time window, we additionally group the NetFlow by IP source addresses. For each group (time window, IP source address) we calculate the following statistics:

number of flows sum of transferred bytes average sum of bytes per NetFlow average communication time between unique IPs number of unique IP addresses number of unique destination ports most frequently used protocol (e.g. TCP, UDP) by specific IP source address In contrast to the previous method, the advantage of this approach it the fact that it allows the network administrator to identify the possibly infected IP addresses.

Machine-learning module

In our research, we have selected different machine learning algorithms available in the WEKA software package [START_REF]WEKA Data Mining Software[END_REF]. We have considered such algorithms as NaiveBayes, Logistic, MultilayerPerceptron, SimpleLogistic, IBk, Classifica-tionViaRegression, LogitBoost, RandomCommittee, RandomizableFilteredClassifier, JRip, PART, J48, RandomForest, RandomTree. During the experiments, we have used different configurations of the algorithms in order to obtain optimal results.

Data Visualisation

The visualisation module is dedicated for network administrator in order to facilitate the in-depth analysis of network traffic. Different figures allow for visual detection of possibly anomalous network situations (e.g. port scanning). The examples of GUI screenshots (for the same scenario) has been shown in Fig. 2 and Fig. 3. The system allows also the administrator to visualise:

number of NetFlows for different time windows amount of bytes transferred for specific search criteria destination port utilisation results of classification process dependencies analysis between possibly infected hosts and other ones

Experiments

Validation Methodology

For the evaluation purposes, we have adapted stratified 10-fold cross-validation methodology. The method was used to assess the TPR -true positives, and FPR -false positives rates.

True Positives Ratio (TPR) is defined as the number samples (feature vectors) identified correctly as infected (True Positives -TP) divided by the number of all samples that are infected (True Positives + False Negatives).

T P R = T P T P + F N (1)
False Positives Ratio (FPR) is defined as the number of samples identified wrongly as infected (False Positives -FP) divided by the number of all clean samples (True Negatives + False Positives).

F P R = F P T N + F P (2)
The procedure for effectiveness evaluation is following:

-The dataset representing particular scenario in the CTU-13 dataset is divided into 10 parts. -The 9 parts are used for training the algorithms while the remaining part is used for the evaluation purposes. -The NetFlows are grouped in time windows.

-For two extraction methods, the feature vectors are extracted (according to the procedure described in 3). -Different ML algorithms are trained on the training dataset and the results are obtained on the testing dataset.

The algorithms are learnt and evaluated 10 times and the obtained results are averaged.

Evaluation Dataset

For the evaluation purposes we have used CTU-13 dataset [START_REF] Garcia | An empirical comparison of botnet detection methods[END_REF]. This dataset includes different scenarios, which represents different types of attack scenarios including a different type of botnets. Each of these scenarios contains collected traffic in form of NetFlows. As it is explained in [START_REF] Garcia | An empirical comparison of botnet detection methods[END_REF], the data was collected for the realistic testbed. We have presented the results and the discussion for one of the most problematic scenarios. Each of the scenarios has been recorded in a separate file as NetFlow using CSV notation. Each of the row in a file has 15 attributes (columns): It must be noted that the "Label" field is an additional attribute provided by authors of the dataset. Normally, the NetFlow will have 14 attributes and the "Label" will be assigned by the classifier.

Results

The proposed methods have been evaluated on the scenario concerning the Rbot malware. According to the scenario description, the malware realises ICMP DDoS attack.

The values of TPR and FPR ratios have been presented in Table 1. The results obtained with the second method for feature extraction have achieved better results. The average effectiveness of botnet detection for all the classifiers for the first method is 47.0% while for the second method is 63.0%. However, the classifiers combined with the first method for pattern extraction yielded high FP ratios.

The conclusion from this experiment is that the second feature extraction method combined with RandomForest (or RandomCommittee) allowed us to achieve 66.7% of malware detection while having no false positives.

Conclusions

In this paper, we have proposed preliminary results of the malware detection method. Our approach relies on the analysis of malware network activity that is captured by means of NetFlows. We have presented the architecture of the proposed system. The current implementation includes two methods for pattern extraction that analyses the NetFlows in disjoint time windows. The extracted feature vectors have been used to train different machine learning algorithms. The methods have been evaluated on the publicly available dataset. Future work will be dedicated to the evaluation of scalability of the proposed methods and further improvements towards online machine learning.

Fig. 1 .

 1 Fig. 1. System architecture diagram

Fig. 2 .

 2 Fig.2. An example of the proposed system visualisation capabilities for the selected scenario. The figure presents the amount of traffic generated on average by all hosts (green line), by the most active hosts (orange line), and the infected host (red line).

Fig. 3 .

 3 Fig. 3. The figure presents the number of established connection by different hosts for the analysed scenario. It can be noticed that the infected host establishes suspiciously high number of connections.

-

  StartTime -Start time of the recorded NetFlow, -Dur -Duration, -Proto -IP protocol (e.g. UTP, TCP), -SrcAddr -Source address, -Sport -Source port, -Dir -Direction of the recorded communication, -DstAddr -Destination Address, -Dport -Destination Port, -State -Protocol state, -sTos -Source type of service, -dTos -Destination type of service, -TotPkts -Total number of packets that have been exchanged between source and destination, -TotBytes -Total bytes exchanged, -SrcBytes -Number of bytes send by source, -Label -Label -label assigned to this NetFlow (e.g. Background, Normal, Botnet)

Table 1 .

 1 Effectiveness of different algorithms for Rbot malware activity detection.

			Feature extraction method
	Algorithms	Method 1		Method 2
		TPR	FP	TP	FP
	NaiveBayes	60,0%	33,3%	50,0%	0,2%
	Logistic	40,0%	50,0%	33,3%	0,0%
	Multilayer Perceptron	40,0%	25,0%	33,3%	0,0%
	SimpleLogist	0,0%	0,0%	25,0%	0,0%
	IBk	20,0%	41,7%	58,3%	0,0%
	CVR	40,0%	25,0%	33,3%	0,0%
	Logit Boost	40,0%	16,7%	33,3%	0,0%
	Random Committe	20,0%	33,3%	66,7%	0,0%
	JRip	0,0%	16,7%	50,0%	0,0%
	PART	60,0%	50,0%	50,0%	0,0%
	J48	60,0%	50,0%	50,0%	0,0%
	RandomForest	40,0%	25,0%	66,7%	0,0%
	RandomTree	20,0%	16,7%	58,3%	0,0%


Giridhar Maji
email: giridhar.maji@gmail.com

Soumya Sen
email: iamsoumyasen@gmail.com

Amitrajit Sarkar
email: amitrajit.sarkar@ara.ac.nz

Share Market Sectoral Indices Movement Forecast with Lagged Correlation and Association Rule Mining

Keywords: stock indices prediction, lagged correlation, association rule mining

This paper analyses the correlation between two different sectoral indices (e.g. between Automobile sector index and between Metal sector index, between Bank sector index and IT sectoral index etc.) in a time lagged manner. Lagging period is varied from 1 day to 5 days to investigate if any selected sector has lagged influence over any other sectoral index movement. If any upward/downward movement of a sectoral index (sector A) is correlated with similar upward/downward movement of another sectoral index (Sector B) with a time lag of ‗d' days, then with association rule mining support and confidence is calculated for the combination. If d is the lag for which support and confidence is maximum then depending on the higher correlation as well as higher support and confidence value it is possible to forecast future (d days ahead of current day) movement of sector B based on present day movement of sector A. This model first uses correlational analysis to identify the level of dependence among two different sectors, then considers only those sectors having higher value of correlation for association rule mining. Those sector are not considered for which combination correlation is very low or 0.

This model has been tested with Indian share market data (NSE sectoral index data of 6 sectors) of 2015. Result shows it is possible to predict in short term (1 to 5 days in future) price movement of sectoral indices using other lagged correlated sector price index movement.

Introduction

Predicting the future stock prices are the most important queries for the investors in share market. Many different techniques, mathematical formulation, genetic algorithm (GA) based models, neural network models, machine learning based techniques etc. have been proposed and tested with mixed success [START_REF] Liu | A new investment strategy based on data mining and Neural Networks[END_REF][START_REF] Inthachot | Artificial Neural Network and Genetic Algorithm Hybrid Intelligence for Predicting Thai Stock Price Index Trend[END_REF][START_REF] De Oliveira | Applying Artificial Neural Networks to prediction of stock price and improvement of the directional prediction index-Case study of PETR4, Petrobras, Brazil[END_REF][START_REF] Dutta | PREDICTION OF STOCK PERFORMANCE IN INDIAN STOCK MARKET USING LOGISTIC REGRESSION[END_REF]. Predicting the future price of some stock is inherently difficult as the price movement depends on large number of issues gre tly of macro-economic, micro-economic, technical parameters as well as a lot of unknown parameters which come in to the context all of a sudden. Future stock price of a company becomes stochastic due to difference in perception about the future of the company among investors. A group of investor foresees a fu-ture uptrend or good earnings for the company and they expect its stock price to go up in near future. Therefore they buy at current price to sell at some higher price in future and earn profit. At the same time some other groups of investors with a perception th t the comp ny's future outlook is not so good nd stock prices m y f ll in future, they sell with current price with a view to latter buy the same or more quantity of shares with lower price in future to earn profit. The basic idea behind technical analysis is that current stock price of a company incorporates impacts and effects of economic, financial, political and psychological factors. It studies the historical stock prices and assumes that the future trend will follow the past behavior. The technical analysis offers information about the possible future evolution of the stock market. Technical analysis is done based on a lot of different technical indicator parameters such s ‗n-d ys moving ver ge' (where ‗n' c n be 5/10/20/50 etc. d ys), ‗n-days weighted ver ge', MACD, relative strength index, momentum etc. along with priceto-earnings ratio, dividend yield, profit margin , return on investment etc. [START_REF] Inthachot | Artificial Neural Network and Genetic Algorithm Hybrid Intelligence for Predicting Thai Stock Price Index Trend[END_REF][START_REF] De Oliveira | Applying Artificial Neural Networks to prediction of stock price and improvement of the directional prediction index-Case study of PETR4, Petrobras, Brazil[END_REF][START_REF] Imandoust | Forecasting the direction of stock market index movement using three data mining techniques: the case of Tehran Stock Exchange[END_REF][START_REF] Dutta | PREDICTION OF STOCK PERFORMANCE IN INDIAN STOCK MARKET USING LOGISTIC REGRESSION[END_REF]. But investor's perception also depends on rumors & market speculation and some unforeseen sudden big events and their unknown reaction towards stock prices of different comp nies. This l ter p rt m kes the -sell‖ or -buy‖ decision of n investor a stochastic random event but due to the technical parameters it is also not totally unpredictable.

In any Stock market listed companies are categorized into different sectors depending on the business domain the company belongs to. We have considered the following six sectors for our study: Banks, Automobiles, IT & Software, Metals, Pharmaceuticals and FMCG (Fast Moving Consumer Goods). These different sectors have sectoral index to represent their aggregated trends in a stock exchange. It is similar to the stock exchange index (for example SENSEX, NIFTY in BSE and NSE). These sectoral indices react with different external and internal events differently and hence their movement. Same external event may affect different industry sector differently. Depending on a many different factors some sectoral index moves in positive direction while in the same time some other sector moves into the negative zone (or may remain neutral). As an example when dollar value increases with respect to Indian Rupee (INR) almost all export companies of India gains and IT sectors majorly get most of the benefits as they earn in dollar and spend in INR. At the same time importers incur losses. This is a very complex relationship to measure. In this research work we aim to focus on this in terms of following issues:

1. If these reactions with the external factors are correlated between the sectors. 2. Identifying how different sectors are related? They may be highly correlated, correlated, neutral or not co-related at all. 3. Among the highly correlated sector pairs which are positively correlated and which are negatively correlated. 4. Is there any correlation among the highly correlated sector pairs with some days l g, i.e. if tod y's sectoral index movement of sector-A is correlated with sectoral index movement of sector-B on d days in future. If we find a high correlation among two different sectors with a time lag of d days then we can forecast sectoral index movement of Sector-B,‗d' days ahead.

In the next sub section we briefly discuss about Indian share market as well as sectoral indices that are considered in this case study. Then we will discuss about Association rule mining techniques along with support and confidence that will be used in our analysis.

An Overview of Indian Share Market

Two most important stock exchanges in India are BSE and NSE. The Bombay Stock Exchange (BSE) is one of the oldest stock exchanges in India and one of the top stock exchanges globally with respect to number of listed companies and market capitalization. The 30 company index from BSE is known as SENSEX or BSE30 is a stock market index of 30 well established and financially sound companies listed on BSE. These are some of the largest and most actively traded stocks, hence it is considered as representative of various industrial sectors of the Indian economy. It is published since 1st January 1986 and regarded as the pulse of the domestic stock markets in India [START_REF][END_REF]. The NIFTY 50 index is n tion l stock exch nge of Indi 's benchmark stock market index for Indian equity market [10]. It covers 22 sectors of Indian economy. As SENSEX and NIFTY is used to understand average trend and movement of BSE and NSE for almost all financial purposes, each stock exchange has industry sectors and each sector has many sectoral index(s) that reflect the behavior and performance of the concerned sector. In this study following 6 sectors are considered: Auto, Bank, Pharma, FMCG, IT and Metal. All index values are taken from NIFTY industrial sectors. Different sectoral index(s) consists of different number of representative company stocks. For example NSE Auto Index consists of 15 stocks and NIFTY bank index comprises of 12 banking sector stocks.

Statistical Correlation

Let Xt and Yt are two given time series closing prices for N days. If we consider a lag of d days between them then co-variance between the two series is defined as-∑ where μ X and μ Y are the sample means of the time series X and Y. Cross correlation between them is defined as-

Where

x , and Y ;

Sx , Sy being the sample standard deviations of series X and Y. The value of r varies between +1 to -1. Depending on the sign of r following can be inferred:

 Positive correlation: r value closer to +1 signifies strong positive correlation between the variables. An r value of exact +1 indicates a perfect positive fit. Any positive r values between 0 and +1 indicates that the relationship between x and y variables are such that with increase in values of X, Y value also increases.

 Negative correlation: If x and y have a strong negative linear correlation, r is close to an r value of exactly -1 indicates a perfect negative fit. Negative values indicate a relationship between x and y such that as values for x increase, values for y decrease.

 No correlation: r value closer to 0 signifies that there is no linear correlation or a very weak correlation. In other words x and y values are completely un-correlated and there is a random, relationship between the two variables x, y.

A perfect correlation of ± 1means that all the data points are lying on a straight line. Correlation coefficient ‗r' does not have a dimension; hence it does not depend on the units used. Generally an ‗r' value of greater than 0.8 is considered as highly correlated and less than 0.5 is considered weakly correlated. A point to remember is th t bove threshold v lues v ry with the ‗type' of d t used. Gener lly with noisy data less threshold values are considered.

Association Rule Mining

Data mining, an important part of knowledge discovery in databases (KDD) process employs many different techniques for knowledge discovery and prediction such as classification, clustering, sequential pattern mining, association rule mining and analysis. Nowadays it is used in almost all the data driven decision models such as business analysis, strategic decision making, financial forecasting, future sales prediction etc. Agrawal [START_REF] Agr W L, R Kesh | Mining ssoci tion rules between sets of items in large databases[END_REF] first introduced association rules for frequent pattern mining among items in large transaction dataset. They introduced the Apriori principle which says: Any subset of a frequent itemset must be frequent. Hence it can also be said in another term as: No superset of any infrequent itemset should be calculated for further processing. From the frequent item-sets a set of strong rules are calculated. Strength of a rule is measured based on support and confidence values. Not all frequent itemsets are considered as strong, only those with a minimum support and confidence are considered for the next step. This Aprori principle elimin tes the ‗curse of dimensionlity' nd m kes computations feasible. Let us consider an association rule :{ bread, sugar} => {butter} It indicates if people are buying bread and sugar then they may also buy butter. Association rule mining (ARM) is used here to show the relationship between different item-sets. It is also known as market basket analysis. An association rule is expressed in the form of an implication as: X → Y, where X and Y are disjoint item-sets, i.e. ∩ Y = ∅.

Support and confidence measures the strength of an association rule. Support is used to find how frequently a rule is applicable, whereas confidence finds how frequently items in itemset Y also appear in transactions containing itemset X. The formal definitions of these metrics are: Support is the fraction of the total transactions that matches the rule. It is defined for rule R as the ratio of the number of occurrence of R, given all occurrences of all rules [START_REF] De Oliveira | Applying Artificial Neural Networks to prediction of stock price and improvement of the directional prediction index-Case study of PETR4, Petrobras, Brazil[END_REF].

Support (X → Y) = P (X U Y) =
Support of the rule {tire, auto accessories} → {Automotive Service} is 0.98 signifies that 98% of people who purchase tires and auto accessories also get automotive services done.

Confidence signifies the strength of the rule. The confidence of a rule X -> Y, is the ratio of the number of occurrences of Y given X, among all other occurrences given X. [START_REF] De Oliveira | Applying Artificial Neural Networks to prediction of stock price and improvement of the directional prediction index-Case study of PETR4, Petrobras, Brazil[END_REF].

Confidence (X -> Y) = P (Y|X), the probability of Y given X = A minimum support threshold value (min_sup) is generally defined to select the point of interest. It is used to discard those itemsets with support less than min_sup as that may not be interesting from business perspective. Confidence gives an idea of the conditional probability of Y given X. It is a measure of reliability of the inference made by a rule. Higher value of confidence implies that it is more likely for Y to be present in transactions that contain X.

One important point to consider is that not all strong rules (based on support and confidence values) are necessarily interesting. As we can see support-confidence framework can be misleading; it can identify a rule (A=>B) as interesting (strong) when, in fact the occurrence of A might not imply the occurrence of B. Correlation Analysis provides an alternative framework for finding interesting relationships and allows to improve understanding of meaning of some association rules . Measure of interest or Lift is one of such correlational measure of association rules. Lift is defined as [START_REF] Brin | Dynamic itemset counting and implication rules for market basket data[END_REF] :

If lift = 1 i.e. P (AꓴB) = P (A) P (B) , then the occurrence of itemset A is independent of the occurrence of B; or else both the item-sets are dependent and correlated. If lift value is less than 1 then A and B are negatively correlated i.e. occurrence of one likely implies the absence of the other. A lift value of more than 1 implies positive correlation between A and B.

Related Study

Several researches have been done over the period on predicting future stock price or price movement direction (upward or downward) along with trend analysis based on mainly different statistical modeling [START_REF] De Oliveira | Applying Artificial Neural Networks to prediction of stock price and improvement of the directional prediction index-Case study of PETR4, Petrobras, Brazil[END_REF][START_REF] Reddy | Prediction of Stock Market indices-Using SAS[END_REF][START_REF] Liao | Data mining investigation of co-movements on the Taiwan and China stock markets for future investment portfolio[END_REF][START_REF] Fournier-Viger | SPMF: Open-Source Data Mining Platform[END_REF][START_REF] Fonseka | A Data mining algorithm to analyse stock market data using lagged correlation[END_REF][START_REF] Rusu | Forec sting methods nd stock m rket n lysis‖[END_REF][START_REF] Dutta | PREDICTION OF STOCK PERFORMANCE IN INDIAN STOCK MARKET USING LOGISTIC REGRESSION[END_REF]. Rusu et al. discussed stock forecasting [START_REF] Rusu | Forec sting methods nd stock m rket n lysis‖[END_REF] methods used by classical approaches such as fundamentalists and chartists and at the same time discussed various recent stochastic methods like white noise, random walk, auto-regressive models etc. In another research work [START_REF] Reddy | Prediction of Stock Market indices-Using SAS[END_REF] various models used for stock price prediction using SAS© System tools. Models like Time Series analysis, Auto Regression (AR), Exponential Smoothening, Moving Average (MA) etc. has been discussed along with illustrated procedure for FORECAST and ARIMA (Autoregressive Integrated Moving Average) models. Dutta et al. [START_REF] Dutta | PREDICTION OF STOCK PERFORMANCE IN INDIAN STOCK MARKET USING LOGISTIC REGRESSION[END_REF] used logistic regression methods with various financial ratios as independent variables to cluster selected 30 stocks into good and bad performing groups based on rate of return. Another model CARIMA [START_REF] Wichaidit | Predicting SET50 stock prices using CARIMA (Cross Correlation ARIMA)[END_REF] (Cross Correlation Autoregressive Integrated Moving Average) was proposed to predict short term stock price. Main idea of CARIMA is to find the most highly correlated stock to predict the target price. Stock prices of SET50 from Stock Exchange of Thailand has been used to test the effectiveness of the model with better price trend prediction with similar % MAE (Mean Absolute Error) than ARIMA model. In another study work authors investigated stock index comovement between two different countries namely Taiwan and Hong Kong using association rules and cluster analysis [START_REF] Liao | Data mining investigation of co-movements on the Taiwan and China stock markets for future investment portfolio[END_REF]. They have used 30 categories of stock indices as decision variables to observe the behavior of stock index association. This study tried to identify the correlation between the similar category sectoral index movements between two different countries and that also used to recommend investment portfolio as a follow up reference. Forecasting horizon is the time lag between the price movement of independent stock price and correlated stock price. If two stocks are highly correlated with a delay of d days then following the trend of former stock, l tter one's trend c n be predicted d d ys he d. The bove method is proposed with suitable generic algorithm for automated data preprocessing and analysis using correlation [START_REF] Fonseka | A Data mining algorithm to analyse stock market data using lagged correlation[END_REF]. This model has predicted with 67% accuracy while tested with real stock market data. Authors in [START_REF] Mahajan | APPLICATION OF DATA MINING TOOLS FOR SELECTED SCRIPTS OF STOCK MARKET[END_REF] has analyzed correlation between stock price fluctuation, gold price and US dollar price along with association rule induction methods amongst different stocks of same sector. A rigorous mathematical discussion on ten different data mining techniques such as Support vector machine (SVM), Least squares support vector machine (LS-SVM), Linear discriminant analysis (LDA), Quadratic discriminant analysis (QDA), Logit model, neural network, Bayesian models etc. has been discussed in [START_REF] Ou | Prediction of stock market index movement by ten data mining techniques[END_REF]. In another work authors proposed and evaluated a stock price prediction based recommender system [START_REF] Nair | Clustering stock price time series data to generate stock trading recommendations: An empirical study[END_REF] that used historical stock prices as input to the system and applied regression trees for dimensionality reduction and Self Organizing Maps (SOM) for clustering. The proposed system helped investors with possible profit-making opportunities with buy or sell recommendations.

The main objective of this research work is to measure the association between sectors pair-wise instead of specific stock. These would provide an integrated view of stock market including several business sectors. Here we study time lagged prediction model for the analysis on the well-established, industry defined sectors or domains of businesses like automobile, banking, reality, metal etc. As we identify the sectors instead of specific stock we able to consider number of stocks at a time and could choose the top performing stocks of the sector as required. The sectoral index of each sector has been used to find the correlation in our study. This way total number of possible sector pair reduces drastically and at the same time individual investors can gain an idea to which sectoral stocks are going to give good earning in short-term. Similarly mutual fund managers can also use it to diversify their sectoral portfolio as the movement trend of sectors is going to be identified.

Methodology

Research Framework

The research framework of this study is shown in Fig. 1. It involves collecting index values of 6 industrial sectors from NSE. Each trading days closing prices are used as the raw input data for our analysis. Initial time series plotting of sectoral indices of selected sectors gives a basic graphical visualization of the raw data about their co-movement pattern. Fig 2 shows the time series plot of the selected sectors. Raw dataset is then processed into proper format to be used in association rule mining and for correlation analysis.

Correlation Analysis

Our data set consists of day wise closing prices of 6 different sectoral indices of 2015. We then calculated pairwise correlation for all the possible pair of sectors with a lag of 0 day to 5 days. A delay of 0 day means same day correlation between the two sectoral indices.

Let's s y we h ve tot l of N d y closing price of ny two sector S1 nd S2 s X = {p 1 ,p 2 …p n } for sector S1 and Y = {p 1+d , p 2+d ,… p n+d }for sector S2 where prices are from (1+d) d y to (n+d) d y i.e. ‗d' d ys he d of the prices in .

Correl tion with del y of ‗d' d ys is c lcul ted s the correl tion between the two data arrays X,Y as below: Microsoft excel spreadsheet based statistical tools has been used to derive the results shown in table 1 and Fig. 3.

In this study a correlation value of r >=0.8 has been considered as good correlation nd correl tion v lue of r<=0.5 h s been neglected s ‗we k or no correl tion'. Based on the correlation between different sectoral movements sector pairs are selected for further analysis using association rule mining. Only sector pairs with high positive or negative correlation are considered for further analysis as discussed in the next sub section.

Data Preprocessing and Encoding

Let's consider d t set Ps = { pi}; i = 1 to N is the sectoral index closing values of some sector S; N being the number of trading days considered. Whole dataset contains such sectoral index closing prices of 6 sectors.

Let's lso define toler nce ∆t as the percentage of value up to which we ignore price changes i.e. we take consider it as no-change if percentage price change is less th n equ ls to ∆t. For our experiments we have considered ∆t =0.2 as it gives good results. We have varied it from 0 to 1 and selected 0.2.

Step 1: change in index values are calculated for each sector as follows: ∆pi = pi+1 -pi Step 2: Different sectoral index values has different base and movement amount in absolute values so to normalize all sectors we consider percentage change. It is calculated as below: Ci = (∆pi/pj). Ci value may be positive or negative depending on the price movement of the sectoral index.

Step 3: Sectoral index price percentage change is encoded as follows:

{

Here v i becomes +1 if change is in positive direction i.e. sectoral index moves upwards. It becomes -1 if change is in negative direction i.e. sectoral index moves downward. A value of 0 is assigned if the change in percentage value is below considered toler nce limit. We consider it s ‗no-ch nge' or ‗no-movement'.

Mining Association Rules with Apriori

Apriori is the most frequently used frequent itemset mining algorithm with good time bound as already discussed in the section 2.3 above. We adapt the association rule mining using Apriori from [START_REF] Dongre | The role of Apriori algorithm for finding the association rules in Data mining[END_REF] and used lift value [START_REF] Brin | Dynamic itemset counting and implication rules for market basket data[END_REF] as a measure of interest of the mined rules.

Generate Input Transaction set:

For days d = 0 to 5 Do For each sector pair S1, S2 Generate transactions T as:

T d = {v i s1 , v i+d s2 }; i = 1 …N ; d is the day lag.
T d is a set of 2 item itemsets with possible items as ‗+1', ‗-1' and ‗0'. For example if sector S1has positive upward movement from i th day to (i+d) th day and sector S2 has a negative movement between i th day to (i+d) th day then i th itemset in Td becomes (+1,-1), similarly for (i+1) th day's itemset will be (+1,+1) if both the sector shows an upward movement from (i+1) th day to (i+1+d) th day.

Apriori algorithm is now suitably modified to be used on above generated transactions T = {Td}; d = 0 to 5, to find the association between any two sectors movement trend. Here we restrict our analysis in finding association between any two sectors, where index movement direction of one sectoral index is used to find the probability of movement direction of another sectoral index. It is possible to use the same algorithm to find association rules where multiple sectoral index movements will be used to predict the movement of some another sectoral index.

Let min_s = minimum threshold support for an itemset to be considered. It is used only to retain healthy rules.

In a similar way min_c = minimum threshold for confidence measure.

L k is the k-element itemset generated from k-1 element item-sets using Apriori principle.

Deriving the Association rules with Apriori

1. Find all individual elements (1 element itemset, L1)from Transactions dataset Td with support more than min_s. L1 consists of only ‗+1', or ‗-1' or ‗0'.

2. DO a. Use previously found j element itemset (Lj) to find all (j+1) element itemsets with a minimum support of min_s.

b. This becomes the set of all frequent (j+1) itemsets that are interesting c. Divide each frequent itemset X into two parts antecedent (LHS) and consequent (RHS). The Association rule becomes of the form R: LHS->RHS.

d. The confidence of such a rule is calculated as:

Confidence (R) : = support(X) / support(LHS)
e. Discard all rules whose confidence is less than min_c.

3. WHILE itemset size less than k.

Rank the Generated Association Rules

Rank all the derived association rules as per there support and confidence value. Top K rules are of importance. Value of K depends on the investors risk profile and preferences.

Results and Analysis

We have used open source java based frequent pattern mining library SPMF [START_REF] Fournier-Viger | SPMF: Open-Source Data Mining Platform[END_REF] for deriving association rules with apriori and suitably modified to incorporate other required changes. For our experiments we have considered minimum support as 0.2, minimum confidence value as 0.4 and minimum lift as 0.1 with acceptable results. Fig. 2 shows the initial time series plotting of different sectors where co-movement patterns can be visually seen. One important point to consider regarding Fig. 2 is that it shows same day co-movement pattern, hence it cannot be used for prediction analysis. So next logical step is to introduce some days lag between any two sectoral index movements and find if there is any correlation. Then correlation coefficient among different sector pairs with different delay period from 0 day to 5 days has been calculated as shown in table 1. Different correlation values are plotted against delay in Fig. 3 to show the positive, negative as well as no-correlation between different sectors with varying delays. It is observed that a day lag of 0 denotes same day index movement correlation. Hence high same day correlation does not help in forecasting as that cannot be used to gain profit. Finally table 2 shows the top 15 association rules that re mined using the bove mentioned method nd r nked s per rules' support nd confidence measure. As a measure of interest of the rules lift values are also calculated and shown. From the results we see that amongst considered 6 sectors metal and FMCG go hand in hand where as auto index has very low co movement with other sectors considered. IT and pharma index also shows similar pattern. From pure economic point of view both IT and pharma sector greatly dependent on dollar exchange value and with the changes in dollar price both the sector reacts similarly. Auto index movements were very low during the year 2015 than all other sectors and it again can be attributed to non-reduction of car loan interest rates during the year. So this gives out some interesting correlation between different sectors. Rule R0 is interpreted as if metal index goes down then after 5 days pharma sector may be up with a support of 42% and confidence of 49.5%. Similarly rule R2 indicates if auto index moves up then with a forecasting horizon of 5 days metal index may move downwards. Corresponding lift values also support our prediction as lift values are less than 1 so it implies negative correlation.

Conclusion and Future work

Association rule mining along with statistical correlation analysis has been applied on sectoral index dataset to investigate co-movement patterns among them. Aprori algorithm, a well-known frequent itemset mining tool has been modified and applied for the present analysis. This study finds that different sectoral indices are correlated among themselves. One more interesting finding is that there exists a time delayed lagged correlation between different sectoral indices. This correlation can be exploited to predict the future index movement direction with a forecast horizon of d days where d is the number of day lag considered. Hence this model can be used by different investors in balancing their portfolio to minimize risk as well as in deciding which sector to invest next. This model can be considered for short term investment as only prediction of next few d ys is possible using current d y's sector l index movements. Results shows that some sectors are completely un-correlated but some are highly correlated (positively or negatively) with correlation coefficient values more than 0.8.

Future work will include analysis considering all sectors at a time instead of only a single sector predicts another. For example in this study association rules of the form, R: S1->S2 is used for simplicity, but in future all possible rules of the form R: (S1…Sj)-> Sk, where ll other sectors jointly predicts some nother sector's movement can be studied. Artificial neural network models can also be considered in combination with association rules to predict the sectoral index movement. In this study only historical closing values of indices are considered but there are many other factors and features like trading volume, market capitalization, debt ratio etc. that can be considered for prediction.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Research framework followed in this study

Fig. 3 .

 3 Fig. 3. Correlations among six sectoral indices with a day lag of 0 day to 5 days.

Table 1 .

 1 Correlation values (r) among different sector pairs with different day lag.

	Day Lag->	0	1	2	3	4	5
	Auto-Bank	0.9638	0.9633	0.9625	0.9618	0.9611	0.9604
	Auto-FMCG	0.8827	0.8821	0.8813	0.8805	0.8796	0.8787
	Auto-Metal	-0.4220	-0.4228	-0.4238	-0.4248	-0.4257	-0.4266
	Auto-IT	0.9491	0.9491	0.9489	0.9488	0.9485	0.9482
	Auto-Pharma	0.9723	0.9725	0.9725	0.9725	0.9725	0.9725
	Bank-FMCG	0.8094	0.8089	0.8083	0.8076	0.8067	0.8058
	Bank-Metal	-0.2981	-0.2997	-0.3018	-0.3039	-0.3059	-0.3078
	Bank-IT	0.8779	0.8772	0.8764	0.8757	0.8748	0.8741
	Bank-Pharma	0.9226	0.9227	0.9226	0.9224	0.9223	0.9222
	FMCG-Metal	-0.6889	-0.6891	-0.6892	-0.6893	-0.6894	-0.6894

Table 2 .

 2 Top 15 Association rules generated

	(0.0 -1.0)
	r
					lag in days (d= 0 -5)
		Auto-Bank	Auto-FMCG	Auto-Metal	Auto-IT		Auto-Pharma
		Bank-FMCG	Bank-Metal	Bank-IT	Bank-Pharma	FMCG-Metal
		FMCG-IT	FMCG-Pharma Metal-IT	Metal-Pharma IT-Pharma
	Rule#			Delay	Association			Lift
		Sector pair		(days)	Rule	Supp	Conf
	R0	Metal-Pharma	5	-1 ==> 1	0.4198	0.4951	0.562
	R1	FMCG-Metal		2	-1 ==> 1	0.4106	0.4856	0.556
	R2	Auto-Bank		5	1 ==> -1	0.4033	0.4851	0.572
	R2	IT-Pharma		5	-1 ==> 1	0.3951	0.5161	0.562
	R3	FMCG-Pharma	3	-1 ==> 1	0.3918	0.4120	0.558
	R4	Metal-Pharma	2	-1 ==> 1	0.3902	0.4550	0.521
	R5	Bank-FMCG		5	-1 ==> 1	0.3827	0.4721	0.539
	R6	Auto-Bank		1	1 ==> -1	0.3806	0.4476	0.537
	R7	FMCG-Metal		1	-1 ==> 1	0.3765	0.4471	0.5111
	R8	FMCG-Pharma	2	-1 ==> 1	0.3699	0.4973	0.525
	R9	Bank-IT		5	-1 ==> 1	0.3663	0.4406	0.5228
	R10	IT-Pharma		2	-1 ==> 1	0.3659	0.4762	0.5223
	R11	Bank-FMCG		4	-1 ==> 1	0.3607	0.4444	0.5091
	R12	Metal-Pharma	4	-1 ==> 1	0.3607	0.4251	0.4825
	R13	FMCG-Pharma	4	-1 ==> 1	0.3566	0.4833	0.50833
	R14	FMCG-Metal		4	-1 ==> 1	0.3566	0.4244	0.4838


Lapo Cioni
email: lapo.cioni@stud.unifi.it

Luca Ferrari
email: luca.ferrari@unifi.it

Enumerative Results on the Schröder Pattern Poset

The set of Schröder words (Schröder language) is endowed with a natural partial order, which can be conveniently described by interpreting Schröder words as lattice paths. The resulting poset is called the Schröder pattern poset. We find closed formulas for the number of Schröder words covering/covered by a given Schröder word in terms of classical parameters of the associated Schröder path. We also enumerate several classes of Schröder avoiding words (with respect to the length), i.e. sets of Schröder words which do not contain a given Schröder word.

Introduction

In the literature several definitions of patterns in words can be found. In the present article we consider a notion of pattern which is rather natural when words are interpreted as lattice paths, by using each letter of the alphabet of the word to encode a possible step. The notion of pattern in a lattice paths investigated here has been introduced in [START_REF] Bacher | The Dyck pattern poset[END_REF][START_REF] Bernini | Pattern avoiding Dyck paths[END_REF], where it has been studied in the case of Dyck paths. Aim of the present work is to find some analogous enumerative results in the case of Schröder paths. In order to make this paper self-contained, we will now briefly recall the main definitions and notations concerning patterns in paths, and we introduce the basic notions concerning the Schröder pattern poset.

For our purposes, a lattice path is a path in the discrete plane starting at the origin of a fixed Cartesian coordinate system, ending somewhere on the x-axis, never going below the x-axis and using only a prescribed set of steps Γ . We will refer to such paths as Γ -paths. As a word, a Γ -path can be represented by the sequence of the letters encoding the sequence of its steps. In view of this, in the following we will often use the terms "path" and "word" referred to the same object. Classical examples of lattice paths are Dyck, Motzkin and Schröder paths, which are obtained by taking Γ to be the set of steps {U, D}, {U, D, H} and {U, D, H 2 }, respectively (see Figure 1). Here letters represents the steps U (p) = (1, 1), D(own) = (1, -1), H(orizontal) = (1, 0) and H 2 (orizontal of length 2 ) = (2, 0), respectively. Given a Γ -path P , its length is given by the final abscissa of P . Also important is the word length of P , which is the length of the word associated with P . For instance, the Schröder path in Figure 1 has length 22 and word length 17. Notice that the length of a Schröder path is necessarily even; for this reason it is sometimes more meaningful to refer to the semilength of a Schröder path.

Given two Γ -paths P and Q, we declare P ≤ Q whenever P occurs as a (not necessarily contiguous) subword of Q. In this case, we say that P is a pattern of Q. So, for instance, the Schröder path U H 2 U DDH 2 U H 2 H 2 D is a pattern of the Schröder path in Figure 1. When P is not a pattern of Q we will also say that Q avoids P . The set P Γ of all Γ -paths endowed with the above binary relation is clearly a poset.

In the case of Schröder paths, the resulting poset will be denoted S. It is immediate to see that S has a minimum (the empty path), does not have maximum and is locally finite (i.e. all intervals are finite). Moreover, S is a ranked poset, and the rank of a Schröder path is given by its semilength. An important fact concerning S is that it is a partial well order, i.e. it contains neither an infinite properly decreasing sequence nor an infinite antichain (this is actually a consequence of a well known theorem by Higman [START_REF] Higman | Ordering by divisibility in abstract algebras[END_REF]). Notice that this is not the case in another famous pattern poset, the permutation pattern poset, where infinite antichains do exist (see [START_REF] Spielman | An infinite antichain of permutations[END_REF]).

The present paper is devoted to the investigation of some structural and enumerative properties of the Schröder pattern poset. Specifically, in Section 2 we study the covering relation of S and in Section 3 we enumerate some classes of Schröder paths avoiding a single pattern.

We would like to remark that, even when Γ -paths are interpreted as words over a suitable alphabet, other kinds of patterns can be defined which are equally natural and interesting. Just to mention one of the most natural, one can require an occurrence of a pattern to be constituted by consecutive letters. This originates what is sometimes called the factor order, which has been studied for instance in [START_REF] Björner | The Möbius function of factor order[END_REF] (in the unrestricted case of all words on a given alphabet). Many papers, such as [START_REF] Bilotta | Avoiding cross-bifix-free binary words[END_REF], investigate properties and applications of this more restrictive notion of pattern, also extending it to the case in which the pattern is not required to be a Γ -path itself.

The Covering Relation in the Schröder Pattern Poset

In the Schröder pattern poset S, following the usual notation for the covering relation, we write P ≺ Q (Q covers P ) to indicate that P ≤ Q and the rank of P is one less than the rank of Q (i.e., rank(P ) = rank(Q)-1). The results contained in the present section concern the enumeration of Schröder paths covered by and covering a given Dyck path Q. We need some notation before stating them.

In a Schröder path Q, let k + 1 be the number of points of Q (having integer coordinates) lying on the x-axis (call such points p 0 = (0, 0), p 1 , . . . , p k ). Then Q can be factorized (in a unique way) into k Schröder factors F 1 , . . . , F k , each F i starting at p i-1 and ending at p i . Denote with f i and h i the number of U and H 2 steps of factor F i , respectively. Notice that f i also equals the number of D steps of the same factor. Let a i (resp., d i ) be the number of ascents (resp. descents) in F i , where an ascent (resp. descent) is a maximal consecutive run of U (resp., D) steps. Moreover, we denote with p(Q) and v(Q) the number of occurrences in Q of a consecutive factor U DU and DU D, respectively. Finally, we denote with h(Q) the total number of flats of Q, a flat being a maximal sequence of consecutive H 2 steps. The path depicted in Figure 1 has 4 factors, and we have

f 1 = 4, f 2 = f 3 = 0, f 4 = 2, h 1 = h 2 = h 3 = 1, h 4 = 2, a 1 = 3, a 2 = a 3 = 0, a 4 = 2, d 1 = 2, d 2 = d 3 = 0, d 4 = 2, p(Q) = 1, v(Q) = 0 and h(Q) = 4. Proposition 1. If Q = F 1 F 2 • • • F k is
a Schröder path with k factors, with F i having a i ascents and d i descents, then the number of Schröder paths covered by Q is given by

1≤i≤j≤k d i a j -p(Q) -v(Q) + h(Q) . (1)
Proof. There are two (mutually exclusive) ways to obtain a Schröder path covered by Q, namely:

1. by removing a H 2 step, or 2. by removing a U step and a D step.

We examine the two cases separately.

1. It is immediate to observe that one obtains the same path by removing any of the steps belonging to the same flat, whereas removing a step from different flats gives rise to different paths. Therefore, the number of distinct Schröder paths obtained by Q by removing an H 2 step is h(Q). 2. We wish to prove that there are 1≤i≤j≤k d i a j -p(Q)-v(Q) ways to remove a U steps and a D steps from Q and to obtain another Schröder path. We will proceed by induction on the number k of factors of Q. If k = 1, then necessarily Q starts with a U step and ends with a D step (otherwise Q = H 2 , which has no U and D steps). Observe that, in this case, we can remove any of the U steps and any of the D steps and the resulting path is still a Schröder path. Removing steps from the same ascent (and from the same descent) returns the same path, so we have a 1 possible choices to remove a U step and d 1 possible choices to remove a D step. However, there are some special cases in which, though removing from different ascents or descents, we obtain the same path. Specifically, if we have a consecutive string U DU in Q, then removing from Q the U D of such a string returns the same path as removing the DU , in spite of the fact that the two U steps belong to different ascents.

In a similar way, the presence of a factor DU D in Q gives the possibility of getting the same Schröder paths by removing steps from different descents.

To avoid overcount, we thus have to subtract the number of consecutive strings U DU and DU D of Q, thus obtaining a total of

d 1 a 1 -p(Q) -v(Q) paths. Now suppose that k > 1.
There are three distinct cases to analyze.

-If we remove both the U and the D steps from the prefix

F 1 • • • F k-1 of Q consisting of the first k -1 factors (which is a Schröder path in itself, of course), by induction we have 1≤i≤j≤k-1 d i a j -p(F 1 • • • F k-1 ) - v(F 1 • • • F k-1 ) distinct choices.
-If we remove both the U and the D steps from the last factor F k , using the same argument as the case k = 1 we get

d k a k -p(F k )-v(F k ) distinct paths.
-Finally, suppose we choose to remove the D step from the prefix

F 1 • • • F k-1
and the U step from the last factor F k (notice that we are not allowed to do the opposite, otherwise the resulting path would not be Schröder). In this case we have a k possible choices for U and k-1 i=1 d i possible choices for D. Once again, however, there are some paths that are overcounted, occurring when F 1 • • • F k-1 and F k share a consecutive U DU or a consecutive DU D. A quick look shows that this overcount is corrected by subtracting the number of such shared occurrences of consecutive U DU and DU D. The sum of the above three cases gives the required expression.

Finally, summing up the quantities obtained in 1. and 2., we obtain precisely formula [START_REF] Bacher | The Dyck pattern poset[END_REF].

Remark. If Q is a Dyck paths, then h(Q) = 0, and formula (1) reduces to the analogous formula for Dyck paths obtained in [START_REF] Bernini | Pattern avoiding Dyck paths[END_REF][START_REF] Bacher | The Dyck pattern poset[END_REF], since a Schröder path covered by a Dyck path is necessarily a Dyck path.

Proposition 2. Let P = F 1 • • • F k be a Schröder path having k factors. Denote with f i the number of U steps in the factor F i (this is also the number of D steps in F i ) and with h i the number of H 2 steps in F i . Moreover, let be the word length of P . Then the number of Schröder paths covering P is given by

2 + + (i,j) 1≤i≤j≤k (f i + h i )(f j + h j ).
(2)

Proof. We have two options to obtain a Schröder path covering P :

1. either we add a H 2 step, or 2. we add a U step and a D step.

As in the previous proposition, we examine the two cases separately. If a U step is added before a D step in F i , we observe that we cannot add the new D step in a factor F j , with j < i, otherwise the path would fall below the x-axis. With this constraint in mind, we are now allowed to add the new D step either before a U or before a H 2 or at the end of the path. However, in the first of the three previous cases, we cannot of course add the new D step before the first allowed U (i.e., at the beginning of the factor); moreover, adding the new D right before the new U step just added would produce a substring DU D, which can be obtained also by first adding the U step in the following available position of P and then adding the D step immediately after it. Thus, in this case, the number of paths covering P is obtained by considering the number of possible choices for U to be added in F i , which is f i , and the number of possible choices for D, which is j≥i (f j + h j ), and so it is

(i,j) 1≤i≤j≤k f i (f j + h j ).
If a U step is added before a H 2 step in F i , as in the previous case, we cannot add the new D step in a factor F j , with j < i. We can now add the new D step either before a U (except for the first U of F i , of course), or before a H 2 or at the end of P . So, in this case, the number of paths covering P is given by

k i=1 h i •   1 + k j=i (f j + h j )   .
Finally, if we add the new U step at the end of P , then the new D step must necessarily be added after it.

Summing up, we therefore obtain the following expression for the total number of paths covering P :

2 k i=1 f i + 1 + (i,j) 1≤i≤j≤k f i (f j + h j ) + k i=1 h i •   1 + k j=i (f j + h j )   + 1 =2 + k i=1 (2f i + h i ) + (i,j) 1≤i≤j≤k f i (f j + h j ) + (i,j) 1≤i≤j≤k h i (f j + h j ) =2 + + (i,j) 1≤i≤j≤k (f i + h i )(f j + h j ), (3)
which is formula (2).

Remark 1. Notice that f i + h i is the semilength of the factor F i . Denoting it with ϕ i , formula (2) can be equivalently written as

2 + + (i,j) 1≤i≤j≤k ϕ i ϕ j .
Remark 2. If P is a Dyck path, then, in the first expression in the chain of equalities (3), the summand 2 k i=1 f i + 1 gives the number of non-Dyck paths covering P (i.e., those having one H 2 step), and the remaining summands give the number of Dyck paths covering P . Also in this case, recalling that h i = 0 for all i, we recover the analogous formula for Dyck paths obtained in [START_REF] Bernini | Pattern avoiding Dyck paths[END_REF][START_REF] Bacher | The Dyck pattern poset[END_REF].

Enumerative Results on Pattern Avoiding Schröder Paths

Main goal of the present section is to enumerate several classes of Schröder paths avoiding a given pattern. For any Schröder path P , denote with S n (P ) the set of Schröder paths of semilength n avoiding P , and let s n (P ) = |S n (P )| be its cardinality. It is completely trivial to observe that

-s n (∅) = 0; -s n (H 2 ) = C n , where C n = 1 n+1 2n
n is the n-th Catalan number (sequence A000108 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]), counting the number of Dyck paths of semilength n; s n (U D) = 1 when n > 0.

Starting from patterns of semilength 2, we get some interesting enumerative results. In the next subsections we define several classes of Schröder paths avoiding a single pattern, each of which suitably generalizes the case of a pattern of semilength 2. In all cases, after having described a general enumeration formula, we illustrate it in the specific case of the relevant pattern of semilength 2.

Before delving into computations we state an important lemma, which in several cases reduces the enumeration of pattern avoiding Schröder paths to the case of pattern avoiding Dyck paths. In this lemma, as well as in several subsequent proofs, we will deal with the multiset coefficient n k , counting the number of multisets of cardinality k of a set of cardinality n. As it is well known, the multiset coefficients can be expressed in terms of the binomial coefficients, namely n k = n+k-1 k . Lemma 1. Given a Dyck path P , denote with d n (P ) the number of Dyck paths of semilength n avoiding P . Then

s n (P ) = n h=0 n + h n -h d h (P ). (4)
Proof. Let Q be a Schröder path. Clearly Q avoids P if and only if the Dyck path Q obtained from Q by deleting horizontal steps avoids P . Therefore, the set of Schröder paths of semilength n with n -h horizontal steps avoiding P is obtained by taking in all possible way a Dyck path of semilength h avoiding P and then adding to it n -h horizontal steps in all possible ways. Observe that, in a Dyck path of semilength h, one has 2h + 1 possible sites where to insert a horizontal step, and any number of horizontal steps can be inserted into the same site. Thus, if n -h horizontal steps have to be inserted, it is necessary to select a multiset of cardinality n -h from the set of the possible 2h + 1 sites. This can be done in (2h+1)+(n-h)-1 n-h

= n+h

n-h ways, as it is well known. Since h can be chosen arbitrarily in the set {0, 1, 2, . . . , n}, the total number of Schröder paths of semilength n avoiding P is given by formula (4), as desired.

The Pattern (U D) k

Since (U D) k is a Dyck path, this case can be seen as an immediate consequence of Lemma 1 together with the results of [START_REF] Bernini | Pattern avoiding Dyck paths[END_REF][START_REF] Bacher | The Dyck pattern poset[END_REF]. Proposition 3. For i, j ≥ 1, let N i,j = 1 i i j i j-1 be the Narayana numbers (sequence A001263 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]). Extend such a sequence by setting N 0,0 = 1 and N i,0 = N 0,j = 0, for all i, j > 0. Then

s n ((U D) k ) = n h=0 k-1 j=0 n + h n -h N h,j . (5)
The case k = 2 gives rise to an interesting situation. In fact, for the pattern U DU D, recalling that N 0,0 = 1, N i,0 = 0 and N i,1 = 1 for all i > 0, formula [START_REF] Higman | Ordering by divisibility in abstract algebras[END_REF] gives

s n (U DU D) = n h=0 n + h n -h N h,0 + n h=0 n + h n -h N h,1 = 1 + n h=1 n + h n -h = n h=0 2n -h h . ( 6
)
Since it is well known that Fibonacci numbers (F n ) n (sequence A000045 in [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]) can be expressed in terms of binomial coefficients as1 F n+1 = k≥0 n-k k , we get s n (U DU D) = F 2n+1 , i.e. Schröder paths avoiding U DU D are counted by Fibonacci numbers having odd index (sequence A122367 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]).

Remark. Notice that, for a Schröder path, avoiding the (Schröder) path U DU D is equivalent to avoiding the (non-Schröder) path DU . As suggested by one of the referees, a simple combinatorial argument to count Schröder words of semilength n avoiding the subword DU is the following: if the words contains k H 2 steps, then it can be constructed by taking the word U n-k D n-k and inserting k H 2 steps. Taking into account all possibilities, and summing over k, gives precisely formula (6).

The Pattern U k D k

This case is similar to the previous one, in that it can be easily inferred from Lemma 1, since the generic pattern of the class is a Dyck path. Thus, applying the above mentioned lemma and using results of [START_REF] Bernini | Pattern avoiding Dyck paths[END_REF][START_REF] Bacher | The Dyck pattern poset[END_REF], we obtain the following result.

Proposition 4. For all k ≥ 0, we have

s n (U k D k ) = k-1 h=0 n + h n -h C h + n + k n -k (C k -1) + min{2k-1,n} h=k+1 j≥1 n + h n -h b 2 k-j,h-k+j , (7)
where the C n 's are the Catalan numbers and the b i,j 's are the ballot numbers (sequence A009766 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]).

Setting k = 2 in formula [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF], for Schröder paths of semilength n ≥ 3 avoiding U U DD we obtain the following polynomial of degree 4 (sequence A027927 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]):

s n (U U DD) = 1 + n + 1 n -1 + n + 2 n -2 = 1 + n(n + 1)(n 2 + n + 10) 24 .

The Pattern H k 2

In this case the generic pattern of this class is not a Dyck path. However, we are able to give a direct argument to count Schröder paths avoiding H k 2 .

Proposition 5. For all n, k ≥ 0, we have

s n (H k 2 ) = k-1 i=0 2n -i i C n-i . (8)
Proof. We observe that a Schröder path avoids the pattern H k 2 if and only if it has at most k -1 H 2 steps. Thus, the set of all Schröder paths of semilength n avoiding H k 2 can be obtained by taking the set of all Dyck paths of semilength n -i and inserting in all possible ways i H 2 steps, for i running from 0 to k -1. Since in a Dyck path of semilength n -i there are precisely 2n -2i + 1 points in which inserting the horizontal steps, and we have to insert i horizontal steps (possibly inserting more than one H 2 step in the same place), we get

s n (H k 2 ) = k-1 i=0 2n -2i + 1 i C n-i = k-1 i=0 2n -2i + 1 + i -1 i C n-i = k-1 i=0 2n -i i C n-i , as desired.
When k = 2 we obtain the following special case:

s n (H 2 H 2 ) = C n + (2n -1)C n-1 = n + 3 2 C n = n + 3 2(n + 1) 2n n ,
which is valid for n ≥ 1. This is sequence A189176 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF], whose generating function is

1-5x+4x 2 -(1-5x) √ 1-4x 2x(1-4x)
, and can be also obtained as the row sums of a certain Riordan matrix (see [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF] for details).

The Pattern

U H k-1 2 D
This class of patterns requires a little bit more care, nevertheless we are able to get a rather neat enumeration formula. Proposition 6. For all n ≥ 0, k > 1, we have

s n (U H k-1 2 D) = 1 + n h=1 min{k-2,n-h} i=0 2h -1 i (n -h -i + 1)C h . (9)
Proof. Let P be a Schröder path of semilength n avoiding U H k-1 2 D. If P does not contain U steps, then necessarily P = H n 2 . Otherwise, P can be decomposed into three subpaths, namely:

a prefix, consisting of a (possibly empty) sequence of horizontal steps; a path starting with the first U step and ending with the last D step (necessarily not empty); a suffix, consisting of a (possibly empty) sequence of horizontal steps.

The central portion of P in the above decomposition has at most k -2 horizontal steps. Thus it can be obtained starting from a Dyck path of semilength h, for some 1 ≤ h ≤ n, and adding i horizontal steps, for some 0 ≤ i ≤ min{k -2, n -h}. Such horizontal steps can be inserted into 2h -1 possible sites (here we have to exclude the starting and the ending points, since the subpath is required to start with a U and end with a D), with the possibility of inserting several steps into the same site, as usual. The resulting path has therefore semilength h + i, and has to be completed by adding a suitable number of horizontal steps at the beginning and at the end, to obtain a Schröder path of semilength n: there are n -h -i + 1 possible ways to do it. We thus obtain formula (9) for s n (U H k-1 2 D), as desired. Formula (9) becomes much simpler in the special case k = 2 of Schröder paths of semilength n avoiding U H 2 D. Indeed we obtain:

s n (U H 2 D) = 1 + n h=1 (n -h + 1)C h = n h=0 C h (n -h) + n h=0 C h -n.
In this case, we can find an interesting expression for the generating function of these coefficients in terms of the generating function C(x) = n≥0 C n x n of Catalan numbers, which provides an easy way to compute them:

n≥0 s n (U H 2 D)x n = C(x) • n≥0 nx n + C(x) • n≥0 x n - n≥0 nx n = C(x) x (1 -x) 2 + 1 1 -x - x (1 -x) 2 = 1 (1 -x) 2 (C(x) -x).
Roughly speaking, the above generating function tells us that s n (U H 2 D) is given by the partial sums of the partial sums of the sequence of Catalan numbers where C 1 is replaced by 0. The associated number sequence starts with 1, 2, 5, 13, 35, 99, 295, . . . and does not appear in [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

The Pattern H

k-1 2 U D
The last class of patterns we consider is the most challenging one. It gives rise to an enumeration formula which is certainly less appealing than the previous ones. Due to space limitation, we will just sketch its proof and simply state the special case corresponding to k = 2. Before illustrating our final results, we need to introduce a couple of notations.

We denote with P k,h the number of Dyck prefixes of length k ending at height h. Notice that we can express these coefficients in terms of the ballot numbers b i,j = i-j+1 i+1 i+j i , counting the number of Dyck prefixes with i up steps and j down steps, as follows:

P h,k = i,j i-j=h i+j=k b i,j .
Moreover, we denote with S n,q the number of Schröder paths of semilength n having exactly q horizontal steps. Since each such path can be uniquely determined by a Dyck path of semilength n -q with q horizontal steps added, we have a rather easy way to compute S n,q in terms of the Catalan numbers C n :

S n,q = C n-q 2(n -q) + 1 q = 2n -q q C n-q .
Proposition 7. For all n ≥ 0, k > 1, we have

s n (H k-1 2 U D) = k-2 q=0 S n,q + 2n-2k+2 p=0 2n-p-2k+2 h=0 P p,h p + 1 k -2 2n-h-p-2k+4 2 h . (10)
Proof. Let P be a Schröder path of semilength n. If P contains less than k -1 horizontal steps, then it necessarily avoids H k-1 2 U D. This gives the term k-2 q=0 S n,q in the r.h.s. of (10). If instead P contains at least k -1 horizontal steps, then, in order to avoid H k-1 2 U D, it has to be decomposable into a Schröder prefix ending at some height h and having exactly k -2 horizontal steps, and a suffix starting with a horizontal steps followed exclusively by H 2 and D steps (with exactly h D steps). The generic Schröder prefix of the required form can be obtained by taking a Dyck prefix of length p, for some 0 ≤ p ≤ 2n -2k + 2, and adding k -2 H 2 steps in all possible ways. We thus get a total of P p,h • p+1 k-2 Schröder prefixes of length p + 2k -4 ending at height h and containing exactly k -2 H 2 steps. The generic suffix of the required form contains h D steps and 2n-h-p-2k+4 2 H 2 steps. Such a suffix can be obtained by inserting the h down steps into the sequence of horizontal steps in all possible ways. Since the first step has to be a horizontal one, this gives a total of It would be very interesting to investigate in more detail the structural properties of the Schröder pattern poset. A typical question in this context concerns the computation of the Möbius function, which is still open even in the Dyck pattern poset. Another (partially related) issue is the enumeration of (saturated) chains. More generally, can we say anything about the order structure of intervals (for instance, is it possible to determine when they are lattices?)?

Concerning the enumeration of pattern avoiding classes, the next step would be to count classes of Schröder words simultaneously avoiding two or more patterns.

Finally, it would be nice to have information on the asymptotic behavior of integer sequences counting pattern avoiding Schröder words. In the Dyck case, all the sequences which count Dyck words avoiding a single pattern P have the same asymptotic behavior (which is roughly exponential in the length of P ). This is in contrast, for instance with the permutation pattern poset, where the asymptotic behavior of a class of pattern avoiding permutations depends on the patterns to be avoided (this is the ex Stanley-Wilf conjecture, proven by Marcus and Tardos [START_REF] Marcus | Excluded permutation matrices and the StanleyWilf conjecture[END_REF]). What does it happen in the Schröder pattern poset?

Fig. 1 .

 1 Fig. 1. The Schröder word U U DU H2U DDDH2H2U H2U DH2D represented as a Schröder path.

2 U

 2 together all the contributions, we get the desired expression for s n (H k-1 D).Specializing to k = 2 we obtains n (H 2 U D) = C n +

  1. Adding a new H 2 step in any point of a flat of P returns the same path.Hence, in order to obtain distinct paths, we can add a H 2 step either before a U step, or before a D step, or at the end of P . Thus we have a total of We start by observing that adding a U step in any point of an ascent returns the same path, and the same holds for D steps (with ascents replaced by

	k
	2	f i + 1
	i=1
	paths covering P in this case.
	2.

descents). Suppose to add a new U step to P first. In order to obtain distinct paths, we can add U either before a D step, or before a H 2 step, or at the end of P .

Notice that the sum contains only a finite number of nonzero terms, since the binomial coefficients vanish when k > n/2

Partially supported by INdAM-GNCS 2017 project: "Codici di stringhe e matrici non sovrapponibili".


Antonio Bernini
email: antonio.bernini@unifi.it

Restricted Binary Strings and Generalized Fibonacci Numbers

Keywords: Generalized Fibonacci numbers, restricted strings, consecutive patterns avoidance

We provide some interesting relations involving k-generalized Fibonacci numbers between the set F (k) n of length n binary strings avoiding k of consecutive 0's and the set of length n strings avoiding k + 1 consecutive 0's and 1's with some more restriction on the first and last letter, via a simple bijection. In the special case k = 2 a probably new interpretation of Fibonacci numbers is given. Moreover, we describe in a combinatorial way the relation between the strings of F (k) n with an odd numbers of 1's and the ones with an even number of 1's.

Introduction

In the paper we mainly faces with binary strings avoiding consecutive patterns, providing some enumerative and constructive properties. The notion of pattern was introduced by Knuth [Kn] about permutations. Then, it was also absorbed within the context of other combinatorial objects as set partitions [Kl,S], trees [BBFGPW,BFPW,DPTW,R], so that the notion of pattern has become one of the most studied in the last decades in Combinatorics. Actually, in our paper we are dealing with consecutive patterns [BFS,EN], which probably are the most useful from an applicative point of view being often related to the Theory of Codes [BBPSV,BBPV,CKPW].

Very often, during the study of a particular matter, it is possible to have to deal with some related problems which could be deeper investigated. This is what happened during the writing of the paper [BBBP] about non-overlapping matrices. There, it was very important the analysis of some sets of binary strings with some constraints, constituting the row of the studied matrices. In particular, due to enumerative reasons, we needed to find the cardinality of B n (0 k , 1 k ) (the binary strings of length n avoiding k consecutive 0's and k consecutive 1's), Z n (0 k , 1 k ) (the strings in B n (0 k , 1 k ) ending with 0), and R n (0 k , 1 k ) (the strings in B n (0 k , 1 k ) starting with 1 and ending with 0). We observed a strong similarity between the recurrence relation defining the sequence enumerating B n (0 k , 1 k ) and the one defining the k-generalized Fibonacci numbers, and we proved [BBBP], in a very easy analytic way and by induction, that the cardinalities of B n (0 k , 1 k ), Z n (0 k , 1 k ), and R n (0 k , 1 k ) are strictly related to the well-known sequence.

One result of the present paper is an alternative explanation of that interesting link. It is well-known [Kn] that the set of binary strings having length n and avoiding k consecutive 0's, denoted by

F (k)
n , is enumerated by the k-generalized Fibonacci numbers. Section 2 is devoted to the definition of a bijection between Z n (0 k , 1 k ) and the set

F (k-1)
n-1 , so providing a combinatorial and constructive description for the cardinalities of Z n (0 k , 1 k ), B n (0 k , 1 k ), and R n (0 k , 1 k ). Moreover, this section contains a reading of the famous Fibonacci numbers which is new to the best of our knowledge.

The bijection restricted to R n (0 k , 1 k ) maps its strings in the strings of

F (k-1) n-1
having an odd numbers of 1's, and a purely analytic argument leads to the intriguing fact that the strings in

F (k) n
with an odd number of 1's and the ones with an even number of 1's are equinumerous or differ by one string, depending on n and k. Section 3 presents a construction of the set F n (k) via generating trees, and it reveals the reason why it happens.

A simple bijection and some applications

Let F (k) n be the set of length n binary strings avoiding k consecutive 0's, with k ≥ 2. It is known [Kn] that, ∀n ≥ 0, denoting by

|F (k) n | the cardinality of F (k) n , |F (k) n | = f (k) n+k ,
where f (k) n is the sequence of the k-generalized Fibonacci numbers defined by

f (k) n =                  0 if 0 ≤ n < k -1 1 if n = k -1 k i=1 f (k) n-i if n ≥ k . Posing f (k) n = f (k) n+k we have, ∀n ≥ 0, f (k) n =          2 n if 0 ≤ n ≤ k -1 k i=1 f (k) n-i if n ≥ k (1)
and

|F (k) n | = f (k) n .
We denote by Z n (0 k , 1 k ) the set of length n binary strings ending with 0, avoiding k consecutive 0's and k consecutive 1's (these two patterns in the following will be denoted by 0 k and 1 k , respectively). Let z

(k) n = |Z n (0 k , 1 k )|.
It can be proved, by induction [BBBP], that

z (k) n =    1 if n = 0 f (k-1) n-1 if n ≥ 1 .
(2)

We provide a simple bijection ϕ between Z n (0 k , 1 k ) and

F (k-1)
n-1 , so giving a combinatorial interpretation of the above formula.

Definition 1. Let u ∈ Z n (0 k , 1 k ), u = u 1 u 2 . . . u n and let v = v 1 v 2 . . . v n-1 be a string of length n -1. We define the map ϕ from Z n (0 k , 1 k ) into the set of binary strings of length n -1 such that ϕ(u) = v where v i =    1 if u i = u i+1 0 if u i = u i+1 , or, equivalently, v i = u i XOR u i+1 , for i = 1, 2, . . . , n -1.
We have the following proposition:

Proposition 1. The map ϕ is a bijection between Z n (0 k , 1 k ) and F (k-1) n-1 . Proof. First of all, if u ∈ Z n (0 k , 1 k ), we show that ϕ(u) = v ∈ F (k-1)
n-1 . Clearly, v has length n -1 by its definition. Moreover, being u ∈ Z n (0 k , 1 k ), the string u presents at most k -1 equal consecutive symbols (0 and/or 1) so that the string v = ϕ(u) has at most k -2 consecutive symbols equal to 0. In other words, the string v avoids k -1 consecutive 0's and so v ∈ F (k-1) n-1 . It is not difficult to see that the map ϕ is an injective function: if u (1) and u (2) are two different strings in Z n (0 k , 1 k ), let j be the greatest index such that u

(1) j = u

(2) j (surely j = n and u

(1) 2)) and ϕ is injective, then ϕ is also surjective and the thesis follows.

j+1 = u (2) j+1 ). Then, the two pairs u (1) j u (1) j+1 and u (2) j u (2) j+1 are mapped in two different symbols by ϕ, so that ϕ(u (1) ) = ϕ(u (2) ). Since |Z n (0 k , 1 k )| = |F (k-1) n-1 | (see (
The inverse of ϕ is easily seen to be defined by ϕ -1 (v) = u with

u i =      0 if i = n u i+1 if v i = 0 ūi+1 if v i = 1 , for i = n, n -1, . . . 3, 2, 1
, where ūj = 1 if u j = 0 and ūj = 0 if u j = 1. The string u can be recovered from v by starting from the right side: starting from u n = 0, one entry u i is equal to the successive one if

v i = 0, while if v i = 1, then u i is the complement of u i+1 .
The set of length n binary strings avoiding 0 k and 1 k , denoted by

B n (0 k , 1 k ) whose cardinality is defined by b (k)
n , is strictly related to the set Z n (0 k , 1 k ). More precisely, from [BBBP], we have that

z (k) n = 1 if n = 0 b (k) n /2 if n ≥ 1 , so that, using (2), it is b (k) n = 1 if n = 0 2f (k-1) n-1 if n ≥ 1 .
(3)

Proposition 1 can be used to provide a combinatorial proof of ( 2) and (3). Moreover, in the special case k = 3, it allows the interpretation, probably new, of Fibonacci sequence as the numbers counting the length n binary strings ending with 0 and avoiding 000 and 111 (3 consecutive 0's and 3 consecutive 1's).

Besides the sets B n (0 k , 1 k ) and Z n (0 k , 1 k ), we also consider the set R n (0 k , 1 k ) of the length n binary strings, starting with 1, ending with 0 and avoiding 0 k and 1

k , for n ≥ 1. Note that if k = 2, then R n (0 2 , 1 2 ) = {(10) n/2 } if n is even, while if n is odd, then R n (0 2 , 1 2 ) = ∅, therefore we consider k ≥ 3. Posing R 0 (0 k , 1 k ) = {λ} and r (k) n = |R n (0 k , 1 k )|,
it can be proved by induction (see [BBBP]) that

r (k) n =      1 if n = 0 f (k-1) n-1 +d (k) n 2 if n ≥ 1 (4)
where

d (k) n =            1 if (n mod k) = 0 -1 if (n mod k) = 1 0 if 2 ≤ (n mod k) ≤ k -1 . If u ∈ R n (0 k , 1 k ), then ϕ(u) is a string of F (k-1) n-1
with an odd number of 1's since, clearly, u has an odd number of consecutive pairs of different bits (01 or 10) which are mapped by ϕ in the bit 1. Inversely, if v is a string of

F (k-1) n-1 with an odd number of 1's, then it is easily seen that ϕ -1 (v) ∈ R n (0 k , 1 k ). Denoting by F (k) n,odd the subset of F (k) n
of the strings with an odd number of 1's and by

f (k) n,o its cardinality, then R n (0 k , 1 k ) is in bijection with F (k-1)
n-1,odd (via ϕ) and, for n ≥ 1 and k ≥ 3, due to the above argument,

r (k) n = f (k-1) n-1,o .
(5)

With the additional notation of

F (k)
n,even for the subset of

F (k) n
of the strings with an even number of 1's and of f

(k)
n,e for its cardinality, using (4), ( 5) and the trivial fact that f

(k-1) n-1 = f (k-1) n-1,o + f (k-1)
n-1,e , we deduce that

f (k-1) n-1,o = f (k-1) n-1,e + d (k) n for n ≥ 1 and k ≥ 3 , (6)
which is clearly equivalent to

f (k) n,o = f (k) n,e + d (k+1) n+1 for n ≥ 0 and k ≥ 2 , (7)
The aim of the next paragraph is to give a combinatorial description of (7).

3 Number of 1's in the strings of

F (k) n
We recall the construction for the strings in

F (k) n : if their length is n ≤ k -1, then all the binary strings having length n belong to F (k) n , while if n ≥ k, the strings in F (k)
n can be obtained by appending the prefixes 1, 01, 001, . . . , 0 k-1 1 to all the strings with length n-1, n-2, n-1, . . . , n-k, respectively. In other words, denoting by B n the length n binary strings and using the notation proposed in [V], we have:

F (k) n =      {λ} if n = 0 B n if 1 ≤ n < k 1 • F (k) n-1 ∪ 01 • F (k) n-2 ∪ . . . ∪ 0 k-1 1 • F (k) n-k if n ≥ k . (8)
Note that the binary strings in B n can be obtained in a recursive way by prepending 0 and 1 to the strings in B n-1 , starting from the empty string λ:

B n = {λ} if n = 0 0 • B n-1 ∪ 1 • B n-1 if n ≥ 1 . ( 9
)
The recursive definition (8) of

F (k)
n can also be read by means of a set of generating trees. They are a useful tool which is widely employed in Combinatorics (see for example [E,W1,W2]). Each node of such trees is a binary string of F (k) n which generates its children at different levels, as we are going to explain in the following.

Definition 2. Given k ≥ 2, let w be a length j binary string belonging to B j , with 0 ≤ j < k. We define a generating tree T w as follows:

w is the root of T w ; w has j + 1 children which are strings obtained by adding to the left of w the prefixes 0 k-1-i 1, from left to right, with i = j, j -1, . . . , 1, 0, so that the first child is obtained for i = j. each node with length t ≥ k has k children which are strings obtained by adding to its left the prefixes 0 k-1-i 1 from left to right with i = k -1, k -2, . . . , 1, 0, so that the first child is for i = k -1. the level of each node v, indicated by L(v), of T w which is a child of u, v = 0 k-1-i 1u for some i, is recursively defined as follows:

L(v) = j if v = w (u is the root) L(u) + k -i otherwise .
Clearly, the level of a node gives the length of the represented string.

Notice that the children of the root appear only starting from level k, while the children of any other node at level t ≥ k appear at each level from t + 1 to t + k. Actually, also the children of a node at level k -1 appear in the levels from k to 2k -1. Therefore, we observe that each node v at level t ≥ k -1 has k children as described in Definition (2), namely 1v, 01v, 001v, . . . , 0 k-1 1v. They can be visualized in Figure 1 where we have labelled the edges leaving v with 1, 01, . . . , 0 k-1 (corresponding to the prefixes added on the left of v) from left to right, according to Definition (2). In Figure 2 we present two different generating trees T w with roots w = 0 and w = 01, with k = 4. In the next figures we omit the labels of the edges. Considering all the generating trees T w rooted in each w ∈ B n with 0 ≤ n < k, we obtain a set T of 2 k -1 generating trees which are clearly disjoint. It is also straightforward to see that the set F (k) n coincides with the set of strings appearing in the nodes of the trees of T , since the definition of the children of a node, given in (2), reflects the recursive definition (8). For example, for k = 3 we have 7 generating trees as depicted in Figure 3, where only the first levels of each tree are presented. In each level n ≥ 0, all the strings of F (k) n are obtained.

In order to give a combinatorial proof of (7) we will attempt to provide a matching between the strings in F (k) n with an odd number of 1's and the ones with an even number of 1's. We will see that the construction of an exact pairing is not possible at each level n, since it depends on the value of n mod (k + 1).

We first analyse the strings (appearing in the nodes) of T not belonging to T λ . We start with a simple remark on the list of the binary strings of the same length j ≥ 1 obtained by recursive definition (9). Such strings differ only for the last bit if we start from the first one and we consider them two by two. More precisely, if B j = {a 1 , a 2 , a 3 , . . . , a 2 j -1 , a 2 j }, then a 2i-1 and a 2i differ for the last bit, for i = 1, 2, . . . , 2 j-1 . For example, if j = 3, then 001, 010, 011, 100, 101, 110, 111} and within the couples {a 1 = 000, a 2 = 001}, {a 3 = 010, a 4 = 011}, {a 5 = 100, a 6 = 101}, {a 7 = 110, a 8 = 111} the strings differ only for the last bit. This fact implies evidently that the strings at the same level in the generating trees T a2i-1 and T a2i (i = 1, 2, . . . , 2 j-1 ) can be obtained each from each other by switching the last bit, since they are generated by adding the same prefixes to two roots, a 2i-1 and a 2i , differing only in the last bit. In other words, the generating trees T a2i-1 and T a2i are isomorphic and two corresponding nodes are obtained by switching the last bit. This is clearly true for each length j of the roots, with 1 ≤ j ≤ k -1. Therefore, if at a level n of T \ {T λ } there are a certain number of strings in F (k) n with an odd number of 1's, there are also the same number of strings with an even number of 1's, at that level. Summarizing, the following proposition holds:

B 3 = {000,
Proposition 2. The strings in F (k)
n,odd and in F (k) n,even not belonging to the generating tree T λ are equinumerous, for each n ≥ 1.

What is left to do in order to combinatorially describe formula ( 7) is the analysis of the generating tree rooted in the empty string λ. Following Definition (2) the root λ has only one child, namely the string 0 k-1 1 at level k, which, on its turn, has k children (see Figure 4). We denote by c i (v) = 0 i-1 1v, with |v| ≥ k and i = 1, 2, . . . , k, the k children of a node v. Note that c 1 (0 k-1 1) = 10 k-1 1 is the only node at level k + 1 of the sub-tree T 0 k-1 1 . Moreover, it can be observed that c i (c 1 (0 k-1 1)) = 0 i-1 110 k-1 1 and c i+1 (0 k-1 1) = 0 i 10 k-1 1, for i = 1, 2, . . . , k -1, at level k + 1 + i, differ only by the (k + 2)-th from last digit. Consequently, the sub-trees T ci(c1(0 k-1 1)) and T ci+1(0 k-1 1) are isomorphic and the corresponding strings can be obtained by switching the (k + 2)-th from last bit (in Figure 4 isomorphic subtrees have been framed in a rectangular border) . Then, referring to T 0 k-1 1 and to Figure 4, we can summarize that:

1. at level k there is only the string 0 k-1 1 ∈ F (k) k,odd ; 2. at level k + 1 there is only the string 10 k-1 1 ∈ F (k) k,even ; 3. from level k + 2 on, the strings in F (k) n,odd belonging to T ci(c1(0 k-1 1)) and T ci+1(0 k-1 1) , for i = 1, 2, . . . , k -1, are as many as the strings in F (k) n,even belonging to the same subtrees, for each n ≥ k + 2.

(10 3 1) p = v p 1(10 3 1) p 01(10 3 1) p 0 2 1(10 3 1) p 0 3 1(10 3 1) p 0 3 (10 3 1) p 0 2 (10 3 1) p 0( 10 3 1 0 10 3 1 0 2 10 3 1 0 3 10 3 1 0 3 1(10 3 1) 2 110 3 1 0110 3 1 0 2 3 1 110 0 3 110 3 1 0 3 (10 3 1) 2 0 2 (10 3 1) 2 0(10 3 1) 2 (10 3 1) 2 1(10 3 1) 2 3 2 01(10 1) 0 2 1(10 3 1) 2 0 3 1(10 3 1) p-1 = u p Fig. 4. The subtree T 0 k-1 1 in the case k = 4. Within each rectangular border there are two isomorphic subtrees.

Note that in point 3. of the above list i = k, but we have to consider the k-th child of 10 k-1 1, i.e. c k (10 k-1 1) = 0 k-1 110 k-1 1, which is the root of a new subtree generating many other strings. We observe that this subtree, T 0 k-1 110 k-1 1 , is isomorphic to T 0 k -1 1 and all its nodes can be obtained from the nodes of T 0 k-1 1 by appending the suffix 10 k-1 1 to each of them. This fact induces a recursive structure on T 0 k-1 1 . In general, it can be observed that, for any p ≥ 1, each level n = (k + 1)p -1 contains the string u p = 0 k-1 1(10 k-1 1) p-1 and each level n = (k + 1)p contains the string v p = (10 k-1 1) p . Note that u p and v p are the only strings which do not belong to any sub-tree rooted in c i (v p-1 ) or c i+1 (u p-1 ), for i = 1, 2, . . . , k -1 and p > 1. Moreover, the strings c i (v p ) and c i+1 (u p ) for i = 1, 2, . . . , k -1 at level (k + 1)p + i differ only for the ((k + 1)p + 1)-th by last bit. Consequently, the sub-trees T ci(vp) and T ci+1(up) are isomorphic and the corresponding strings can be obtained by switching the ((k + 1)p + 1)-th from last bit. At any level n ≥ (k + 1)p + i, the number of strings with an odd number of 1's deriving from the root c i (v p ) is equal to the number of strings with an even number of 1's deriving from the root c i+1 (u p ), for any p ≥ 1 and i = 1, 2, . . . , k -1.

Since, evidently,

u p ∈ F (k) n,odd and v p ∈ F (k)
n,even , we can more generally rephrase the above numbered list in the following proposition:

Proposition 3. The strings in F (k) n,odd and in F (k)
n,even belonging to the generating tree T 0 k-1 1 are such that, for any p ≥ 1,

-at each level n = (k +1)p-1 the set F (k)
n,odd has one string more than F

(k) n,even , namely u p = 0 k-1 1(10 k-1 1) p-1 ; -at each level n = (k + 1)p the set F (k)
n,even has one string more than F (k) n,odd , namely v p = (10 k-1 1) p ; from level (k + 1)p + 1 on, the strings in F (k) n,odd belonging to the subtrees T ci(vp) and T ci+1(up) , for i = 1, 2, . . . , k -1, are as many as the strings in

F (k)
n,even belonging to the same subtrees. n,e only in the case n = (k + 1)p -1 and n = (k + 1)p, for any p ≥ 1. More precisely, noting that if n = (k + 1)p -1 then n mod (k + 1) = k, f (k) n,o = f (k) n,e + 1 if n mod (k + 1) = k and f (k) n,o = f (k) n,e -1 if n mod (k + 1) = 0. In all the remaining levels, again from Propositions (2) and (3), it is

Recalling that |F

f (k) n,o = f (k)
n,e . Defining n,e + dn (k+1) .

which is equivalent to (7) since, clearly, dn

(k+1) = d (k+1)
n+1 .

Conclusion

Binary unrestricted strings of length n with an odd number of 1's and the ones with an even number of 1's are clearly equinumerous, since, for instance, a string of the first group gives a string of the second one by switching the last bit. If we consider binary strings of length n avoiding the consecutive pattern 0 k , even if the above easy fact is not true anymore, it is natural to expect that the two subsets have almost the same cardinality. In Section 3 of the present paper we provided a rigorous proof of this, showing that they are always the same, except that in particular cases depending on the values of n and k.

The simple bijection ϕ presented in Section 2 let to find a combinatorial and constructive explanation of the cardinalities of the sets Z

Fig. 1 .

 1 Fig. 1. The children of a node v at level t ≥ k -1.

Fig. 2 .

 2 Fig. 2. Two generating trees in the case k = 4. The added prefixes are in bold character. Each little circle replaces a string.

Fig. 3 .

 3 Fig. 3. The seven generating trees in the case k = 3. The generated strings are shown only up to level 4. Differently from Figure 2, we omit the little circles at the end of each edge.

  only by induction. Moreover, bijection ϕ led to a probably new interpretation of the famous Fibonacci numbers.

This work is partially supported by the GNCS -INDAM research project 2017 "Codici di stringhe e matrici non sovrapponibili".