A380201 Triangle T(n,k) read by rows, where row n is a permutation of numbers 1 through n, such that if a deck of n cards is prepared in this order, and SpellUnder-Down dealing is used, then the resulting cards are put down in increasing order.

1, 2, 1, 1, 3, 2, 2, 4, 3, 1, 5, 3, 2, 1, 4, 4, 2, 5, 1, 3, 6, 2, 3, 4, 1, 6, 5, 7, 5, 6, 8, 1, 7, 4, 3, 2, 6, 5, 4, 1, 9, 3, 8, 2, 7, 4, 9, 10, 1, 3, 6, 8, 2, 5, 7, 6, 7, 3, 1, 11, 5, 8, 2, 10, 4, 9, 10, 3, 5, 1, 11, 12, 7, 2, 4, 6, 8, 9, 3, 8, 7, 1, 11, 6, 4, 2, 12, 13, 10, 9, 5, 12, 10, 6, 1, 13, 4, 9, 2, 14, 8, 11, 5

Offset: 1

Author

Tanya Khovanova and the MIT PRIMES STEP junior group, Jan 16 2025

Keywords

• nonn
• word
• tabl

Comments

In Spell Under-Down dealing, we spell the positive integers starting from O-N-E, moving 1 card from the top of the deck underneath the deck for each letter, followed by dealing or "putting down" the top card. So we start by putting 3 cards under for O-N-E, then we deal a card. Then we put 3 cards under for T-W-O, then we deal a card. Then we put 5 cards under for T-H-R-E-E, and subsequently deal a card. This dealing sequence is highly irregular because it depends on English spelling. The dealing pattern starts: UUUDUUUDUUUUUD, where each "U" corresponds to putting a card “under” and each "D" corresponds to dealing a card “down”.

This card dealing can be thought of as a generalized version of the Josephus problem. In this version of the Josephus problem, we spell the positive integers in increasing order, each time skipping past 1 person for each letter and executing the next person. The card in row n and column k is x if and only if in the corresponding Josephus problem with n people, the person numbered x is the k-th person eliminated.

Equivalently, each row of the corresponding Josephus triangle A380247 is an inverse permutation of the corresponding row of this triangle. The first column is A380246, the order of elimination of the first person in the corresponding Josephus problem. The index of the largest number in row n is A380204(n), corresponding to the index of the freed person in the corresponding Josephus problem. The number of card moves if we start with n cards is A380202 = A067278(n) + n.

Examples

			Triangle begins:
  1;
  2, 1;
  1, 3, 2;
  2, 4, 3, 1;
  5, 3, 2, 1, 4;
  4, 2, 5, 1, 3, 6;
  2, 3, 4, 1, 6, 5, 7;
  5, 6, 8, 1, 7, 4, 3, 2;
  ...
For n = 4 suppose there are four cards arranged in order 2, 4, 3, 1. Three cards go under for each letter in O-N-E, then 1 is dealt. Now the deck is ordered 2,4,3. Three cards go under for each letter in T-W-O, then card 2 is dealt. Now the leftover deck is ordered 4,3. Five cards go under for each letter in T-H-R-E-E, then card 3 is dealt. Finally, card 4 is dealt. The dealt cards are in numerical order. Thus, the fourth row of the triangle is 2, 4, 3, 1.
		

Crossrefs

Cf. A005589, A006257, A225381, A321298, A378635, A380201, A380202, A380204, A380246, A380247, A380248.

Programs

Python

from num2words import num2words as n2w
def spell(n):
    return sum(1 for c in n2w(n).replace(" and", "").replace(" ", "").replace(",","").replace("-", ""))
def nthRow(n):
    l = []
    for i in range(0,n):
        l.append(0)
    zp = 0
    for j in range(1,n+1):
        zc = 0
        while zc <= spell(j):
            if l[zp] == 0:
                zc += 1
            zp += 1
            zp = zp % n
        l[zp-1] = str(j)
    return l
l = []
for i in range(1,20):
    l += nthRow(i)
print(", ".join(l))