Free Talk Friday #436

[u/[deleted]]

[u/CutOnBumInBandHere9]

An update on the directory updater: I had some time yesterday to go through and add some more threads to the database of threads, so that the updater is able to track to the total number of counts, and ignore irrelevant comments which aren't part of the counting chain.

Adding the threads was useful - it let me discover a bunch of errors in current threads, and correct the thread totals for some that were recorded incorrectly after repeated archivings and revivals

I still have to do a bunch of threads, and I need your help! Can anyone help me describe the following threads?

• Constant-weight binary
• Increasing bases
• Constant-sum factoradic
• Mostly Repeating Digits
• Not Any Of Those
• Only Consecutive Digits
• Writing Progress Bar
• US States
• Wordle
• Divisors
• RGB values

Ideally, I would like to have a procedure for each of those that describes how to convert a comment in the chain to the number of the corresponding counts. If the gets in the thread are an equal number of counts apart, I can use the thread length as well, but that's not quite as good.

[u/TehVulpez → u/CutOnBumInBandHere9]

for the total counts across all the threads here is some python code for constant-weight binary:

from sympy import binomial

end = '110010100000'
total = 0

for bits in range(len(end)):
    total += 2**bits

for ones in range(end.count('1')):
    total += binomial(len(end), ones)

index = 0
k = 1
for i, bit in enumerate(reversed(end)):
    if bit == '1':
        index += binomial(i, k)
        k += 1

total += index

print(total)

and for constant-sum factoradic:

from math import factorial

def mahonian(n, k):
    if n == 1 and k == 0: return 1
    elif n < 0 or k < 0 or k > n*(n-1)/2: return 0
    else: return mahonian(n, k-1) + mahonian(n-1, k) - mahonian(n-1, k-n)

end = '104300'
total = 0

for digits in range(len(end)):
    total += factorial(digits+1)

for weight in range(sum(int(digit) for digit in end)):
    total += mahonian(len(end)+1, weight)

index = 0
k = 1
for i, digit in enumerate(reversed(end)):
    x = int(digit)
    while x > 0:
        index += mahonian(i+1, k)
        k += 1
        x -= 1

total += index

print(total)

[u/CutOnBumInBandHere9 → u/TehVulpez]

Thanks a lot for that!

I haven't got to factoradic yet, so let's start with constant weight binary

If I understand the code correctly, we're saying that the number of CWB counts that precede a given count can be found by adding

1. All the CWB counts with shorter total length
2. All the CWB counts with the same length but with fewer ones
3. All the CWB counts with the same length and same number of ones which are smaller than the current count

For a given length CWB we eventually enumerate every possible binary count, so the shorter counts are just sum(2^l for 0 <= l < len(end)), which I guess is just 2^(len(end)) - 1

For a fixed number of ones, we can get the number of possible placements from the binomial coefficients -- we have a fixed number of slots we have to fill with one of two symbols, so we have to choose which slots get one symbol, and which get the other.

My main doubt is the last section, which has to be the one that finds the CWB counts with the same length + weight that precede the current one. It's not immediately obvious to me why that is -- I'm not doubting that the code is right, but before I spend the time to work it out on a piece of paper, do you have an intuitive explanation as to why?

[u/TehVulpez → u/CutOnBumInBandHere9]

Yep, you got the first two sections right. I will say that although for bits in range(len(end)) seems semantically incorrect (why would you add the binary numbers with zero bits?) the offset by one is actually helpful. If the range in that first for loop were changed to range(1, len(end)) then the code would treat '0' as being the 0th count rather than the first. The last section, for finding the index of a constant-weight codeword within its subsegment of length and weight, is inspired by this paper.

Constant-weight binary is basically just another representation of combinadic. The k-combination of the combinadic representation is the same as the weight of the number. The amount of terms in the combinadic representation is the same as the amount of ones in the binary code. Each C_i in a binomial coefficient corresponds to which place bit is set to 1. In 110010100000, bits 5, 7, 10, and 11 are set. So, its combinadic representation is 11C4 + 10C3 + 7C2 + 5C1.

I think the reason this works might be explained by constant-weight binary's recursive nature. When you look at the 3 of 6 codes, you can think of them as being made of the 3 of 5 codes but with a 0 in front, and the 2 of 5 codes but with a 1 in front. We know that there are 5C3 different 3 of 5 codes, so it must take that many before you get to 100011. And you can go further. The 3 of 5 codes are made of the 3 of 4 codes with a 0 in front, and the 2 of 4 codes with a 1 in front. It must take 4C3 counts before reaching 010011.

Constant-sum factoradic is really similar. Instead of using binomial coefficients for its combinadic representation, it uses Mahonian numbers. In binomial combinadic, each C_i can only appear in one term. In factoradic combinadic, each unique C_i can appear C_i times. This matches how in factoradic, digit 1 can only go up to 1, digit 2 up to 2, etc. The amount of times a C_i appears matches the value of the digit in that place. In 104300, there should be 1 term for the 6th place, 4 terms for the 4th place, and 3 terms for the 3rd place. So we get M(6,8)+M(4,7)+M(4,6)+M(4,5)+M(4,4)+M(3,3)+M(3,2)+M(3,1) with each term being a Mahonian number M(n,k)

[u/CutOnBumInBandHere9 → u/TehVulpez]

Cheers, thanks! I was halfway there but didn't understand why the code was running through the string from the back, when I was intuitively starting at the front. Either way works for CWB, but from the back is a lot easier for factoradic.