Discussione:
Facce k-dimensionali di [0,1]^n
Aggiungi Risposta
ngs
2018-11-22 15:58:40 UTC
Rispondi
Permalink
Sia f_k(n) il numero di facce k-dimensionali dell'ipercubo unitario
[0,1]^n. Si trovi una formula chiusa per f_k(n).

Suggerimento: disegnate l'ipercubo per n = 0, 1, 2, 3, 4, 5.

Kiuhnm
El Filibustero
2018-11-22 21:53:31 UTC
Rispondi
Permalink
Post by ngs
Sia f_k(n) il numero di facce k-dimensionali dell'ipercubo unitario
[0,1]^n. Si trovi una formula chiusa per f_k(n).
f_k(n) = (n su k)*2^(n-k). Ciao
ngs
2018-11-22 22:47:00 UTC
Rispondi
Permalink
Post by El Filibustero
Post by ngs
Sia f_k(n) il numero di facce k-dimensionali dell'ipercubo unitario
[0,1]^n. Si trovi una formula chiusa per f_k(n).
f_k(n) = (n su k)*2^(n-k). Ciao
Procedimento (a grandi linee)?
Io ho costruito parte del "triangolo di numeri", dedotto e scritto la
regola ricorsiva per un'intera riga (ho usato una serie) e quindi
risolto la semplice ricorrenza lineare da cui
(2+s)^n = \sum_{k=0}^n f_k(n) s^k

Kiuhnm
El Filibustero
2018-11-23 08:14:23 UTC
Rispondi
Permalink
Post by ngs
Procedimento (a grandi linee)?
quando l'n-cubo viene traslato in una dimensione perpendicolare per
formare l'(n+1)-cubo, oltre a formarsi quest'ultimo, le sue k-facce
raddoppiano e inoltre a esse se ne aggiungono altre dello stesso tipo
a causa della traslazione: esattamente tante quante erano le
(k-1)-facce dell'n-cubo. Ergo

f_{n+1}(n+1) = 1
f_k(n+1) = 2*f_k(n) + f_{k-1}(n)

ossia

f_k(n) = (n su k)*2^(n-k). Ciao
JTS
2018-11-23 11:26:08 UTC
Rispondi
Permalink
Post by El Filibustero
Post by ngs
Procedimento (a grandi linee)?
quando l'n-cubo viene traslato in una dimensione perpendicolare per
formare l'(n+1)-cubo, oltre a formarsi quest'ultimo, le sue k-facce
raddoppiano e inoltre a esse se ne aggiungono altre dello stesso tipo
a causa della traslazione: esattamente tante quante erano le
(k-1)-facce dell'n-cubo. Ergo
f_{n+1}(n+1) = 1
f_k(n+1) = 2*f_k(n) + f_{k-1}(n)
ossia
f_k(n) = (n su k)*2^(n-k). Ciao
*Forse* funziona anche cosi'.

Numero di facce n-1 dimensionali n*2

n-2 dimensionali: (n*2)* ((n-1)*2) /2 (ogni faccia n-1 dimensionale ha
il suo numero di facce n-1 dim., il risultato della moltiplicazione va
diviso per due perche' le facce n-1 dim sono condivise fra due facce n-1
dim.)

(# n-3 dim) = (# n-2 dim) * ((n-2)*2) /3 (diviso tre perche' condivise
fra tre facce n-1 dim.)

etc.

Mi sembra che la formula coincida con quella di ElF

Ma non so giustificare il perche' della "condivisione" delle facce di
dimensione inferiore con un numero sempre crescente di facce della
dimensione immediatamente superiore.
JTS
2018-11-23 11:28:16 UTC
Rispondi
Permalink
Post by JTS
(# n-3 dim) = (# n-2 dim) * ((n-2)*2) /3 (diviso tre perche' condivise
fra tre facce n-1 dim.)
correzione

