Combinatorial Identities Via Phi Functions and Relatively Prime Subsets

Details Combinatorial Identities Via Phi Functions and Relatively Prime Subsets Combinatorial Identities Via Phi Functions and Relatively Prime Subsets

2010-02-17

arxiv.org/abs/1002.3254v1

Mathematics

Number Theory

Scientific paper

Let $n$ be a positive integer and let $A$ be nonempty finite set of positive integers. We say that $A$ is relatively prime if $\gcd(A) =1$ and that $A$ is relatively prime to $n$ if $\gcd(A,n)=1$. In this work we count the number of nonempty subsets of $A$ which are relatively prime and the number of nonempty subsets of $A$ which are relatively prime to $n$. Related formulas are also obtained for the number of such subsets having some fixed cardinality. This extends previous work for the cases where $A$ is an interval or a set in arithmetic progression. Applications include: a) An exact formula is obtained for the number of elements of $A$ which are co-prime to $n$; note that this number is $\phi(n)$ if $A=[1,n]$. b) Algebraic characterizations are found for a nonempty finite set of positive integers to have elements which are all pairwise co-prime and consequently a formula is given for the number of nonempty subsets of $A$ whose elements are pairwise co-prime. c) We provide combinatorial formulas involving Mertens function.

Affiliated with

Also associated with

No associations

Rating

Combinatorial Identities Via Phi Functions and Relatively Prime Subsets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorial Identities Via Phi Functions and Relatively Prime Subsets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial Identities Via Phi Functions and Relatively Prime Subsets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-51923