Primes and Squares

Nathan Merrill

3:25 AM

I've got a math problem:

Let's say I've got all 26 letters in order

A-Z

I can rearrange them by having "priorities"

So, lets assume there are 2 priorities: high and low

so, if Z was high priority, then the new order of letters is

"ZABCD...XY"

If Z and M were high priority, then the order would be "MZABCD..."

So, with a single priority system there's exactly 1 out of 26! possible orderings

Two priorities gives you (2^26)/26! orderings (right?)

Now, the question is: How many orderings are there with 3?

It's not 3^26, because 26^26 > 26!

Oh, 2^26 is wrong

because "A" at high priority is equivalent to "A" a low priority (if all other letters are low priority)

El'endia Starman

Hmm, true.

Nathan Merrill

I think it's 2^26 - 26

El'endia Starman

24 choices for the first of the high priority letters (B-Y), and then there's (23, 22, ..., 1) second choices if the first one is (B, C, ..., Y). Thus, 23 * 24 / 2 = 23 * 12 = 276, I think.

Nathan Merrill

You can have as many letters as you want to be high priority

El'endia Starman

Yeah, the 276 is for two high-priority letters.

It should be symmetric since picking X out of N to be high priority is equivalent to picking N-X out of N to be low priority.

I think this is almost exactly N choose X.

Nathan Merrill

3:39 AM

2^26 because each of the 26 letters has a high and low state. However, the only cases of equivalency is if the first N letters are high priority

Nathan Merrill

3:49 AM

@El'endiaStarman oh, by "two high-priority letters" you mean "three priorities"

is N^N - N! = N! ?

I don't think that's right

yeah, that's not

El'endia Starman

@NathanMerrill Eh? ... Oh, I think I misunderstood you.

Let's work with 3 letters for now. :P

What are the possibilities with two priorities?

Nathan Merrill

Sure. You have "LLL" "HLL" "HHL" "HHH" as equivalents to "LLL"

El'endia Starman

Really?

Nathan Merrill

"LHL", "LLH", "HLH", "LHH" aren't equivalent

El'endia Starman

Oooh.

I get it, okay.

Nathan Merrill

3:54 AM

The last four would be "BAC", "CAB", "ACB", "BCA" respectively

Of note here, is that "CBA" is impossible to represent without 3 priorities

El'endia Starman

Uh-huh, I'm tracking.

Nathan Merrill

You would need high, medium, low

Anyways, if L is the number of letters, and P is the number of priorities

if P = 2, then the number of possibilities is 2^L - L

El'endia Starman

I agree.

Nathan Merrill

awesome. So what's P=3?

or, even better, what's the equation for any P?

El'endia Starman

I think the first part is P^N because any letter can be any priority.

Nathan Merrill

3:58 AM

Right, I agree

And similar principles can apply

El'endia Starman

The second part is essentially the number of permutations that are already ordered. There's a name for this in combinatorics, lemme find it.

Nathan Merrill

You can take each of the possibilities with 2 priorities, and multiply it by L

El'endia Starman

Stars and bars (combinatorics)

In the context of combinatorial mathematics, stars and bars is a graphical aid for deriving certain combinatorial theorems. It was popularized by William Feller in his classic book on probability. It can be used to solve many simple counting problems, such as how many ways there are to put n indistinguishable balls into k distinguishable bins. == Statements of theorems == The stars and bars method is often introduced specifically to prove the following two theorems of elementary combinatorics. === Theorem one === For any pair of positive integers n and k, the number of k-tuples of posi...

Nathan Merrill

oh, stars and bars!

that's obviously the answer here

El'endia Starman

Yeah, IIRC my combinatorics teacher in high school called it "the hotdog problem" which made searching for it a bit harder. :P

So, stars and bars isn't the full story here since each group can itself be chosen from the population.

Nathan Merrill

4:10 AM

How is it not?

I'm pretty confident it is P^N - (n-1 choose p-1)

nevermind, the math isn't adding up

Ok, here's my tentative formula:

P^N - ((N+P-1) choose (P-1)) + 1

So, I'm pretty confident stars and bars is all we need here

For example, take a look at this:

AAAAA BAAAA BBAAA BBBAA BBBBA BBBBB CAAAA CBAAA CBBAA CBBBA CBBBB CCBAA CCBBA CCBBB CCCAA CCCBA CCCBB CCCCA CCCCB CCCCC

That's all of the possibilities for N = 5 and P = 3

We can basically insert a bar inbetween each letter change

which gives us P-1 bars and N + (P-1) locations to put them

So, now the real test: if P = N, then this equation should equal N!

...which is only true at N = 1 and N = 2

bah, lame

El'endia Starman

hehe

Let's go back to the example of P=2, N=3. One possibility is HHL (after sorting), and we have three distinct choices for the high priority letters, yeah? They yield ABC, ACB, BCA. The first is already sorted so is not distinct from the original.

|LLL  1  0
H|LL  3  2  BAC, CAB
HH|L  3  2  ACB, BCA
HHH|  1  0

With a given arrangement of bars, a group of size X will have N choose X possibilities for choosing the letters in that group, minus 1 because there is one selection of letters that isn't different from the original permutation.

