# I. Introduction

Until now, stamp folding, or in other words origami, was considered more of a child's pastime and hobby. However, in recent years, this folding technique has been applied in various fields and is being actively studied. In addition, many mathematicians have been working on the stampfolding problem, which is addressed in this paper, for a long time, but it has not yet been solved.( [1], [2], [3], [4])

Generally speaking, the stamp folding problem is "make n creases at equal intervals of length n + 1 and fold it to length 1. How many ways to fold it at this time?" In other words, the problem of stamp folding is to count the methods of folding to length 1 without worrying about the allocation of creases. A slightly smaller stamp folding problem is that the left edge of the paper must not be covered by the folded paper, that is, the left edge of the paper must be visible from the outside, and the rest of the paper must be able to be attached to the outside. This is the former divided by n (the cyclic permutation of a foldable stamp sequence is always foldable in itself), and in this paper, we consider this case and call it F(n).

This problem can also be rephrased as [the number of ways in which a curve with an infinite orientation on one side intersects a straight line n times]. Known methods for calculating these numbers take exponential time as a function of n. In short, there are no formulas or efficient algorithms that can extend this sequence to very large values of n.

The sequence of F(n) is as follows. By the way, the maximum value we know is F (43), which is 21 digits.

In addition, although not dealt with here, new concept problems such as the problem of the folding complexity and the problem of crease width also arise, making this a very interesting field.( [5], [6])

The stamp folding problem is not represented by a recurrence formula, and it is thought that F(n) cannot be found to be related to F(n-1 or less). However, I now find that any large value of F(n) is related to F(n-1 or less).

First, let us consider a small value F(5) as an example. F( 5) is 10 ways in the figure below (Figure 1). Vertical is not counted by connecting. The horizontal line has a different length on the figure, but it is length 1. For the sake of clarity, it is as follows.

The stamp folding list of F (5) From these 10 ways, you can see that A) ~ E) and F) ~ J) are symmetrical with the second stamp from the left as the boundary. A) and H). B) and F). D) and J). E) and I). It can be seen that C) and G) are also upside down, only the beginnings are upside down. Since this must not cover the leftmost stamp, the stamps A) to E) must be closed in the clouds in Figure 2, and so are F) to J). And since each of the remaining three stamps is placed, they have the same shape (Figure 2). Moreover, this idea is the same after n = 5. So you should consider either starting below or above the second stamp. From now on, I will consider only the case of starting from the bottom of the second stamp from the left (here A) to E)) Next, I would like to look at the relationship between F (5) and F (4). The stamp on the left end is the same, so I don't think about it. Considering the second and subsequent points, it can be seen that there are four F (4) inverted left and right other than C). As with the previous idea, the fact that the remaining three are always configured below the second from the left end is nothing but the placement of F (4). This is the same for F(5) and above, and can be considered in terms of stamps excluding the first leftmost stamp. In short, it means F(n) which is n+1 -1. In addition, in order to cover all stamp folding methods, there is always an inverted one at the boundary of the second stamp, so it is necessary to double it. From the above, the following equation is extracted (n is 5 or more). Here we can easily see that this sequence grows exponentially.
A) B) C) D) E) F) G) H) I) J) Schematic diagram of F (5) X pattern X pattern A)?E) F)?J) © 2023 Global Journals
Next, I would like to consider how to fold F (n + 1) not represented by F (n), C) in F ( 5).

Here, I would like to consider F (7) as an example for a closer look. Figure 3 below is a list of things that started below the second stamp and moved to the top of the second stamp in the middle. First, consider c), d), f) and g). All of these have the same arrangement of the first four stamps. After that, it consists only above the second stamp (clouds in Figure 4). This means that there are only three clouds left, so we can see that F (4) = 4 ways. Here, the first stamp is fixed, so we have to do 3+1 ,or generally speaking n+1.


# ?(? + 1) > 2?(?)

(1)
?(?) > 2 ??2(2)
A list of things that started below the second stamp and moved to the top of the second stamp in the middle (F(7)) 
a) b) c) d) e) f) g) h) i)1Notes Schematic diagram of classification of F (7) a),b), i) c),d),f),g)
Judgment diagram that it is facing outward From now on, put this number (the total number of points in F(x) where a given vertex value r faces outwards) as G (x, r1, r2, .. rj). Indicates which vertex the second and subsequent vertices r1 to rj are facing outward, counting from the last vertex. If nothing is attached like G (x), it is the last vertex. Also, if r is 0, it agrees with F (x).


# OK NG

Patterns such as these a), b), j) that first start under the second stamp, come over the second stamp only once, and never again come under the second stamp be. These and the patterns that hold only under the second stamp discussed above are summarized in Next, consider a), b), and i). These three are the same that the last stamp is placed above the second stamp. This is the last stamp of F (5) facing outwards. Because if you subtract the first fixed stamp and the last stamp, 7-2=5. Also, in order to go from the penultimate stamp to the last stamp (by passing the second stamp), the penultimate stamp must always face outward as shown in Figure 5. In other words, if we think in terms of vertices rather than stamps, we have numbers whose last vertices are not in valleys and are not enclosed. This is due to the fact that the lines (surfaces) must not intersect (physically impossible) when folding stamps.  Notes folding number F(n). The left side is the value of the stamp placed above the second stamp, and the right side is the value of the stamp placed below the second stamp. The row direction is arranged according to the number of times. The right side of Table 1 shows the final vertex facing outward in F() until the stamp placed below the second stamp goes up. In short, according to the definition mentioned above, it is represented by G(). Shown on the left side of Table 1 are the values placed above the second stamp, which are not returned below the second stamp anymore and are closed there, so represented by the remaining number F(). One thing to keep in mind is that it always takes two stamps to wrap, so you have to think about +2. It goes without saying that n=x+y if we assume F(x) and G(y) when looking at each row. From this, the following equation ( 3) can be derived. The brackets {} are multiplied by 2 because we are considering the case starting above the second stamp. Finally, e) and i) are patterns that start from the bottom of the second stamp, move to the top of the second stamp, and then return to the bottom of the second stamp. Since it is complicated after this, I would like to think comprehensively rather than individually.

