[PDF] Some Combinatorics of Factorial Base Representations

Some Facts about Factorials

Some Facts about Factorials By definition, n=n(n−1)(n−2) (3)(2)(1) In words, the factorial of a number n is the product of n factors, starting with n, then 1 less than n, then 2

Sur la somme de certaines séries de factorielles

La somme est finie et la formule est valable V x E C~ si n 0 ou ,~3 E ~T ~et dans ce cas x non entier négatif); elle est valable pour Rx > sinon Démonstration - Pour n = 0, c est trivialement vérifié Pour n -Ion procède par récurrence sur -n Les égalités prouvent la relation si n = -1

Some Combinatorics of Factorial Base Representations

23 11 Article 20 3 3 2 Journal of Integer Sequences, Vol 23 (2020), 3 6 1 47 Some Combinatorics of Factorial Base Representations Tyler Ball Clover Park High School

Top Ten Summation Formulas

Top Ten Summation Formulas Name Summation formula Constraints 1 Binomial theorem (x+y) n= Xn k=0 n k x − ky integer n ≥ 0 Binomial series X k α k xk = (1+x)α x < 1 if α 6=

Analyses factorielles simples et multiples - 5e édition

viii Table des matières 10 3 Première analyse : les tableaux en supplémentaire dans l’AFC de leur somme 239 10 4 Deuxième analyse : AFC de variables croisées ou de tableaux

Structures de contrôle itératives - Fiche 1 Exercice 1

writeln('La somme est ', s:5:2) ; End Exercice 2: Écrire un programme qui permet de faire le factoriel d'un entier n donné Exemples : 6= 1 x 2 x 3 x 4 x 5 x 6 = 720 Algorithme : 0) Début Factoriel 1) Ecrire('Donner un entier') , lire(n) 2) [f← 1] pour i de 2 à n faire f ← f * i FinPour 3) Ecrire(''Le factoriel est '', f) 4) Fin Factoriel

Calcul mathématique avec Sage

Calcul mathématique avec Sage 3 lien,MarcMezzarobba,ClémentPernetetNicolasThiéryd’écrireunlivresur Sage,tousontréponduprésent

wwwnormalesuporg

Created Date: 8/27/2019 3:48:00 PM

Analyse Factorielle des Correspondances

9) Pour qualifier d'importante la contribution d'un point à un axe factoriel, on calcule une valeur-repère Pour les données Régions, on pourra prendre comme valeur repère 1/22=0,046 a) Utiliser cette valeur repère pour déterminer les régions contribuant aux axes 1 et 2 b) Indiquer en quoi consiste, en résumé, l'axe 1

Les plans d’expériences Initiation à la construction et l

On ne peut donc pas prendre la somme des écarts comme mesure de la dispersion C'est pourquoi on fait disparaitre le signe négatif en prenant les écarts 3 Ces écarts à la moyenne sont donc élevés au carré et additionnés On obtient ainsi la somme des carrés des écarts à la moyenne: (-0 4)² + (1 1)² + (-1 1)² + (0 40)² = 2 74 4

[PDF] exercice nombre d'or 1ere s

[PDF] obésité classe 1

[PDF] imc normal

[PDF] indice poids taille age

[PDF] indice de masse corporelle

[PDF] calculer son imc

[PDF] cdt alcool taux normal

[PDF] taux cdt

[PDF] calcul taux alcoolémie formule

[PDF] taux d'alcoolémie mortel

[PDF] taux d'alcool permis quebec

[PDF] 0.08 alcool age

[PDF] multiplication et division de fraction

[PDF] évaluation 5ème maths

[PDF] mathématiques 5ème

2311Article 20.3.3Journal of Integer Sequences, Vol. 23 (2020),

2 3 6 1 47

Some Combinatorics of

Factorial Base Representations

Tyler Ball

Clover Park High School

Lakewood, WA 98499

USA t.ball.6174@gmail.com

Paul Dalenberg

Department of Mathematics

Oregon State University

Corvallis, OR 97331

USA dalenbep@oregonstate.edu

Joanne Beckford

University of Pennsylvania

Philadelphia, PA 19104

USA joannemb@sas.upenn.edu

Tom Edgar

Department of Mathematics

Pacific Lutheran University

Tacoma, WA 98447

USA edgartj@plu.edu

Tina Rajabi

University of Washington

Seattle, WA 98195

USA rajabit@uw.edu

Abstract

Every non-negative integer can be written using the factorial base representation. We explore certain combinatorial structures arising from the arithmetic of these rep- resentations. In particular, we investigate the sum-of-digits function, carry sequences, and a partial order referred to as digital dominance. Finally, we describe an analog of a classical theorem due to Kummer that relates the combinatorial objects of interest by constructing a variety of new integer sequences. 1

