Search

We denote by b(n) the number of ways of expressing the positive integer n as the sum of powers of 2 and we call b(n) ‘the binary partition function’. This function has been studied by Euler (1), Tanturri (2–4), Mahler (5), de Bruijn(6) and Pennington (7). Euler and Tanturri were primarily concerned with deriving formulae for the precise calculation of b(n), whereas Mahler deduced an asymptotic formula for log b(n) from his analysis of the functions satisfying a certain class of functional equations. De Bruijn and Pennington extended Mahler's work and obtained more precise results.

Golomb has conjectured that the number of cycles generated by an arbitrary binary recurrence relation does not exceed Z(n), the number of cycles generated by the pure cycling register. Lempel gives a conjecture which implies that of Golomb, and he also introduces so called V-sets. We color the vertices of the de Bruijn graph Bn in order to find V-sets, and this leads to a proof of Lempel's conjecture.

A result of Sperner [1] determining the maximal number of subsets of a given set, such that no one is included in the other, has been generalized and strengthened modifying the restrictive condition by Erdos [2], by Katona [3], and Kleitman [7], and by others [4, 5]. A different kind of generalization has been obtained by de Bruijn, Tenbergen, and Kruywijk [6] using the same restrictive condition but for more general entities than sets, namely, for systems in which the elements may occur more than once. That approach is fundamental for number-theoretical considerations since the totality of prime divisors of a given number (each considered with its multiplicity) is of that nature. In this paper we will generalize the results of [2] and [3, 7] in the sense of [6].

We investigate Ford's method for generating a de Bruijn cycle of degree n . We show that the feedback function which generates the cycle has the minimum possible number of positions equal to 1 and we give an algorithm which finds those positions for all n .

where 0? a ?1. The purpose of this article is to investigate the rapidity of convergence of sequences generated by functions of the class H and of certain subclasses. We first dispose of the cases 0

Let G be a group acting on a finite set S. Let L be a G-stable subset of S and denote by $\Delta $ a transversal for the orbit partition of G acting on L. The problem of devising efficient generating algorithms for $\Delta $ is called the “isomorph rejection” problem. Given a field F of characteristic zero, let $F^S $ denote all functions from S to F. Note that $F^S $ is an algebra under the operations of pointwise addition and multiplication. The problem of generating $\Delta $ or $I_\Delta $ (the Indicator or characteristic function of $\Delta $) may be regarded as a special case of the problem of generating and representing functions $\varphi $ in $F^S $ (in case $\varphi = I_\Delta $). In this context, instead of attempting to generate $I_\Delta $ directly one may instead choose a pair of linear operators $(T_0 ,T_1 )$ and attempt to construct functions $v_1 , \cdots ,v_p $ in $F^S $ such that $T_0 (v_1 + \cdots + v_p ) = T_1 (I_\Delta )$. The construction of $(v_1 , \cdots ,v_p )$ may be regarded as ...

The Fabry-Perot interferometer approximately by a system of two infinitely long, plane parallel strip mirrors is investigated on the basis of a standing-wave type formulation. The corresponding integral equation is numerically solved for a very small value of the Fresnel number. The field distributions in the plane of symmetry are given and discussed. In this limit of a very small Fresnel number the mirrors are very far apart and the problem under investigation may be looked at from the viewpoint of antenna theory. The Bouwkamp and de Bruijn work on the optimum current distribution of a thin wire antenna is outlined, and the connection with the resonator theory is established. It is demonstrated that these two theories predict similar distributions. In a sense, the resonator formulation may be considered to be a generalization of that antenna work. Siegman has carried out experiments with a ruby laser whose end faces had been unsilvered except over a minute area of one end face. The mode patterns observed at the opposite end face are in favourable agreement with the theoretical results presented. In conclusion, it is believed that Siegman hs now verified by experiment the mathematical analysis carried out by Bouwkamp and de Bruijn two decades ago.

The paper settles the asymptotic behaviour of the solutions of the difference-differential equation (1.1) in a case that was left open in N. G. de Bruijn [1]. Theorem 3.1 states that in this case all solutions have limits for x → ∞. A result about the speed of convergence is given by theorem 4.1.

Let {ai} be an increasing sequence of positive integers containing no three distinct elements ai, aj, ak, for which the lowest common multiple of i, j is equal to k. By using the theorem mentioned in the tille, we prove that for sufficiently large n,∑ai⩽n1ai

