Newsgroup: it.hobby.enigmi
Titolo: Cataste de lena

Supponete di avere N ciocchi di legna.Quanti tipi di catasta potremo fare 
se i ciocchi possono disporsi soltanto uno parallelo all'altro?
Esempio esplicativo:
(_)=ciocco(cilindro)visto di fronte ed adagiato sul terreno
N=5 abbiamo 5 cataste
                    (_)              (_)              (_)     (_)(_)
(_)(_)(_)(_)(_)   (_)(_)(_)(_)  (_)(_)(_)(_)  (_)(_)(_)(_)  (_)(_)(_)
Spero di essere stato chiaro.

 se i ciocchi possono disporsi soltanto uno parallelo all'altro?
non ho trovato uno straccio di formula, nè chiusa nè ricorsiva. Non appena n
cresce i casi si moltiplicano e non sono riuscito a fare una analisi
completa. Volevo usare la forza bruta solo per conferma, ma per ora è tutto
quello che ho.
Ecco la tabella dei primi venti valori, se vi serve ne posto di più. Sembra
quasi una fibonacci, all'inizio, poi se ne discosta. Ci sono dei salti in
prossimità degli n "triangolari", com'era facile prevedere, e la successione
sfugge ai miei tentativi di domarla.
1         1
2         1
3         2
4         3
5         5
6         9
7         14
8         24
9         40
10        67
11        112
12        187
13        314
14        526
15        883
16        1483
17        2493
18        4195
19        7067
20        11914
--
Silv:o)

 quasi una fibonacci... 
Per comodita' sostituisco la legna (troppo pesante da manipolare) con le 
solite monetine. Se imponi l' ulteriore limitazione (o era implicito nella 
domanda originale ?) che le monete di una stessa fila non possono essere 
separate, es. di disposizione non valida:
   (_)   (_)
(_)(_)(_)(_)(_)
allora la Fibonacci sembra proprio andare bene.
ciao dario

 Bentornato "onoff"!
Grazie,grazie.Troppo gentile!

 allora la Fibonacci sembra proprio andare bene.
Io avevo considerato tutte le cataste in grado di stare in piedi da
sole, con i tronchi che si inseriscono tra due della riga inferiore.
Per me č valida, ad esempio, questa:
.     O
.  O O O   O
. O O O O O O
Purtroppo, come detto, so generarle tutte e contarle in tempi
ragionevoli (almeno per n non troppo grande, diciamo fino 50), ma non
ho alcuna formula che calcoli esplicitamente o per ricorsione il
numero delle cataste.
Anche l'enciclopedia on-line delle sequenze note non mi aiuta molto,
pur se i primi termini coincidono con certe successioni che hanno a
che fare con i numeri catalani.
... e visti alcuni precedenti dello stesso autore, la cosa comincia a
puzzarmi ;)
--
Ciao, Silv:o)

 20        11914
Dal 7 in poi mi risultano piu` soluzioni:
 7     15  soluzioni
 8     26  soluzioni
 9     45  soluzioni
10     78  soluzioni
11    135  soluzioni
12    234  soluzioni
13    406  soluzioni
14    704  soluzioni
15   1222  soluzioni
16   2120  soluzioni
17   3679  soluzioni
18   6385  soluzioni
19  11081  soluzioni
20  19232  soluzioni
Ecco le 15 soluzioni con 7 ciocchi:
O O O O O O O    1
 O
O O O O O O      2
   O
O O O O O O      3
     O
O O O O O O      4
       O
O O O O O O      5
         O
O O O O O O      6
 O O
O O O O O        7
 O   O
O O O O O        8
 O     O
O O O O O        9
   O O
O O O O O       10
   O   O
O O O O O       11
     O O
O O O O O       12
 O O O
O O O O         13
  O
 O O
O O O O         14
    O
   O O
O O O O         15
e 26 soluzioni con 8 ciocchi:
O O O O O O O O                          1 sol.
 O                               O
O O O O O O O   ...   O O O O O O O      6 sol.
 O O                         O O
O O O O O O     ...   O O O O O O       10 sol.
 O O O                   O O O
O O O O O       ...   O O O O O          4 sol.
  O                         O
 O O                       O O
O O O O O       ...   O O O O O          3 sol.
  O                       O
 O O O                 O O O
O O O O               O O O O            2 sol.
        Mauro

 O O O O         15
Ho controllato. Mi manca proprio la 15.
Aggiusto il programma e riprovo, per conferma.
Hai trovato qualcosa a livello di formule?
--
Silv:o)

 20  19232  soluzioni
bug fixed, era un classico "<" al posto di un "<="
Confermo i tuoi numeri e ne rilancio altri
21     33379
22     57933
23     100550
24     174519
25     302903
26     525734
27     912493
Appena ho tempo li metto in un bel foglio Excel e vedo se giocandoci un po'
riesco a tirarci fuori una qualche regola.
--
Ciao, Silv:o)

 Hai trovato qualcosa a livello di formule?
No.
Guardando il grafico ha l'aspetto di un esponenziale,ma per ora niente
formule.
Intanto ecco le ultime soluzioni trovate:
 27      912 493
 28    1 583 775
 29    2 748 893
 30    4 771 144
 31    8 281 088
 32   14 373 165
 33   24 946 955
 34   43 299 485
 35   75 153 286
        Mauro

 formule.
Taglio e incollo da Sloane:
ID Number: A005169 (Formerly M0708)
Sequence:  1,1,1,2,3,5,9,15,26,45,78,135,234,406,704,1222,2120,3679,
6385,11081,19232,33379,57933,100550,174519,302903,525734,
912493,1583775,2748893,4771144,8281088,14373165,24946955,
43299485,75153286,130440740
Name:      Fountains of n coins.
Comments:  A fountain is formed by starting with a row of coins, then stacking
additional coins on top so that each new coin touches two in the previous
row.
References Probably first studied by Jim Propp (unpublished).
Glasser, M. L.; Privman, V.; Svrakic, N. M.; Temperley's triangular
lattice compact cluster model: exact solution in terms of the $q$
series. J. Phys. A 20 (1987), no. 18, L1275-L1280.
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95
(1988), no. 8, 697-712.
A. M. Odlyzko and H. S. Wilf, The editor's corner: n coins in a fountain,
Amer. Math. Monthly, 95 (1988), 840-843.
Links:     P. Flajolet, Combinatorial aspects of continued fractions, 
Discrete Mathematics 32 (1980), pp. 125-161.
A. M. Odlyzko, Asymptotic enumeration methods, pp. 1063-1229 of R. L. 
Graham et al., eds., Handbook of Combinatorics, 1995; see Example 10.12 
(pdf, ps)
Formula:   A005169(n) = f(n, 1), where f(n, p) = 0 if p > n, 1 if p = n, 
SUM(1 <= q <= p+1; f(n-p, q)) if p < n.
Example:   An example of a fountain with 19 coins:
... O . O O
.. O O O O O O . O
. O O O O O O O O O