1 IntroductionKummer"s theorem famously draws a connection between the traditional addition algorithm

of base-prepresentations of integers and the prime factorization ofbinomial coefficients. Theorem 1(Kummer).Letn,m, andpall be natural numbers withpprime. Then the exponent of the largest power ofpdividing?n+m n?is the sum of the carries when adding the base-prepresentations ofnandm.

Ball et al. [

2] define a new class of generalized binomial coefficients that allow them to

extend Kummer"s theorem to base-brepresentations whenbis not prime, and they discuss connections between base-brepresentations and a certain partial order, known as the base-b (digital) dominance order. Furthermore, whenpis prime, de Castro et al. [

3] show that this

partial order encodes more information about the exponentsof the corresponding binomial coefficients, adding to investigations of Pascal"s trianglemodulo prime powers and related Sierpi´nski-like triangles arising from generalized binomial coefficients.

Edgar et al. [

5] use similar techniques with rational base representations to describe fami-

lies of generalized binomial coefficients with Kummer"s theorem analogs for the corresponding representations. In the present work, we investigate the representation of integers as sums of factorials, which have been well-studied [

7,8,13,14]. We use these representations to define

a new family of integer partitions, some new families of generalized binomial coefficients, and the corresponding digital dominance order yielding analogs of Kummer"s theorem for these representations. The paper is organized as follows. In Section

2, we discuss known

results about factorial base representations, the factorial base sum-of-digits function, and the arithmetic arising from these representations. In Section

3, we investigate the set of

carry sequences coming from factorial base arithmetic and explain how these sequences are connected to a new family of integer partitions, which we call hyperfactorial partitions; in particular, we describe how to construct, and how to count, hyperfactorial partitions. In

Section

4, we introduce the notion of generalized binomial coefficients and describe three

different families of generalized binomial coefficients. We show that all of these generalized binomial coefficients are integral by producing three different analogs of Kummer"s theorem for factorial base representations. Finally, in Section

5, we demonstrate how the results

of de Castro et al. [

3] basically extend to factorial base representations and describe the

connections between the factorial base sum-of-digits function, hyperfactorial partitions, one family of generalized binomial coefficients, and the digitaldominance order defined in terms of factorial base representations. 2

2 Factorial base representations and the sum-of-digits

function

Figure

1[4] provides a visual demonstration (in the case when?= 4) of the fact that

i=1i·i! = (?+ 1)!-1 (1) for all positive integers?, which can be proved in general by induction; this formula provides the well-known fact that every natural numberncan be written uniquely as n=n1·1! +n2·2! +n3·3! +···+nk·k! =k? i=1n i·i! thefactorial base representationforn. We note that we have written the factorial base in order from the least significant to most significant digit, which is nonstandard. Also, we mention that it is often convenient to append 0"s to a representation to change the length of the corresponding list. Factorial base representations have been well-studied and provide a standard way of enumerating and ranking permutations [

7,8,9,10,12,13].

For example 17 = 1·1!+2·2!+2·3! so 17 = (1,2,2)!and 705 = 1·1!+1·2!+1·3!+4·4!+5·5!

so that 705 = (1,1,1,4,5)!. We also define thefactorial base sum-of-digits functions!by s !(n) =?ki=1niwheren= (n1,n2,...,nk)!, so thats!(17) = 1 + 2 + 2 = 5 ands!(705) =

1 + 1 + 1 + 4 + 5 = 12.

Fraenkel [

8] shows how to construct factorial base representations using the repeated

division algorithm; one consequence of his construction isthe following factorial base digit formula, which can also be proved using equation 1. n i=? (i+ 1)·?n (i+ 1)!?? ?n i!? mod (i+ 1), where{x}=x- ?x?represents the fractional part ofx.

The following corollary seems to be well known.

Corollary 3.For alln?N,s!(n) =n-?ki=1i·?

n (i+1)!?

Proof.Letn= (n1,n2,...,nk)!. Then by Theorem

2, 3 2! 3 4 3! 5 4! Figure 1: A proof without words about the factorial sum in equation ( 1). 4 s!(n) =k? i=1n i=k? i=1? (i+ 1)·?n(i+ 1)!?? =k? i=1? (i+ 1)?n(i+ 1)!-?n(i+ 1)!??? k? i=1? n i!-(i+ 1)?n(i+ 1)!?? n (i+1)!? is an integer so that we now have s!(n) =k? i=1? n i!? -k? i=1(i+ 1)?n(i+ 1)!? =k? i=1? ni!? -k+1? i=2i?ni!? ?n 1!? +k+1? i=2? ni!? -?n(k+ 1)!? -k+1? i=2i?ni!? =n-?n (k+ 1)!? +k+1? i=2? ni!? -k+1? i=2i?ni!? =n-?n (k+ 1)!? -k+1? i=2(i-1)?ni!? =n-?n (k+ 1)!? -k? i=1i?n(i+ 1)!?