And that applies to all but the last group since once the other groups have been determined, there's no more choice available.

Let's take the HHL example again. The first group has two items, so that's (3 choose 2 - 1) = (3 - 1) = 2, as expected.

Hrm wait, that's not a good way to do it since the available letters shrinks for each successive group.

Okay, better way: consider all N! permutations. Each group of size K defined by the bars divides this total by K! (because all permutations of letters within a group are the same after sorting).

So with HHL, the total is N!/(K_1! K_2!) = 3!/(2! 1!) = 3. Minus 1 for the permutation that's the same as the original.

Nathan Merrill

4:51 AM

Back

I realized where my algorithm went wrong, and it's slightly different than what you are describing, I think

Consider HLH

Unlike HHL (which produces ABC), it produces ACB

However, when we move up to 3 priorities: We have another equivalency

HLM is equivalent to HLH

I need to count not just the number of strings that are equivalent to ABC...Z, but any string that is equivalent to a string generated by P-1 priorities

El'endia Starman

I was taking HHL to mean that it was already sorted.

Nathan Merrill

What do you mean?

Oh, I understand

Stars and bars works way better if you don't sort it

and there's a 1 to 1 relationship

HLH means "High A Low B High C" or "AC B"

My stars and bars calculations were (nearly) correct, but I still have no idea how to count this other classification

El'endia Starman

@NathanMerrill Oh man, that's true. Well, partially. By my syntax, HHL and HML do overlap, kinda. HHL has the possibilities ACB and BCA whereas HML has the possibilities ACB, BAC, BCA, CAB, and CBA. So HML contains HHL.

@NathanMerrill I sort it because it fits stars and bars better that way. :P

Nathan Merrill

What are you counting with stars and bars?

If you are simply counting the number of equivalencies to ABCDEF, you never need to sort

Because if "E" is High priority, then the only way we keep it in "ABCDEF" order is if "ABCD" are all high priority as well

El'endia Starman

5:06 AM

For a given N and P < N, there exist permutations that cannot be represented so you have to subtract those out too.

Nathan Merrill

So, if N = 10, and P = 2, then we are looking at every permutation of H and L (assuming not sorted), right?

1. HHHHHHHHLL
2. HHHHHHHLHL
3. HHHHHHHLLH

etc

All of those are valid orderings that I need to count

but I need to subtract the equivalencies

so, because HHHHHHHHLL is equivalent to LLLLLLLLLL, I have to subtract it

but I don't have to subtract HHHHHHHLLH, because that's a unique ordering unobtainable any other way

in other words, there's no way to obtain "ABCZDEF..." using only 2 priorities without it being "HHHLLL....LLH"

El'endia Starman

Mmm, okay.

Are you missing HHHHHHHHHL?

Nathan Merrill

oh, right.

Any number of Hs and Ls

permutations with repetition

However, things get interesting with 3. The same sort of pattern arises, but its much harder to count

consider the equivalencies to HHHLHHL

they are

(I'm going to use "S" as "super-high" to make it obvious what is happening)

HHHLHHL
SHHLHHL
SSHLHHL
SSSLHHL
SSSLSHL
SSSLSSL
SSSHSSL
SSSHSSH

El'endia Starman

Uh-huh.

Nathan Merrill

So...counting that is...tough

El'endia Starman

5:18 AM

It's just N though, isn't it? You march down the "sorted" string and shift each of them to a higher priority. Oooh, not so easy if P>=4...

This might be an excellent PPCG question.

Nathan Merrill

I'd post it on Math.SE first

El'endia Starman

That too, yeah.

Lemme see if I can write some Python for this on TIO.

El'endia Starman

5:46 AM

Try it online!

Nathan Merrill

...somethings wrong with that algorithm

For example, all_perms(5,2) doesn't contain "20134"

El'endia Starman

Hmmm.

Hmm, 20134 would correspond to the binary number 11011, or 51 in decimal.

Nathan Merrill

Correct. Where are you going with this?

El'endia Starman

Oh duh, I have n ** p when it should be p ** n.

I put in a print statement that would print stuff when i == 51 and it didn't print anything. :P

tio.run/…

Nathan Merrill

6:01 AM

ok, so I'm now getting an off by 1-error

El'endia Starman

What do you mean?

Nathan Merrill

By my count, there should be 2^5 - 6 orderings

oh, wait, no, just 2^6 - 5

there are 6 equivalent elements, but we actually have to count one of them

El'endia Starman

By the way, you literally hit the first case where my code was wrong. Both versions gave the same answer for n = 1, 2, 3, 4 and p > 0.

  p 1   2   3   4   5   6
n
1   1   1   1   1   1   1
2   1   2   2   2   2   2
3   1   5   6   6   6   6
4   1   12  23  24  24  24
5   1   27  93  119 120 120
6   1   58  360 662 719 720

Nathan Merrill

oh lol :)

good thing, then too: Otherwise looking this up on OEIS would have led us on a goose chase

El'endia Starman

yeah, probably

Nathan Merrill

6:08 AM

This is it:

oeis.org/A179457

El'endia Starman

wooooo

Nathan Merrill