|
%I #8 Nov 06 2018 13:29:26
%S 1,3,9,24,60,141,328,738,1647,3618,7893,17055,36619,78144,165888,
%T 350619,738012,1548279,3237611,6752439,14046525,29157612,60396996,
%U 124885167
%N Number of possible states when placing n tokens of 2 alternating types on 3 piles.
%C Piles start empty and have no height limit. A token can only be placed on top of a pile. The starting token is fixed.
%e With alternating symbols A and B on three piles (starting with A), the following states emerge after placing 3 symbols in all 3^3 possible ways:
%e 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
%e A A
%e B B B A A A A A A B B B
%e A__ AA_ A_A AB_ AB_ ABA A_B AAB A_B BA_ BA_ BAA AA_ _A_ _AA
%e 16 17 18 19 20 21 22 23 24 25 26 27
%e A
%e A A A A A A B B B
%e AAB _AB _AB B_A BAA B_A ABA _BA _BA A_A _AA __A
%e 3 pairs of states (numbered (6,22), (8,16) and (12,20)) are identical, all others are different, hence a(3)=24.
%o (Python)
%o def fill(patterns, state_in, ply_nr, n_plies, n_players, n_stacks):
%o ....if ply_nr>=n_plies:
%o ........patterns.add(tuple(state_in))
%o ....else:
%o ........symbol=chr(ord('A')+ply_nr%n_players)
%o ........for st in range(n_stacks):
%o ............state_out=list(state_in)
%o ............state_out[st]+=symbol
%o ............fill(patterns, state_out, ply_nr+1, n_plies, n_players, n_stacks)
%o def A320731(n):
%o ....n_plies, n_players, n_stacks = n, 2, 3
%o ....patterns=set()
%o ....state=[""]*n_stacks
%o ....fill(patterns, state, 0, n_plies, n_players, n_stacks)
%o ....return len(patterns)
%Y For 2 token types on 2 piles, see A320452.
%K nonn,more
%O 0,2
%A _Bert Dobbelaere_, Oct 20 2018
| 