Mathematics desk
< June 18	<< May \| June \| Jul >>	June 20 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 19

Diophantine Linear Equations

Is there a system of linear equations over $\mathbb {Z}$ that has a solution iff exactly one of the variables {x,y,z} equals one, and the rest equal zero?
Is there a system of linear equations over $\mathbb {Z}$ that has a solution iff at least one of the variables {x,y,z} equals one, and the rest equal zero?

Notice that there's no restiction on the number of variables in the system, nor there's a restriction on the number of equations. Besides, it's worth saying that equations over $\mathbb {Z} _{n}$ can be represented as equations over $\mathbb {Z}$ . Equations of the form 3x+5y+7z=1 (mod 3*5*7) or 3x+5y+7z = 3+5+7 (mod gcd(3+5,3+7,5+7)) seem to me really close to the desired, and lead me to believe that maybe such a system actually exists. 80.246.139.190 (talk) 14:00, 19 June 2016 (UTC)[reply]

If (1, 0, 0) and (0, 1, 0) are solutions then (2, -1, 0) is also a solution. To get the kind of solution sets you're talking about you'd need to have some inequalities or non-linear equations. --RDBury (talk) 14:23, 19 June 2016 (UTC)[reply]

I didn't know that, Thnak you! 185.32.179.31 (talk) 07:13, 21 June 2016 (UTC)[reply]

to index a permutation

I'd like to number the 34650 permutations of AAAABBBBCCCC, so that given the index number a fairly simple algo can return the permutation (and vice versa). Is there such an algorithm, short of generating all permutations? —Tamfang (talk) 23:49, 19 June 2016 (UTC)[reply]

Let's see, you have 4 A's, 4 B's, and 4 C's and want to index all they possible ways the can exist in a 12 character string, right ? For the first 4 digits, you would just have all 3 possible letters, while for the 5th digit on, you would need to consider if any of the letters is already used up in the previous digits, but it seems doable, yes. (The last digit can only be one possibility, based on the previous 15.) StuRat (talk) 00:21, 20 June 2016 (UTC)[reply]

More generally, suppose there are p A's, q B's and r C's and you want to find permutation K out of M = (p+q+r choose p, q, r). It turns out that the number of permutations that start with A is pM/(p+q+r), so if K ≤ this number then output A and continue with p-1, q, r and K. If K is between pM/(p+q+r) and (p+q)M/(p+q+r) then output B and continue with p, q-1, r and K-pM/(p+q+r). Finally if K>(p+q)M/(p+q+r) then output C and continue with p, q, r-1 and K-(p+q)M/(p+q+r). Repeat until p=q=r=0. --RDBury (talk) 01:31, 20 June 2016 (UTC)[reply]

What is (p+q+r choose p, q, r)? I understand (p+q+r choose p) is (p+q+r)!/(p!*(q+r)!). -- SGBailey (talk) 12:38, 21 June 2016 (UTC)[reply]

multinomial coefficient Sławomir Biały (talk) 12:41, 21 June 2016 (UTC)[reply]

BTW, producing every permutation and plunking them in an array should only take the smallest portion of a second for a computer, and fill a tiny 100 KB of memory if done efficiently (3.4 GB if done inefficiently), so I'd just do that. StuRat (talk) 02:52, 20 June 2016 (UTC)[reply]

Yes, well, I also do it with bigger sequences. —Tamfang (talk) 03:22, 17 March 2019 (UTC)[reply]

You could associate 0 with A, 1 with B and 2 with C and turn a sequence of letters into a 12 digit number. For example,

BAC BAC BAC BAC

=102102102102.

However, if you (or your programming language) don't like having 12-digit integers hanging around, you could go on to interpret that as a number in base-3

BAC BAC BAC BAC

=102102102102_{3}=224840_{10}

.

Then the index numbers run from 3320 to 528120. 129.234.0.24 (talk) 13:38, 20 June 2016 (UTC)[reply]

Sorry if I was unclear: I want a numbering such that every integer in the range is uniquely associated with a permutation. I thought of your scheme already. —Tamfang (talk) 07:05, 21 June 2016 (UTC)[reply]

Here's a Python 3 implementation of an algorithm like RDBury's.

Code and usage example

    import functools, operator

    def product(xs):
        return functools.reduce(operator.mul, xs, 1)

    def factorial(n):
        return product(range(n, 0, -1))

    def count_permutations(group_sizes):
        return factorial(sum(group_sizes)) // product(map(factorial, group_sizes))

    def nth_permutation(group_sizes, alphabet, n):
        group_sizes = list(group_sizes)
        total = count_permutations(group_sizes)
        assert len(group_sizes) == len(alphabet)
        assert n in range(total)
        out = []
        for letters_remaining in range(sum(group_sizes), 0, -1):
            for i in range(len(group_sizes)):
                subtotal = total * group_sizes[i] // letters_remaining
                if n < subtotal:
                    out.append(alphabet[i])
                    group_sizes[i] -= 1
                    total = subtotal
                    break
                n -= subtotal
            else:
                assert False
        return ''.join(out) if isinstance(alphabet, str) else tuple(out)

Example:

    >>> count_permutations((4, 4, 4))
    34650
    >>> nth_permutation((4, 4, 4), 'ABC', 0)
    'AAAABBBBCCCC'
    >>> nth_permutation((4, 4, 4), 'ABC', 1)
    'AAAABBBCBCCC'
    >>> nth_permutation((4, 4, 4), 'ABC', 34649)
    'CCCCBBBBAAAA'

-- BenRG (talk) 16:37, 20 June 2016 (UTC)[reply]

Thanks! I hope I get around to trying it before this section scrolls off. :/ First I'll have to see if I have Py3 installed … —Tamfang (talk) 07:07, 21 June 2016 (UTC)[reply]

Actually it works as-is in Python 2 also (except extremely old versions). -- BenRG (talk) 02:18, 25 June 2016 (UTC)[reply]

Ah, so it does. Even better. (Still, I suppose I really ought to migrate to 3 sooner than later.) —Tamfang (talk) 05:56, 26 June 2016 (UTC)[reply]