(diviso tre perche' condivise fra tre facce n-2 dim.)
El Filibustero
2018-11-23 13:13:11 UTC
Rispondi
Permalink
Post by JTS
Numero di facce n-1 dimensionali n*2
n-2 dimensionali: (n*2)* ((n-1)*2) /2 (ogni faccia n-1 dimensionale ha
il suo numero di facce n-1 dim., il risultato della moltiplicazione va
diviso per due perche' le facce n-2 dim sono condivise fra due facce n-1
dim.)
(# n-3 dim) = (# n-2 dim) * ((n-2)*2) /3 (diviso tre perche' condivise
fra tre facce n-2 dim.)
etc.
Mi sembra che la formula coincida con quella di ElF
Esatto.
Post by JTS
Ma non so giustificare il perche' della "condivisione" delle facce di
dimensione inferiore con un numero sempre crescente di facce della
dimensione immediatamente superiore.
E' abbastanza naturale:

da un vertice di un quadrato partono 2 lati, di un cubo 3 spigoli...
da un vertice di un n-cubo partono n 1-spigoli; quindi nell'n-cubo ci
sono n 1-facce che condividono uno stessa 0-faccia (vertice).

uno spigolo di cubo e' comune a due facce, ma uno spigolo di 4-cubo e'
comune a tre facce quadrate... cosi' via. Ciao
JTS
2018-11-23 14:35:23 UTC
Rispondi
Permalink
Post by El Filibustero
Post by JTS
Numero di facce n-1 dimensionali n*2
n-2 dimensionali: (n*2)* ((n-1)*2) /2 (ogni faccia n-1 dimensionale ha
il suo numero di facce n-1 dim., il risultato della moltiplicazione va
diviso per due perche' le facce n-2 dim sono condivise fra due facce n-1
dim.)
(# n-3 dim) = (# n-2 dim) * ((n-2)*2) /3 (diviso tre perche' condivise
fra tre facce n-2 dim.)
etc.
Mi sembra che la formula coincida con quella di ElF
Esatto.
Post by JTS
Ma non so giustificare il perche' della "condivisione" delle facce di
dimensione inferiore con un numero sempre crescente di facce della
dimensione immediatamente superiore.
da un vertice di un quadrato partono 2 lati, di un cubo 3 spigoli...
da un vertice di un n-cubo partono n 1-spigoli; quindi nell'n-cubo ci
sono n 1-facce che condividono uno stessa 0-faccia (vertice).
uno spigolo di cubo e' comune a due facce, ma uno spigolo di 4-cubo e'
comune a tre facce quadrate... cosi' via. Ciao
Ok, grazie al tuo ragionamento ci sono arrivato (mi manca qualche dettaglio).

Se sono su una faccia uno-dimensionale del cubo 4-dimensionale, posso muovermi in tre direzioni ortogonali trovandomi rispettivamente sulla corrispondente faccia due-dimensionale. Nello stesso modo per altre dimensioni.
ngs
2018-11-23 13:34:30 UTC
Rispondi
Permalink
Post by El Filibustero
Post by ngs
Procedimento (a grandi linee)?
quando l'n-cubo viene traslato in una dimensione perpendicolare per
formare l'(n+1)-cubo, oltre a formarsi quest'ultimo, le sue k-facce
raddoppiano e inoltre a esse se ne aggiungono altre dello stesso tipo
a causa della traslazione: esattamente tante quante erano le
(k-1)-facce dell'n-cubo.
Sì, l'idea è quella. Ecco perché ho suggerito di disegnare [0,1]^n per
un po' di n.
Post by El Filibustero
Ergo
f_{n+1}(n+1) = 1
f_k(n+1) = 2*f_k(n) + f_{k-1}(n)
ossia
f_k(n) = (n su k)*2^(n-k). Ciao
Qui ho preferito usare una serie per "algebricizzare" lo shift di quel
k-1 e sbarazzarmi della k, ma la relazione è quella, ovviamente.

Kiuhnm
Gino Di Ruberto IK8QQM - K8QQM
2018-11-25 01:15:47 UTC
Rispondi
Permalink
Post by El Filibustero
quando l'n-cubo viene traslato in una dimensione perpendicolare per
formare l'(n+1)-cubo, oltre a formarsi quest'ultimo, le sue k-facce
raddoppiano e inoltre a esse se ne aggiungono altre dello stesso tipo
a causa della traslazione: esattamente tante quante erano le
(k-1)-facce dell'n-cubo. Ergo
f_{n+1}(n+1) = 1
f_k(n+1) = 2*f_k(n) + f_{k-1}(n)
ossia
f_k(n) = (n su k)*2^(n-k). Ciao
Molto interessante. Ti ringrazio molto.
È più o meno lo stesso ragionamento che ho fatto in un post del 5 ottobre scorso:
https://groups.google.com/d/msg/it.scienza.matematica/uZla9MpPgcs/oCczwn7lAgAJ
vedere nota finale (e piccola correzione al post successivo),
solo che sono stato un po' sciocco a considerare solo il caso k=1 e a non intuire che poteva facilmente essere esteso a k qualunque.

Ciao.
--
Gino Di Ruberto, IK8QQM
(american callsign K8QQM),
ID DMR: 2228273
El Filibustero
2018-11-23 12:48:13 UTC
Rispondi
Permalink
Post by ngs
Procedimento (a grandi linee)?
Altro modo, piu'"analitico": scrivendo le 2^n n-uple dei vertici di
[0,1]^n come i numeri binari 0..2^n-1, una k-faccia e' associata a un
insieme di 2^k numeri che hanno uno stesso bit. Esempio: in [0,1]^3
dello spazio xyz, l'insieme dei 2^2 numeri

000
001
100
101

che hanno tutti i secondi bit=0 puo' indicare la 2-faccia che sta sul
piano xz. Anche cosi', con un ragionamento induttivo su n si potrebbe
dimostrare che in 0..2^n-1 esistono (n su k) 2^(n-k) insiemi di 2^k
numeri con uno stesso bit. Ciao
Loading...