Again, consider the second stamp as a boundary. As shown in Figure 6 below, place the stamps that come and go at the second boundary as D1 ~ Di. For the sake of understanding only this Figure 6, the vertical line is the second stamp. The line connecting D? and D? is not counted as a connection. To conclude first, it can be seen that this is the product of the total number of folds of the stamps on the left side (lower side) and the number of folds of the stamp group on the right side (upper side) with the second stamp as the boundary. However, there is a condition that the bridge from left to right and from right to left must always face outward. If it meets that requirement, no matter how it is folded on the right or left side, it belongs to the total number of folding methods. This is because, as I said before, the lines (faces) of a stamp never cross. Then, pass the second stamp without covering (crossing) the already folded D?. In other words, the place where the second stamp passed is kept on the outside, and the number that will increase from now on from the stamps that have already been counted should be added. Since it will continue, it is sufficient to have information on the total number of right (lower) and left (upper) stamps on the second stamp and the number of F() facing outside of each total.  
Notes Schematic diagram of F (n)
Next, we have to think about the combination of the left side and the right side with the second stamp as the boundary. This can be done by considering the division of numbers and composition. There is already a theorem for this as in the following equation. It should be noted that both the right side and the left side are always even numbers except for the last D1. This is because it doubles when folded. D1 becomes odd when n is odd, and even when n is even. There is no need to wrap at the end, so there are both odd and even numbers.

For example, consider the case of F (12). The first two stamps are fixed, so subtract 2 to get 10. When 10 is divided, it becomes as shown in Table 2 below. bj is the division number and ck is the combination number. Table 2:


# Notes

Common cases are shown in Table 3 below. The value of comp () is the number of terms in the composition and corresponds to the value of j in bj.If one frame of Table 3 is placed as Bj, k, it will be expressed by the following formula (4).


# Divided composition diagram of F (n) (4)

Explain the formula. First, the inside of G () in the first line shown first is the one that does not own the last D1. Therefore, i is on the even side. And the first row in G () is the total number of stamps on the even side. +1 is the addition of the leftmost stamp. The second row is the first outside, but after D 1 it does not return to the even side anymore, so it becomes 1. After that, the sum of D2, D4,? D2i becomes the outside.

Next, in the second line G (), this is the one who owns D1. Therefore, i is on the odd side. Similarly, the first column in G () is the total number of stamps on the odd side. The second column is D1 at first, but the number of vertices is one larger than the number of stamps, so add +1. After that, the sum of D3, D5 ,... D2i-1 becomes the outside. Then, the product of each G () is Bj, k.

Then, by adding Bj, k by the amount of bj x ck, F(n) can be obtained. By the way, this formula also applies to the cases b1 and b2 obtained earlier. As mentioned earlier, if G () is 0 in the second and subsequent columns, it will be F(n).

In addition, this time, we discussed the stamp folding problem in the case where the first stamp is fixed, but in the usual case where the first stamp is not fixed, simply multiply the equation (5) by n. (5)


# Notes

Table 3:

Stamps never cross. Then, it moves independently on the boundary of the second stamp.

Focusing on these two points, I clarified the stamp folding problem and devised a recurrence formula.
5![Figure 1:](image-2.png "Ref 5 .")
![Figure 3:](image-3.png "")
4![Figure 4:](image-4.png "Figure 4 :")
5![Figure 5:](image-5.png "Figure 5 :")
![?(? + 1) > 2 {?(?) + ? (?(? ? 2? ? 1) × ?(2? + 1)) diagram of F (n + 1) and F (n less), G (n or less)](image-6.png "")
![Figure 6:](image-7.png "")
![, ? ? ) + 1, 1, ? 2 (? ? , ? ? ) + 1, . . . , ? ? 2? , ? ? ) + 1, ? 1 (? ? , ? ? ) + 1, . . , ? ? 2??](image-8.png "")
1below for each
1
		
		
			

				


* 
	
		Contribution à l'étude du problème des timbres poste
		
			JacquesTouchard
		
	
	
		Canadian Journal of Mathematics
		
			2
			
			1950
		
	
	in French




* 
	
		The combinatorics of paper folding
		
			MartinGardner
		
	
	
		Wheels, Life and Other Mathematical Amusements
				New York
		
			W. H. Freeman
			1983
			
		
	




* 
	
		Folding a strip of stamps
		
			JohnEKoehler
		
	
	
		Journal of Combinatorial Theory
		
			5
			2
			
			1968
		
	




* 
	
		Stamp foldings, semi-meanders, and open meanders: fast generation algorithms
		
			Joe;Sawada
		
		
			RoyLi
		
	
	
		Electronic Journal of Combinatorics
		
			19
			2
			16
			2012
		
	




* 
	
		
	
	
		Ryuhei Uehara. On Stretch Minimization Problem on Unit Strip Paper
		
			22
		
	




* 
	
		Canadian Conference on Computational Geometry
				
			2010/8/9-11
			
		
	




* 
	
		Complexity of the stamp folding problem
		
			TakuyaUmesato
		
		
			ToshikiSaitoh
		
		
			RyuheiUehara
		
		
			HiroIto
		
		
			YoshioOkamoto
		
	
	
		Theoretical computer Science
		
			497