However, sincen <(k+1)!, we have?

n (k+1)!? = 0; therefore,s!(n) =n-?ki=1i·? n(i+1)!? The OEIS [18] lists the factorial base sum-of-digits sequence inA034968; the first few terms of this sequence are

0,1,1,2,2,3,1,2,2,3,3,4,2,3,3,4,4,5,....

Figure

1inspires us to write this sequence in an irregular table in Figure2; each of the rows

T n-1+ 1 throughTnhaven! entries whereT?=??i=1irepresents the triangular number. 5 row 00 row 1 1 row 21 2 row 3 2 3 row 41 2 2 3 3 4 row 5

2 3 3 4 4 5

row 6

3 4 4 5 5 6

row 71 2 2 3 3 4 2 3 3 4 4 5 3 4 4 5 5 6 4 5 5 6 6 7 row 8

2 3 3 4 4 5 3 4 4 5 5 6 4 5 5 6 6 7 5 6 6 7 7 8

row 9

3 4 4 5 5 6 4 5 5 6 6 7 5 6 6 7 7 8 6 7 7 8 8 9

row 10

4 5 5 6 6 7 5 6 6 7 7 8 6 7 7 8 8 9 7 8 8 9 9 10

Figure 2: The factorial base sum-of-digits sequence arranged in an irregular table inspired by Figure 1. Notice that rowTn+1 (highlighted in red) can be obtained by re-listing all of the entries from rowsTn-1+ 1 toTnfollowed by the entries of rowTneach incremented by 1. For instance, row 11 (not pictured) would contain 120 entries: the first 24 would be the same as row 7, the second 24 the same as row 8, the third 24 the same as row 9, the fourth 24 the same as row 10, and the last 24 would be obtained by incrementing each entry of row 10 by 1: row 10

5 6 6 7 7 8 6 7 7 8 8 9 7 8 8 9 9 10 8 9 9 10 10 11+1

Furthermore, notice that rowTn+ 1 always begins with 1 since this entry corresponds to the sum of digits ofn!. By equation (

1), we see that the last entry in rowTnisTnsince this

entry corresponds to the sum of digits ofn!-1 = (1,2,3,...,n-1)!. There are many other interesting patterns to find in this table; for instance, if we fix a row, sayr, with?! entries, then the sum of entriessand?!-sin rowrwill be the same no matter whatswe choose. We finish this section by describing the arithmetic of factorial base representations.

Lenstra [

14] states how to determine the factorial base representationof a sum if we know

the factorial base representations of the two summands. We make the process more formal in order to define a combinatorial object of interest. Given two positive integersnandm, we define thefactorial carry sequencefornandm, denoted?n,m!= (?0,?1,?2,...,?k), by 0= 0; i=?

1,ifni+mi+?i-1> i.

We will leave off the subscript, !, and when there is no confusion aboutnandm, we will simply write?:=?n,m!. An alternate characterization of each entry in?n,mis given by the following proposition. Proposition 4.Let?be the factorial carry sequence for two natural numbersnandm.

Then?i=??i-1+ni+mi

i+1?fori >0. 6

0 =?0 + 0 + 0

i+ 1? = 0.

Therefore,

?mi+ni+?i-1 i+1?= 0.

Case 2.If?i-1+mi+ni≥i+ 1, then?i= 1 and

1 =?i+ 1

i+ 1? =?2i+ 1i+ 1? = 1

Therefore,

?mi+ni+?i-1 i+1?= 1. Since in each case the equality holds,?i=??i-1+ni+mi i+1?. The carry sequence allows us to construct the factorial baserepresentation of the sum of two integers. Theorem 5.Letn= (n1,n2,...,nk)!,m= (m1,m2,...,mk)!, andn+m= ((n+m)1,(n+ m)2,...,(n+m)k))!where we append zeroes to ensure all three representations are the same length. If?= (?0,?1,...,?k)is the factorial carry sequence fornandm, then(n+m)i= n i+mi+?i-1-?i·(i+ 1)for alli. n n factorial base representation of some numbera.

Now, we see that

k i=1a i·i! =k? i=1(ni+mi+?(i-1)-?i·(i+ 1))·i!quotesdbs_dbs12.pdfusesText_18