A phenotype system is a mapping of a set of genotypes into a set of phenotypes. Two phenotype systems are permutationally equivalent if some permutation or combination of permutations of gene symbols or locus symbols makes them identical. A set of permutationally equivalent phenotype systems is called a phenogram . Two mappings of a set D into a set R are said to be equivalent and to belong to the same pattern if the first mapping performed on some permutation of D is identical to the second performed in conjunction with some permutation of R . Thus the number of phenotype systems which are identical under some permutation of gene or locus symbols is precisely the number of patterns of phenotype systems. De Bruijn's extension of Polya's fundamental counting theorem, which enumerates the number of patterns, is introduced in terms sufficiently general to allow its application to other biological enumeration problems. The theorem is used to solve the general phenogram enumeration problem, i.e. given any genetic system whatever, how many phenograms are there with exactly φ phenotypes? The results of calculations for several basic genetic systems are presented, along with some observations on these. A nomenclature which simplifies the presentation of two locus systems showing epistasis is suggested. Several applications of phenogram analysis are discussed.

Summary A special problem in renewal theory is considered. The asymptotic behavior of the renewal function was studied by W. L. Smith. Here we show that his result with an exponentially small remainder term follows from a theorem of De Bruijn on Volterra integral equations.

The structure of complementing pairs A and B has been studied by de Bruijn [1], [2], [3] for the cases C = I and C = N and by A. M. Vaidya [7] who reproduced a fundamental result of de Bruijn for the latter case. In case C = N it is easy to see that A Π B = {0} and that 1 e A U B. Moreover, if we agree that 1 e A, it follows from the work of de Bruijn, that, except in the trivial case A = N, B = {0}, A and B are infinite complementing subsets of N if and only if there exists an infinite sequence of integers {m

A homomorphism of the de Bruijn graph that maps a graph of order n onto one of order n-1 and its applications to the design of nonsingular feedback shift registers are discussed. The properties preserved under this mapping suggest a new design technique whose main advantage is due to the fact that the problem of designing a desired n-stage shift register may be reduced to a problem of order n-1 or less. Among the results obtained is a recursive formula for a feedback function that generates a cycle of maximum length.

where e is an arbitrarily small positive number, p denotes primes, h> 2, and the constants implied in the 0-symbols depend on e and h. Vinogradoff [4] in his proof of the theorexm that every large odd number is the sum of three primes, gives a much cruder estimate than (1'). Recently Ankeny2 proved that if p-3 (mod 4), then n(p) Po(e), where n(p) is the least positive quadratic nonresidue of the prime p. This proof uses de Bruijn's estimates for J (x, y) and g(x, y) in a sharper form, however, than those given above. We follow de Bruijn in proving (1') and (1") which are listed as Theorems 1 and 2 below. Although these results are only special cases of de Bruijn's work, they seem important enough to merit simple proofs. Although our proof follows de Bruijn's very closely, we believe it is considerably simpler. Writing

This paper establishes an extremal property for finite projective planes; it is a characteristic property, if we disregard configurations containing fewer than four points. A finite plane consists of k2-k+I points, with lines each of which contains only k points; nevertheless every two lines meet. This would not be remarkable if, say, we could define a "line" as any set of k points containing a specified point Po; but we must satisfy the homogeneity condition, that each point is contained in exactly k lines. The theorem says that k2-k+l is the largest number of points which can be arranged in such a pattern. A similar, almost characteristic, inequality has been established by de Bruijn and Erd6sl [1 ]: in a set of n points one cannot find more than n subsets, every two of which have exactly one common point. There are two trivial ways of constructing such a family for any n, but if there are to be four points, no three of which are on a line, then the finite projective planes are the only possibilities. Both theorems generalize2 to the case in which a pair of lines must have more than one common point. The precise results are

Using a theorem due to de Bruijn, van Aardenne-Ehrenfest, C. A. B. Smith and Tutte concerning the number of circuits in oriented linear graphs, an expression is found for the probability of a specified frequency count of $m$-tuples in a circular sequence where the $n$-tuple $(n < m)$ count is given. The corresponding result for linear sequences can be deduced--see [14]. The result is valid for stationary Markovity of any order up to and including the $(n - 1)$-st. A method of deriving asymptotic distributions is indicated, and a few additional observations made concerning the distribution of pairs in a circular array.

The number of (n - m) terms as a function of the length between their recurrence is derived for maximal length linear n -stage shift-register generated sequences. An (n - m) term is defined as that state remaining following specification of m components, of the n component shift-register state, as "don't care" variables. The derivation makes application of the cycle-and-add property for such sequences. The distribution is shown to be of value (2^{m} - 1) for all recurrence lengths less than the period of the sequence and of value (2^{n} - 1) when the recurrence length is equal to the period of the sequence. [1] In addition, it is concluded that the distribution of (n - m) terms for de Bruijn sequences (maximal-length nonlinear recursions) is dependent upon (n - m) term construction.