Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: combinatorics

  1. #1
    Member
    Joined
    Dec 2017
    From
    Tel Aviv
    Posts
    127

    combinatorics

    I try to divide the problems to sub-problems.
    The set S contain four element {0, 1, 2, 3}. n = 4. n = number of element
    a,b,(a+b) is in the set.
    Why the number of equations in S that have: a+b=b+a is n*(n+1)?
    In the set operation 4*5=20.
    There are 20 equations that:
    0+1=1+0
    1+1=1+1
    ...
    I repeat on the question to be clear:
    Why the number of exercises (with the + operation) is the number of element of S (n) multiplied by (n+1)?
    If You don't understand, explain to me what sentence you don't understand(!!) so I will fix it...
    Last edited by policer; Aug 18th 2018 at 11:40 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,631
    Thanks
    1457

    Re: combinatorics

    Here are some reasons why this is difficult to understand. There are only 4 elements in the set, so that means that there are only $4\times 4 = 16$ possible expressions of elements in the set being added. Yet, you say there are 20 set operations? I am not sure where you got this number or why you think that it is even possible that it is correct.
    Next, you are asking why addition is commutative? That is not even remotely related to combinatorics, so I think I may not be understanding why you are asking how many commutative additions are possible.
    Then, you have the word "exercises" being used in a way that I am not familiar. An "exercise" may be a practice problem or what a person does when they exert themselves physically, but I am not sure I am understanding your intended meaning for the word. From the context, it may be that you meant to use the word expression, as an expression could be of the form 0+1, as you wrote above.
    Finally, I am wondering if you really mean that this is a combinatorics problem or if you are discussing group theory. You are asking about commutativity and then you mention $S(n)$, which is the symmetric group on $n$-elements. It happens to be a group of tremendous value in combinatorics, but it is not an additive group, it is multiplicative. And its multiplication is not commutative. And how you are using the numbers in the set $S$ are not quite how you would use it in group theory, which makes me think maybe you are not talking about the symmetric group. But then, I don't understand the relevance of $S (n)$.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2017
    From
    Tel Aviv
    Posts
    127

    Re: combinatorics

    The set A contains the items 0,1,2,3.


    How many expression obey the commutative law (with the operation +) If the result of the expression belong to A?

    What the number of expression in set M that contain n items from 0..n-1 that it result is the expression and the result belong to M?
    [With plus operation]
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,631
    Thanks
    1457

    Re: combinatorics

    What are you actually asking? If you are looking for the number of expressions with exactly one plus sign over four elements, it is 16:

    0+0
    0+1
    0+2
    0+3
    1+0
    1+1
    1+2
    1+3
    2+0
    2+1
    2+2
    2+3
    3+0
    3+1
    3+2
    3+3

    But, what constitutes an expression in general? If you do not specify that you are only interested in expressions with exactly one plus sign, then you can have expressions of the form $0+0+\cdots + 0$. In this case, there are infinitely many expressions possible.

    And I do not understand why you specify that the expression must obey the commutative law over addition. 0,1,2,3 are all natural numbers, and unless specified otherwise, they inherit the addition from the natural numbers. That addition is commutative for all natural numbers, so any expression you can create will obey the commutative law.

    What you are asking has too many answers to be a valid mathematical question. Math requires some degree of specificity.

    What is the set M? I am not understanding what its elements are. Are they the expressions of elements in A? And what do you mean the "result is the expression and the result belong to M?" It is starting to sound like you are looking for the cardinality of the free group with four generators (hint: it is infinite).

    So, here are my guesses for answers (this is the best I can do):

    My guess is that $M = \{'a+b': a,b \in A\}$ is the set of all expressions with a single plus sign where the operands are elements in $A$.

    $$|M| = 4\times 4 = 16$$

    Next, you seem to be discussing a function $E:M \to \mathbb{N}$ such that $'a+b' \mapsto a+b$. You are looking for the cardinality of the set $\{'a+b'\in M: E('a+b') \in A\}$. That would be the following elements:
    0+0
    0+1
    0+2
    0+3
    1+0
    1+1
    1+2
    2+0
    2+1
    3+0

    There are 10 expressions whose sums are in $A$. This is $\dfrac{4(4+1)}{2}$. In general, $A$ contained elements $\{0,\ldots, n-1\}$ then the number of expressions with a single addition symbol such that the expressions evaluate to values in $A$, there would be $\dfrac{n(n+1)}{2} = \dbinom{n+1}{2}$ of them. This is proven because:

    0 can be added to any element of $A$.
    1 can be added to any element of $A$ except $n$.
    2 can be added to any element of $A$ except $n-1$ or $n$.
    In general, $i\in A$ can be added to any element $j\in A$ except $n-i+1, \ldots, n$ (there are $i$ forbidden elements).
    This gives the number of possible additions:

    $$\sum_{k=0}^n (n-k) = \sum_{k=0}^n k = \dbinom{n+1}{2} = \dfrac{n(n+1)}{2}$$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics - HELP! ( FCP)
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Oct 26th 2013, 01:57 AM
  2. Combinatorics
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: May 6th 2012, 11:56 AM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 6th 2009, 08:25 AM
  4. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 28th 2009, 12:57 PM
  5. Need help with combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 16th 2009, 09:03 AM

/mathhelpforum @mathhelpforum